非随机的标签传播社区划分算法

针对传统社区传播算法存在局部震荡、划分结果不稳定、划分结果分辨率高等弱点,提出了非随机的标签传播社区划分算法,通过去除传统算法的随机性进而克服其弱点.该算法主要进行了3个方面的改进:按特定顺序更新节点的标签;计算标签数量时,不仅统计邻居节点,而且统计待更新节点本身;通过贡献函数避免多个最大值时的随机选择.实验证明,该算法不仅保证了算法的划分正确性,而且大幅度减少了计算过程中的随机选择动作.

Nonrandom Community Detection Algorithm Based on Label Propagation

Abstract： The advantages of classical community detection algorithm based on label propagation include precision and time complexity. On the other hand, there are several disadvantages, such as oscillation, unstable result, tendency of big community. The nonrandom community detection algorithm based on label propagation (NCDAL) proposed by this paper improves the disadvantages of the classical algorithm by getting rid of its random procedures. There are three improvements in the NCDAL: when renewing the label, there is the special order; when summing up the labels, both current vertex and its neighbors are counted; and when selecting the label, the contribution function is defined to avoid random selection. It is approved by the experiments that the proposed algorithm not only has high precision, but also decreases random procedures of the classical algorithm.