一种稳定的标签传播社区发现算法

A STABLE LABEL PROPAGATION ALGORITHM FOR COMMUNITY DETECTION

标签传播算法存在大量随机性,极大地破坏了算法的稳定性。在深入分析标签传播算法随机性产生原因的基础上,提出基于节点度的标签传播算法。该算法初始化时仅赋予节点度的极值点以标签,并根据邻接节点中具有相同标签的节点度之和进行标签更新。实验表明该算法极大地降低了算法中的随机性,提高了社区划分的稳定性,加快了算法的收敛速度。

A great deal of randomness existing in label propagation algorithm severely breaks its robustness. We propose a node degreebased label propagation algorithm（ LPAD） on the basis of thoroughly analysing the generation cause of the randomness of label propagation algorithm. The algorithm only assigns the labels to extremum points of the node degree in its initialisation,and updates the label according to the sum of node degrees of same labels among their neighbouring nodes. Experiments show that the LPAD greatly reduces the randomness of algorithm,improves the robustness of community partition,and speeds up the convergence rate too.