  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
communities 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
average case 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. 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. However, 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.
