Correlations between Community Structure and Link Formation in Complex Networks

Zhen Liu, Jia Lin He, Komal Kapoor, Jaideep Srivastava

Research output: Contribution to journalArticlepeer-review

45 Scopus citations


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.

Original languageEnglish (US)
Article numbere72908
JournalPloS one
Issue number9
StatePublished - Sep 6 2013


Dive into the research topics of 'Correlations between Community Structure and Link Formation in Complex Networks'. Together they form a unique fingerprint.

Cite this