基于节点对的局部社区发现算法

Local community detection algorithm based on node pair

现有算法存在两点不足:1)采取爬坡策略,每次只能合并1个节点,容易陷入局部最优化的陷阱;2)对待合并节点没有考虑到外部连接情况,最终影响局部社区发现的质量.基于此,提出了一种基于节点对的局部社区算法RCD(Relative community detection).首先,通过引入改进Katz系数提出了节点对的概念,进而提出了一种新的待合并节点选择策略;其次,对不同类型节点采取不同的合并策略,从而提出了一种新的节点合并策略;最后,在3个数据集中进行实验,证明了相较于LS算法,RCD算法减少了迭代次数.改善了局部社区发现的质量.

Aiming at two of the deficiencies in the existing algorithms:a)only one node can be merged each time and it will be easy to fall into the trap of local optimization when the hillclimbing algorithm is used.b)The merged node does not take into account the external connection and ultimately the quality of local community detection is affected.Based on this,paper proposed an algorithm(called RCD).Firstly,the concept of node pairing with Katz index is proposed.Then,a new node selection strategy is proposed.Secondly,a new node merging strategy taking different methods for different types of nodes is proposed.Finally,experiments on three datasets were tested and the experimental results show that the RCD algorithm can reduce the number of iterations,and improve the quality of local community detection.