计算机科学与探索 ›› 2020, Vol. 14 ›› Issue (5): 749-759.DOI: 10.3778/j.issn.1673-9418.1905015

• 网络与信息安全 • 上一篇    下一篇

面向复杂网络的节点相似性度量

穆俊芳,梁吉业,郑文萍,刘韶倩,王杰   

  1. 1. 山西大学 计算机与信息技术学院,太原 030006
    2. 山西大学 计算智能与中文信息处理教育部重点实验室,太原 030006
  • 出版日期:2020-05-01 发布日期:2020-05-08

Node Similarity Measure for Complex Networks

MU Junfang, LIANG Jiye, ZHENG Wenping, LIU Shaoqian, WANG Jie   

  1. 1. School of Computer and Information Technology, Shanxi University, Taiyuan 030006, China
    2. Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education, Shanxi University, Taiyuan 030006, China
  • Online:2020-05-01 Published:2020-05-08

摘要:

在复杂网络中,度量节点之间的相似性是一项基础且具有挑战性的工作。基于邻域节点的相似性度量仅考虑了节点的邻域信息。基于路径的相似性度量考虑了节点之间的路径信息,使得多数节点与大度节点相似。为了更准确地度量节点之间的相似性且避免多数节点与大度节点相似,定义了每个节点的距离分布,并在此基础上采用相对熵和距离分布提出了一种节点相似性度量方法(DDRE)。DDRE方法通过节点之间的最短路径生成每个节点的距离分布,根据距离分布计算节点之间的相对熵,进而得到节点之间的相似性。6个真实网络数据集的对比实验结果表明,DDRE方法在对称性以及SIR模型中影响其他节点的能力这两方面表现较好。

关键词: 复杂网络, 节点相似性, 节点距离分布, 相对熵

Abstract:

Quantifying similarity between nodes is a fundamental and challenging task in many fields of complex network. The similarity measure based on neighborhood nodes only considers the information of neighbors. The similarity measure based on path considers the information of path, which makes large nodes become general node. In order to more accurately measure the similarity between nodes and avoid the majority of nodes being similar to large nodes, this paper defines the distance distribution of each node, and based on this, it proposes a node similarity measurement method based on distance distribution and relative entropy (DDRE). The DDRE method generates the distance distribution of each node through the shortest path between nodes. According to the distance distribution, the relative entropy between nodes is calculated and the similarity between nodes is obtained. The experimental results of 6 real network data sets show that the DDRE method performs well in both the symmetry and the ability to affect other nodes in the SIR model.

Key words: complex network, node similarity, node distance distribution, relative entropy