论文部分内容阅读
复杂网络(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-核影响矩阵”和“三维集成特征”的算法模型构建,并在第五章给出详细的实验验证过程;最后总结全文,展望今后的研究方向。