基于密度峰值和社区归属度的重叠社区发现算法

Overlapping Community Detection Based on Density Peaks and Community Belongingness

现实世界中,网络节点通常会隶属于多个重叠社区,例如社交网络、文献引用网络等.因此,重叠社区发现在复杂网络分析中具有重要意义,如何高效准确地识别网络中的重叠社区是社区发现研究的难点.提出一种基于密度峰值和社区归属度的重叠社区发现算法.首先,提出一种基于节点直接邻居和间接邻居的节点间距离度量方法.其次,给出密度峰值聚类算法簇中心的局部密度阈值和跟随距离阈值计算方法,根据这两个阈值自动选取簇中心.最后,把密度峰值聚类算法应用到社区发现中,并给出社区归属度的计算方法,根据社区归属度对社区边界节点进行社区归属划分.在人工数据集和真实数据集上的实验表明:该算法能够准确的识别重叠社区结构,且具近似线性的时间复杂度,适用于大规模复杂网络.

In the real world,network nodes usually belong to multiple overlapping communities,such as social networks,document reference networks,and so on.Therefore,overlapping community detection have a great significance in the analysis of complex networks.How to identify overlapping communities in the networks efficiently and accurately is a difficult task in community detection research.In this paper,an overlapping community detection algorithm based on the density peaks clustering(DPC)and community belongingness is proposed.First,a method for measuring the distance between nodes based on direct neighbors and indirect neighbors of nodes is proposed.Second,a new method for calculating the local density threshold and the following distance threshold of the cluster centers in DPC is devised,then the cluster centers automatic selection can be finished according to the two thresholds.Finally,the DPC algorithm is applied to discovering communities.A new method for calculating community belongingness is given as well.According to the community belongingness,the community boundary nodes can be assigned to appropriate communities.Experiments on artificial datasets and real datasets show that the proposed algorithm can accurately identify the overlapping communities and has near linear time complexity,which is suitable for large-scale social networks analysis.