论文总字数：19579字

摘 要

在现实生活中，存在很多复杂系统——如社交系统、神经系统等，这些系统可以通过抽象的方式剥离出网络，即社交网络、神经网络等

网络链接预测是网络研究的重要课题。网络链接预测(Link Prediction)是指通过网络中已知的节点以及网络结构等信息来进行，预测网络中所未知的两个节点之间产生链接的可能性。

通过网络链路预测，不仅可以知道网络中链接存在的可能性、去除网络中已知链接的错误链接，而且可以对于网络的结构的获得更准确的认知。

本文针对基于相似性的链接预测算法，开发出链接预测平台。该平台主要利用基于局部信息的相似性指标—CN指标（Common Neighbors）、PA指标(Preferential Attachment Index)、AA指标(Adamic-Adar Index)、RA指标(Resource Allocation)，基于路径的相似性指标—Katz指标，以及基于随机游走的相似性指标--RWR指标等算法对于数据进行处理，得到数据处理的评价指标—AUC、精确度，并根据得到的结果做出相应的图进行比较。

本文首先通过介绍研究背景介绍以及现状，然后介绍了基于相似性的链路预测的相关算法。之后，本文列出实现算法实现的关键代码。紧接着，本文对该平台进行了测试，并对测试结果进行总结。最后，本文总结了所做的工作，并提出了下一步工作的展望。

关键词：网络，基于相似性的链路预测，算法，评价指标

The implementation of similarity-based methods

for link prediction in networks

Abstract

In real life, there are many complex systems, such as social system, nervous system etc. These systems can be stripped out in an abstract way, which is, social networks, neural networks, etc.

Link prediction is an important subject of networks research. Link prediction is to predict the possibility of link between the two nodes which don’t have a link now, based on the information of known nodes and network structure.

Through a network link prediction, not only can we know possibility of links in the network, remove wrong links, but also can get better understanding of the structure of the network.

In this thesis, I develop a platform for link prediction based on link prediction algorithm of similarity. The platform is mainly based on local information-Common Neighbors, Preferential Attachment Index, Adamic-Adar Index, Resource Allocation, path information-Katz index, and random walk with restart-RWR algorithms for data processing. The platform can obtain evaluation data-AUC and Precision, and generate graphs according to the results.

Firstly, this thesis introduces the research background and current situation, and then introduces some algorithms of link prediction based on similarity. After that, this thesis lists the key code of algorithms. Then, I test the platform, summarize and analyze the results. Last, this thesis summarizes the works which have been done, and puts forward the prospect of next step of work.

Keywords: Network， Link prediction based on similarity，Algorithm，Data evaluation

目 录

摘 要 i

Abstract ii

目 录 iii

第一章 绪论 1

1.1 引言 1

1.2 研究背景及现状 1

1.3 论文组织结构 2

第二章 相关技术 4

2.1 Python、R概述 4

2.1.1 Python 4

2.1.2 R 5

2.2 Python开发环境 6

2.3 本章小结 7

第三章 基于相似性的链接预测算法 8

3.1 基于局部信息的相似性指标 8

3.2 基于路径的相似性指标 10

3.3 基于随机游走的相似性指标 10

3.4 评价指标 11

3.4.1 AUC（area under the receiver operating characteristic curve） 11

3.4.2 精确度 11

3.5 本章小结 12

第四章 系统实现 13

4.1 开发环境配置 13

4.1.1 安装Python 13

4.1.2 安装pip 13

4.1.3 安装R语言 13

4.1.4 Boost Library安装 14

4.2软件功能实现 14

4.3 本章小结 17

第五章 系统测试 18

5.1 测试目的与方案 18

5.2 测试环境 18

5.3 算法测试结果 18

5.4 本章小结 27

第六章 总结和展望 28

6.1 毕业设计总结 28

6.2 进一步工作 29

致 谢 30

参考文献 31

第一章 绪论

1.1 引言

自然界中存在大量的复杂系统，而这些系统可以通过各式各样的网络来描述。一个典型的网络是由很多的节点以及连接这些节点之间的边组成，其中节点代表系统中不同的个体，边表示个体之间的关系。边表示两个节点之间存在某种关系，没有边则不存在，两个节点如果有边相连，在网络中被视为相邻。

真实世界中的常见的网络主要有社会网络、技术网络以及生物网络。社会网络是社会研究中较为成熟的，主要又分为社会合作网络、朋友网络、通信网络等；技术网络是人造的网络，常见的有互联网、交通网、电力网络；生物网络表现着生物几十亿年的演化历程，食物链网、新陈代谢网络等等，都可以体现生物的演化过程。

剩余内容已隐藏，请支付后下载全文，论文总字数：19579字