复杂网络上的链路预测及信息传播研究

论文摘要

复杂网络描述了由大量相互作用的个体所组成的系统,而信息传播是个体间相互作用的一种基本形式。现实世界中的很多传播现象,例如观点、舆论、新闻、潮流、行为和谣言的传播,都可以抽象为复杂网络上的信息传播。利用复杂网络的分析方法,能够对网络系统的结构进行刻画,进而理解真实网络上的信息传播规律,最终实现对网络上信息传播过程的干预和优化。揭示复杂网络上的信息传播机制与规律具有重要的现实应用意义,例如,为谣言的预警与防控、产品的营销以及社会潮流的引导提供理论依据。由于真实网络的复杂性,对其结构和其上信息传播过程的研究面临着很多的挑战。一方面,由于数据保护、技术及人为原因,通常所获得的真实网络结构是充满噪声的。链路预测是对噪声连边进行识别的一种有效途径。去除噪声有助于还原真实的网络结构,从而为进一步分析网络上的信息传播过程提供准备。另一方面,由于网络结构和传播机制的错综复杂,信息传播过程的理论分析仍然存在着不少的困难。例如,对于促进信息传播的网络结构优化问题,传播范围（即优化的目标函数）缺乏显式表达式,对其优化往往依赖于启发式方法而缺乏解析结果。再例如,共演传播过程的动力学方程组往往是高度非线性的,这也给解析带来很大的困难。针对以上的问题,本文将从复杂网络的链路预测和信息传播动力学两方面展开研究。主要的研究内容和创新点总结如下:（1）链路预测算法设计和链路可预测性问题研究。真实网络在不同尺度上都有着丰富的结构。为了设计更加有效的链路预测算法,需要利用网络多尺度的结构信息。本文提出回路模型并运用于链路预测。首先,利用网络中不同长度的回路对网络的多尺度结构进行刻画;然后,利用指数随机图模型将回路信息转换为链路预测算法。在大量真实网络上的实验表明,回路模型的链路预测准确度高于其它先进算法。链路预测算法的表现不仅取决于算法自身,还依赖于所考虑的网络。例如,对于随机连边的Erd¨os-R′enyi网络,算法不会比随机猜测表现得更好。本文提出一个新的问题,即如何刻画网络本质的链路可预测性;为了尝试回答这一问题,本文提出了结构一致性指标。结构一致性指标将未知的连边看作对已知网络的微扰,并假设如果微扰剧烈地改变了已知网络的结构,那么对应的未知连边是难以预测的;反之,则是容易预测的。利用矩阵微扰理论,结构一致性指标对结构改变的剧烈程度进行了量化。大量的实验表明,结构一致性是链路可预测性的合理衡量指标。此外,基于对邻接矩阵的微扰,能够衍生出一种新的链路预测算法,即结构微扰法。实验显示这一算法具有很好的准确性和鲁棒性。有效的链路预测方法降低了网络的噪声,从而为进一步研究网络上的动力学提供了必要的准备。（2）促进双层网络信息传播的最优层间结构设计。真实网络很少是互相独立的,信息能够以各种方式跨越不同的网络进行传播。因此,很多真实网络系统需要用多层网络进行描述,而多层网络的层间结构对于信息传播动力学有着显著的影响。本文研究了使传播范围最大化的双层网络最优层间结构问题。首先,研究了传播阈值点附近多条层间连边的最优结构设计。在传播阈值点附近,本文基于特征值微扰理论推导出传播范围表达式,并在此基础上证明了贪婪地连接高特征向量中心性的节点可以获得最优的层间结构。数值实验表明,所提出的方法比经典启发式方法表现得更好。然后,研究了一般参数条件下最优的层间连边问题。通过发展离散马尔科夫链的微扰理论,本文给出了双层网络上传播范围的表达式,从而得出了最优的层间连边。在小规模网络上,通过穷举所有层间连边,我们发现这一方法可以给出最优或接近最优的层间连边。对于大规模网络,本文所提出的方法总是优于其它基于静态结构的方法。本文从网络结构微扰的角度对信息传播过程进行优化,能够为优化真实的信息传播过程提供理论支持。（3）共演传播动力学的临界行为研究。真实世界的信息、行为和疾病传播往往不是互相独立的。例如,WNCRY勒索病毒在扩散的同时,关于其解决和预防措施的信息也在快速传播,从而降低了经济损失。这类相互作用的传播过程被称为共演传播。共演传播能够产生复杂的动力学现象;然而,由于模型的错综复杂,其系统性的理论分析方法仍然匮乏。基于谱降维方法,本文提出了一个复杂网络上共演传播动力学的普适理论。具体而言,通过将微观的淬火平均场方程组粗粒化为二维的宏观状态方程组,本文给出了共演SIS模型完整相图的解析解,同时确定了相邻相区间的相变类型。这一相图不仅验证了已知的临界现象,还预测了未知的现象:例如,非连续相变和磁滞回线间的相互作用以及三相点的涌现。此外,本文还得出了磁滞回线出现的条件。本文提出的理论为理解共演传播过程提供了一种有效的方法,同时,也为如何利用一个信息传播过程干预其它信息传播的问题提供了理论基础。

