Community detection in networks: Structural communities versus ground truth

Abstract

Algorithms to find communities in networks rely just on structural information and search for cohesive subsets of nodes. On the other hand, most scholars implicitly or explicitly assume that structural communities represent groups of nodes with similar (non-topological) properties or functions. This hypothesis could not be verified, so far, because of the lack of network datasets with information on the classification of the nodes. We show that traditional community detection methods fail to find the metadata groups in many large networks. Our results show that there is a marked separation between structural communities and metadata groups, in line with recent findings. That means that either our current modeling of community structure has to be substantially modified, or that metadata groups may not be recoverable from topology alone.

21 pages, 19 figures

References in corpus (9)

• Fast unfolding of communities in large networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Cooperative Game Theory Approaches for Network Partitioning
• Maps of random walks on complex networks reveal community structure
• Benchmark graphs for testing community detection algorithms
• Comparing community structure identification
• Detecting the overlapping and hierarchical community structure of complex networks
• Finding statistically significant communities in networks
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems

Cited by in corpus (8)

• Community detection in networks: A user guide
• IEDC: An Integrated Approach for Overlapping and Non-overlapping Community Detection
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• Structure constrained by metadata in networks of chess players
• Clustering attributed graphs: models, measures and methods
• Community detection algorithm evaluation with ground-truth data
• Optimization in large graphs: Toward a better future?
• Error-Correcting Decoders for Communities in Networks