1、1 绪论1.1 选题背景在繁复的世界里，存在越来越多的问题，比方：为什么现在马路越宽，交通越拥堵？为什么有些地方金融动乱，从而引发地区甚至全球的金融危机？为什么现在各种搜索引擎都能几乎准确的进行用户推荐？这些一系列的问题看上去各不相同，但却存在一个共同的特征：每个问题都是一个复杂的系统，而这些复杂系统均可以用复杂网络进行表示。在现代社会中，存在着各种各样的系统，包括：社交系统，互联网系统，电力系统，交通系统，新陈代谢系统以及食物链等等。这些系统中的实体抽象成网络中的节点(node)，实体之间的关系抽象成网络中的边（edge）。并且通过给复杂系统中的一些实体赋予不同的含义来更深入的刻画和描述复杂
2、系统的特点。比方：名称，方向和权重等。在不同的网络中，节点和边有着不同的含义。例如：在社会合作网中，节点代表参与合作的人，边代表他们之间是否存在合作关系；在航空网络中，节点是机场，边是航线；在蛋白质相互作用网络中，节点代表不同的蛋白质，如果两个蛋白质能相互作用形成化学键，那么存在连边。这些网络的存在激发了越来越多的学者研究的兴趣，已经成为目前科研中最受关注的科学前沿学科之一。研究网络的过程中首要考虑的问题是对于网络演化过程的模拟Error! Reference source not found.。近年对网络演化的相关研究说明，真实网络的演化是由多种不同机制共同驱动的结果。比方，BA模型可以模拟
3、出度的幂律分布，但是不能模拟聚类性。基于此，很多学者考虑将多种机制进行结合，以便可以更好的刻画真实网络的各种特征。Papadopolos等人Error! Reference source not found.将网络的相似性和流行性进行了结合，提出了一种数学模型来刻画网络的所有特征，还有学者Error! Reference source not found.考虑了网络的空间结构，将地理位置和拓扑结构进行了结合。为了研究各种不同的复杂网络在结构上的共同点，需要一种数学工具对其进行刻画，这个工具在数学上称为图。借助图工具，复杂系统和复杂网络的研究都可以转化成对图的研究。图（Graph）是用点和线对各
4、种实际网络进行抽象，这种抽象的好处是它可以使得我们通过现象看本质，通过对抽象的图进行研究从而得到实际网络的拓扑结构和特性Error! Reference source not found.。以“Konigsberg七桥问题Error! Reference source not found.（如图1.1）为例，欧拉把被河流分割的四块陆地抽象为节点，将连接两块陆地的桥看作连边，因此七桥问题被转换成四个节点，七条边是否存在每条边只经过一次且不存在回路的问题。由此，欧拉开创了一个新的数学中研究拓扑特性的分支拓扑学（Topology）。通过将实际网络抽象成图进行研究可以比较不同网络之间拓扑结构的异同点。
5、实际网络可以抽象为节点集和边集组成的网络。给定网络,是由节点集在无向图中，如果两个节点之间存在连边，即，那么称这两个节点互为邻居节点。如图中，节点4和节点1,3,6邻接，那么这三个节点两两互为邻居。一个节点所连接的其他节点的边数称为该节点的度，节点4有三个邻接点，那么节点4的度为3。在二十世纪六十年代，美国哈佛大学的社会心理学家Milgram最早提出了“小世界的概念，他认为美国任意两个人之间的平均距离是6。也就是说，一个人平均只要通过5个中间人就可以与任何一个人发生联系。这就是著名的“六度别离推断。此后，在1998年6月，、Error! Reference source not found.在
6、Nature上发表了题为“小世界的动力学文章，1999年10月，和Albert RError! Reference source not found.在Science上发表了关于“随机网络中标度的涌现文章。这两篇文章第一次提出了“小世界特性和“无标度特性，这两大特性的提出，使得越来越多的学者对复杂网络产生了兴趣，并投入该研究领域。通过大量实验论证得到，具有不同拓扑结构的网络之间存在着一些共同特性。比方：大局部的复杂网络具有明显的社区结构（Community Structure），换言之，整个网络可以看作是由假设干不同的社区构成。并且通过大量实验论证，一般社区内部的节点相比于社区外部的节点连接更
7、加紧密，所属不同社区的节点连接稀疏。如图1.3所示： 从图中可以看出社区结构的这一特性为人们研究复杂网络提供了一种新的研究视角。而作为复杂网络研究中的一个重要的研究方向链路预测，被用到社交网络，酵母菌蛋白质网络等多个复杂网络中。链路预测的定义Error! Reference source not found.是：通过认识和分析的网络的结构和信息对网络中尚未产生连边的节点之间存在连接的可能性进行预测。预测分为两种，第一种是对于未来链路的预测，即网络中的节点之间没有连边，在未来可能会存在连边。第二种是对未知链路的预测，即网络中存在连边但尚未被发现，复杂网络链路预测不仅在网络科学和信息科学理论上有重
8、要的研究价值，而且在实际应用方面有着重要的意义，譬如：找出交通传输网络中的重要作用连边，指导蛋白质相互作用实验，进行社交和爱好推荐等。1.2 复杂网络研究现状为什么命名为“网络结构的研究现状。要针对自己研究的问题论述当前针对该问题的研究现状。或者从更广的角度论述复杂网络研究现状，最后落脚到自己的研究问题上。简单来说，网络是由节点集合和连边集合组成。节点之间的连边说明了两者之间的关系，根据关系的不同含义，刻画出了不同类型的复杂网络。如图1.4（a）所示，为朋友网络，通过对Facebook上500多万用户的好友列表信息进行分析，Golder等人Error! Reference source not
9、 found.发现了一个符合于著名的“150法那么Error! Reference source not found.（即一个人最多能维持的好友关系数量大约在150人左右）的现象，即在Facebook中，每个用户的平均好友数量大约为180，中值是144。后来，Ahn等人Error! Reference source not found.通过研究和实验又印证了该法那么。又如，科学家合作网络，如图1.4（b）所示，在之前的研究中，如果两位科学家之间最少合作过一篇文章，那么科学家之间会存在一条连边。根据这个规那么，可以对科学家网络用无向无权图进行刻画，无向表示科学家之间的连边没有方向，无权表示科学家
10、之间的奉献没有强弱之分，为了进一步详细的刻画科学家合著的关系，通过给连边赋予权值，将网络刻画为，连边表示科学家之间合著文章的数目，连边的粗细代表权重大小，即科学家之间合作的次数。在上个世纪，对于网络的研究重点集中于刻画规那么的网络。但是，随着大数据的开展，学者们开始关注大规模真实网络的建模和计算，经过研究得到随机网络和规那么网络不能完整地刻画真实世界的网络，此后，、以及和Albert R分别提出了小世界网络模型和无标度网络模型。基于这两个模型，许多学者开始对于真实网络进行深入研究。Kumar等学者Error! Reference source not found.观察到在线社交网络的增长过程，
11、随着网络规模的增加，这些网络的平均距离反而减小了。除了拥有短的平均距离，真实网络还具有较高的聚类性。在宏观层面上，一些真实网路还存在着层级组织关系，比方新陈代谢网络Error! Reference source not found.等，这些网络中的节点分布于不同层。通过有规律的循环增长模式，网络形成了特殊的层次结构。例如，初始网络有四个节点，节点之间两两连接，根据同构关系，将网络中的节点分为中心节点和边缘节点，然后将这个初始网络复制三份，每一份的边缘节点与原小网络的中心节点进行相连，再将网络进行迭代，然后所有初始网络的边缘节点与中心节点进行相连，迭代下去，便构成了一个具有明显层次结构，并且具有
12、自相似性质的网络。通过研究发现，许多真实网路具有自相似Error! Reference source not found.的特性，包括朋友网络，食物链网络，新陈代谢网络，万维网等。在中观层面，依据网络节点之间连接的紧密程度，将网络划分成不同大小的社区。在不同的网络中，其社区具有不同的特性，譬如，在银行交易网络中，社区代表了不同的交易群体，在科学家合作网络中，社区可能代表不同的科研团队，朋友网络中，社区代表了不同的朋友圈等。社区划分的方法有很多种，有基于网络的模块度进行划分的，以模块度的划分为标准，模块度越大社区划分的效果越好Error! Reference source not found.。
13、但是，该方法对小团体的网络划分效果不是很好，基于此，许多学者提出了更详细的社区划分指标，如模块密度指标Error! Reference source not found.，基于自然密度的模块化程度Error! Reference source not found.，局部模块化程度Error! Reference source not found.等。在划分社区的算法方面，通过某种相似性或者接近程度将节点聚集在一起的思想成为研究的主流。对于网络结构进行更局部的分析，网络可以看作由许多三元组构成，根据三元闭包特性可知，网络具有聚类特性。无向网络中的三元闭包结构可以看作三个点的完全图，也称为三阶派系
14、，类似的，可以得到C阶派系，通过研究它们的组织方式，对于网络中重叠社区Error! Reference source not found.Error! Reference source not found.的发现具有重要的意义。而且很多经典的链路预测算法，都是基于三角形结构的闭包提出的。从微观层面，一个节点的重要程度可以通过中心指标来进行刻画。如度，接近中心性，介数中心性等。其中，节点的度是最简单的用来刻画节点重要程度的指标Error! Reference source not found.，度越大，节点越重要，但是度的大小只考虑了节点的局部信息，所以，仅仅用这一个指标来衡量节点的重要性，并不
15、全面。在后来的研究中，学者们提出了PageRank算法Error! Reference source not found.和LeaderRank算法Error! Reference source not found.来衡量节点的重要性。用k-壳分解法Error! Reference source not found.刻画节点在网络中所处的位置。除了这些方法，通过考虑路径信息，利用接近中心性Error! Reference source not found.计算距离的平均值等。还有一些方法考虑了节点自身的重要性，如用于网页排名的LeaderRank算法，累计排名算法Error! Referenc
16、e source not found.，还有基于网络的特征向量的中心性指标等。链路预测的研究进展这里需要指出既有研究工作的缺乏？这样才能突出自己研究工作的意义早期学者们主要通过马尔可夫链等传统机器学习技术进行链路预测的研究。最早是在2022年，SarukkaiError! Reference source not found.提出了一种新的概念，即使用马尔可夫链的概率连接预测和路径分析，并将马尔可夫链在HTTP请求分析等四个应用中进行链路预测和路径分析。此后，在Zhu的文章Error! Reference source not found.中将马尔可夫链应用到WWW网络，对用户进行了在线导航;此后，Wang等人Error! Reference source not found.通过马尔可夫随机域，得到节点之间连边的概率特征。应用节点的属性建立概率模型进行预测的还有很多。譬如，OMadadhain等人Error! Reference source not found.提出了一个条件概率模型的算法，通过网