计算机工程 ›› 2019, Vol. 45 ›› Issue (6): 199-205.doi: 10.19678/j.issn.1000-3428.0051211

• 人工智能及识别技术 • 上一篇    下一篇

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

单康康a,郭晔a,陈文智b   

  1. 浙江大学 a.信息技术中心; b.计算机科学与技术学院,杭州 310027
  • 收稿日期:2018-04-16 出版日期:2019-06-15 发布日期:2019-06-15
  • 作者简介:单康康(1984—),男,工程师、硕士,主研方向为模式匹配、迁移学习;郭晔,教授级高级工程师、博士;陈文智,教授、博士、博士生导师。
  • 基金项目:

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

Random parallel community detection based on greedy local path reconnection

SHAN Kangkanga,GUO Yea,CHEN Wenzhib   

  1. a.Information Technology Center; b.College of Computer Science and Technology,Zhejiang University,Hangzhou 310027,China
  • Received:2018-04-16 Online:2019-06-15 Published:2019-06-15

摘要:

为提高社区检测的效率与精度,提出一种随机并行的局部搜索算法。用图模型结构表示复杂系统,将顶点划分成簇。构建贪婪随机自适应搜索过程与路径重连过程,以解决加权图的模块最大化问题。引入一种{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

中图分类号: