### DIMACS Theoretical Computer Science Seminar

Title: Finding Overlapping Communities in Social Networks: Toward a Rigorous Approach

Speaker: **Rong Ge**, Princeton University

Date: Wednesday, September 14, 2011 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

A community in a social network is usually understood to be a group of
nodes more densely connected with each other than with the rest of the
network. Many existing methods for finding them use heuristic
algorithms where the solution concept is defined in terms of an
NP-complete problem such as CLIQUE or HIERARCHICAL CLUSTERING.

We introduce a more formal approach whereby we make rigorous
definitions that sidestep the pitfall of high computational complexity
and allow efficient algorithms for finding communities. Our definition
includes as subcases more traditional definitions of communities
including clique and dense subgraph. The hallmark of our approach is
that it allows each node to belong to more than one community, which
had seemed problematic in earlier approaches that view communities as
nonexpanding sets.

The ability to sidestep computational complexity arises from making
"common sense" assumptions about the network that are between
worst-case and average-case assumptions. A key tool in our algorithms
is use of random sampling similar to that in property testing and
algorithms for dense graphs. We note however that our networks are not
necessarily dense graphs, not even in local neighborhoods.

Our algorithms explore a local-global relationship between ego-centric
and socio-centric networks that we hope will provide a fruitful
framework for future work.