基于限制性随机游走局部谱近似社区发现算法  

Local spectrum approximation algorithm with limited random walk for community detection

作　　者：吴卫江[1,2] 桑睿彤 郑艺峰 WU Wei-jiang;SANG Rui-tong;ZHENG Yi-feng(Beijing Key Lab of Petroleum Data Mining,China University of Petroleum-Beijing,Beijing 102249,China;College of Information Science and Engineering,China University of Petroleum-Beijing,Beijing 102249,China;Key Laboratory of Data Science and Intelligence Application,Fujian Province University,Minnan Normal University,Zhangzhou 363000,China;School of Computer Sciences,Minnan Normal University,Zhangzhou 363000,China)

机构地区：[1]中国石油大学(北京)石油数据挖掘北京市重点实验室,北京102249 [2]中国石油大学(北京)信息科学与信息工程学院,北京102249 [3]闽南师范大学数据科学与智能应用福建省高等学校重点实验室,福建漳州363000 [4]闽南师范大学计算机学院,福建漳州363000

出　　处：《计算机工程与设计》2021年第9期2472-2477,共6页Computer Engineering and Design

基　　金：国家自然科学基金项目(61701213);福建省自然科学基金项目(2019J01748);福建省教育厅中青年基金项目(JAT190392)。

摘　　要：针对大型网络中社区发现优化方法的效率问题,提出一种局部社区发现方法(LRW-LSA),从少量种子节点中识别本地社区的所有潜在社区成员。采用限制性随机游走进行采样处理,从种子节点出发得到一个相对较小的子图;利用种子的归一化指示向量对子图进行Lanczos迭代,得到相关节点与目标社区的隶属概率用以恢复出目标社区。在不同领域的真实数据集和合成数据集上进行实验,结果表明,LRW-LSA优于现有的社区发现方法。To optimize the efficiency of community detection in large networks,a local community detection approach was proposed,called LRW-LSA,which identified all potential community members of the local community from a small number of seed nodes.The limited random walk method was utilized to obtain a relatively small sub-graph from the seed node.To obtain the membership probability of relevant nodes and target community to recover the target community,the normalized indicator vector of the seed was employed to Lanczos iteration on the sub-graph.Experimental results on real data sets and synthetic data sets in different fields show that the proposed approach is superior to the existing community detection methods.

关 键 词：局部社区发现 限制性随机游走 Lanczos迭代 种子节点 目标社区 

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