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

来源：计算机科学与探索杂志2018年第8期北京时间：

作者：李春英，汤志康，汤庸，赵剑冬，黄泳航

单位：1. 广东技术师范学院 计算机科学学院，广州 5106652. 华南师范大学 计算机科学学院，广州 510631

摘要：考虑到社会网络中影响力大的节点对社区的形成具有一定的促进作用，以及基于局部微观角度更加易于检测社区结构等问题，提出一种基于局部微观结构极大团的同步自适应标签传播算法（synchronous adaptive label popagation algorithm，ALPA-S）和异步自适应标签传播算法（asynchronous adaptive label propagation algorithm，ALPA-A）检测社会网络中的社区结构。这两种算法均是通过寻找社会网络中不相交极大团，并为极大团中节点赋予标签及权重的方式获取标签更新时需要的种子，采用社会网络中节点均拥有标签作为算法迭代终止条件。这种策略降低了两种算法的开销，并使标签在有意义的局部范围内传播。在仿真网络和真实网络上的实验结果表明该微观结构极大团是社区结构的核心，异步算法ALPA-A较同步算法ALPA-S更易于收敛以及同步算法ALPA-S具有较好的社区检测质量、自适应性和健壮性，能够适应多种类型拓扑结构的社会网络。

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