复杂网络重要结点发现算法研究

发布时间：2018-06-19 12:42

本文选题：复杂网络 + 重要结点　；参考：《云南财经大学》2016年硕士论文

【摘要】：复杂网络(complex network)的研究持续数十载,在众多应用领域一直属于热门研究课题,它是普遍认可的、剖析自然界和人类社会等多种复杂系统的有效工具与手段。因为海内外众多学者的推动,相关研究已渗入计算机科学、经济学、管理学、生命科学、社会学、物理学,甚至是语言学、文学、艺术等多元领域。复杂网络中存在一类被称作“重要结点”的特殊结点,它们与网络其余结点相比,对网络的结构和功能等方面的影响更加显著。同时,确定复杂网络中的关键结点对优化网络结构、增强网络结构鲁棒性及掌握信息传播动态等具有十分重要的理论意义与应用价值。因此,伴随网络科学的快速发展,重要结点的发现研究引起了有识之士的广泛关注。经典重要结点识别算法有度中心性(degree centrality)、介数中心性(betweenness centrality)、紧密度中心性(closeness centrality)和K-核分解(k-shell decomposition)等方法,其中,度仅仅考虑到结点局部属性;介数与紧密度这两种全局评估指标由于计算复杂,因而难以普及到大型网络;K-核分解利用结点的位置信息发现单源核心结点,然而,它对同层结点的重要性区分力度较差。这些方法相对简单,能够在一定程度上评估结点的重要性;然而,由于它们缺乏对结点多方面特征的全面考察,导致算法的评判结果不够理想,局限性较大。为更加有效的识别复杂网络中的重要结点,本文提出两个重要结点发现算法:基于“K-核影响矩阵”的重要结点发现算法(k-shell influence matrix,KsIM算法)和基于结点“三维集成特征”的重要结点发现算法(node importance of three dimensions,NI3算法)。KsIM算法从网络拓扑层次入手、利用结点K-核属性表征结点间的局部依赖强度,并结合结点效率构建结点重要度评估矩阵,打破了常规方法用度刻画结点之间重要度贡献的局限,为重要度贡献形式提供了新的量化标准。而NI3算法在分析结点横向、纵向、分层三维特征基础上,定义结点广度、深度和强度指标:三者从结点的直接邻居结点(广度)、结点影响力所能到达的极远处(深度)以及结点施加其影响力于其它结点的效率(强度)三方面刻画结点的影响程度,并集成为一个表征结点重要性的定量指标。本文所述算法性能均通过SIR模型仿真实验进行验证。SIR模型可以很好地模拟信息、病毒的传播过程,是理解相关传播机制并对传播过程进行理论分析的得力助手。借助SIR仿真模型、运用Kendall相关系数、不准确率、相关热度等多种评价标准,在多个不同拓扑结构的真实网络数据上获取的实验结果表明,基于“K-核影响矩阵”的重要结点发现算法KsIM和基于结点“三维集成特征”的重要结点发现算法NI3切实有效、识别重要结点的准确性与针对不同拓扑结构复杂网络的鲁棒性均胜过传统算法。本文结构安排如下:第一章为绪论,介绍了复杂网络重要结点发现的研究背景、现状与意义,表明本课题研究的重要性;第二章与第三章分别介绍了相关的重要算法模型和主要的算法评估标准;之后,重点介绍基于结点“K-核影响矩阵”和“三维集成特征”的算法模型构建,并在第五章给出详细的实验验证过程;最后总结全文,展望今后的研究方向。
[Abstract]:The research of complex network (complex network) has lasted for decades and has been a popular research topic in many applications. It is an effective tool and means to analyze complex systems such as nature and human society. Because of the promotion of many scholars at home and abroad, the related research has infiltrated into computer science, economics, management, and so on. Life science, sociology, physics, even linguistics, literature, art and other fields. There is a special node called "important node" in complex networks. Compared with the rest of the network, they have a more significant impact on the structure and function of the network. At the same time, the key nodes in the complex network are determined to optimize the network. With the rapid development of network science, the discovery of important nodes has aroused wide attention of the people of insight. The classical important node identification method has the degree centrality (degree centrality) and the medium center. Betweenness centrality, compact degree centrality (closeness centrality) and K- kernel decomposition (K-shell decomposition), in which the degree only takes into account the local attribute of the node; the two global evaluation indexes of the number and the tightness are difficult to popularize to the large network because of the complexity of the computation; K- kernel decomposition uses the location information of the nodes. However, it is relatively simple and can evaluate the importance of the nodes to a certain extent. However, because of their lack of comprehensive investigation of the multifaceted features of the nodes, the results of the algorithm are not ideal and limited. Two important node discovery algorithms are proposed in this paper: the important node discovery algorithm based on the "K- kernel impact matrix" (K-shell influence matrix, KsIM algorithm) and the important node discovery algorithm based on the node "three dimensional integration features" (node importance of three dimensions, NI3 algorithm).KsIM algorithm from the network Starting with the topology level, using the node K- kernel attribute to characterize the local dependence intensity between nodes, and combining the node efficiency to construct the evaluation matrix of node importance, breaking the limitation of the important degree contribution between the nodes of the conventional methods and providing a new quantitative standard for the important degree contribution form, and the NI3 algorithm in the analysis of the horizontal and vertical nodes. On the basis of stratified 3D features, we define the breadth, depth and intensity of nodes: the three ones from the direct neighbor node (breadth) of the nodes, the extreme distance (depth) that the node influence can reach, and the three aspects of the efficiency (intensity) of the nodes exerting its influence on other nodes, and integrate it as a token node. The performance of the proposed algorithm is verified by the SIR model simulation experiment. The.SIR model can simulate the information well. The propagation process of the virus is the right assistant to understand the related propagation mechanism and analyze the propagation process. With the help of the SIR simulation model, the Kendall correlation coefficient, inaccuracy rate, and related heat are used. The experimental results obtained on real network data of multiple different topologies show that the important node discovery algorithm KsIM based on the "K- kernel impact matrix" and the important node discovery algorithm based on the node "3D integration feature" are effective, identifying the accuracy of important nodes and aiming at different topology nodes. The robustness of the complex network is better than the traditional algorithm. The structure of this paper is arranged as follows: the first chapter is the introduction, introducing the research background, the status and significance of the complex network important node discovery, and the importance of the research. The second chapter and the third chapter respectively introduce the important algorithm model and the main algorithm evaluation criteria; after that, This paper focuses on the construction of the algorithm model based on the node "K- kernel impact matrix" and "three dimensional integration features", and gives a detailed experimental verification process in the fifth chapter. Finally, it summarizes the full text and looks forward to the future research direction.
【学位授予单位】：云南财经大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5

【相似文献】