摘 要

这是一个数据爆炸的时代，也是一个万事万物依靠关系连接成网的时代。小到身体细胞的正常新陈代谢，大到浩瀚宇宙的天体运行，无一例外都构成了复杂的网络系统。为了应对具体的实际系统和解决生活中的实际问题，例如传染病的防控，电力系统的优化，需要人们从科学的角度建立模型从而更深层次的了解和认识这些网络。

本文根据复杂网络下的双曲几何框架，提出了一种基于网络社区及其层次结构的双曲映射方法，该方法首先利用社区间的联系将网络映射到双曲空间，随后利用双层角度优化的方法优化坐标，从而帮助我们更好的了解复杂网络结构特征、演化机制。随后，基于映射得到的双曲坐标，结合节点的局部信息或者全局信息，提出了三种描述节点相似性的链路预测指标，并用AUC来评价其预测效果。

实验结果表明，本文提出的双曲映射方法能较好的在准确度和时间复杂度上进行权衡，与其他算法相比较而言，映射准确度较高。而基于双曲距离所提出的几种链路预测指标在不同网络都具有较好的预测效果，

关键词：复杂网络；链路预测；社区结构；双曲映射

Abstract

This is an era of data explosion.And it is also a time when all things depend on connections to form a net.From the normal metabolism of the body cells to the celestial bodies of the vast universe, without exception, it constitutes a complex network system. In order to deal with specific systems and solve practical problems,such as the prevention and control of infectious diseases and the optimization of power systems,it is necessary to establish models scientifically to gain deeper understanding of these networks.

According to the hyperbolic geometric framework under the complex network,this paper proposes a hyperbolic mapping method based on the network community and its hierarchical structure. This method first uses the connections between communities to map the network to the hyperbolic space and then use double-angle method to optimizing the coordinates , which helps us better understand the complex network structure characteristics and evolution mechanism. Subsequently, based on the hyperbolic coordinates obtained from the mapping,combining node’ s local or global information,three link prediction indicators describing the similarity of nodes are proposed, and the AUC is used to evaluate the prediction results.

The experimental results show that the hyperbolic mapping method proposed in this paper can well balance the accuracy and time complexity. Compared with other algorithms, the mapping accuracy is higher. The link predictions based on the hyperbolic distance have better prediction effect in different networks.

Key words：Complex Networks；Link Prediction；Community Structure；Hyperbolic Mapping

目 录

第一章 绪论 1

1.1 研究目的及意义 1

1.2 国内外研究现状 1

1.2.1社区发现算法研究现状 2

1.2.2复杂网络双曲模型研究现状 3

1.2.3复杂网络双曲映射方法研究现状 4

1.2.4复杂网络链路预测研究现状 4

1.3本文主要工作 6

第二章 复杂网络基本概论 7

2.1 无权无向网络 7

2.2 复杂网络相关术语 7

2.3 基本网络模型 9

2.3.1 规则网络 9

2.3.2 随机网络 9

2.3.3 小世界网络 9

2.3.4 无标度网络 9

2.4 生成网络模型EPSO 10

2.5 实验网络数据 11

第三章 复杂网络双曲映射方法 13

3.1 社区发现FUA算法 13

3.2 社区排序算法 14

3.3 社区-扇区假设 16

3.4 双曲映射算法CSHM 16

3.4.1 计算节点的径向坐标 18

3.4.2 计算节点的初始角度坐标 18

3.4.3 角度坐标优化模型 18

3.5 实验验证 19

3.2.1 生成网络 20

3.2.2 社区排序算法的验证 20

3.2.3 映射算法准确度的验证 22

第四章 链路预测 28

4.1 评价指标 28

4.1.1 排序分 28

4.1.2 精确度 29

4.1.3 AUC 29

4.2 相似性指标 29

4.3 实验验证 31

第五章 总结与展望 34

5.1 全文总结 34

5.2 课题展望 34

参考文献 36

致 谢 41

第一章 绪论

研究目的及意义

21世纪，是数据爆炸的时代，各类数据相互作用、链接成网。形成的网络既不是规则网络，同样也不随机，我们称其为复杂网络^[1-4]。生活中的许多系统都能抽象成一个个网络，其中，节点代表一个个实体，用连边代表节点之间的相互关系。我们的交通系统是一个网络，它的顺畅与否影响着我们市民出行的方便与快捷；我们的电力系统是一个网络，源源不断的电能通过电线输送到祖国的各家各户；我们的神经系统是一个网络，神经细胞的相互关联保障了人体的正常新陈代谢。研究复杂网络有助于我们发现大型真实网络的共同结构特征，因此在生活中有着诸多应用^[5-8]

