一种基于节点相似度的标签传播算法

A New Algorithm Based on Node Similarities for Community Detection

互联网技术的发展使诸如微博等社会网络的规模迅速增长,对这些网络进行挖掘分析,揭示网络特性对研究人们之间的联系具有重要意义。因此,发现高质量的网络社区结构是当前社会网络分析研究中的重要方向。传统的关系圈挖掘算法复杂度高,在大规模网络结构中性能下降。相比于传统社区发现算法,标签传播算法(LPA)具有时间复杂度上的巨大优势,而且其改进的SLPA还具有挖掘重叠社区的能力,但是标签传播算法内在的随机策略使得算法稳定性不高。针对标签传播算法的缺点,提出一种基于节点相似度的标签传播算法(NS-SLPA),根据节点相似度进行节点标签的初始化过程,以降低传播过程中的随机选择性。实验结果证明,NS-SLPA相比于SLPA,具有更高的稳定性和有效性。

The development of Internet technology makes social network scale growth rapidly,such as micro-blog,it is of great importance to analysis of these social network to reveal its characteristic to study the relationship between people,so mining the structure of the network community efficiently is an important direction in the current social network analysis.The traditional algorithm of relation mining is complex and lead to performance degradation in large scale network.Compared with the traditional community discovery algorithm,Label Propagation Algorithm（LPA）has a great advantage in time complexity,and its improved algorithm SLPA has the ability of mining overlapping communities,but the inner randomized strategy makes it unstable.Proposing a kind of node similarities-based Label Propagation Algorithm（NS-SLPA）based on defect of SLPA,this algorithm implement labels’ initialization process according to node similarities,reducing the problem of random selection in the process of spread.It’s proved by experiments that NS-SLPA is more stable and effective than SLPA.