论文部分内容阅读
从宏观的角度讲,我们生活的世界可以看作是无数个不同规模、无穷层次、各种功能的网络的嵌套。这些自然界和人类社会中的广泛存在的网络都能够抽象成节点和连边的形式,通过网络科学的知识理论去诠释和刻画。在网络科学的思想理论与方法的大框架下,人们可以从全新的网络的视角和观点来探讨世间万物的复杂性问题。对于有益的网络,我们希望通过优化设计、协调控制、防御修复等手段来保障诸如电力网络、物流网络、关键基础设施网络的持续、稳定、有效地运转。对于病毒传播网络、谣言扩散网络、金融危机网络、军事体系对抗中的敌方网络等有害网络,网络瓦解(注射疫苗,查杀病毒,谣言阻断、体系破击等方式)作为是一种重要手段,让我们能够通过免疫、封锁、隔离、干扰、袭击等行动,从网络中“移除”部分关键节点,从而控制和瓦解这些有害网络。然而,在现实世界中决策者常常会面对信息缺失的情况。制定网络瓦解决的过程中很难,甚至不可能获得目标网络的全部信息。例如,在疾病防控中,只有传播网络中的少量接触关系是已知的;在军事对抗中,通常只能侦测到敌方作战网络的部分结构信息,等等。显然,网络结构信息的缺失会影响瓦解效果,这给复杂网络瓦解研究带来巨大挑战。链路预测作为信息挖掘领域的一种技术手段,是连通网络科学与信息科学的桥梁。因此,本论文基于链路预测对复杂网络瓦解问题展开建模与分析,并对链路预测中存在的链路可预测性及预测精度评价等问题进行深入探讨。论文围绕“怎么将链路预测与网络瓦解问题结合”“怎样计算网络自身的结构可预测性”“怎样构建链路预测精度评价体系”三个科学问题,深入系统地研究了不完全信息条件下复杂网络瓦解的建模问题,并解决了链路预测过程中预测算法遴选、预测比例确定、预测精度评价等关键技术问题。论文主要研究工作及创新点如下:(1)提出了一种基于特征谱的可预测性度量指标。通过计算该指标,能够在选择算法前获取目标网络能够被预测的难易程度,解决到底是不可预测的网络还是不合适的算法的问题,为目标网络与预测算法之间的选择和匹配问题提供解决方案。(2)将链路预测引入不完全信息情况下的瓦解策略研究。基于链路预测,进行网络缺失拓扑信息的刻画、恢复与重构。论文研究表明,考虑到最优预测强度随着信息缺失的增加而减小,即在缺失信息适中时,加入少量预测链路通常是有益的;大于这个强度的新增连边会带来信息噪音,对瓦解效果产生负影响,即在大量信息缺失的情况下,目标网络的结构信息很难被刻画和恢复,此时作为决策者应该谨慎添加连边。(3)揭示了链路预测的漫画效应。研究表明,当缺失的链接信息不是太大时,借助于链接预测,我们得到的攻击效果甚至优于完整信息情况下的攻击效果。我们称这种现象为链路预测的漫画效应(comic effect of link prediction)。这是因为链路预测在刻画相似性时能够基于算法原理给出很多网络演化可能机制的提示,并通过新增连边,补充那些缺失的或者理论上应该存在的连边,使得网络特征像漫画一样被夸张和放大,网络中的关键节点被重新识别,有利于决策者制定瓦解策略。(4)建立了基于边重要性的链路预测精确度指标体系。本文提出从连边在维持网络聚类系数(Clustering)和全局连通性(Connectivity)的两大作用出发,构建基于边重要性的链路预测精确度指标。相对于传统指标只考虑了预测连边的正误,基于边重要性的精确度指标体系指标综合考虑了网络结构的重构过程中,新增连边在维持网络结构功能上的正效应和副作用,对链路预测算法的贡献给出了更为全面的评价。特别地,当两个算法在传统的Precision指标评价下表现相差不大时,我们的指标能够通过评估算法在恢复网络结构属性上的表现,选出更实用的算法。(5)设计了基于链路预测的网络结构分析与瓦解应用的人机交互系统。基于MATLAB GUI,集成整合本文关于链路预测和网络瓦解所做的研究工作,设计实现了一个基于链路预测的网络结构分析与瓦解应用的交互系统平台。该系统能够辅助用户自主实现从生成初始网络隐藏部分信息到基于链路预测进行网络重构,再到基于各种策略展开网络瓦解的整个流程,并就仿真实验结果与用户进行可视化交互。旨在为用户方便快捷的掌握目标网络结构信息,做出高效决策提供辅助和建议。