基于结构特性的复杂网络链路预测研究

发布时间：2018-03-10 09:38

  本文选题：复杂网络　切入点：网络科学　出处：《浙江大学》2017年硕士论文　论文类型：学位论文

【摘要】：链路预测问题是数据挖掘和知识发现领域的一个开放性问题,吸引了来自不同研究团体的研究人员的关注。链路预测的研究对于理解现实世界的网络类系统的组成和演化具有深远的科学意义。另一方面,优秀的链路预测算法在不同的领域具有广泛的应用,例如生物网络中鉴定可能的蛋白质-蛋白质相互作用、在线社交网络中为用户推荐潜在的好友、在电子商务系统中提供个性化的推荐服务。本文中,我们从不同类型的网络深入细致地研究了链路预测问题。具体地,本文的主要内容和成果如下:1.我们从信息论的角度重新审视了网络结构在预测缺失链接中的作用,并提出了一个基于信息论的链路预测模型来同时利用多种结构特征。根据提出的模型,我们利用一种刻画节点的局部结构,即邻居集合,提出了一个叫做邻居集合信息(NSI)的预测指标。根据我们的实验结果,和其它的相似性指标相比,NSI指标在十二个真实网络中表现良好。以NSI指标为例,我们还给出了关于信息论模型的深入讨论。2.我们根据局部网络结构带来的互信息提出了一个适用于加权网络的加权互信息模型,它同时充分利用了结构和权重信息。我们在四个真实网络中进行了实证实验,结果表明相较于传统的无权指标和典型的加权指标,提出的模型能够提供更准确的预测。进一步地,我们从另外一个角度揭示了弱链接在链路预测中的影响。3.我们根据一种网络的局部结构,即节点的邻居集合,设计了一种权重预测方法,并在两种情况下评估了该方法的预测效果。在第一种情况下,一些连边连同它们的权重同时缺失;而在第二种情况下,所有的连边都存在只有部分连边的权重缺失。在六个真实网络的实证实验表明我们的方法在这两种情况下均能够给出准确的连边权重预测。
[Abstract]:Link prediction is an open problem in the field of data mining and knowledge discovery. It has attracted the attention of researchers from different research groups. The study of link prediction is of profound scientific significance in understanding the composition and evolution of network systems in the real world. On the other hand, Excellent link prediction algorithms are widely used in a variety of fields, such as identifying potential protein-protein interactions in biological networks, recommending potential friends to users in online social networks, In this paper, we study the problem of link prediction from different types of networks. The main contents and results of this paper are as follows: 1.We re-examine the role of network structure in predicting missing links from the perspective of information theory. A link prediction model based on information theory is proposed to simultaneously utilize various structural features. According to the proposed model, we use a local structure of nodes, that is, neighbor set, to describe the local structure of nodes. A prediction index called neighbor set Information (NSI) is proposed. According to our experimental results, compared with other similarity indexes, the NSI index performs well in twelve real networks. Take the NSI index as an example, We also give an in-depth discussion on the information theory model. 2. We propose a weighted mutual information model for weighted networks according to the mutual information brought by the local network structure. It makes full use of both structure and weight information. We have carried out empirical experiments in four real networks, and the results show that compared with the traditional unauthorized index and the typical weighted index, The proposed model can provide more accurate prediction. Further, we reveal the influence of weak link in link prediction from another angle. 3. According to the local structure of a network, that is, the neighbor set of nodes, A weight prediction method is designed and evaluated in two cases. In the first case, some connected edges are missing with their weights at the same time; in the second case, All the connected edges are only partially connected, and the experimental results of six real networks show that our method can predict the weight of connected edges accurately in both cases.
【学位授予单位】：浙江大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5
，

本文编号：1592776