Cargando…

Finding Statistically Significant Communities in Networks

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 ha...

Descripción completa

Detalles Bibliográficos
Autores principales: Lancichinetti, Andrea, Radicchi, Filippo, Ramasco, José J., Fortunato, Santo
Formato: Texto
Lenguaje:English
Publicado: Public Library of Science 2011
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3084717/
https://www.ncbi.nlm.nih.gov/pubmed/21559480
http://dx.doi.org/10.1371/journal.pone.0018961
_version_ 1782202537555787776
author Lancichinetti, Andrea
Radicchi, Filippo
Ramasco, José J.
Fortunato, Santo
author_facet Lancichinetti, Andrea
Radicchi, Filippo
Ramasco, José J.
Fortunato, Santo
author_sort Lancichinetti, Andrea
collection PubMed
description 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.
format Text
id pubmed-3084717
institution National Center for Biotechnology Information
language English
publishDate 2011
publisher Public Library of Science
record_format MEDLINE/PubMed
spelling pubmed-30847172011-05-10 Finding Statistically Significant Communities in Networks Lancichinetti, Andrea Radicchi, Filippo Ramasco, José J. Fortunato, Santo PLoS One Research Article 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. Public Library of Science 2011-04-29 /pmc/articles/PMC3084717/ /pubmed/21559480 http://dx.doi.org/10.1371/journal.pone.0018961 Text en Lancichinetti et al. http://creativecommons.org/licenses/by/4.0/ This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are properly credited.
spellingShingle Research Article
Lancichinetti, Andrea
Radicchi, Filippo
Ramasco, José J.
Fortunato, Santo
Finding Statistically Significant Communities in Networks
title Finding Statistically Significant Communities in Networks
title_full Finding Statistically Significant Communities in Networks
title_fullStr Finding Statistically Significant Communities in Networks
title_full_unstemmed Finding Statistically Significant Communities in Networks
title_short Finding Statistically Significant Communities in Networks
title_sort finding statistically significant communities in networks
topic Research Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3084717/
https://www.ncbi.nlm.nih.gov/pubmed/21559480
http://dx.doi.org/10.1371/journal.pone.0018961
work_keys_str_mv AT lancichinettiandrea findingstatisticallysignificantcommunitiesinnetworks
AT radicchifilippo findingstatisticallysignificantcommunitiesinnetworks
AT ramascojosej findingstatisticallysignificantcommunitiesinnetworks
AT fortunatosanto findingstatisticallysignificantcommunitiesinnetworks