1、摘 要链路预测作为复杂网络的重要研究方向之一，它是将目前已存在的连边与未来可能存在或者存在但未被发觉的连边联系起来的重要桥梁之一，简而言之，它是解决了复杂网络的根本问题缺失信息的还原和预测，在理论和应用层面上都有重要的意义和价值。理论上，链路预测是通过网络中已知节点的信息，来预测网络中尚未产生连边的节点之间存在连边的概率。如果能够将链路预测的算法进行改进，并且将其与网络结构特性相结合，这样对于网络演化过程的模拟有很重要的价值，在应用方面，如果有比较优秀的链路预测算法，可以将预测算法应用到各种网络关系中，如蛋白质网络，可以大大降低试验成本。传统网络的链路预测，其研究对象都是基于静态网络，获得网络
2、的拓扑结构，然后利用其节点的各种属性进行相似度预测。这对于分析理解网络的宏观发展具有很大的帮助。但是，对于动态演变的网络而言，传统意义上的网络链路预测算法，其效果并不明显。目前主流的链路预测算法主要有两类，一类是基于马尔科夫链或者机器学习，这类算法主要考虑网络中节点的属性，在预测效果方面虽然能够达到较好的预测精度，但是因为其计算过程中涉及很多参数的约束而受到限制；另一类基于网络结构的最大似然估计算法具有很高的计算复杂度，不适用于数据量较大的复杂网络。由此可见，传统的链路预测主要是针对静态网络，而不适用于动态网络的分析。而且目前已有的链路预测算法其复杂度较高。而本论文以银行交易形成的复杂网络为研
3、究对象，由于交易网络会随着时间发生变化，节点的连接属性，连接情况都会发生变化，原来连接的节点，会随着时间，不发生连接。之前不连接的节点会在后期的网络演变中具有很高的邻居节点。因此动态网络的预测算法不仅需要考虑网络的本身结构属性，还要考虑网络动态演变的趋势。根据以上情况，本文试图寻找一种适用于动态网络的链路预测算法。为此，本文主要完成的工作如下所示：第一，对复杂网络和链路预测的基本概念及研究现状进行了梳理，对已有的基于不同特性所提出的链路预测算法与评价指标进行了分析。第二，根据复杂网络分析方法对银行客户的交易数据进行了研究，定义并构建了无向有权的客户交易网络模型。在构建交易网络结构的基础上，本论
4、文研究了不同时间戳的交易网络的拓扑结构特性，包括度分布，聚类系数，平均路径长度。通过对于这些特性进行大量的实验分析，验证了客户交易网络具有复杂网络的小世界和无标度特性。第三，由于交易网络的动态特性，针对目前已有的研究中对于动态网络链路预测算法的欠缺，在分析客户交易网络结构的基础之上，设计并实现了一种适用于交易网络的动态预测算法。算法主要包括已连接的节点和未连接节点之间的预测。结合交易网络的特性，提出了网络节点的连接强弱性与节点的连接重要性概念，进一步的对我们提出的原始算法进行了改进，基于实际数据集，分别对本文所提出的算法与改进的算法进行了实验与分析。第四，将本文提出的动态预测算法，改进的链路预
5、测算法以及随机算法，用于某商业银行的交易数据中，预测的准确度大概在72%，然后将这三种算法运用到具有动态交易特性的三种实际数据集中，通过实验验证得到，算法的预测精度在75%和89%左右，最后将本文提出的算法与链路预测中的经典的算法进行对比，本文的算法预测准确度大约提高了10%。关键词：复杂网络；动态网络；强弱性；重要性；链路预测目 录摘 要IAbstractIII1 绪论11.1 选题背景11.2 复杂网络研究现状41.3链路预测的研究进展61.4 本文研究内容及意义81.5 论文章节及其安排82链路预测102.1问题描述102.2链路预测评价指标112.3链路预测算法122.4小结143 商
6、业银行网络结构分析153.1交易网络与复杂网络153.1.1交易网络及其特征153.1.2交易网络的数据属性163.2交易网络的静态网络特性183.2.1网络结构的表示183.2.2交易网络的统计特征203.3交易网络的社区特性263.4小结264 交易网络的链路预测274.1 引言274.2 数据处理274.2.1异常数据处理284.2.2网络中孤立节点对的处理284.2.3数据集的分类284.3基于已连接节点的预测算法294.3.1算法思路294.3.2自适应节点重要性累计算法定义与说明304.3.3 INSAA算法描述314.3.4算法分析与改进344.4基于未连接节点的预测算法384.
7、4.1引言384.4.2基于相似性的链路预测384.4.3结构相似性指标算法描述394.5算法比较414.5.1三个网络数据集414.5.2实验结果与分析424.5.3四个网络六种算法分析434.6小结44结 论45致 谢47参 考 文 献48攻读学位期间的研究成果51.261 绪论1.1 选题背景在繁复的世界里，存在越来越多的问题，比如：为什么现在马路越宽，交通越拥堵？为什么有些地方金融动荡，从而引发地区甚至全球的金融危机？为什么现在各种搜索引擎都能几乎准确的进行用户推荐？这些一系列的问题看上去各不相同，但却存在一个共同的特征：每个问题都是一个复杂的系统，而这些复杂系统均可以用复杂网络进行表
8、示。在现代社会中，存在着各种各样的系统，包括：社交系统，互联网系统，电力系统，交通系统，新陈代谢系统以及食物链等等。这些系统中的实体抽象成网络中的节点(node)，实体之间的关系抽象成网络中的边（edge）。并且通过给复杂系统中的一些实体赋予不同的含义来更深入的刻画和描述复杂系统的特点。比如：名称，方向和权重等。在不同的网络中，节点和边有着不同的含义。例如：在社会合作网中，节点代表参与合作的人，边代表他们之间是否存在合作关系；在航空网络中，节点是机场，边是航线；在蛋白质相互作用网络中，节点代表不同的蛋白质，如果两个蛋白质能相互作用形成化学键，则存在连边。这些网络的存在激发了越来越多的学者研究的
9、兴趣，已经成为目前科研中最受关注的科学前沿学科之一。研究网络的过程中首要考虑的问题是对于网络演化过程的模拟Error! Reference source not found.。近年对网络演化的相关研究表明，真实网络的演化是由多种不同机制共同驱动的结果。比如，BA模型可以模拟出度的幂律分布，但是不能模拟聚类性。基于此，很多学者考虑将多种机制进行结合，以便可以更好的刻画真实网络的各种特征。Papadopolos等人Error! Reference source not found.将网络的相似性和流行性进行了结合，提出了一种数学模型来刻画网络的所有特征，还有学者Error! Reference s
10、ource not found.考虑了网络的空间结构，将地理位置和拓扑结构进行了结合。为了研究各种不同的复杂网络在结构上的共同点，需要一种数学工具对其进行刻画，这个工具在数学上称为图。借助图工具，复杂系统和复杂网络的研究都可以转化成对图的研究。图（Graph）是用点和线对各种实际网络进行抽象，这种抽象的好处是它可以使得我们通过现象看本质，通过对抽象的图进行研究从而得到实际网络的拓扑结构和特性Error! Reference source not found.。以“Konigsberg七桥问题Error! Reference source not found.（如图1.1）”为例，欧拉把被河流分
11、割的四块陆地抽象为节点，将连接两块陆地的桥看作连边，因此七桥问题被转换成四个节点，七条边是否存在每条边只经过一次且不存在回路的问题。由此，欧拉开创了一个新的数学中研究拓扑特性的分支拓扑学（Topology）。通过将实际网络抽象成图进行研究可以比较不同网络之间拓扑结构的异同点。实际网络可以抽象为节点集和边集组成的网络。给定网络,是由节点集在无向图中，如果两个节点之间存在连边，即，则称这两个节点互为邻居节点。如图2.2中，节点4和节点1,3,6邻接，则这三个节点两两互为邻居。一个节点所连接的其他节点的边数称为该节点的度，节点4有三个邻接点，则节点4的度为3。在二十世纪六十年代，美国哈佛大学的社会心
12、理学家Milgram最早提出了“小世界”的概念，他认为美国任意两个人之间的平均距离是6。也就是说，一个人平均只要通过5个中间人就可以与任何一个人发生联系。这就是著名的“六度分离”推断。此后，在1998年6月，D.Watts、S.StrogatzError! Reference source not found.在Nature上发表了题为“小世界”的动力学文章，1999年10月，Barabsi A.L和Albert RError! Reference source not found.在Science上发表了关于“随机网络中标度的涌现”文章。这两篇文章第一次提出了“小世界特性”和“无标度特性”，
13、这两大特性的提出，使得越来越多的学者对复杂网络产生了兴趣，并投入该研究领域。通过大量实验论证得到，具有不同拓扑结构的网络之间存在着一些共同特性。比如：大部分的复杂网络具有明显的社区结构（Community Structure），换言之，整个网络可以看作是由若干不同的社区构成。并且通过大量实验论证，一般社区内部的节点相比于社区外部的节点连接更加紧密，所属不同社区的节点连接稀疏。如图1.3所示： 从图中可以看出社区结构的这一特性为人们研究复杂网络提供了一种新的研究视角。而作为复杂网络研究中的一个重要的研究方向链路预测，被用到社交网络，酵母菌蛋白质网络等多个复杂网络中。链路预测的定义Error! R
14、eference source not found.是：通过认识和分析已知的网络的结构和信息对网络中尚未产生连边的节点之间存在连接的可能性进行预测。预测分为两种，第一种是对于未来链路的预测，即网络中的节点之间没有连边，在未来可能会存在连边。第二种是对未知链路的预测，即网络中存在连边但尚未被发现，复杂网络链路预测不仅在网络科学和信息科学理论上有重要的研究价值，而且在实际应用方面有着重要的意义，譬如：找出交通传输网络中的重要作用连边，指导蛋白质相互作用实验，进行社交和爱好推荐等。1.2 复杂网络研究现状简单来说，网络是由节点集合和连边集合组成。节点之间的连边表明了两者之间的关系，根据关系的不同含义
15、，刻画出了不同类型的复杂网络。如图1.4（a）所示，为朋友网络，通过对Facebook上500多万用户的好友列表信息进行分析，Golder等人Error! Reference source not found.发现了一个符合于著名的“150法则Error! Reference source not found.”（即一个人最多能维持的好友关系数量大约在150人左右）的现象，即在Facebook中，每个用户的平均好友数量大约为180，中值是144。后来，Ahn等人Error! Reference source not found.通过研究和实验又印证了该法则。又如，科学家合作网络，如图1.4（b
16、）所示，在之前的研究中，如果两位科学家之间最少合作过一篇文章，则科学家之间会存在一条连边。根据这个规则，可以对科学家网络用无向无权图进行刻画，无向表示科学家之间的连边没有方向，无权表示科学家之间的贡献没有强弱之分，为了进一步详细的刻画科学家合著的关系，通过给连边赋予权值，将网络刻画为，连边表示科学家之间合著文章的数目，连边的粗细代表权重大小，即科学家之间合作的次数。在上个世纪，对于网络的研究重点集中于刻画规则的网络。但是，随着大数据的发展，学者们开始关注大规模真实网络的建模和计算，经过研究得到随机网络和规则网络不能完整地刻画真实世界的网络，此后，D.Watts、S.Strogatz以及Barabsi A.L和Albert R分别提出了小世界网络模型和无标度网络模型。基于这两个模型，许多学者开始对于真实网络进行深入研究。Kumar等学者Error! Reference