论文目录

摘要

abstract

第一章绪论

1.1 研究背景与意义

1.2 国内外研究现状

1.2.1 复杂网络的链路预测

1.2.2 促进信息传播的结构最优化

1.2.3 共演传播动力学

1.3 本文研究内容与创新点

1.4 本文结构与章节安排

第二章链路预测与信息传播动力学相关基础知识

2.1 复杂网络基础知识介绍

2.1.1 基本结构刻画

2.1.2 经典网络模型

2.1.3 多层网络

2.2 链路预测相关知识

2.2.1 链路预测的基本概念

2.2.2 经典方法

2.3 信息传播动力学

2.3.1 经典信息传播模型

2.3.2 网络传播动力学的理论分析

2.4 本章小结

第三章链路预测算法设计与链路可预测性研究

3.1 基于回路模型的链路预测算法设计

3.1.1 基于回路的网络结构刻画

3.1.2 将结构刻画转换为链路预测算法的框架研究

3.1.3 实验结果与分析

3.2 复杂网络的链路可预测性研究

3.2.1 结构一致性指标的提出

3.2.2 基于结构一致性的链路预测算法设计

3.2.3 结构一致性与链路可预测性的对比分析

3.2.4 基于结构一致性的加权网络链路预测算法设计

3.3 本章小结

第四章促进双层网络信息传播的的层间结构最优化设计

4.1 传播阈值点附近的多条连边最优结构研究

4.1.1 双层网络上SIS模型的离散马尔科夫链方法

4.1.2 双层网络特征值扰动理论与最优层间结构

4.1.3 实验与结果

4.2 一般参数条件下单条连边最优化研究

4.2.1 离散马尔科夫链微扰理论与最优层间连边

4.2.2 实验与结果

4.3 本章小结

第五章共演传播动力学的临界行为研究

5.1 基于淬火平均场理论的共演SIS模型

5.2 共演SIS模型的降维方法

5.3 降维后共演SIS模型的临界行为分析

5.3.1 降维后淬火平均场方程的平衡点及其稳定性分析

5.3.2 基于平衡点及其稳定性的临界行为分析

5.3.3 相变类型讨论

5.3.4 观测到磁滞回线的条件分析

5.4 实验结果与误差分析

5.5 本章小结

第六章总结与展望

6.1 全文总结

6.2 研究展望

致谢

参考文献

攻读博士学位期间取得的成果

文章来源

类型: 博士论文

作者: 潘黎明

导师: 周涛

关键词: 复杂网络,链路预测,传播动力学,多层网络,共演传播动力学

来源: 电子科技大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 电子科技大学

基金: 国家留学基金委提供的联合培养奖学金,国家自然科学基金

分类号: O157.5

DOI: 10.27005/d.cnki.gdzku.2019.000012

总页数: 153

文件大小: 8468K

下载量: 362

复杂网络上的链路预测及信息传播研究

论文摘要

论文目录

文章来源

相关论文文献

猜你喜欢