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

Sanjeev Arora, Rong Ge, Sushant Sachdeva, Grant Schoenebeck

###
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. This is an important concept
in most domains where networks arise: social, technological, biological, etc. For many years
algorithms for finding communites implicitly assumed communities are nonoverlapping (leading
to use of clustering-based approaches) but there is increasing interest in finding overlapping
communities. A barrier to finding communities is that the solution concept is often defined in
terms of an NP-complete problem such as Clique or Hierarchical Clustering.

This paper seeks to initiate a rigorous approach to the problem of finding overlapping communities,
where “rigorous” means that we clearly state the following: (a) the object sought by
our algorithm (b) the assumptions about the underlying network (c) the (worst-case) running
time.

Our assumptions about the network lie between worst-case and average-case. An averagecase
analysis would require a precise probabilistic model of the network, on which there is
currently no consensus. However, some plausible assumptions about network parameters can be
gleaned from a long body of work in the sociology community spanning five decades focusing on
the study of individual communities and ego-centric networks (in graph theoretic terms, this is
the subgraph induced on a node’s neighborhood). Thus our assumptions are somewhat “local”
in nature. Nevertheless they suffice to permit a rigorous analysis of running time of algorithms
that recover global structure.

Our algorithms use 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 both in computer science
and sociology.

###
Versions

- [arXiv]
- Extended abstract in
*Proceedings of the 2012 ACM Conference on Electronic Commerce,* (EC '12). [To Appear]
- [pdf]

[
back to Grant's homepage]