A shadowing problem in the detection of overlapping communities: lifting the resolution limit through a cascading procedure

Abstract

Community detection is the process of assigning nodes and links in significant communities (e.g. clusters, function modules) and its development has led to a better understanding of complex networks. When applied to sizable networks, we argue that most detection algorithms correctly identify prominent communities, but fail to do so across multiple scales. As a result, a significant fraction of the network is left uncharted. We show that this problem stems from larger or denser communities overshadowing smaller or sparser ones, and that this effect accounts for most of the undetected communities and unassigned links. We propose a generic cascading approach to community detection that circumvents the problem. Using real and artificial network datasets with three widely used community detection algorithms, we show how a simple cascading procedure allows for the detection of the missing communities. This work highlights a new detection limit of community structure, and we hope that our approach can inspire better community detection algorithms.

14 pages, 12 figures + supporting information (5 pages, 6 tables, 3 figures)

References in corpus (19)

• Modularity and community structure in networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Maps of random walks on complex networks reveal community structure
• Resolution limit in community detection
• Detecting the overlapping and hierarchical community structure of complex networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Line Graphs, Link Partitions and Overlapping Communities
• Clique percolation in random networks
• Narrow scope for resolution-limit-free community detection
• Weighted network modules
• Parsimonious module inference in large networks
• Community detection in networks: Structural communities versus ground truth
• A sequential algorithm for fast clique percolation
• Random graphs containing arbitrary distributions of subgraphs
• Estimating the resolution limit of the map equation in community detection
• Propagation dynamics on networks featuring complex topologies
• Fundamental statistical features and self-similar properties of tagged networks
• Bond percolation on a class of correlated and clustered random graphs
• Revealing Multiple Layers of Hidden Community Structure in Networks

Cited by in corpus (4)

• Asymptotic resolution bounds of generalized modularity and multi-scale community detection
• Growing networks of overlapping communities with internal structure
• Link community detection through global optimization and the inverse resolution limit of partition density
• Uncovering the Local Hidden Community Structure in Social Networks