改进的谱二分法在重叠社团发现中的应用  

Application of improved spectral bisection method to overlapping community discovery

作　　者：桂春[1] GUI Chun(College of Mathematics and Computer Science, Northwest University for Nationalities, Lanzhou 730030, China)

机构地区：[1]西北民族大学数学与计算机科学学院,甘肃兰州730030

出　　处：《武汉大学学报（工学版）》2019年第4期372-376,共5页Engineering Journal of Wuhan University

基　　金：国家自然科学基金项目(编号:61562075);西北民族大学甘肃省一流学科专项资金项目(编号:31920180119)

摘　　要：社团发现算法在学术界得到了广泛的关注和研究,但是利用网络的边属性进行重叠社团发现的研究还比较新颖.通过将谱分析应用到边图上来发现重叠社团,谱二分法被改进为能够发现重叠节点的新算法.实验中改进的谱二分法与经典的边社团检测LC算法、分裂型的社区结构发现GN算法和派系过滤CPM算法在3个评价准则上进行对比,在3个真实网络上的实验结果表明本文提出的改进谱二分法效果更好,该算法不但实现了准确的社团划分,而且找到了社团之间的重叠节点.因此,可以认为基于拉普拉斯矩阵的谱二分法在以网络的边为研究对象时仍然适用,并且在边图上谱二分法实现了重叠社团发现的目的.Community discovery algorithm has been widely concerned and studied in the academic field;but the research on the overlapping community discovery by using the edge attributes of the network is relatively new. Spectral bisection method is modified to find overlapping communities through the spectral analysis is applied to the edge graph. The improved spectral bisection method is compared with the LC algorithm, GN algorithm and CPM algorithm on three evaluation criterions. Three real world networks are used to show experimental results that the improved spectral bisection method realized the community discovery and found the overlapping nodes between communities. Therefore, it can be considered that the spectral bisection method based on the Laplacian matrix is still applicable when the edges of the network are used.

关 键 词：社团发现 特征值 谱二分法 拉普拉斯矩阵 重叠节点 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]