局部优先的社会网络社区结构检测算法  

Community Detection Algorithm with Local-First Approach in Social Networks

作　　者：李春英[1] 汤志康[1] 汤庸[2] 赵剑冬 黄泳航[2] LI Chunying1, TANG Zhikang1, TANG Yong2, ZHAO Jiandong1, HUANG Yonghang2(1. School of Computer Science, Guangdong Polytechnic Normal University, Guangzhou 510665, China; 2. School of Computer Science, South China Normal University, Guangzhou 510631, Chin)

机构地区：[1]广东技术师范学院计算机科学学院,广州510665 [2]华南师范大学计算机科学学院,广州510631

出　　处：《计算机科学与探索》2018年第8期1263-1277,共15页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金No.61502180;广东省重大科技专项No.2014B010116002;广东省科技计划项目No.2015B010109003;广东省教育厅项目Nos.991460337;2014WTSCX078;广东技术师范学院创新强校项目Nos.991460306;991460317~~

摘　　要：考虑到社会网络中影响力大的节点对社区的形成具有一定的促进作用,以及基于局部微观角度更加易于检测社区结构等问题,提出一种基于局部微观结构极大团的同步自适应标签传播算法(synchronous adaptive label popagation algorithm,ALPA-S)和异步自适应标签传播算法(asynchronous adaptive label propagation algorithm,ALPA-A)检测社会网络中的社区结构。这两种算法均是通过寻找社会网络中不相交极大团,并为极大团中节点赋予标签及权重的方式获取标签更新时需要的种子,采用社会网络中节点均拥有标签作为算法迭代终止条件。这种策略降低了两种算法的开销,并使标签在有意义的局部范围内传播。在仿真网络和真实网络上的实验结果表明该微观结构极大团是社区结构的核心,异步算法ALPA-A较同步算法ALPA-S更易于收敛以及同步算法ALPA-S具有较好的社区检测质量、自适应性和健壮性,能够适应多种类型拓扑结构的社会网络。Considering that the nodes with big influence in social network will motivate the construction of commu- nities and easier to detect the structure of communities, this paper proposes a synchronous adaptive label propagation algorithm （ALPA-S） and asynchronous adaptive label propagation algorithm （ALPA-A） based on local micro structure to detect the community structure in social network. Both ALPA-S and ALPA-A starts with getting label propagation seeds by detecting disjoint max-cliques and granting labels and weights to the nodes in max-cliques and ends when all nodes in social network possess labels and weights. These strategies cut costs and lead propagation in a meaningful local scope. The experimental results on benchmark and real-world networks show that max-cliques with micro structure are the kernel of community structure. ALPA-A will converge more easily than ALPA-S, and ALPA-S is better in the quality, adaptability and robustness. ALPA-S can adapt to the social network with many topological structure types.

关 键 词：社会网络 社区检测 极大团 同步更新 异步更新 

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