Cargando…
Correlations between Community Structure and Link Formation in Complex Networks
BACKGROUND: Links in complex networks commonly represent specific ties between pairs of nodes, such as protein-protein interactions in biological networks or friendships in social networks. However, understanding the mechanism of link formation in complex networks is a long standing challenge for ne...
Autores principales: | , , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Public Library of Science
2013
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3765235/ https://www.ncbi.nlm.nih.gov/pubmed/24039818 http://dx.doi.org/10.1371/journal.pone.0072908 |
_version_ | 1782283265952972800 |
---|---|
author | Liu, Zhen He, Jia-Lin Kapoor, Komal Srivastava, Jaideep |
author_facet | Liu, Zhen He, Jia-Lin Kapoor, Komal Srivastava, Jaideep |
author_sort | Liu, Zhen |
collection | PubMed |
description | BACKGROUND: Links in complex networks commonly represent specific ties between pairs of nodes, such as protein-protein interactions in biological networks or friendships in social networks. However, understanding the mechanism of link formation in complex networks is a long standing challenge for network analysis and data mining. METHODOLOGY/PRINCIPAL FINDINGS: Links in complex networks have a tendency to cluster locally and form so-called communities. This widely existed phenomenon reflects some underlying mechanism of link formation. To study the correlations between community structure and link formation, we present a general computational framework including a theory for network partitioning and link probability estimation. Our approach enables us to accurately identify missing links in partially observed networks in an efficient way. The links having high connection likelihoods in the communities reveal that links are formed preferentially to create cliques and accordingly promote the clustering level of the communities. The experimental results verify that such a mechanism can be well captured by our approach. CONCLUSIONS/SIGNIFICANCE: Our findings provide a new insight into understanding how links are created in the communities. The computational framework opens a wide range of possibilities to develop new approaches and applications, such as community detection and missing link prediction. |
format | Online Article Text |
id | pubmed-3765235 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2013 |
publisher | Public Library of Science |
record_format | MEDLINE/PubMed |
spelling | pubmed-37652352013-09-13 Correlations between Community Structure and Link Formation in Complex Networks Liu, Zhen He, Jia-Lin Kapoor, Komal Srivastava, Jaideep PLoS One Research Article BACKGROUND: Links in complex networks commonly represent specific ties between pairs of nodes, such as protein-protein interactions in biological networks or friendships in social networks. However, understanding the mechanism of link formation in complex networks is a long standing challenge for network analysis and data mining. METHODOLOGY/PRINCIPAL FINDINGS: Links in complex networks have a tendency to cluster locally and form so-called communities. This widely existed phenomenon reflects some underlying mechanism of link formation. To study the correlations between community structure and link formation, we present a general computational framework including a theory for network partitioning and link probability estimation. Our approach enables us to accurately identify missing links in partially observed networks in an efficient way. The links having high connection likelihoods in the communities reveal that links are formed preferentially to create cliques and accordingly promote the clustering level of the communities. The experimental results verify that such a mechanism can be well captured by our approach. CONCLUSIONS/SIGNIFICANCE: Our findings provide a new insight into understanding how links are created in the communities. The computational framework opens a wide range of possibilities to develop new approaches and applications, such as community detection and missing link prediction. Public Library of Science 2013-09-06 /pmc/articles/PMC3765235/ /pubmed/24039818 http://dx.doi.org/10.1371/journal.pone.0072908 Text en © 2013 Liu 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 Liu, Zhen He, Jia-Lin Kapoor, Komal Srivastava, Jaideep Correlations between Community Structure and Link Formation in Complex Networks |
title | Correlations between Community Structure and Link Formation in Complex Networks |
title_full | Correlations between Community Structure and Link Formation in Complex Networks |
title_fullStr | Correlations between Community Structure and Link Formation in Complex Networks |
title_full_unstemmed | Correlations between Community Structure and Link Formation in Complex Networks |
title_short | Correlations between Community Structure and Link Formation in Complex Networks |
title_sort | correlations between community structure and link formation in complex networks |
topic | Research Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3765235/ https://www.ncbi.nlm.nih.gov/pubmed/24039818 http://dx.doi.org/10.1371/journal.pone.0072908 |
work_keys_str_mv | AT liuzhen correlationsbetweencommunitystructureandlinkformationincomplexnetworks AT hejialin correlationsbetweencommunitystructureandlinkformationincomplexnetworks AT kapoorkomal correlationsbetweencommunitystructureandlinkformationincomplexnetworks AT srivastavajaideep correlationsbetweencommunitystructureandlinkformationincomplexnetworks |