复杂网络的链接分析及预测研究
现实世界中,有许多科技、商业、经济和生物的数据可用复杂网络来表示,例如电力网格、电话交互网、社交网络、万维网以及科学家的合著关系和引用网络;在生物学领域,有流行病学网络、细胞与新陈代谢网络和食物网络;在人际关系中,公司内部的E-mail信息交互、新闻组、聊天室、朋友联系都是网络数据的例子。

现在,链接预测问题在社会学、人类学、信息科学以及计算机科学等各个领域都受到了广泛的关注。

当前,对网络数据进行链接预测的方法主要有基于相似度的、基于似然分析的和基于概率模型的方法等。

本文对当前网络链接预测的现状进行了分析,针对当前预测算法中存在的一些问题进行了研究,提出了相应的有效的算法。

本文的主要工作如下:(1)提出了直接优化AUC的链接预测算法。

快速扩展的互联网形成了具有高维、稀疏和冗余特性的复杂网络。

因此需要有效的链接预测技术来提高链接预测的精度。

考虑到AUC指标是衡量链接预测结果质量的主要标准,提出了直接优化AUC的链接预测算法。

在该算法中,将链接预测问题看成是二值分类问题,将AUC最大化作为优化的目标,使用hinge函数作为损失函数,使用随机次梯度下降算法迭代权重向量。

实验结果表明,本算法与其他算法的结果相比,不但在AUC指标上有较大的提高,在其他指标上也超过其他算法,可以实现更高质量的预测。

(2)提出了针对节点带有属性的网络的链接预测算法。

在很多领域,比如社会学、人类学、信息科学、计算机科学中,网络节点所代表的实体往往具有自己的属性。

这些属性的取值为链接预测提供了很有价值的信息。

如何应用这些信息进行
链接预测的问题已经吸引了相当多的关注。

本文提出了利用模块度测度反映网络社区结构信息链接预测算法。

基于同一个社区中的节点对之间的链接的可能性比在不同的社区中大这一事实,提出了模块度贡献的概念。

基于模块度贡献的概念,将网络的节点映射到一个低维的欧氏空间。

在这个低维空间中,在同一个社区内的节点的将处于相邻的位置。

计算节点在低维空间中位置的余弦相似性,作为链接预测的相似性度量。

本文也扩展该方法,将其应用到节点带有属性的网络的链接预测中。

实验结果表明,该算法可以获得理想的预测结果。

(3)提出了针对多关系网络的链接预测算法。

许多现实世界中的网络包含多种类型的相互作用和关系。

对这样的多关系网络进行链接预测成为网络分析中的一个重要课题。

在所提出的多关系网络的链接预测方法中,考虑了不同类型之间关系的相似性和影响力。

本文提出了一种置信度传递的方法来计算每个节点的置信度,并构建每种类型链接之间的置信度向量。

使用置信度向量之间的相似性来衡量不同类型关系之间的影响。

在此基础上,提出了一种基于非负矩阵分解的多关系网络链接预测算法。

我们还从理论上证明了所提出的方法的收敛性和正确性。

实验结果表明,本方法与其他类似的算法相比,可以降低维度,减少存储空间,取得高质量的预测结果。

(4)提出了对单个节点进行链接预测的基于抽样的算法。

在许多现实应用中,需要对用户感兴趣节点的相似性进行预测,而不需要预测网络中的所有节点间的
链接。

为此,提出了一种快速的以相似度为基础的方法来预测相关节点的链接。

在该方法中,首先构造一个围绕感兴趣节点的子图。

对这样的子图,通过设定适当的大小,可以将相似度的误差限制在一个给定的阈值范围内。

由于只要计算这个小子图中的节点的相似性得分,该算法可以大大减少计算时间。

通过在实际网络上的实验结果表明,本算法与其他方法相比,可以在更短的时间获得高精度的预测结果。