论文部分内容阅读
链路预测是复杂系统与网络领域研究的前沿和热点问题之一,高精度的局部链路预测算法不仅能够有效预测虚假连边和未知连边,还可以帮助我们精细地分析网络结构。同时,网络零模型是复杂网络结构分析的关键技术之一,通过与原始网络的对比,零模型可以帮助我们准确的分析出各类网络属性的作用,并且能够帮助我们分析出各类网络的相对稳定性。近十五年,随着局部链路预测技术和零模型技术的快速发展,结合这两项技术对复杂网络结构采取精细分析正成为一个网络结构研究新的突破口。本文基于对各类网络统计量、局部链路预测算法和置乱算法的研究,针对网络的各类重要结构和属性特征,提出了相应的简单而高效的链路预测和零模型算法,对网络结构进行了细致化的分析。本文具体的创新性工作如下:1.针对动态演化网络上节点和连边的演化问题,提出了历史网络和未来网络的框架,并以在线演化社交网络为例,对复杂网络中节点的度和强度分布进行了详细研究。根据在线社交网络高度的交互特性将有向网络转化为无向网络,并通过对动态网络节点度和强度的分析,将用户分为活跃用户、消失的用户、新增用户和超级用户四类,同时将网络连边分为活跃连边、消失连边、新增连边和超级连边四类。本文的研究结果表明,在分析演化社交网络交互特性的时候,静态网络结构数据存在一定的局限性。本文的研究结果还揭示了在用户及其交互强度存在大范围变化的情况下,动态社交网络的统计量基本稳定的原因。2.针对传统静态链路预测算法及其评价指标缺乏演化特性的问题,本文给链路预测的评价指标引入了时间元素,调整了传统链路预测算法的结构,并探索已知的直接连边对链路预测所起的作用。此外,由于之前的研究表明,利用静态无权网络的结构信息对演化网络的连边分析和预测存在一定的局限性,因此本文利用连边的权重,对演化网络的链路预测问题进行了深入地探讨,并对网络结构有了进一步研究。本文通过对比实证演化网络和零模型上的链路预测算法性能,发现直接连边算法要优于间接连边算法,还论证了网络结构对链路预测所起的作用要远大于连边权重。更多地,本文的研究结果表明共同邻居数对网络弱链接现象的产生起着关键性作用。3.针对直接连边的预测功能问题,本文发现直接连边还可以帮助我们预测共同邻居、分析网络结构。因此,本文提出了一种非常简洁的链路预测方法,在静态网络和演化网络上对节点对的共同邻居或者节点对与共同邻居之间的连边进行预测。此外,本文还结合零模型,对网络结构的稳定性进行了分析。本文的研究结果表明节点对之间的直接连边可以帮我们有效地预测共同邻居。本文发现动态经济网络最难预测,非社交网络的稳定性要优于社交网络,工程网络最好预测且最为稳定,地理位置和连边权重均对交通网络的预测有着重要影响。4.针对有向网络上的链路预测问题,本文提出了有向网络节点的相位-动态算法来分析连边方向的作用,并证明了单向连边和双向连边对链路预测或者网络的形成有着不同的作用。此外,我们在实证网络中也首次发现双向连边对链路预测或者网络的形成有着更重要的作用。进一步,我们提出了新的方向置乱算法,发现具有单向连边和双向连边的节点比例分别对单向连边和双向连边预测作用的稳定性有着决定性的作用。5.针对BA网络模型和配置模型存在的缺陷,本文提出了现实世界系统适配网络的概念,并将网络的连通性、度分布和反映网络优先连接程度的PAI算法精度作为网络的三个关键适配性指标。进一步,基于对BA模型缺陷的分析,提出了相应的模型修正算法,并提出了富人俱乐部BA模型和随机化BA模型。在此基础上,最终成功地构造出了与14种现实世界网络有着相同连通性、更加相似的度分布和PAI精度的适配网络。