基于节点间影响力的重叠社团发现算法

摘要

为了降低重叠社团发现算法的时间复杂度,提高社团发现的准确性和稳定性,基于标签传播和COPRA算法的思想,提出了一种基于节点间影响力的重叠社团发现算法OCDI(Overlapping Community Detection Algorithm Besed on Influence Between Nodes)。该算法首先采用PageRank算法计算出各节点的PageRank值,并进行迭代,直到稳定;然后采用节点的PageRank值衡量节点的重要性,根据节点的重要性按照升序对节点进行排序,进而确定更新节点标签的顺序;其次在标签更新策略中,引入节点与其邻居节点之间的影响力,基于这种影响力计算节点标签的隶属度,最终发现重叠社团。在真实网络和人工合成网络上的实验结果表明,文中设计的OCDI算法不仅能够有效地检测出重叠社团,而且具有较高的稳定性和近似于线性的时间复杂度。