Finding Statistically Significant Communities in Networks

By Andrea Lancichinetti, Filippo Radicchi, José J. Ramasco, Santo Fortunato. PLoS ONE, 2010

1,000 citations recorded by the source corpus.

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.

Subfields: Molecular Biology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/7b875545ced83c468a8e7c5bbf1c4acd109eb93f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Molecular Biology

In Statistical and Nonlinear Physics

Citations in the corpus

Multi-scale brain networks (2016, neutral): “Modularity maximization for community detection begins with the assumption that the network is modular (Lancichinetti et al., 2011), and as a technique is prone to false positives (Guimera et al.”
Modular Brain Networks (2015, methodology): “One such method is OSLOM (Order Statistics Local Optimization Method) (Lancichinetti et al. 2011), which scores communities based on how likely it is to find a community with similar properties in a random network with no community structure (Lancichinetti et al. 2010).”
Community detection in networks: A user guide (2016, methodology): “The code for OSLOM is downloadable from the dedicated website http://www.oslom.org.”
Mapping the human brain’s cortical-subcortical functional network organization (2018, neutral): “Among the different algorithms explored were OSLOM (Lancichinetti et al., 2011), k-means, standard hierarchical clustering, SpeakEasy (Gaiteri et al.”
Human mobility: Models and applications (2017, background): “Furthermore, it was found that the networks can be divided into modules with a certain level of self-contained traffic [273], although this division is not seasonably stable when the focus is set on smaller geographical scales such as the US network [280].”
Consensus clustering in complex networks (2012, methodology): “Very few methods are capable to take all these factors into consideratio”
Overlapping Communities Explain Core–Periphery Organization of Networks (2014, background): “As a point of comparison and a sanity check we also run the AGM on small networks that were thoroughly studied in literature [3, 6, 16, 20, 23, 34, 45].”