网络社区发现优化:基于随机游走的边权预处理方法

Optimizing Community Detection Using the Pre-processing of Edge Weighted Based on Random Walk in Networks

在网络日趋复杂化、巨大化的背景下,仅依靠网络拓扑特征难以提高现有社区发现算法的精确度和性能。该文提出一种优化网络社区发现的边权预处理方法,基于马尔可夫随机游走理论建模社区结构对复杂网络行为的影响,根据多重随机游走对网络连接的遍历情况,重新衡量网络边权。预处理后的边权作为网络拓扑的有效补充信息,能够将网络社区结构去模糊化,从而改善现有算法的社区发现性能。对于一些典型的计算机生成网络和真实网络,经实验验证:该预处理方法能够有效提升现有部分社区发现算法的准确性和效率。

In the context of social network becomes more and more complicated and huge, it is difficult to improve the accuracy and performance of existing community detection algorithms only relying on the network topological features. Based on Markov random walk theory, this paper proposes a method of edge weighted pre-processing for optimizing community detection, models community structures how to influence on the complex network behaviors. According to the situation of multiple random walk traverses on the network links, the network edges weight is reset, and makes it as the network topology effective supplementary information to promote the network community structure defuzzification, thus the performance of the existing algorithms is improved for community detection. For a set of typical benchmark computer-generated networks and real-world network data sets, the experimental results show that the pre-processing method can effectively improve the accuracy and efficiency of some existing community detection algorithms.