《基于银行交易网络的链路预测》由会员分享，可在线阅读，更多相关《基于银行交易网络的链路预测（11页珍藏版）》请在金锄头文库上搜索。
1、1绪论1.1选题背景在繁复的世界里，存在越来越多的问题，比如:为什么现在马路越宽,交通越拥堵?为什么有些地方金融动荡，从而引发地区甚至全球的金融危机？为什么现在各种搜索引擎都能几乎准确的进行用户推荐？这些一系列的问题看上去各不相同，但却存在一个共同的特征:每个问题都是一个复杂的系统，而这些复杂系统均可以用复杂网络进行表示。在现代社会中，存在着各种各样的系统,包括:社交系统,互联网系统,电力系统，交通系统，新陈代谢系统以及食物链等等。这些系统中的实体抽象成网络中的节点（node),实体之间的关系抽象成网络中的边（ege）。并且通过给复杂系统中的一些实体赋予不同的含义来更深入的刻画和描述复杂系统的
2、特点。比如：名称,方向和权重等。在不同的网络中,节点和边有着不同的含义。例如:在社会合作网中，节点代表参与合作的人，边代表他们之间是否存在合作关系；在航空网络中,节点是机场，边是航线；在蛋白质相互作用网络中,节点代表不同的蛋白质,如果两个蛋白质能相互作用形成化学键,则存在连边。这些网络的存在激发了越来越多的学者研究的兴趣,已经成为目前科研中最受关注的科学前沿学科之一。研究网络的过程中首要考虑的问题是对于网络演化过程的模拟1。近年对网络演化的相关研究表明，真实网络的演化是由多种不同机制共同驱动的结果。比如,BA模型可以模拟出度的幂律分布，但是不能模拟聚类性。基于此,很多学者考虑将多种机制进行结合
3、,以便可以更好的刻画真实网络的各种特征。Papadpoo等人2将网络的相似性和流行性进行了结合,提出了一种数学模型来刻画网络的所有特征,还有学者3考虑了网络的空间结构,将地理位置和拓扑结构进行了结合。为了研究各种不同的复杂网络在结构上的共同点,需要一种数学工具对其进行刻画,这个工具在数学上称为图。借助图工具,复杂系统和复杂网络的研究都可以转化成对图的研究。图(Graph)是用点和线对各种实际网络进行抽象,这种抽象的好处是它可以使得我们通过现象看本质,通过对抽象的图进行研究从而得到实际网络的拓扑结构和特性4。以“Knigsberg七桥问题(如图1.1)”为例,欧拉把被河流分割的四块陆地抽象为节点
4、，将连接两块陆地的桥看作连边,因此七桥问题被转换成四个节点，七条边是否存在每条边只经过一次且不存在回路的问题。由此,欧拉开创了一个新的数学中研究拓扑特性的分支拓扑学（Toology)。通过将实际网络抽象成图进行研究可以比较不同网络之间拓扑结构的异同点。实际网络可以抽象为节点集和边集组成的网络。给定网络,是由节点集在无向图中，如果两个节点之间存在连边,即，则称这两个节点互为邻居节点。如图中，节点4和节点,，6邻接，则这三个节点两两互为邻居。一个节点所连接的其他节点的边数称为该节点的度,节点4有三个邻接点，则节点4的度为3。在二十世纪六十年代，美国哈佛大学的社会心理学家Milgram最早提出了“小
5、世界”的概念，他认为美国任意两个人之间的平均距离是6。也就是说,一个人平均只要通过5个中间人就可以与任何一个人发生联系。这就是著名的“六度分离”推断。此后,在1998年6月,、6在Nature上发表了题为“小世界”的动力学文章,199年10月，和lbertR在Scienc上发表了关于“随机网络中标度的涌现”文章。这两篇文章第一次提出了“小世界特性”和“无标度特性”，这两大特性的提出，使得越来越多的学者对复杂网络产生了兴趣，并投入该研究领域。通过大量实验论证得到,具有不同拓扑结构的网络之间存在着一些共同特性。比如:大部分的复杂网络具有明显的社区结构(ommnity Struture）,换言之，整
6、个网络可以看作是由若干不同的社区构成。并且通过大量实验论证,一般社区内部的节点相比于社区外部的节点连接更加紧密,所属不同社区的节点连接稀疏。如图13所示： 从图中可以看出社区结构的这一特性为人们研究复杂网络提供了一种新的研究视角。而作为复杂网络研究中的一个重要的研究方向链路预测，被用到社交网络，酵母菌蛋白质网络等多个复杂网络中。链路预测的定义8是：通过认识和分析已知的网络的结构和信息对网络中尚未产生连边的节点之间存在连接的可能性进行预测。预测分为两种，第一种是对于未来链路的预测，即网络中的节点之间没有连边，在未来可能会存在连边。第二种是对未知链路的预测，即网络中存在连边但尚未被发现,复杂网络链
7、路预测不仅在网络科学和信息科学理论上有重要的研究价值，而且在实际应用方面有着重要的意义，譬如:找出交通传输网络中的重要作用连边,指导蛋白质相互作用实验,进行社交和爱好推荐等。2复杂网络研究现状为什么命名为“网络结构的研究现状”。要针对自己研究的问题论述当前针对该问题的研究现状。或者从更广的角度论述复杂网络研究现状，最后落脚到自己的研究问题上。简单来说，网络是由节点集合和连边集合组成。节点之间的连边表明了两者之间的关系,根据关系的不同含义，刻画出了不同类型的复杂网络。如图1.4(a)所示,为朋友网络，通过对cebok上500多万用户的好友列表信息进行分析，Goer等人发现了一个符合于著名的“15
8、法则0”（即一个人最多能维持的好友关系数量大约在150人左右)的现象,即在cbok中,每个用户的平均好友数量大约为180,中值是14。后来,Ahn等人11通过研究和实验又印证了该法则。又如，科学家合作网络,如图1.(b）所示,在之前的研究中，如果两位科学家之间最少合作过一篇文章，则科学家之间会存在一条连边。根据这个规则,可以对科学家网络用无向无权图进行刻画，无向表示科学家之间的连边没有方向,无权表示科学家之间的贡献没有强弱之分，为了进一步详细的刻画科学家合著的关系，通过给连边赋予权值,将网络刻画为，连边表示科学家之间合著文章的数目，连边的粗细代表权重大小，即科学家之间合作的次数。在上个世纪，对
9、于网络的研究重点集中于刻画规则的网络。但是,随着大数据的发展，学者们开始关注大规模真实网络的建模和计算,经过研究得到随机网络和规则网络不能完整地刻画真实世界的网络，此后,、以及和Albrt R分别提出了小世界网络模型和无标度网络模型。基于这两个模型,许多学者开始对于真实网络进行深入研究。Kmar等学者12观察到在线社交网络的增长过程，随着网络规模的增加,这些网络的平均距离反而减小了。除了拥有短的平均距离,真实网络还具有较高的聚类性。在宏观层面上,一些真实网路还存在着层级组织关系,比如新陈代谢网络3等,这些网络中的节点分布于不同层。通过有规律的循环增长模式，网络形成了特殊的层次结构。例如,初始网
10、络有四个节点，节点之间两两连接，根据同构关系,将网络中的节点分为中心节点和边缘节点，然后将这个初始网络复制三份，每一份的边缘节点与原小网络的中心节点进行相连，再将网络进行迭代，然后所有初始网络的边缘节点与中心节点进行相连，迭代下去,便构成了一个具有明显层次结构,并且具有自相似性质的网络。通过研究发现,许多真实网路具有自相似14的特性，包括朋友网络，食物链网络，新陈代谢网络，万维网等。在中观层面，依据网络节点之间连接的紧密程度，将网络划分成不同大小的社区。在不同的网络中，其社区具有不同的特性,譬如,在银行交易网络中，社区代表了不同的交易群体,在科学家合作网络中,社区可能代表不同的科研团队,朋友网
11、络中，社区代表了不同的朋友圈等。社区划分的方法有很多种,有基于网络的模块度进行划分的，以模块度的划分为标准，模块度越大社区划分的效果越好5。但是,该方法对小团体的网络划分效果不是很好,基于此,许多学者提出了更详细的社区划分指标，如模块密度指标1，基于自然密度的模块化程度17，局部模块化程度8等。在划分社区的算法方面,通过某种相似性或者接近程度将节点聚集在一起的思想成为研究的主流。对于网络结构进行更局部的分析,网络可以看作由许多三元组构成，根据三元闭包特性可知,网络具有聚类特性。无向网络中的三元闭包结构可以看作三个点的完全图，也称为三阶派系,类似的，可以得到阶派系,通过研究它们的组织方式,对于网
12、络中重叠社区192的发现具有重要的意义。而且很多经典的链路预测算法,都是基于三角形结构的闭包提出的。从微观层面,一个节点的重要程度可以通过中心指标来进行刻画。如度,接近中心性，介数中心性等。其中,节点的度是最简单的用来刻画节点重要程度的指标21,度越大,节点越重要,但是度的大小只考虑了节点的局部信息，所以，仅仅用这一个指标来衡量节点的重要性,并不全面。在后来的研究中，学者们提出了PaeRk算法2和Leaera算法23来衡量节点的重要性。用k-壳分解法4刻画节点在网络中所处的位置。除了这些方法,通过考虑路径信息，利用接近中心性25计算距离的平均值等。还有一些方法考虑了节点自身的重要性,如用于网页
13、排名的LaerRank算法，累计排名算法6，还有基于网络的特征向量的中心性指标等。链路预测的研究进展这里需要指出既有研究工作的不足？这样才能突出自己研究工作的意义早期学者们主要通过马尔可夫链等传统机器学习技术进行链路预测的研究。最早是在202X年，Saruka7提出了一种新的概念,即使用马尔可夫链的概率连接预测和路径分析,并将马尔可夫链在HTP请求分析等四个应用中进行链路预测和路径分析。此后，在的文章8中将马尔可夫链应用到WW网络，对用户进行了在线导航；此后,ag等人29通过马尔可夫随机域，得到节点之间连边的概率特征。应用节点的属性建立概率模型进行预测的还有很多。譬如，OMdahai等人0提出
14、了一个条件概率模型的算法，通过网络的拓扑结构信息以及节点的属性进行预测。Li3基于节点属性信息定义了节点的相似性，从而进行链路预测。在无向无权的网络中,节点之间的连接方式只有两种，即存在连接或不存在连接,如果按照此方面作为判断依据,链路预测属于典型的二元分类问题。而在传统机器学习领域中,二分类问题可以使用朴素贝叶斯,决策树，支持向量机等进行建模处理。如果要建立一个有效的分类器,就要对特征向量进行选择,如网络的结构信息，节点的属性信息等。Popscl和ngar32通过文献的作者信息,词频统计等信息进行建模,应用回归方法对文献的引用关系进行预测；Scelat等3人通过有监督的分类模型对缺失的好友关
15、系进行预测;Li等人34通过用户的相关属性，提出了一种基于图形内核的学习方法,对用户的购书行为进行预测，他。lov等人35引入了语义分析,包括论文题目以及摘要信息等;除过以上这些,还有一些研究是基于最优问题对网络中的连边进行预测。前面的链路预测算法都是传统的基于机器学习和概率统计的方法,如马尔可夫链，朴素贝叶斯网络,其主要利用节点的属性以及节点与节点之间的强关联关系进行分析。在预测的过程中，虽然这些算法的精度较高，但是这些网络模型的参数和复杂度较高。而且通过研究显示,考虑节点的属性信息可以提高预测的效果,但是在实际中，获取这些信息的难度很大。即使获得这些信息,但是信息的可靠性和准确性不能得到保证。例如在微博网络中的用户,其信息往往含有很多虚假成分。因此,在有节点属性信息的情况下，如何鉴别哪些信息对网络的链路预测是有用的，哪些信息是没用的，这本身就是一个问题。由于节点属性信息真假难辨，剩下可用的信息只有网络的拓扑结构。随着研究的不断深入，基于网络结构的链路预测方法受到越来越多的关注。而且，基于拓扑结构进行链路预测对于相似的网络具有一定的普遍适用性。但是在加权网络中,网络中节点的权值在一定程度上反应了节点之间连接的紧密程度,如果说只是简单的考虑权重的话，它的预测准确度反而会降低363。只有将网络结构与其他信息进行结合才能更好的预测节点连接的准确度。在后续的研究中,Linbn-No
