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

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