计算机工程与应用 ›› 2020, Vol. 56 ›› Issue (8): 42-48.DOI: 10.3778/j.issn.1002-8331.1904-0493

• 理论与研发 • 上一篇    下一篇

基于社区划分的节点重要性评估方法

王安,顾益军   

  1. 中国人民公安大学 信息技术与网络安全学院,北京 102600
  • 出版日期:2020-04-15 发布日期:2020-04-14

Nodes Importance Ranking Method Based on Community Detection

WANG An, GU Yijun   

  1. College of Information Technology and Network Security, People’s Public Security University of China, Beijing 102600, China
  • Online:2020-04-15 Published:2020-04-14

摘要:

对于PageRank方法结果过于集中,未考虑复杂网络社区结构特性的问题,提出了一种改进的,基于复杂网络社区划分的节点重要性排序方法CD-PR。根据标签传播算法(LPA)对复杂网络进行社区划分的结果,将社区的内外连接关系转化为社区选择的概率表示;按照社区选择概率,分别从各个社区提取一定比例的候选关键节点;将这些候选节点重新排序,得到关键节点排序结果。以4个真实复杂网络作为实验数据,与现有算法进行对比,进行SIR传播性能实验。实验结果表明,CD-PR算法筛选出的节点在整体传播性能上具有更好的效果,CD-PR算法可以有效地对复杂网络的节点进行重要性排序。

关键词: 复杂网络, 节点重要性, 社区划分, PageRank, SIR

Abstract:

The results of PageRank methods are too centralized and do not take into account the structural characteristics of communities in complex network. To solve this problem, an improved nodes importance ranking method CD-PR based on complex network community detection is proposed. According to the result of community detection of complex networks by Label Propagation Algorithm(LPA), the internal and external connection relationship of community is transformed into the probability representation of community selection. According to the probability of community selection, a certain proportion of candidate key nodes are extracted from each of them respectively. Finally, these candidate nodes are reordered and the key node sorting results are obtained. Using four real complex networks as experimental data, compared with some existing algorithms, the SIR performance experiments are carried out respectively. The experimental results show that CD-PR has a better effect on overall propagation performance. CD-PR algorithm can effectively sort the importance of nodes in complex networks.

Key words: complex network, node importance, community detection, PageRank, SIR