Defining and Evaluating Network Communities Based on Ground-Truth
Authors:
- Jaewon YangJYJaewon Yang
- Jure LeskovecJLJure Leskovec
- 1 December 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15504786,p. 745-754
Abstract
Nodes in real-world networks organize into densely linked communities where edges appear with high concentration among the members of the community. Identifying such communities of nodes has proven to be a challenging task mainly due to a plethora of definitions of a community, intractability of algorithms, issues with evaluation and the lack of a reliable gold-standard ground-truth. In this paper we study a set of 230 large real-world social, collaboration and information networks where nodes explicitly state their group memberships. For example, in social networks nodes explicitly join various interest based social groups. We use such groups to define a reliable and robust notion of ground-truth communities. We then propose a methodology which allows us to compare and quantitatively evaluate how different structural definitions of network communities correspond to ground-truth communities. We choose 13 commonly used structural definitions of network communities and examine their sensitivity, robustness and performance in identifying the ground-truth. We show that the 13 structural definitions are heavily correlated and naturally group into four classes. We find that two of these definitions, Conductance and Triad-participation-ratio, consistently give the best performance in identifying ground-truth communities. We also investigate a task of detecting communities given a single seed node. We extend the local spectral clustering algorithm into a heuristic parameter-free community detection method that easily scales to networks with more than hundred million nodes. The proposed method achieves 30% relative improvement over current local clustering methods.Keywords
All Related Versions
This publication has 31 references indexed in Scilit:
- The life and death of online groups2012
- Empirical comparison of algorithms for network community detection2010
- Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined ClustersInternet Mathematics, 2009
- The dynamics of viral marketingACM Transactions on the Web, 2007
- Modularity and community structure in networksProceedings of the National Academy of Sciences of the United States of America, 2006
- Community structure in social and biological networksProceedings of the National Academy of Sciences of the United States of America, 2002
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular GraphsSIAM Journal on Scientific Computing, 1998
- An Ecology of AffiliationAmerican Sociological Review, 1983
- The Strength of Weak TiesAmerican Journal of Sociology, 1973
- The Hungarian method for the assignment problemNaval Research Logistics Quarterly, 1955