一种基于局部相似性的社区发现算法

作     者：吴钟刚 吕钊 WU Zhonggang;L(U) Zhao

作者机构：华东师范大学计算机科学技术系上海200241 

出 版 物：《计算机工程》 (Computer Engineering)

年 卷 期：2016年第42卷第12期

页      面：196-203页

学科分类：08[工学] 0835[工学-软件工程] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：上海市科学技术委员会科研计划项目(1451110700 14511106803) 上海市张江国家自主创新示范区专项发展资金(201411-JA-B108-002) 

主　　题：社区发现 图聚类 属性图 节点重要性 局部相似性 节点相似度 

摘      要：现有社区发现算法大多仅考虑图的拓扑结构或节点的属性信息,其中结合两者的属性图聚类算法挖掘效果不理想,而基于共享邻居的局部相似性算法却未充分度量节点间相似度。针对上述问题,提出一种新的基于局部相似性的节点相似度社区发现算法。该算法包括基于局部相似性的节点相似度计算和节点聚类2个模块。利用Pagerank算法计算基于图链接结构的节点重要性,衡量节点间的链接强度并结合节点的属性得到节点对相似性。为避免基于共享邻居的节点相似度计算的低估倾向,引入邻居节点集之间的相似度作为节点局部相似性。采用K-Medoids聚类算法将节点与分组中心节点的局部相似性值作为节点类别归属的判断,得到社区划分的结果。实验结果表明,与经典SA-Cluster与k-SNAP等算法相比,该算法能挖掘出质量更高的社区,具有较好的社区划分效果。