Skip to main content

Finding overlapping communities in social networks: Toward a rigorous approach

Author(s): Arora, Sanjeev; Ge, R; Sachdeva, S; Schoenebeck, G

To refer to this page use:
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 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. The key contribution of this work is the distillation of the prior sociology studies into general assumptions that at once accord well with sociology research and the current understanding of social networks while allowing computationally efficient solutions. 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 (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.
Publication Date: 2012
Citation: Arora, S, Ge, R, Sachdeva, S, Schoenebeck, G. (2012). Finding overlapping communities in social networks: Toward a rigorous approach. 37 - 54. doi:10.1145/2229012.2229020
DOI: doi:10.1145/2229012.2229020
Pages: 37 - 54
Type of Material: Conference Article
Journal/Proceeding Title: Proceedings of the ACM Conference on Electronic Commerce
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.