然而，回顾2017年，可以发现各类网络安全层出不穷。17年的3月份，Dunamp;Bradstreet——世界著名的商业信息服务机构，遭遇了52GB数据库的泄露，影响了大部分美国从业者；WanaCry病毒在英国、中国、俄罗斯等99个国家进行广泛传播，使医疗、教育、企业、电信等机构网络瘫痪、业务丢失。2018年以来，许多国家都在调整自己的网络政策以及加强网络军事力量的建设，以应对越来越复杂多变的网络形势。

由此可以看出，虽然网络将人们联系在一起，方便了人们的交流与合作，促进了信息的广泛传播，看似盘根错节、环环相扣，却并非坚不可摧。有心人往往只要攻击网络中某个节点或某条链路，就可以导致整个复杂系统的瘫痪。

因此，要想防患于未然，或者让网络具有更强的健壮性，我们需要研究复杂网络。许多研究表明，不同的复杂网络之间往往有着共性，研究不同类型的复杂网络数据，在不确定性中找到确定性，才能够找到处理它们的通用方法，增强网络的抗毁性。

此外，研究怎样对链路进行预测也是复杂网络的一个方面。它是通过已知的网络结构和节点的固有属性等信息来预测网络中尚未产生连边的两个节点之间产生连接的可能性，它所需要处理的问题是信息的还原与预测。该问题从已观察到的网络结构入手，预测存在但未被观察到，或者未来可能会出现的链路。它不仅可以用于提取缺失的信息，帮助分析数据缺失的网络，还可以用来识别虚假的交互，评估网络演进机制等等，在现实生活中具有非常广泛的应用。

国内外研究现状

复杂网络的开端可以说是从1736年Euler的哥尼斯堡七桥问题的研究开始的，随后，各国的科学家们开始从七桥问题所引出的图论探究起了简单规则的网络。然而规则网络过于理想化而无法表示现实网络的复杂性，终于在20世纪60年代由两位匈牙利数学家 Erdős, P,和Rényi, A建立了随机图理论(Random Graph Theory)^[9]，从此开创了复杂网络的系统性研究。进入20世纪90年代，人们从真实的网络数据中发现其具有的性质并非简单的满足随机网络或者规则网络的性质，因此特地将这样的特殊的网络称为复杂网络。1998年6月，复杂网络具有小世界特征^[10]的性质被Watts和其导师Strogatz教授提出，并相对应地建立了WS小世界网络模型，次年10月复杂网络的无标度特性^[11]以及相对应的BA增长网络模型被Barabāsi教授及学生Albert发现。至此，人们对复杂网络的研究又上了一个新的台阶。

在考虑网络特征的时候，我们往往可以使用聚类系数、有向无向、平均路径长度等来衡量网络。小世界特征又被称为六度分割理论（Six degrees of seperation），小世界特征有两个显著的特点——大聚类系数、短特征路径长度；无标度特征是指网络节点度服从幂率分布^[12]，这种特性缺乏明显的特征尺度来描述，可能会存在度数非常大的节点。

1.2.1社区发现算法研究现状

复杂网络中的的节点往往会集群出现，展现出社区结构，而集群出现的一个个节点组则被称为社区^[13]（community）。由于社区是由一类相似（不管是功能还是性质）的节点组成，例如大学中每个社团聚集了一批具有相同兴趣爱好的人；同一片区域，人种都相对集中，因此更有利于人们发现社区结构和功能之间的关系。现实网络中，一个节点可能不只属于一个社区，就像一个人的兴趣爱好可能不止一种，我们称属于多个社区的节点为“重叠节点”，而社区之间重叠节点的存在被称为“重叠社区^[14]”。

为了寻找网络中的社区结构，科学家们研究出了许多社区发现算法。传统的社区发现算法基于图分割（graph partitioning），其基本思想是将图分割成两个子图，然后进行迭代。Kernighan等人基于贪婪优化的启发式过程将已知网络划分成已知大小的两个社区，提出了K-L（Kernighan-Lin）^[15]算法。Simon提出了谱二分法^[16]，它是利用Laplace矩阵的特征值和特征向量的性质来做社区划分。G.W.Flake给网络增加虚拟源节点和终点节点，提出了基于最大流的算法。

以上是毕业论文大纲或资料介绍，该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取，微信号：bysjorg。

相关图片展示：