基于贪婪局部路径重连的随机并行社区检测  

Random Parallel Community Detection Based on Greedy Local Path Reconnection

作　　者：单康康 郭晔 陈文智[2] SHAN Kangkang;GUO Ye;CHEN Wenzhi(Information Technology Center,Zhejiang University,Hangzhou 310027,China;College of Computer Science and Technology,Zhejiang University,Hangzhou 310027,China)

机构地区：[1]浙江大学信息技术中心,杭州310027 [2]浙江大学计算机科学与技术学院,杭州310027

出　　处：《计算机工程》2019年第6期199-205,共7页Computer Engineering

基　　金：浙江省科技计划项目(2011C23109,2012R10040-08)

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

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]