复杂网络重要节点识别方法研究

发布时间：2018-10-10 16:28

【摘要】：复杂网络是一门新兴的交叉学科,近年来一直活跃在科研的各个领域。在自然界中,绝大多数复杂系统都可以抽象成网络,一般由节点、边、权重等基本单元构成。在复杂网络中能够从很大程度上影响网络的抗毁性和传播、同步、控制等功能的节点被称为重要节点。随着网络规模的增大和网络拓扑结构日趋复杂,合理且精准地评价节点重要性是复杂网络研究中的一个重要问题。本文主要对复杂网络节点重要性排序和重要节点挖掘两部分内容开展研究:1.针对现有节点重要性排序算法时间复杂度较高,排序机理比较单一的问题,提出了一种基于膨胀率抽样的节点重要性排序算法,该算法能够发现网络中度中心性较小但位于不同社区之间的桥接节点,此类节点在信息传播的速度和扩散范围上具备独有的位置优势。仿真实验表明,排序结果具有较高的识别精度,算法时间复杂度较低,而且能够发现一些被其他算法同时忽略掉的重要节点。2.针对信息传播最大化的Top-k节点挖掘算法时间复杂度高,传播范围重叠的问题,提出了一种基于节点局部信息指数的挖掘算法,将初始种子节点分布在合理位置,使其在传播过程中规避富人俱乐部现象,降低重叠传播的损耗。仿真实验表明,挖掘出的种子节点组合传播力较强,且算法时间复杂度为线性,运算时间非常短。本文致力于重要节点识别方法的研究,提出了基于膨胀率的节点排序算法和基于局部信息的Top-k节点挖掘算法。较现有算法运算速度更快,且排序和挖掘精度能够达到或超过同类算法水平。补充和完善了重要节点识别算法研究体系,提升了算法性能。本研究在网络信息挖掘方面具备积极的理论研究意义,且研究成果可以较好地应用于社交网络、生物信息、电力网络等实际应用领域,有较高的应用价值。
[Abstract]:Complex network is a new interdisciplinary subject, which has been active in various fields of scientific research in recent years. In nature, most complex systems can be abstracted into networks, which are generally composed of nodes, edges, weights and other basic units. Nodes that can greatly affect the survivability, propagation, synchronization, control and other functions of complex networks are called important nodes. With the increase of network scale and the increasing complexity of network topology, it is an important problem to evaluate node importance reasonably and accurately. In this paper, the importance of the complex network node ranking and important node mining two parts of research: 1. Aiming at the problem of high time complexity and single sorting mechanism of existing node importance sorting algorithms, a node importance sorting algorithm based on expansion rate sampling is proposed. The algorithm can find the bridging nodes with moderate centrality but located between different communities, which have unique location advantages in the speed and spread range of information dissemination. Simulation results show that the sorting results have higher recognition accuracy, lower time complexity, and can find some important nodes neglected by other algorithms. 2. Aiming at the problem of high time complexity and overlapping propagation range of Top-k node mining algorithm with maximum information dissemination, a mining algorithm based on local information index of nodes is proposed, which distributes the initial seed nodes in a reasonable position. Make it avoid the rich club phenomenon in the process of communication, reduce the loss of overlapping transmission. The simulation results show that the combined propagation power of the extracted seed nodes is strong, and the time complexity of the algorithm is linear, and the operation time is very short. In this paper, we focus on the research of important node recognition methods, and propose a node sorting algorithm based on expansion ratio and a Top-k node mining algorithm based on local information. The algorithm is faster than the existing algorithms, and the precision of sorting and mining can reach or exceed the level of similar algorithms. It complements and perfects the research system of important node recognition algorithm and improves the performance of the algorithm. This research has positive theoretical significance in the field of network information mining, and the research results can be applied to social networks, biological information, power networks and other practical applications, which has a higher application value.
【学位授予单位】：河南师范大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【参考文献】