论文部分内容阅读
近年来,随着复杂网络相关研究的不断开展,越来越多的复杂系统逐渐成为复杂网络的研究对象。作为网络科学领域的研究热点,拓扑演化模型和链路预测分别从宏观统计和实际网络数据上对演化机制进行了实证研究。两者在复杂系统的演化、网络拓扑体系构建以及现实科研生活中均具有重要实际应用价值。符合网络宏观统计规律的网络演化模型可以指导、推理演化机制,为链路预测提供新思路;同时,链路预测技术可在海量的真实网络数据中验证演化机制的有效性,进而验证对应演化模型的合理性。当前,对于拓扑演化和链路预测的研究已经取得较大进展,然而仍然存在以下问题:1)已有的拓扑演化模型虽然对网络统计中的幂律分布等做了实证研究,但许多现实网络统计发现,网络的度分布并非纯粹的幂律分布,呈现近幂律分布、分段幂律分布、漂移幂律分布等多种不同的形式,亟需拓扑演化模型实证相应的宏观统计规律;2)针对多样化的大型实际网络数据,许多相似性链路预测方法在节点间的相似性上仍然需要进一步刻画,缺乏复杂度相对较低、预测精度较高的相似性链路预测方法;3)对于拓扑演化模型和链路预测技术的研究都相对独立、互不联系,并没有在一种演化机制下进行统一的实证研究。鉴于拓扑演化模型和链路预测技术的紧密联系,本文依托国家863项目,重点开展复杂网络拓扑演化和链路预测关键技术研究。首先,在拓扑演化模型上,分别从点的“拓展”和边的“串联”上研究了拓扑演化问题,依次探讨了基于网络模体和信息传播的拓扑演化模型;然后,在链路预测技术上,从“点权”、“路径”和“边权”三个方面分别探讨了共同邻居加权、节点间资源交互和局部拓扑加权的链路预测方法。最后,在两者的统一上,实证了拓扑演化模型和链路预测方的统一性。概括起来,论文的主要研究内容包括以下几点:1.为了探讨不同“尺度”的偏好连接对拓扑演化的影响,提出了一种基于模体顶点引力的拓扑演化模型。该模型从网络模体这一尺度出发,基于模体顶点度提出模体顶点引力量化局部组织结构对于节点偏好的影响,并在局域世界模型的基础上进行模体顶点引力的优先选择。仿真实验表明,模型具有小世界特性,集聚系数随局域世界大小而变化,不同参数下度分布呈现从幂律分布到指数分布变化,部分情形呈现出分段幂律分布。此外,模型能够随着网络模体顶点度占比不同而呈现不同匹配模式的网络。2.为了研究网络中重要的“内在动力”信息传播对于拓扑演化的影响,提出了信息传播促进网络增长的耦合拓扑演化模型。该模型包括信息传播促进网内增边、新节点通过局域世界建立第一条边和信息传播促进新节点连边三个阶段,通过多次自回避随机游走模拟信息传播过程,节点根据路径节点的节点度和距离与其选择性建立连接,其中包括随机连接、“度优先”连接、“扶贫”连接、近邻连接、“远交”连接以及互相结合的连接方式。理论分析和仿真实验表明,模型不仅具有小世界和无标度特性,而且不同参数下具有“漂移幂律分布”、“广延指数分布”等分布特性,呈现小变量饱和、指数截断等非幂律现象,同时,模型可在不改变度分布的情况下调节集聚系数,并能够产生从同配到异配具有不同匹配模式的网络。3.为了研究共同邻居加权对于链路预测精确度(Precision)的影响,从不同角度分别提出了基于共同邻居集聚程度加权(CCN)和连通度加权(RCN)的相似性链路预测算法。CCN方法中,通过分析集聚程度对于节点间建立连接的影响,利用集聚系数对共同邻居加权,并引入参数调节加权强度,进而刻画不同网络中节点间的相似度;RCN方法中,提出了共同邻居连通度来量化共同邻居与预测节点间的连通程度,并同样引入参数调节不同网络中的连通强度,进而描述节点间的相似度。多个实际网络结果测试表明,相比7个局部和全局相似性方法,两方法均具有较高的Precision结果。相比而言,RCN在多数网络中预测效果总体好于CCN,但CCN在较低集聚性网络如电力网络中表现更好。4.为了同时提升资源分配指标在AUC(感受性曲线下面积)和Precision两个不同衡量标准下的预测效果,提出了一种节点间资源交互的相似性链路预测方法。该方法在资源分配指标的基础上,考虑了更长路径的资源传输过程,并引入参数描述不同网络中较长路径的资源传输量,最后以节点间可能的资源交互量刻画节点间的相似度。多个实际网络数据测试表明,相比7个局部和全局相似性指标,该方法不仅能够提升AUC结果,也能够提升其Precision结果。5.为了研究一种同时提升多个相似性指标预测效果的方法,提出了节点间拓扑加权方法,并通过给现有相似性指标加权的方式提高它们的预测效果。首先,为了刻画节点间的拓扑信息,文章分析了多个场景中不同网络拓扑结构下节点间联系的紧密性,提出一种节点间局部拓扑加权方法,量化节点间联系的紧密程度;然后,将其应用于6个相似性指标,分别提出了6个局部拓扑加权的相似性指标LwCN、LwSalton、LwJaccard、LwRA、LwAA和LwLP。实际数据测试表明,节点间拓扑加权能够大幅度提高6个现有相似性指标的AUC和Precision结果,且在集聚性较低的网络中其提升幅度更大。6.为了实证演化模型和链路预测的统一,基于局部信息耦合促进网络演化这一机制,提出局部拓扑信息耦合加权方法。将其用于BA模型,通过节点强度的优先选择提出EwBA模型和局域世界的EwLW模型;另一方面,将拓扑耦合加权方法应用于多个相似性指标包括共同邻居指标、Salton指标和资源分配指标,提出加权后的相似性链路预测方法。模型演化结果表明,EwBA模型的度分布可随连边数目的增多,迅速从指数分布转变为幂律分布,基于此,提出一种加速演化的A-EwBA模型,以说明现实网络中的加速增长现象,EwLW则展现了从广延指数分布到幂律分布变化的形式。实际网络数据测试表明,加权相似性指标也能够大幅度的提高对应指标的预测效果。从两个方面论证了局部拓扑信息耦合促进网络演化的有效性,也从侧面实证了拓扑演化与链路预测的统一,宏观统计与实际网络数据的统一。