Finding statistically significant communities in networks

Abstract

Community structure is one of the main structural features of networks, revealing both their internal organization and the similarity of their elementary units. Despite the large variety of methods proposed to detect communities in graphs, there is a big need for multi-purpose techniques, able to handle different types of datasets and the subtleties of community structure. In this paper we present OSLOM (Order Statistics Local Optimization Method), the first method capable to detect clusters in networks accounting for edge directions, edge weights, overlapping communities, hierarchies and community dynamics. It is based on the local optimization of a fitness function expressing the statistical significance of clusters with respect to random fluctuations, which is estimated with tools of Extreme and Order Statistics. OSLOM can be used alone or as a refinement procedure of partitions/covers delivered by other techniques. We have also implemented sequential algorithms combining OSLOM with other fast techniques, so that the community structure of very large networks can be uncovered. Our method has a comparable performance as the best existing algorithms on artificial benchmark graphs. Several applications on real networks are shown as well. OSLOM is implemented in a freely available software (http://www.oslom.org), and we believe it will be a valuable tool in the analysis of networks.

24 pages, 25 figures, 1 table. Final version published in PLoS One. The code of OSLOM is freely available at http://www.oslom.org

References in corpus (21)

• Fast unfolding of communities in large networks
• 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
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Comparing community structure identification
• Hierarchical structure and the prediction of missing links in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Quantifying social group evolution
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Line Graphs, Link Partitions and Overlapping Communities
• Extracting the hierarchical organization of complex systems
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Subnetwork hierarchies of biochemical pathways
• Towards real-time community detection in large networks
• Characterizing the community structure of complex networks
• Structural Inference of Hierarchies in Networks
• When are networks truly modular?
• Partitioning and modularity of graphs with arbitrary degree distribution