Lancichinetti, A; Radicchi, F; Ramasco, JJ; Fortunato, S. 2011. Finding Statistically Significant Communities in Networks. PLOS ONE 6 (4): art. no.-e18961

[Eugene Garfield]

Lancichinetti, A; Radicchi, F; Ramasco, JJ; Fortunato, S. 2011. Finding Statistically 
Significant Communities in Networks. PLOS ONE 6 (4): art. no.-e18961..

Author Full Name(s): Lancichinetti, Andrea; Radicchi, Filippo; Ramasco, Jose J.; Fortunato, 
Santo
Document Type: Article

KeyWords Plus: COMPLEX NETWORKS; RANDOM GRAPHS; IDENTIFICATION; 
ORGANIZATION; HIERARCHIES; MODULARITY; EVOLUTION

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.

Addresses: [Lancichinetti, Andrea; Ramasco, Jose J.; Fortunato, Santo] ISI, Complex 
Networks & Syst Lagrange Lab, Turin, Italy; [Lancichinetti, Andrea] Politecn Torino, Dept 
Phys, Turin, Italy; [Radicchi, Filippo] Northwestern Univ, Howard Hughes Med Inst, 
Evanston, IL USA; [Ramasco, Jose J.] UIB, CSIC, IFISC, Palma de Mallorca, Spain
Reprint Address: Lancichinetti, A, ISI, Complex Networks & Syst Lagrange Lab, Turin, Italy.

E-mail Address: fortunato at isi.it
ISSN: 1932-6203
DOI: 10.1371/journal.pone.0018961
Fulltext: http://www.plosone.org/article/info%3Adoi%2F10.1371%2Fjournal.pone.0018961