Lee Juyong, Zhang Zhong-Yuan, Lee Jooyoung, Brooks Bernard R, Ahn Yong-Yeol
Laboratory of Computational Biology, National Heart, Lung, and Blood Institute (NHLBI), National Institutes of Health (NIH), Bethesda, MD, 20852, USA.
Department of Chemistry, Kangwon National University, 1 Kangwondaehak-gil, Chuncheon, 24341, Republic of Korea.
Sci Rep. 2017 Sep 29;7(1):12399. doi: 10.1038/s41598-017-12432-1.
Finding overlapping communities of complex networks remains a challenge in network science. To address this challenge, one of the widely used approaches is finding the communities of links by optimizing the objective function, partition density. In this study, we show that partition density suffers from inverse resolution limit; it has a strong preference to triangles. This resolution limit makes partition density an improper objective function for global optimization. The conditions where partition density prefers triangles to larger link community structures are analytically derived and confirmed with global optimization calculations using synthetic and real-world networks. To overcome this limitation of partition density, we suggest an alternative measure, Link Surprise, to find link communities, which is suitable for global optimization. Benchmark studies demonstrate that global optimization of Link Surprise yields meaningful and more accurate link community structures than partition density optimization.
在网络科学中，寻找复杂网络的重叠社区仍然是一项挑战。为应对这一挑战，广泛使用的方法之一是通过优化目标函数——划分密度来寻找链接社区。在本研究中，我们表明划分密度存在逆分辨率极限；它对三角形有强烈偏好。这种分辨率极限使得划分密度成为全局优化的不合适目标函数。通过使用合成网络和真实网络的全局优化计算，分析推导并证实了划分密度偏好三角形而非更大链接社区结构的条件。为克服划分密度的这一局限性，我们提出一种替代度量——链接惊喜度，用于寻找链接社区，它适用于全局优化。基准研究表明，与划分密度优化相比，链接惊喜度的全局优化能产生更有意义且更准确的链接社区结构。
