基于网络拓扑性质和路径的链路预测算法

发布时间：2018-06-02 19:10

本文选题：复杂网络 + 链路预测　；参考：《兰州大学》2017年硕士论文

【摘要】：我们处在一个由许许多多的复杂系统所构成的世界中,如我们所在的生物圈、我们所在的社会等等,而渗透在我们生活中的这些复杂系统都可以被抽象为复杂网络,在这个网络中,节点表示真实世界中的对象,边表示的是它们之间的关系。网络中蕴含着大量的信息,而且这些信息会随着网络的不断演化而变化,所以在当前复杂网络的研究中网络的演化是一个热点,而在网络演化的研究中有一个基本的问题就是网络的链路预测。链路预测是挖掘网络中的隐含信息和预测网络将要演化的方向。具体的说,就是利用网络中的各种信息,对网络中丢失的连边进行寻找和对目前不存在的连边进行预测。处理链路预测的传统方法是利用机器学习对网络中的节点和边按照它们的属性进行分类。随着我们进入了一个数据爆发的时代,网络的规模越来越大,基于机器学习的方法已经不能够提供良好的预测准确性。所以我们将目光转向了利用网络的结构信息来进行预测。目前基于相似性的链路预测算法是一种受关注度较高的方向,这种算法往往能带给我们较好的预测结果以及相对低的时间复杂度。因此本文主要关注在相似性算法的基础上如何对链路预测的结果进行提升。网络的拓扑结构是网络中所包含的重要结构,是网络性质的决定因素。评价网络拓扑结构的方式有网路聚集系数和社团结构。本文首先将聚集系数应用到相似性指标中,来提高预测结果的准确性。一般来说,聚集系数较高的网络,各种相似性指标均可以获得较为理想的结果,尤其是CN指标,AA指标和RA指标。所以我们将节点的聚集系数结合到基于局部结构的相似性指标中,并在多个网络上进行实验,获得了良好的预测结果。其次,社团结构是网络中另一个重要的拓扑结构,社团结构内部节点之间联系紧密,不同社团之间节点的联系相对稀疏,所以社团结构的这种特性与节点之间的相似性有天然的联系。因此,我们将社团的这种特性结合到相似性指标中,先定义节点之间的紧密程度,随后提出基于节点间紧密度的一类相似性指标,并在多个真实网络上进行实验,验证了基于社团结构的算法的有效性。最后,资源分配的相似性算法是一个预测性能非常好的算法,于是我们它扩展到高阶的路径上,提出新的基于路径的资源分配算法,并验证了它的有效性。本文通过对所提出的算法进行大量实验,结果表明它们都能在一定程度上提升链路预测结果的准确性,对未来进行网路演化机制的深入研究具有重要意义。
[Abstract]:We are in a world of many, many complex systems, such as the biosphere we live in, the society we live in, and the complex systems that permeate our lives can be abstracted into complex networks. In this network, nodes represent real-world objects and edges represent their relationships. There are a lot of information in the network, and these information will change with the evolution of the network, so the evolution of the network is a hot spot in the current research of complex network. In the research of network evolution, a basic problem is network link prediction. Link prediction is the direction of mining hidden information and predicting the evolution of network. To be specific, it is to use all kinds of information in the network to search for the missing connected edges in the network and to predict the non-existent connected edges. The traditional method to deal with link prediction is to classify nodes and edges according to their attributes by using machine learning. As we enter an era of data explosion, the scale of the network is becoming larger and larger, and the machine learning method can not provide good prediction accuracy. So we turn our eyes to the use of network structure information to predict. At present, the link prediction algorithm based on similarity is a kind of high attention direction, which can bring us better prediction results and relatively low time complexity. Therefore, this paper focuses on how to improve the results of link prediction based on similarity algorithm. The topological structure of the network is an important structure contained in the network, and it is the decisive factor of the nature of the network. The network topology is evaluated by network aggregation coefficient and community structure. In this paper, the aggregation coefficient is first applied to the similarity index to improve the accuracy of the prediction results. In general, the network with higher aggregation coefficient can obtain satisfactory results, especially CN index AA index and RA index. So we combine the clustering coefficient of nodes into the similarity index based on local structure and experiment on multiple networks and obtain good prediction results. Secondly, the community structure is another important topology in the network. Therefore, this characteristic of community structure has a natural relationship with the similarity between nodes. Therefore, we combine this characteristic of community into similarity index, define the degree of closeness between nodes, then propose a kind of similarity index based on tightness of nodes, and experiment on many real networks. The validity of the algorithm based on community structure is verified. Finally, the similarity algorithm of resource allocation is a very good predictor, so we extend it to higher-order paths, propose a new path-based resource allocation algorithm, and verify its effectiveness. Through a large number of experiments on the proposed algorithms, the results show that they can improve the accuracy of the link prediction results to a certain extent, and it is of great significance to further study the evolution mechanism of the network in the future.
【学位授予单位】：兰州大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【相似文献】