Self-falsifiable Hierarchical Detection of Overlapping Communities On Social Networks

Abstract

No community detection algorithm can be optimal for all possible networks, thus it is important to identify whether the algorithm is suitable for a given network. We propose a multi-step algorithmic solution scheme for overlapping community detection based on an advanced label propagation process, which imitates the community formation process on social networks. Our algorithm is parameter-free and is able to reveal the hierarchical order of communities in the graph. The unique property of our solution scheme is self-falsifiability; an automatic quality check of the results is conducted after the detection, and the fitness of the algorithm for the specific network is reported. Extensive experiments show that our algorithm is self-consistent, reliable on networks of a wide range of size and different sorts, and is more robust than existing algorithms on both sparse and large-scale social networks. Results further suggest that our solution scheme may uncover features of networks' intrinsic community structures.

arXiv comment21 pages, 11 figures

References in corpus (29)

• Community structure in social and biological 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
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Hierarchical structure and the prediction of missing links in networks
• Stochastic blockmodels and community structure in networks
• Link communities reveal multiscale complexity in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Community detection in networks: A user guide
• Finding statistically significant communities in networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Overlapping Community Detection in Networks: the State of the Art and Comparative Study
• Finding overlapping communities in networks by label propagation
• Finding local community structure in networks
• Spectral redemption: clustering sparse networks
• Line Graphs, Link Partitions and Overlapping Communities
• Extracting the hierarchical organization of complex systems
• The ground truth about metadata and community detection in networks
• An efficient and principled method for detecting communities in networks
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Evaluating Local Community Methods in Networks
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Clique Graphs and Overlapping Communities
• Finding instabilities in the community structure of complex networks
• Exploring the structural regularities in networks
• Community detection in networks with unequal groups
• Network structure, metadata and the prediction of missing nodes and annotations