基于图遍历的局部社区发现算法  

Local community detection algorithm based on graph traversal

作　　者：吴建[1] 王梓权 易亿 孙海霞[2] Wu Jian;Wang Ziquan;Yi Yi;Sun Haixia(College of Communication & Information Technology,Chongqing University ofPosts & Telecommunications,Chongqing 400065,China;College of InformationEngineering,Xizang Minzu University,Xianyang Shaanxi 712082,China)

机构地区：[1]重庆邮电大学通信与信息工程学院,重庆400065 [2]西藏民族大学信息工程学院,陕西咸阳712082

出　　处：《计算机应用研究》2019年第9期2636-2638,2670,共4页Application Research of Computers

基　　金：国家自然科学基金资助项目(61571071)

摘　　要：针对当前局部社区发现算法扩张速度慢不适用于大规模网络的问题,提出了一种基于图遍历的局部社区发现算法。该算法首先找出网络中度数最低的节点,以该节点为起点通过影响力函数将网络中的节点分为社区节点和边界节点,形成初步的社区划分,然后通过适应度函数确定边界节点的社区得到最终划分结果。实验结果表明,该算法在真实网络上进行测试时不仅能够有效地挖掘网络中的社区结构而且具有较快的速度。In view of the problem of the slowness of the community diffusion and not suitable for large-scale network,the paper proposed a local community detection algorithm based on breadth first traversal. The algorithm found out the node with lowest degree in the network,and used this node as a starting point to divide the nodes into community nodes and boundary nodes to form the initial community detection by influence function. Then it used fitness function to get the final cover. The experimental results show that the algorithm tested in a real network can effectively dig out community structure in the network and have faster speed.

关 键 词：复杂网络 模块度 社区发现 图遍历 

分 类 号：TP391[自动化与计算机技术—计算机应用技术] TP301.6[自动化与计算机技术—计算机科学与技术]