摘要：

为提高社区检测的效率与精度,提出一种随机并行的局部搜索算法。用图模型结构表示复杂系统,将顶点划分成簇。构建贪婪随机自适应搜索过程与路径重连过程,以解决加权图的模块最大化问题。引入一种{0,1}矩阵类特征并定义聚类的距离函数,从而进行顶点的邻域搜索,实现社区的高精度检测识别。实验结果表明,该算法的F1值与NMI指标值均较高。

关键词: 路径重连, 模块最大化, 随机图, 并行搜索, 社区检测

Abstract:

To improve the efficiency and accuracy of community detection,a random parallel local search algorithm is proposed.The complex system is represented by graph model structure,and vertices are divided into clusters.The greedy stochastic adaptive search process and path reconnection process are constructed to solve the module maximization problem of weighted graph.A {0,1} matrix class feature is introduced and the distance function of clustering is defined,so that the neighborhood search of vertices can be carried out to achieve high-precision community detection and recognition.Experimental results show that the F1 value and NMI index value of the proposed algorithm are both high.

Key words: path reconnection, module maximization, random graph, parallel search, community detection

中图分类号: 

• TP391