【作者】 王鑫；

【导师】 张燕平； 陈喜；

【作者基本信息】 安徽大学 ， 计算机应用技术， 2018， 硕士

【摘要】 现实世界中,存在着许许多多的复杂系统,如交通、生物以及信息系统等等,这些复杂系统可以用网络来进行描述。系统中的个体可以用网络中的节点来表示,而个体之间的交互关系或者联系用连边来表示。复杂网络会随着时间进行演化,同样其中所蕴含的信息也会不断变化。而网络中的连边作为个体之间交互信息的载体,对其进行挖掘与研究显得非常必要。链路预测就是一种挖掘网络连边信息的重要手段,它不仅可以挖掘出网络中未知的隐含信息,也可以发现一些缺失信息,是对网络不完整性进行补全的一种手段。随着链路预测问题研究的不断深入,多种类型的算法被提出。其中,基于相似性的链路预测方法受到越来越多的关注。该方法的一个关键问题就是如何来定义节点之间的相似性。通常可以将拓扑网络中的各种信息融合在一起来定义节点之间的相似性,其中最重要的信息是节点属性和网络结构。使用节点属性信息有较高的预测精度,但是收集这些信息是不易的,即使可以获得节点属性信息,从这些复杂的信息中鉴别出哪些信息对预测有用处也是较为困难的事。相对的,网络结构信息获取简单且容易筛选。并且,基于网络结构的链路预测方法具有普遍适用性。然而,现阶段对基于网络结构的链路预测算法研究还不够深入,对哪种网络结构对连边有影响的挖掘还不充分。基于此,本文利用网络结构定义了 2种计算节点相似性的方法,提出2种新的链路预测算法。主要工作与贡献如下:1.在实际网络中,由于网络局部拓扑结构是不同的并且不同的节点自身属性也具有差异性,每个节点所代表的影响力是不同的,相应的对连边产生的贡献度也是不同的。还有共同邻居节点之间连接的紧密度一定程度上反映了节点自身所在的局部子网络的紧密程度,这也可能影响子网络中节点之间的连边。因此,本文定义了共同邻居节点的贡献度以及共同邻居之间的链接紧密度,将两者结合提出一种新的链路预测算法,简称LDNC(Link Density and Node Contribution)算法。将该算法在9个真实数据集上进行了实验,用AUC和Precision评价指标和五个算法进行了对比,结果表明LDNC算法是十分有效的。2.由于每个节点或每条路径在网络中所处位置的不同,它们对于网络其他部分的影响也是各不相同的。体现在链路预测中,就是不同的节点和路径对网络中的节点对是否产生连边影响力是不同的。这个影响力我们用节点和路径的权重来表示。基于此,本文给出了新的计算节点权重和路径权重的方法,并将两者结合在一起,提出一种新的链路预测算法,简称CPNW(combining paths weight and nodes weight)算法。将该算法在9个真实数据集上进行了实验,得出相似性分数矩阵,用AUC和Precision评价指标和6个算法进行对比,结果显示CPNW算法准确度较高,证明该算法有效。更多还原

【Abstract】 In real world,many complex systems such as traffic,biological and information system,can be described by network.The individual in the system can be represented by node and the interaction or connection between individuals is represented by edge(link).Complex networks will evolve over time,and its information also change over time.It is very necessary to dig and research edge in network that acts as the carrier of the interactive information among the individuals.Link prediction is an important method of mining edge in network,and it can find some hidden and missing information and it is a kind of method to complete the network.With the in-depth research,many types of algorithms of link prediction have been proposed.Among them,methods based on node similarity is getting more and more attention.In general,the various information in the topology network is mixed together to define the similarity between the nodes,including nodes attributes and network structure.The external information,such as nodes attributes,can obtain a good prediction effect,but in many cases it is extremely difficult to obtain such information.Even though you can obtain nodes attributes information,it is also difficult to distinguish which information is useful to the prediction.In contrast,network structure information is simple and easy to screen.Moreover,the link prediction method based on network structure is universally applicable to the network with similar structure.However,research of link prediction algorithm based on network structure doesn’t go far enough at this stage and it’s not sufficient to mine which network structure has an impact on link.Based on this,we use network structure to define two methods that can compute similarity between nodes,and propose two new link prediction algorithms in this thesis.The main works and contributions of this thesis as listed as follow:1.In real network,because local network topology and properties of nodes are different,and the influence of each node is different,so the corresponding contribution to the link is also different.The link density between common neighbor nodes reflects the tightness of the local sub-network in which nodes are located.It may have an impact on link of nodes in the sub-network.Therefore,this thesis defines node contribution of and link density of common neighbor nodes,and proposes a new link prediction algorithm(LDNC for short)by combining two.Experiments are carried out on 9 real datasets.AUC and Precision are used in comparison with several algorithms,and the results show that the LDNC is very effective.2.Because the location of each node and path in network is different in network,they have different effects on the other parts of the network.In the link prediction problem,it’s that different nodes and paths have different effects on link in network.This influence is represented by the weight of node and path.Based on this,this thesis gives a new method to calculate the weight of node and path,and proposes a new link prediction algorithm(CPNW for short)by combining two.Experiments are carried out on 9 real datasets.AUC and Precision are used in comparison with six Classical algorithms.The result show that the accuracy of the CPNW is high,which proves that the algorithm is effective.更多还原