基于网络结构的复杂网络链路预测算法研究

• 作 者: 王鑫
• 出 处: 安徽大学
• 发表日期: 2004年期
• 关键词: 复杂网络 链路预测 节点相似性 网络结构 权值

现实世界中,存在着许许多多的复杂系统,如交通、生物以及信息系统等等,这些复杂系统可以用网络来进行描述。系统中的个体可以用网络中的节点来表示,而个体之间的交互关系或者联系用连边来表示。复杂网络会随着时间进行演化,同样其中所蕴含的信息也会不断变化。而网络中的连边作为个体之间交互信息的载体,对其进行挖掘与研究显得非常必要。链路预测就是一种挖掘网络连边信息的重要手段,它不仅可以挖掘出网络中未知的隐含信息,也可以发现一些缺失信息,是对网络不完整性进行补全的一种手段。随着链路预测问题研究的不断深入,多种类型的算法被提出。其中,基于相似性的链路预测方法受到越来越多的关注。该方法的一个关键问题就是如何来定义节点之间的相似性。通常可以将拓扑网络中的各种信息融合在一起来定义节点之间的相似性,其中最重要的信息是节点属性和网络结构。使用节点属性信息有较高的预测精度,但是收集这些信息是不易的,即使可以获得节点属性信息,从这些复杂的信息中鉴别出哪些信息对预测有用处也是较为困难的事。相对的,网络结构信息获取简单且容易筛选。并且,基于网络结构的链路预测方法具有普遍适用性。然而,现阶段对基于网络结构的链路预测算法研究还不够深入,对哪种网络结构对连边有影响的挖掘还不充分。基于此,本文利用网络结构定义了 2种计算节点相似性的方法,提出2种新的链路预测算法。主要工作与贡献如下:1.在实际网络中,由于网络局部拓扑结构是不同的并且不同的节点自身属性也具有差异性,每个节点所代表的影响力是不同的,相应的对连边产生的贡献度也是不同的。还有共同邻居节点之间连接的紧密度一定程度上反映了节点自身所在的局部子网络的紧密程度,这也可能影响子网络中节点之间的连边。因此,本文定义了共同邻居节点的贡献度以及共同邻居之间的链接紧密度,将两者结合提出一种新的链路预测算法,简称LDNC(Link Density and Node Contribution)算法。将该算法在9个真实数据集上进行了实验,用AUC和Precision评价指标和五个算法进行了对比,结果表明LDNC算法是十分有效的。2.由于每个节点或每条路径在网络中所处位置的不同,它们对于网络其他部分的影响也是各不相同的。体现在链路预测中,就是不同的节点和路径对网络中的节点对是否产生连边影响力是不同的。这个影响力我们用节点和路径的权重来表示。基于此,本文给出了新的计算节点权重和路径权重的方法,并将两者结合在一起,提出一种新的链路预测算法,简称CPNW(combining paths weight and nodes weight)算法。将该算法在9个真实数据集上进行了实验,得出相似性分数矩阵,用AUC和Precision评价指标和6个算法进行对比,结果显示CPNW算法准确度较高,证明该算法有效。