论文部分内容阅读
大数据时代,信息以网络的形式呈现,可以说网络是对复杂系统的一种抽象表达。节点表示复杂系统中的主体,连边表示主体间的相互作用关系。对网络的研究有助于我们更深刻地理解和认识其所对应的复杂系统。网络中的链路预测则是对复杂系统中主体间相互作用关系的预测。它根据观察到的网络结构等信息,预测实际存在但未被检测到的,或者未来某一时刻可能会出现的连边。 随着信息技术的发展,大量来自社会经济系统中的数据更容易获取和收集,但是由于数量庞大,结构复杂等特点,使得收集的数据存在错误和缺失的问题,这为科学研究的可靠性带来极大的挑战。应用链路预测方法可以对网络中的虚假信息进行识别,对于缺失连接进行补充,进而对网络实现重构,使其更接近于真实的情况。 本文首先回顾了近几年链路预测的研究进展,以及渗流理论在物理和网络科学中的发展概况,然后提出一种创新的基于网络键渗流过程的链路预测方法。网络中每一条边以概率p保留,1-p删除,随着p增大网络形成一个最大的连通分量,此时网络处于渗流状态,所对应的p为渗流临界值,即pc。渗流链路预测方法的基本假设是经过删边过程,网络破碎成多个小的连通分量,如果两个节点处于同一连通分量的概率较大,则他们之间更有可能产生连边。在四个真实网络中的实验结果表明,本算法在网络临界值附近能够获得较高的预测精度,并优于一些传统的链路预测方法。同时,由于该算法可以并行化计算,因此可以处理大规模网络的链路预测问题。为了探究算法的适用性及其内在机制,本论文设计了一系列网络模型来考察算法的影响因素,包括可调节网络集聚系数的模型,可调节网络平均度的模型以及可调节模块度的模型。结果发现:随着集聚系数增加,网络的预测效果越来越好;随着网络密度的增加,最优的预测参数 p*越来越接近网络渗流临界值pc;模块度对p*的影响不明显,但是随着模块度的增加pc越来越大,使得 p*向左偏离 pc;相比传统预测方法,渗流预测方法在集聚系数小且模块度较大的网络中表现出更大的优势。最后,我们将本算法进一步扩展到含权网络中,提出含权渗流链路预测方法,并应用到脑网络连边预测与网络攻击中,均取得较好的效果。