TY - GEN
T1 - Finding overlapping communities in social networks
T2 - 13th ACM Conference on Electronic Commerce, EC '12
AU - Arora, Sanjeev
AU - Ge, Rong
AU - Sachdeva, Sushant
AU - Schoenebeck, Grant
PY - 2012
Y1 - 2012
N2 - 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.
AB - 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.
KW - overlapping community detection
KW - social network analysis
UR - http://www.scopus.com/inward/record.url?scp=84863507265&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84863507265&partnerID=8YFLogxK
U2 - 10.1145/2229012.2229020
DO - 10.1145/2229012.2229020
M3 - Conference contribution
AN - SCOPUS:84863507265
SN - 9781450314152
T3 - Proceedings of the ACM Conference on Electronic Commerce
SP - 37
EP - 54
BT - EC '12 - Proceedings of the 13th ACM Conference on Electronic Commerce
Y2 - 4 June 2012 through 8 June 2012
ER -