顶点带属性网络的链接预测

摘要

现有的复杂网络链接预测算法主要关注网络中节点之间的拓扑相似特征和算法性能的提升，而缺乏对网络中节点属性特征的研究。在一些应用问题中，网络的顶点自身带有极其丰富的属性信息。这些属性反映了顶点所代表对象的特性和内容，这些信息也在很大程度上影响着链接存在的可能性。如果能够把复杂网络的结构信息和属性信息结合到一起，势必能够极大地提高链接预测算法的预测精度。另外，实际情况中网络本身存在的高维度、高稀疏性等问题对链接预测的结果也会造成负面影响。
　　目前，如何将复杂网络的结构信息和属性信息有机地融合在一起，以提高链接预测的质量，还是一个有待探讨的问题。本文针对顶点带属性网络的链接预测问题，从顶点的结构相似性和属性相似性出发，研究如何有机地融合结构信息和属性信息、设计高效的链接预测算法，以提高预测的精度。取得的主要研究成果如下:
　　(1)提出了一种基于奇异值分解和空间映射的链接预测算法
　　为了综合考虑网络的结构特征和节点的属性特征，本文首先对网络的邻接矩阵进行特征分解。然后对特征值进行主成分抽取后再对相应的特征矩阵进行奇异值分解，将得到的新的奇异向量之间的相似度作为拓扑结构的相似度。最后将得到的拓扑相似度矩阵和属性相似度矩阵进行矩阵比对，得到最终的相似度矩阵。实验证明，本文提出的算法能有效提高链接预测的性能。
　　(2)提出了一种基于非负矩阵分解的链接预测算法
　　在实际应用中，复杂网络所对应的信息矩阵可能会存在着高维的问题。本文将非负矩阵分解应用于顶点带属性网络的链接预测中，分别将网络的邻接矩阵和属性相似度矩阵分解成非负的基矩阵和权重矩阵，通过将高维向量空间向低维向量空间的投影，重构不同类型矩阵之间的相关性。实验证明，本文提出的算法不仅拥有较低的复杂度，而且能够减少数据的存储空间，有效地提高链接预测的性能。
　　(3)提出了一种基于相似度传播的二分网络链接预测算法
　　相对于单分网络，二分网络在现实社会的复杂网络中更具有普遍性，已经成为复杂网络的重要研究课题之一。本文提出了一个基于二部图的链路预测算法，该算法使用了基于链接相似度得分的随机游走算法。在该算法中，网络里的每一条边都被分配一个对应顶点对属性相似度的传播概率。不同类节点之间的链接相似性得分是根据它们连边的传输概率来传播的。将该算法得到的拓扑相似度和网络的属性相似度结合，可以使预测的结果更加准确。实验证明，本文所提出的算法可以在较少的时间内得到较高精度的预测结果。

目录

摘要

第一章 绪论

1．1 研究背景及选题意义

1．2 课题的引出

1．3 论文的研究内容

1．4 论文的组织结构

第二章 复杂网络及链接预测

2．1 复杂网络的基本概论

2．1．1 网络的发展

2．1．2 复杂网络的概念

2．2 网络的刻画

2．2．1 图的基本概念

2．2．2 网络的刻画

2．3 链接预测

2．4 数据集的划分

2．4．1 随机抽样法

2．4．2 逐项遍历抽样法

2．4．3 k-折叠交叉验证法

2．4．4 随机游走抽样法

2．5 链接预测的评价指标

2．5．1 AUC指标

2．5．2 精确度

2．5．3 排序分

2．6 本章小结

第三章 基于相似性的链接预测分析

3．1 相似性

3．2 基于局部信息的相似性指标

3．2．1 基于共同邻居的相似性指标

3．2．2 PA指标

3．3 基于路径信息的相似性指标

3．3．1 LP指标

3．3．2 Katz指标

3．3．3 LHN-Ⅱ指标

3．4 基于随机游走的相似性指标

3．4．1 平均通勤时间

3．4．2 SimRank指标

3．5 基于属性的相似性度量

3．5．1 欧几里得度量

3．5．2 余弦距离相似度

3．5．3 相关系数

3．6 结构信息和属性信息的结合

3．7 本章小结

第四章 基于奇异值分解和空间映射的网络链接预测

4．1 问题的定义

4．2 矩阵的奇异值分解

4．3 基于奇异值分解和空间映射的网络链接预测

4．4 映射矩阵的计算

4．5 实验结果及分析

4．5．1 测试数据集

4．5．2 实验结果

4．6 本章小结

第五章 基于非负矩阵分解的网络链接预测

5．1 相关背景介绍

5．2 非负矩阵分解

5．3 基于非负矩阵分解的网络链接预测

5．4 实验结果及分析

5．4．1 测试数据集

5．4．2 实验结果

5．5 本章小结

第六章 基于相似度传播的二分网络链接预测

6．1 二分网络的链接预测

6．2 二分网络上的SimRank指标

6．3 基于相似度传播的顶点带属性二分网络的链接预测

6．4 实验结果及分析

6．5 本章小结

第七章 总结与展望

7．1 研究总结

7．2 研究展望

参考文献

致谢

攻读学位期间发表的学术论文与参加的研究工作

声明