Correlations between Community Structure and Link Formation in Complex Networks

BackgroundLinks 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 FindingsLinks 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/SignificanceOur 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.研究背景：复杂网络中的边（Link）通常指代节点（Node）对之间的特定关联，例如生物网络中的蛋白质-蛋白质相互作用，或是社交网络中的好友关系。然而，阐明复杂网络中边的形成机制，长期以来都是网络分析与数据挖掘领域的一项经典挑战。 研究方法与主要结果：复杂网络中的边具有局部聚集的倾向，进而形成所谓的社区（Community）结构。这一普遍存在的现象，折射出边形成的潜在内在机制。为探究社区结构与边形成之间的相关性，本文提出了一套通用的计算框架，其中涵盖了网络划分与边概率估计的相关理论。该方法能够高效且精准地识别部分观测网络中的缺失边（Missing Link）。社区内连接概率较高的边表明，边的形成优先用于构建团（Clique），进而提升社区的聚集程度。实验结果验证了本文提出的方法能够很好地捕捉该类边形成机制。 结论与意义：本研究结果为理解社区内部的边形成机制提供了全新的研究视角。这套计算框架为开发新的研究方法与应用场景（如社区检测与缺失边预测）开辟了广阔的可能性空间。