基于局部结构的复杂网络链路预测算法研究

发布时间：2018-03-21 21:53

本文选题：复杂网络　切入点：链路预测　出处：《安徽大学》2017年硕士论文　论文类型：学位论文

【摘要】：真实世界中的很多研究领域都可以抽象为复杂网络,网络中的节点表示对象,边表示对象之间的关系。对复杂网络的建模机理和建模过程的深入研究,可以解释隐藏在自然界、社会界、生物界中的复杂系统的共同规律。研究复杂网络对探索网络形成及衍化机制有着重要的意义。其中,链路预测作为复杂网络的重要研究方向越来越受到研究者们的关注。链路预测是指如何通过已知的网络节点以及网络结构等信息预测网络中尚未连接的两个节点之间产生链接的可能性。随着链路预测研究问题的不断发展,很多预测算法被提出。其中,基于节点相似性的链路预测算法得到了广泛的研究。然而,在利用网络局部结构信息研究链路预测问题方面的研究还不够深入。网络局部结构对链路预测算法的性能有很大的影响,研究局部结构特征对提升链路预测算法的预测效果有重大的意义。针对该问题,本文对利用网络局部结构信息研究链路预测算法问题进行深入研究,主要内容包括以下三个方面:第一,网络中的三元闭包结构作为网络中最小局部结构,具有结构平衡和稳定的特征。通过计算出每个节点在网络中所占三元闭包的权重,并将该权重用于节点相似性指标中,提出了 TWCN、TWAA、TWRA三个相似性指标和具有调节参数的三个相似性指标:TWCN*、TWAA*、TWRA*。将新的相似性指标应用到预测算法中,提出了 PWNW算法和PWNW_α算法。采用CN算法、AA算法和RA算法作为对比算法。实验结果表明,PWNW-αα算法在预测精度方面比对比算法更具有优势。这说明利用三元闭包结构信息能够有效地提高预测算法的预测精度。通过分析实验结果,发现了一个现象:在社交网络中拥有较多三元闭包的节点,具有局部稳定性,不倾向于建立更多的新链接。相反,拥有较少三元闭包的节点,具有局部不稳定性,倾向于建立更多的新链接。这种现象也符合社会学中有关于新链接出现的现象。第二,根据节点拥有的三元闭包数目和节点度之间的关系可以计算节点的聚类系数,该信息体现了节点的聚集能力。聚类系数作为重要的节点拓扑属性不仅可以很好的体现局部结构的紧密性,同时对产生链接也会起到一定的作用。而传统的链路预测方法通常使用共同邻居数目或节点的度来衡量节点之间的相似性。然而,节点之间的关系不仅与邻居节点数目和度有关,与节点所处的局部结构有着密切的关系。基于这个观点,提出结合节点度和聚类系数的链路预测算法,简称NDCC算法。利用共同邻居节点的度和聚类系数计算被预测节点对之间的相似性。不仅充分利用网络局部结构信息,还能够体现出共同邻居节点之间存在的差异性。与几个常用的对比算法的相比,NDCC算法在预测精度上具有很好的优势。第三,上述两种预测算法都只考虑了被预测节点对之间的共同邻居节点,这种方式只能体现距目标节点两步以内的网络结构。其缺点是对网络中不具有共同邻居节点的节点对没有预测能力。而新链接的产生不会局限于这种邻居结构。针对该问题,利用社会学强关系理论来提升预测算法的预测能力。强关系理论:三步以内的关系都为强关系,强关系具有触发行为。这种行为可以为未连接的节点提供更多的相互连接的机会。另外,节点的度和聚类系数体现出节点之间连接紧密程度,对网络结构有着很大的影响。结合这两个方面,提出结合节点拓扑属性和强关系的链路预测算法,简称TPSR算法。该算法不仅考虑了节点的拓扑属性信息——节点的度和聚类系数,还结合了强关系对新链接出现的贡献。充分利用局部结构信息来刻画节点之间的相似性。与几个传统的算法相比,该算法具有更大的预测范围和更强的预测能力。
[Abstract]:Many research fields in the real world can be abstracted as a complex network, the nodes in the network represent objects, edges represent relationships between objects. The further study of modeling mechanism and modeling process of complex networks, can explain the hidden in the nature, the society, the common law of complex system in the field of Biology. The research on complex networks to explore the mechanism of network formation and evolution has important significance. The link prediction as an important research direction of complex networks has attracted more and more attention of researchers. The link prediction is how to known network nodes and network structure information network connection is not predicted between two nodes have links with continuous possibilities. Research on the issue of link prediction, many prediction algorithm is proposed. Based on the similarity of node link prediction algorithm has been widely studied. However, the research is not deep enough in the use of network prediction of local structure information of link. The local structure of network has great effect on the algorithm performance prediction of link, study on local structure feature is of great significance to enhance the prediction effect of link prediction algorithm. Aiming at this problem, this paper deeply researches the problem of using the network prediction algorithm the local structure information of the link, the main contents include the following three aspects: first, three yuan closure in the network as the network structure has the characteristics of minimal local structure, balance and stability. Through calculating the weight of three yuan for closure of each node in the network, and the weights for node similarity index the TWCN, TWAA, TWRA, three similarity index and adjust the parameters of the three similarity index: TWCN*, TWAA*, TWRA*., the new similarity index is used to The prediction algorithm, PWNW algorithm is proposed and PWNW_ alpha algorithm. Using CN algorithm, AA algorithm and RA algorithm for comparison algorithm. Experimental results show that the PWNW- alpha alpha algorithm in prediction accuracy than the algorithm has more advantages. This shows that the prediction accuracy by three yuan closure structure information can effectively improve the prediction algorithm. Through the analysis of experimental results, found a phenomenon: many nodes have three yuan closure in a social network, with local stability, do not tend to establish a new link more. Instead, nodes have less three yuan closure, with local instability, tend to build more new links. This phenomenon is consistent with the society in a new link phenomenon. Second, clustering coefficient calculation node can according to the relationship between the number of three yuan closure and node degree node has the information, the node can reflect the As the node clustering coefficient. The topology is important not only can well reflect the tightness of the local structure, at the same time will also play a role in generating links. While the traditional link prediction methods usually use common neighbor number or nodes to measure the degree of similarity between nodes. However, the relationship between the nodes not only related with the number of neighbor nodes and the degree, has a close relationship with the local structure of nodes. Based on this point of view, combining with the link node degree and clustering coefficient prediction algorithm, referred to as NDCC algorithm. Computing similarity between pairs of nodes are predicted using the common neighbor node degree and clustering coefficient. Not only make full use of local network structure information, it can reflect the differences between common neighbor nodes. Compared with the comparison of several commonly used algorithms, NDCC algorithm in prediction accuracy is very good Advantage. Third, the above two kinds of prediction algorithms only consider the predicted node common neighbors between pairs of nodes, this way can only reflect the network structure from the target node within step two. The shortcomings of the common node in the network neighbor node does not have to have predictive ability. And not limited to the new link neighborhood structure. Aiming at this problem, the prediction ability of strong sociological relation theory to improve prediction algorithm. The strong relationship between the theory of relationship within step three have strong ties, strong relationship with trigger behavior. This behavior can provide more opportunities for the connected node is not connected. In addition, the degree of the node and cluster the coefficient reflects the degree of close connections between nodes, has a great impact on the network structure. The combination of these two aspects, combined with the proposed link node topology property and the strong relationship between prediction algorithm, referred to as TPS R algorithm. This algorithm considers not only the topological properties of node degree and clustering coefficient of information nodes, combined with a strong relationship between the emergence of the new link contribution. Make full use of local structure information to describe the similarity between nodes. Compared with several traditional algorithms, the algorithm has ability to predict a greater range of prediction and more.

【学位授予单位】：安徽大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【参考文献】