【作者】 高伟；

【导师】 高琳；

【作者基本信息】 西安电子科技大学 ， 计算机科学与技术， 2019， 硕士

【摘要】 现实世界中很多复杂系统都可以用复杂网络进行建模,比如社交系统、互联网等。在真实的复杂系统中,往往存在一些特殊元素,能够更大程度地影响系统的运行。用复杂网络对系统进行建模后,这些特殊元素就是网络的重要节点。相比网络中其他节点而言,重要节点能更大程度地影响网络的结构与功能。因此,识别网络的重要节点有重要的理论价值与实际意义,比如可以帮助人们控制流行病的爆发、商品推广等。然而,直至目前为止,依然没有一个对重要节点准确的统一的形式化定义,所以现有研究可以从不同角度来识别重要节点,比如节点的位置、权威性、传播能力等。另外,针对有向网络的研究依然很少,大多数现有算法只是对适用于无向网络的算法进行一个简单的有向化扩展或者将有向网络无向化后直接利用适用于无向网络的算法进行识别重要节点,但是其并不一定适用于有向网络。目前,对于复杂网络的宏观拓扑结构已经有了很成熟的研究和可靠的结论,比如无标度特性、小世界特性等,这些结论可以为识别重要节点提供指导性思想。在随机游走的算法框架下,本文首先基于无标度特性和小世界特性提出了三个算法:ScalefreeRank算法、SmallworldRank算法和TopologyRank算法;其次通过实验验证来给出三个算法中的最优推荐。对本文提出的算法在真实网络上进行SIR模拟实验,将传播范围和传播速度作为指标来验证算法的准确性。除此之外,还验证了算法的鲁棒性。通过和现有的五个经典算法进行比较来说明算法的性能优劣。实验结果表明,ScalefreeRank算法无论是准确性还是鲁棒性均优于PageRank算法和LeaderRank算法,但是准确性低于度中心性、K核分解和HITS算法;SmallworldRank算法和TopologyRank算法在准确性方面均优于其它五个算法,但在个别网络中对网络中的删边噪声比较敏感,鲁棒性稍差。最后,通过对这三个算法进行横向对比实验表明,SmallworldRank算法和TopologyRank算法的准确性相差无几,但是远优于ScalefreeRank算法;另外TopologyRank算法的鲁棒性更优,所以本文更推荐使用TopologyRank算法来识别网络中的重要节点。结合目前重要节点的刻画角度以及重要节点的定义,TopologyRank算法具有较好的可解释性。无标度特性体现了节点的权威性;小世界特性可以反映节点的传播能力。TopologyRank算法同时考虑了二者,实验结果显示该算法具有良好的性能,对于很多现实活动具有很好的指导意义。更多还原

【Abstract】 Many complex systems in the real world can be modeled with complex networks,such as social systems,the Internet,and so on.In real complex systems,there are often some special elements that can affect the operation of the system to a greater extent.After modeling this complex system with a complex network,these special elements are important nodes in the network.Important nodes can affect the structure and function of the network to a greater extent than other nodes in the network.Therefore,identifying important nodes has important theoretical and practical significance,such as helping people to control the outbreak of epidemics and conducting advertisements for e-commercial products.However,up to now,there is still no precise and uniform definition of the importance of nodes,so existing research can identify important nodes from different points,such as the location,authority and influence of nodes.In addition,research on directed networks is still rare.Most algorithms for directed networks is extended from algorithms for undirected networks by a slight extension or directly apply the algorithm suit for undirected network after undirecting the network,but they are not necessarily applicable to directed networks.At present,there are already mature researches and reliable conclusions for the macro topology of complex networks,such as scale-free property and small-world property.These conclusions can provide guiding ideas for identifying important nodes.In the framework of random walk,this paper first proposes three algorithms based on scale-free characteristics and small world characteristics: Scalefree Rank algorithm,Smallworld Rank algorithm and Topology Rank algorithm.Secondly,through experimental verification,this paper gives the recommendation that which one is more recommended among the three algorithms.These proposed algorithms are applied to the SIR simulation experiment on the real network,and the spreading range and spreading speed are used to verify the accuracy of the algorithm.In addition to this,the robustness of the algorithm is also verified.The performance of the algorithm is illustrated by comparison with the existing five classical algorithms.The experimental results show that the Scalefree Rank algorithm is superior to the Page Rank algorithm and the Leader Rank algorithm in both accuracy and robustness,but the accuracy is lower than the degree centrality,K-core decomposition and HITS algorithm;the Smallworld Rank algorithm and the Topology Rank algorithm are excellent in accuracy,better than the other five algorithms,but they are more sensitive to the edge-decoding noise in the individual network,so the robustness is slightly worse.Finally,through the horizontal comparison experiments of these three algorithms,the accuracy of the Smallworld Rank algorithm and the Topology Rank algorithm are almost the same,but it is far superior to the Scalefree Rank algorithm.In addition,the Topology Rank algorithm is more robust,so this paper recommends using the Topology Rank algorithm to identify important nodes in the network.Combined with the current points of node’s importance and the definition of important nodes,the Topology Rank algorithm has better interpretability.The scale-free feature embodies the authority of the node;the small world property can reflect the node’s ability to propagate.The Topology Rank algorithm considers both at the same time.The experimental results show that the algorithm has good performance and has good guiding significance for many realistic activities.更多还原