title: Correlations between community structure and link formation in complex networks.
abstract: 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.
  
  
  RESULTS
  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
  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.
authors.affiliation: Web Sciences Center, School of Computer Science and Engineering, University of Electronic Science and Technology of China, ChengDu, SiChuan, China ; Department of Computer Science and Engineering, University of Minnesota, Minneapolis, Minnesota, United States of America.
authors.forename: Zhen
authors.initials: Z
authors.lastname: Liu
authors.forename: Jia-Lin
authors.initials: JL
authors.lastname: He
authors.forename: Komal
authors.initials: K
authors.lastname: Kapoor
authors.forename: Jaideep
authors.initials: J
authors.lastname: Srivastava
mesh_terms: D000465:Algorithms; D019058:Community Networks; D057225:Data Mining; D006801:Humans; D015233:Models, Statistical; D016571:Neural Networks, Computer; D015203:Reproducibility of Results
references.citation: Nature. 1998 Jun 4;393(6684):440-2
references.pmid: 9623998
references.citation: Nature. 2005 Jun 9;435(7043):814-8
references.pmid: 15944704
references.citation: Nat Rev Genet. 2004 Feb;5(2):101-13
references.pmid: 14735121
references.citation: Bioinformatics. 2012 Sep 15;28(18):i480-i486
references.pmid: 22962470
references.citation: Proc Natl Acad Sci U S A. 2007 May 1;104(18):7327-31
references.pmid: 17452639
references.citation: Nature. 2008 May 1;453(7191):98-101
references.pmid: 18451861
references.citation: Philos Trans R Soc Lond B Biol Sci. 1986 Nov 12;314(1165):1-340
references.pmid: 22462104
references.citation: Sci Rep. 2013;3:1613
references.pmid: 23563395
references.citation: Proc Natl Acad Sci U S A. 2009 Dec 29;106(52):22073-8
references.pmid: 20018705
references.citation: PLoS Comput Biol. 2006 Jul 21;2(7):e89
references.pmid: 16854212
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2012 May;85(5 Pt 2):056112
references.pmid: 23004826
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2005 Oct;72(4 Pt 2):046108
references.pmid: 16383469
references.citation: Proc Natl Acad Sci U S A. 2002 Jun 11;99(12):7821-6
references.pmid: 12060727
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2005 Aug;72(2 Pt 2):026132
references.pmid: 16196669
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2004 Dec;70(6 Pt 2):066111
references.pmid: 15697438
references.citation: Proc Natl Acad Sci U S A. 2004 Mar 2;101(9):2658-63
references.pmid: 14981240
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2004 Aug;70(2 Pt 2):025101
references.pmid: 15447530
references.citation: Science. 1999 Oct 15;286(5439):509-12
references.pmid: 10521342
references.citation: PLoS One. 2011 Apr 08;6(4):e18209
references.pmid: 21494658