摘要链路预测作为复杂网络的重要研究方向之一，它是将目前已存在的连边与未来可能存在或者存在但未被发觉的连边联系起来的重要桥梁之一，简而言之，它是解决了复杂网络的根本问题——缺失信息的还原和预测，在理论和应用层面上都有重要的意义和价值。理论上，链路预测是通过网络中已知节点的信息，来预测网络中尚未产生连边的节点之间存在连边的概率。如果能够将链路预测的算法进行改进，并且将其与网络结构特性相结合，这样对于网络演化过程的模拟有很重要的价值，在应用方面，如果有比较优秀的链路预测算法，可以将预测算法应用到各种网络关系中，如蛋白质网络，可以大大降低试验成本。传统网络的链路预测，其研究对象都是基于静态网络，获得网络的拓扑结构，然后利用其节点的各种属性进行相似度预测。这对于分析理解网络的宏观发展具有很大的帮助。但是，对于动态演变的网络而言，传统意义上的网络链路预测算法，其效果并不明显。目前主流的链路预测算法主要有两类，一类是基于马尔科夫链或者机器学习，这类算法主要考虑网络中节点的属性，在预测效果方面虽然能够达到较好的预测精度，但是因为其计算过程中涉及很多参数的约束而受到限制；另一类基于网络结构的最大似然估计算法具有很高的计算复杂度，不适用于数据量较大的复杂网络。由此可见，传统的链路预测主要是针对静态网络，而不适用于动态网络的分析。而且目前已有的链路预测算法其复杂度较高。而本论文以银行交易形成的复杂网络为研究对象，由于交易网络会随着时间发生变化，节点的连接属性，连接情况都会发生变化，原来连接的节点，会随着时间，不发生连接。之前不连接的节点会在后期的网络演变中具有很高的邻居节点。因此动态网络的预测算法不仅需要考虑网络的本身结构属性，还要考虑网络动态演变的趋势。根据以上情况，本文试图寻找一种适用于动态.I网络的链路预测算法。为此，本文主要完成的工作如下所示：第一，对复杂网络和链路预测的基本概念及研究现状进行了梳理，对已有的基于不同特性所提出的链路预测算法与评价指标进行了分析。第二，根据复杂网络分析方法对银行客户的交易数据进行了研究，定义并构建了无向有权的客户交易网络模型。在构建交易网络结构的基础上，本论文研究了不同时间戳的交易网络的拓扑结构特性，包括度分布，聚类系数，平均路径长度。通过对于这些特性进行大量的实验分析，验证了客户交易网络具有复杂网络的小世界和无标度特性。第三，由于交易网络的动态特性，针对目前已有的研究中对于动态网络链路预测算法的欠缺，在分析客户交易网络结构的基础之上，设计并实现了一种适用于交易网络的动态预测算法。算法主要包括已连接的节点和未连接节点之间的预测。结合交易网络的特性，提出了网络节点的连接强弱性与节点的连接重要性概念，进一步的对我们提出的原始算法进行了改进，基于实际数据集，分别对本文所提出的算法与改进的算法进行了实验与分析。第四，将本文提出的动态预测算法，改进的链路预测算法以及随机算法，用于某商业银行的交易数据中，预测的准确度大概在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商业银行网络.II结构分析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.3INSAA算法描述...
VIP
