复杂网络中基于角色传递性和对称性的链接预测算法研究

摘要

最近几年，信息时代的快速发展，复杂网络的研究得到越来越多的关注。复杂网络指的是由许多实体以及这些实体之间存在的各种各样的关系所组成的网状结构。复杂网络研究又称为链接挖掘，旨在发现网络中当前缺失的或者在未来可能形成的链接关系。链接预测作为链接挖掘中的一个热点问题在许多研究领域都有着现实的应用价值。例如，链接预测应用到社交领域的朋友推荐网络中，它可以用来预测人与人之间在将来成为朋友的可能性；链接预测应用到生物信息领域的神经网络中，它可以用来发现神经元之间存在的潜在关系，等等。因此，链接预测为发掘将来可能存在但尚未被发现的链接提供了一种有效的手段。
　　目前已经提出了很多基于节点相似性的链接预测方法，这些方法在链接预测方面的精确性以及时效性都已经非常可观。我们通过分析发现，这些链接预测方法中普遍存在这样一个事实，即它们在计算网络中节点对之间的相似度时，对待每个节点的角色都相同，也就是视作每个节点的角色值都为1。然而在实际中，由于网络中每个节点发挥的作用有大小之分，因而每个节点的角色值不可能都相同。因此，我们为了改善这一情况且进一步提高链接预测的精确度，本文提出了两种基于相似性度量的链接预测方法：CorpSim和AconSi m。
　　CorpSim方法首先引入了Google公司的网页排名PageRank算法计算网络中每个节点的真实角色值，可以有效地解决现有方法对待网络中每个节点的角色都相同这一情况。同时，CorpSim方法中通过角色的传递性来定义并计算节点对之间的相似性。CorpSim方法由两部分组成：路径的中间节点和两个端点角色传递对相似性的贡献，并且CorpSim方法最终使用权衡因子连接这两部分。AconSim方法同CorpSim方法一样，首先会利用PageRank算法计算出网络中每个节点的真实角色值。然后，与CorpSi m方法使用角色传递性来定义并计算节点对之间的相似性不同的是，AconSi m方法利用角色之间的对称性来定义并计算节点对之间的相似性。在真实的网络数据集上的实验结果表明，我们所提出的两种链接预测算法可以很好地提高预测的准确性。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 研究背景及意义

1.2 国内外研究现状

1.3 本文的主要研究内容

1.4 论文组织结构

第二章 复杂网络中链接预测的相关概述

2.1 复杂网络的基本概念

2.2 复杂网络的链接预测任务

2.3 相似性链接预测算法

2.4 链接预测的评测指标

2.5小结

第三章 CorpSim：基于角色传递性的相似性链接预测算法

3.1 CorpSim的设计思想

3.2 CorpSim算法

3.3 实验评估与结果分析

3.4 小结

第四章 A co nS im：基于角色对称性的相似性链接预测算法

4.1 AconSim的设计思想

4.2 AconSim算法

4.3 实验评估与结果分析

4.4 AconSim与CorpSim方法的对比

4.5小结

第五章 总结与展望

5.1 本文工作总结

5.2 下一步的研究工作

参考文献

在学期间的研究成果

致谢