基于局部路径算法去重复路径的链路预测

发布时间：2018-06-15 15:00

本文选题：复杂网络 + 链路预测　；参考：《西安电子科技大学》2015年硕士论文

【摘要】：现实生活中以及科研工作中运用到的各个单位以及他们之间的关系可以抽象化成一个网络,由于网络信息的复杂性,将这种网络称之为复杂网络。复杂网络就是复杂系统的结构,其中包括结构复杂性:就是网络系统具有丰富的结构他包括社区,基序,集聚性,生成规律性等。网络的结构可能会随着时间而变化的;节点复杂性,它包括复杂网络之间相互影响的复杂性以及网络分层结构的复杂性;网络进化,表现在节点或链接的产生与消失,这也表明了网络结构的时变性;连接多样性,他包括连接权重的多样以及方向的多样性;动力学复杂性以及多重复杂性融合等等。以上的种种特征表明,广义网络的复杂性可从多方面去讨论研究。复杂网络根据节点分布社区集聚特性,可分为单分网络和二分网络。复杂网络中所有节点之间都存在连接关系或是存在潜在的连接关系的网络称之为单分网络;然而二分网络是将所有的节点划分为两个集合,两个集合内部之间没有连接关系,集合之间存在连接关系或是存在可能的连接关系。网络的链路预测是指通过已有的节点连接关系去预测不存在连接关系的节点存在连接关系的可能性。这种预测既包含了对本身不存在且以后也不会存在链接的预测,同时也包含了对未来可能存在链接的预测。本文所做工作如下:首先了解了复杂网络以及网络链路预测的相关知识,通过生物种群网络之间的互惠和捕杀行为中找到二分网络在复杂网络中的具体实现,同时还发现在实际生活中存在着很多二分网络迹象。通过对二分网络特性的了解,找到关于二分网络特有的链路预测方法,不仅仅局限于现有的一般性的链路预测方法,这种链路预测方法就是基于局部路径的思想而得到的算法。首先观察到二分网络路径长度只存在奇数路径,因此从指数度量函数联想到删除偶数路径之后就可得到奇数路径,而这个奇数路径从数学的角度上来看,其公式就是三角函数中的双曲正弦函数;还包括冯诺依曼指标,也是同样进行奇数部分的保留来进行二分网络的链路预测。通过对二分网络的了解与预测,在进行路径矩阵分析发现,在路径矩阵中存在着重复路径的问题,且路径长度越长其重复的个数越多,造成不必要的资源浪费,且在一定程度上影响着网络真实路径信息的观察和了解,去重复路径问题就成为本文现阶段讨论的主要问题。通过对路径矩阵生成的形式观察,找出重复路径产生的原因,以及去重复路径的方法。在发现去除重复路径之后的预测结果能够良好的得到预想的实验结果。从二分网络中联想到在一般网络中是否实际也同样存在着重复路径,答案是肯定的。但是由于网络本身的性质因此它并不区分奇数路径和偶数路径。采用和二分网络同样的思路进行重复路径的去除,再对其进行实验分析。
[Abstract]:In the real life and the scientific research work each unit and the relations between them can be abstracted into a network, because of the complexity of network information, this network is called complex network. Complex network is the structure of complex system, which includes the complexity of structure: the network system has rich structure including community, motif, agglomeration, generating regularity and so on. The structure of the network may vary over time; the complexity of nodes, which includes the complexity of interactions between complex networks and the complexity of the hierarchical structure of networks; and the evolution of networks, as shown by the generation and disappearance of nodes or links, It also shows that the network structure is time-varying; the connection diversity, which includes the diversity of connection weights and directions, the dynamic complexity and the fusion of multiple complexity, etc. The above characteristics show that the complexity of generalized networks can be discussed from many aspects. The complex network can be divided into a single network and a binary network according to the characteristics of node distributed community agglomeration. A network in which all nodes in a complex network have a connection or a potential connection is called a single network; however, a binary network divides all nodes into two sets, and there is no connection between the two sets. There is a connection relationship or a possible join relationship between sets. The link prediction of the network refers to the possibility of predicting the existence of the connection relationship between the nodes that do not exist by the existing node connection relationship. This kind of prediction includes not only the prediction that the link itself does not exist and will not exist in the future, but also the prediction of the possible existence of the link in the future. The work of this paper is as follows: firstly, we understand the related knowledge of complex network and network link prediction, and find out the concrete realization of bipartite network in complex network through the reciprocity and killing behavior between biological population networks. At the same time also found in real life there are a lot of dichotomous network signs. Through the understanding of the characteristics of binary networks, we find out that the specific link prediction methods of binary networks are not limited to the existing general link prediction methods. This link prediction method is based on the idea of local path. First, it is observed that there are only odd paths in the path length of binary network, so the odd path can be obtained by associating exponential metric function with deleting even path, and this odd path is mathematically considered. The formula is the hyperbolic sinusoidal function in trigonometric function and the von Neumann index which is also reserved for odd parts to predict the link of bipartite network. Through the understanding and prediction of the binary network, the path matrix analysis shows that there is the problem of repeated paths in the path matrix, and the longer the path length, the more the number of repeat, resulting in unnecessary waste of resources. To some extent, it affects the observation and understanding of the real path information of the network. By observing the form of path matrix generation, we find out the cause of duplicate path and the method of de-repeating path. The predicted results can get the expected experimental results well after the repetitive paths are found out. The answer is yes. However, because of the nature of the network itself, it does not distinguish odd path from even path. The same idea as the binary network is used to remove the repetitive path, and then the experimental analysis is carried out.
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5

【参考文献】