基于信息熵的复杂网络链路预测算法研究

发布时间：2018-04-02 05:08

本文选题：复杂网络　切入点：链路预测　出处：《南京理工大学》2017年硕士论文

【摘要】：链路预测(Link Prediction)问题是数据挖掘领域的研究方向之一,因其有重要的理论研究意义和广泛的应用价值而受到各个领域的关注。链路预测指如何根据已知网络的节点属性和网络拓扑等信息,预测网络节点对之间缺失的连边和未来可能产生的连边。近年来,随着复杂网络理论体系的不断发展,基于网络结构的链路预测算法渐渐成为研究焦点。本文的主要内容如下:首先,介绍了复杂网络的基础知识,包括简单网络、加权网络和多层网络的统计特征和演化模型;其次,介绍了链路预测问题的研究背景、研究现状以及现有的典型链路预测算法的核心思想;然后,介绍了信息熵的基本概念和性质,推导出复杂网络路径熵的表达式,并将路径熵用于节点相似性的度量,提出了一种基于网络局部拓扑结构的路径熵(Path Entropy,PE)相似性指标。实验结果表明,该指标比经典的准局部和局部指标有更好的预测性能;接着,将路径熵和路径的权重结合,提出了一种适用于加权网络的链路预测指标,即加权路径熵指标(Weighted Path Entropy index,WPE)。实验结果表明,该指标比现有的加权指标有更好的预测性能。进一步考虑到现实复杂网络中连边类型的异质性和网络结构的层次性,结合路径熵的概念,提出了一种适用于多层复杂网络的链路预测方案;最后,针对大规模复杂网络链路预测的难点,提出了基于共同邻居下界的并行计算预测模型,着重分析和预测网络"热点区域"中的连边。同时,提出了自预测性指标以度量链路预测算法的性能和评估网络的可预测性。
[Abstract]:Link prediction (Link prediction) is one of the research directions in the field of data mining. It has been paid attention to by many fields because of its important theoretical research significance and wide application value.Link prediction refers to how to predict the missing links between network nodes and the possible future connected edges based on the known network node properties and network topology information.In recent years, with the development of complex network theory system, link prediction algorithm based on network structure has gradually become the focus of research.The main contents of this paper are as follows: firstly, the basic knowledge of complex network is introduced, including the statistical characteristics and evolution model of simple network, weighted network and multilayer network, secondly, the research background of link prediction problem is introduced.Then, the basic concepts and properties of information entropy are introduced, the expression of path entropy of complex network is derived, and the path entropy is used to measure the similarity of nodes.A path entropy path EntropyPe similarity index based on local network topology is proposed.The experimental results show that this index has better prediction performance than the classical quasi-local and local indexes, and then a link prediction index suitable for weighted network is proposed by combining path entropy with path weight.That is weighted Path Entropy index.The experimental results show that this index has better prediction performance than the existing weighted index.Considering the heterogeneity of the connected edge type and the hierarchy of the network structure in the real complex network, a link prediction scheme suitable for the multilayer complex network is proposed by combining the concept of path entropy.Aiming at the difficulties of link prediction in large-scale and complex networks, a parallel computing prediction model based on common neighbor lower bound is proposed, with emphasis on the analysis and prediction of the connected edges in the "hot spot region" of the network.At the same time, a self-predictive index is proposed to measure the performance of the link prediction algorithm and to evaluate the predictability of the network.
【学位授予单位】：南京理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【参考文献】