论文部分内容阅读
真实世界中的很多研究领域都可以抽象为复杂网络,网络中的节点表示对象,边表示对象之间的关系。对复杂网络的建模机理和建模过程的深入研究,可以解释隐藏在自然界、社会界、生物界中的复杂系统的共同规律。研究复杂网络对探索网络形成及衍化机制有着重要的意义。其中,链路预测作为复杂网络的重要研究方向越来越受到研究者们的关注。链路预测是指如何通过已知的网络节点以及网络结构等信息预测网络中尚未连接的两个节点之间产生链接的可能性。随着链路预测研究问题的不断发展,很多预测算法被提出。其中,基于节点相似性的链路预测算法得到了广泛的研究。然而,在利用网络局部结构信息研究链路预测问题方面的研究还不够深入。网络局部结构对链路预测算法的性能有很大的影响,研究局部结构特征对提升链路预测算法的预测效果有重大的意义。针对该问题,本文对利用网络局部结构信息研究链路预测算法问题进行深入研究,主要内容包括以下三个方面:第一,网络中的三元闭包结构作为网络中最小局部结构,具有结构平衡和稳定的特征。通过计算出每个节点在网络中所占三元闭包的权重,并将该权重用于节点相似性指标中,提出了 TWCN、TWAA、TWRA三个相似性指标和具有调节参数的三个相似性指标:TWCN*、TWAA*、TWRA*。将新的相似性指标应用到预测算法中,提出了 PWNW算法和PWNW_α算法。采用CN算法、AA算法和RA算法作为对比算法。实验结果表明,PWNW-αα算法在预测精度方面比对比算法更具有优势。这说明利用三元闭包结构信息能够有效地提高预测算法的预测精度。通过分析实验结果,发现了一个现象:在社交网络中拥有较多三元闭包的节点,具有局部稳定性,不倾向于建立更多的新链接。相反,拥有较少三元闭包的节点,具有局部不稳定性,倾向于建立更多的新链接。这种现象也符合社会学中有关于新链接出现的现象。第二,根据节点拥有的三元闭包数目和节点度之间的关系可以计算节点的聚类系数,该信息体现了节点的聚集能力。聚类系数作为重要的节点拓扑属性不仅可以很好的体现局部结构的紧密性,同时对产生链接也会起到一定的作用。而传统的链路预测方法通常使用共同邻居数目或节点的度来衡量节点之间的相似性。然而,节点之间的关系不仅与邻居节点数目和度有关,与节点所处的局部结构有着密切的关系。基于这个观点,提出结合节点度和聚类系数的链路预测算法,简称NDCC算法。利用共同邻居节点的度和聚类系数计算被预测节点对之间的相似性。不仅充分利用网络局部结构信息,还能够体现出共同邻居节点之间存在的差异性。与几个常用的对比算法的相比,NDCC算法在预测精度上具有很好的优势。第三,上述两种预测算法都只考虑了被预测节点对之间的共同邻居节点,这种方式只能体现距目标节点两步以内的网络结构。其缺点是对网络中不具有共同邻居节点的节点对没有预测能力。而新链接的产生不会局限于这种邻居结构。针对该问题,利用社会学强关系理论来提升预测算法的预测能力。强关系理论:三步以内的关系都为强关系,强关系具有触发行为。这种行为可以为未连接的节点提供更多的相互连接的机会。另外,节点的度和聚类系数体现出节点之间连接紧密程度,对网络结构有着很大的影响。结合这两个方面,提出结合节点拓扑属性和强关系的链路预测算法,简称TPSR算法。该算法不仅考虑了节点的拓扑属性信息——节点的度和聚类系数,还结合了强关系对新链接出现的贡献。充分利用局部结构信息来刻画节点之间的相似性。与几个传统的算法相比,该算法具有更大的预测范围和更强的预测能力。