基于改进随机游走的复杂网络节点重要性评估

Evaluation of Node Importance in Complex Networks Based on Improved Random Walk

摘要: 复杂系统可以抽象为复杂网络，重要节点评估与识别是复杂网络的一个热点问题。针对网络拓扑结构和节点自身属性对有向复杂网络重要节点的影响，提出基于改进随机游走的节点重要性评估方法。首先对节点的出度和入度分别附参数求出节点联合度数为节点质量，并通过调节参数评估节点出度与入度对节点重要性的影响；其次使用SimRank算法得任意两个节点相似值的倒数为引力模型的距离，考虑节点间的拓扑结构；最后通过相对路径数比值做引力模型的系数，考虑节点间信息传播的影响效果。任意两节点的作用力构造引力矩阵，将引力矩阵行归一化构造转移矩阵，然后随机游走对节点进行排序。使用极大强连通性、极大弱连通性和脆弱性等评估指标在四个真实网络上进行实验对比，结果表明，提出的算法相比LeaderRank、PageRank、HITs等方法能更准确地评估节点的重要性。将复杂网络的多种特征进行融合，新创建的重要节点评估方法可以运用在生物领域和经济贸易领域等。

Abstract: Complex systems can be abstracted as complex networks. The evaluation and identification of important nodes is a hot issue in complex networks Aiming at the influence of network topology and node attributes on important nodes in directed complex networks, a node importance evaluation method based on improved random walk is proposed. Firstly, the joint degree of the node is calculated as the node quality by attaching parameters to the outgoing degree and incoming degree of the node respectively, and the influence of the outgoing degree and incoming degree of the node on the node importance is evaluated by adjusting parameters; Secondly, SimRank algorithm is used to get the reciprocal of the similarity value of any two nodes as the distance of the gravity model, considering the topology between nodes; Finally, the relative path number ratio is used as the coefficient of the gravity model to consider the effect of information transmission between nodes. The gravitational matrix is constructed by the force of any two nodes, and the transfer matrix is constructed by normalizing the rows of the gravitational matrix, and then the nodes are ranked by random walking. The experimental comparison is conducted on four real networks using the evaluation indicators of maximum strong connectivity, maximum weak connectivity and vulnerability. The results show that the proposed algorithm can more accurately evaluate the importance of nodes than the methods of Leader Rank, Page Rank, HITs, etc., ntegrate multiple features of complex networks, and the newly created evaluation method of important nodes can be applied in the biological field, economic and trade fields, etc.