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

Descripción completa

Detalles Bibliográficos
Autores principales: Liu, Zhen, He, Jia-Lin, Kapoor, Komal, Srivastava, Jaideep
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