Abstract: Considering that the nodes with big influence in social network will motivate the construction of communities 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.

Key words: social networks, community detection, maximal clique, synchronous propagation, asynchronous propagation

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

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