基于全局—局部属性的复杂网络节点综合影响力评估算法

Comprehensive influence evaluation algorithm of complex network nodes based on global-local attributes

挖掘网络中的关键节点在信息传播、病毒营销、舆论控制等的演进过程中发挥着巨大的作用,关键节点的识别可以有效地帮助控制网络攻击、检测金融风险、抑制病毒和谣言的传播、防止恐怖袭击等。为了突破现有节点影响力评估方法存在的算法复杂度高、准确度低以及评价指标内在作用机制评估角度片面的限制,提出了一种识别关键节点的综合影响力(CI,comprehensive influence)评估算法。该算法通过同时处理网络的局部和全局拓扑来对节点重要性进行排序,从多个角度整合网络属性信息,提供更全面的节点重要性度量。算法中的全局属性考虑的是邻居节点以及节点之间的最短距离,节点的信息熵用来表示节点的局部属性,通过一个参数来调整全局和局部属性的权重比。使用SIR(susceptible infected recovered)模型和Kendall相关系数作为评价标准,在不同规模的现实世界网络上进行实验分析,结果表明,所提出的方法能在识别关键节点方面优于介数中心性(BC,betweenness centrality)、接近中心性(CC,closeness centrality)、重力指数中心性(GIC,gravity index centrality)、全局结构模型(GSM,global structure model)等著名的启发式算法,并且具有更好的排序单调性、更稳定的度量结果,对网络拓扑的适应性更强,适用于绝大多数具有不同结构的真实网络。

Mining key nodes in the network plays a great role in the evolution of information dissemination,virus marketing,and public opinion control,etc.The identification of key nodes can effectively help to control network attacks,detect financial risks,suppress the spread of viruses diseases and rumors,and prevent terrorist attacks.In order to break through the limitations of existing node influence assessment methods with high algorithmic complexity and low accuracy,as well as one-sided perspective of assessing the intrinsic action mechanism of evaluation metrics,a comprehensive influence(CI)assessment algorithm for identifying critical nodes was proposed,which simultaneously processes the local and global topology of the network to perform node importance.The global attributes in the algorithm consider the information entropy of neighboring nodes and the shortest distance nodes between nodes to represent the local attributes of nodes,and the weight ratio of global and local attributes was adjusted by a parameter.By using the SIR(susceptible infected recovered)model and Kendall correlation coefficient as evaluation criteria,experimental analysis on real-world networks of different scales shows that the proposed method is superior to some well-known heuristic algorithms such as betweenness centrality(BC),closeness centrality(CC),gravity index centrality(GIC),and global structure model(GSM),and has better ranking monotonicity,more stable metric results,more adaptable to network topologies,and is applicable to most of the real networks with different structure of real networks.