Skip to main content

Finding overlapping communities in social networks: Toward a rigorous approach

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

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1cm8n
Full metadata record
DC FieldValueLanguage
dc.contributor.authorArora, Sanjeev-
dc.contributor.authorGe, R-
dc.contributor.authorSachdeva, S-
dc.contributor.authorSchoenebeck, G-
dc.date.accessioned2019-08-29T17:05:06Z-
dc.date.available2019-08-29T17:05:06Z-
dc.date.issued2012en_US
dc.identifier.citationArora, S, Ge, R, Sachdeva, S, Schoenebeck, G. (2012). Finding overlapping communities in social networks: Toward a rigorous approach. 37 - 54. doi:10.1145/2229012.2229020en_US
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1cm8n-
dc.description.abstractA 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.en_US
dc.format.extent37 - 54en_US
dc.language.isoen_USen_US
dc.relation.ispartofProceedings of the ACM Conference on Electronic Commerceen_US
dc.rightsAuthor's manuscripten_US
dc.titleFinding overlapping communities in social networks: Toward a rigorous approachen_US
dc.typeConference Articleen_US
dc.identifier.doidoi:10.1145/2229012.2229020-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat 
Finding Overlapping Communities in Social Networks Toward a Rigorous Approach.pdf219.82 kBAdobe PDFView/Download


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