Research On Link Prediction Methods Based On Motifs In Directed Networks

Complex network is an effective tool for modeling and analyzing complex systems,which plays an important role in understanding complex behaviors.Link prediction is one of the hotspots in complex networks,which mainly solves the problem of whether there are links or not.Link prediction can give us better understanding of the structural characteristics and evolution rules of complex networks,and also has a wide range of application scenarios in all walks of life.At present,scholars have studied the formation mechanism of links from different perspectives and levels,and proposed a lot of link prediction methods.However,there are still some limitations of link prediction techniques that need to be solved:(1)there are many directed networks in the real world while current research for link prediction mainly focuses on undirected networks.This leads to the lack of prediction algorithms fitting properties of directed networks.(2)Network motifs are important topological structures in complex networks.How to describe the similarity between nodes from the perspective of network motifs and how to measure the roles of different motifs in similarity calculation need to be further studied.In order to solve the above problems,the research is supported by the project of National Natural Science Foundation of China,focusing on the research of motif-based methods for directed link prediction.In this paper,motifs are used to study the link prediction problem in directed networks from three aspects: triadic motifs,quad motifs and hybrid motifs.The main research contents and innovations are as follows:1.A new method based on triad motifs for directed link prediction is proposed.The proposed metric compare the difference of triad structures between undirected and directed networks and use potential theory to filter the triad patterns.By statistics of triad closeness in various networks,the new method calculates similarity between nodes using the triad closeness index of a network as weight for different triad patterns.Experiments on nine real networks show that accuracy of proposed method is better than benchmark methods.2.We propose a quad motifs index for directed link prediction.In the fact of many quad sub-graphs,reasonable restrict conditions are proposed to simplify the situation.Z-score method is used to further analyze the importance of different quad sub-graphs.Two important motifs are chosen among 199 sub-graphs to calculate similarity.Local information of motifs is also taken into consideration to improve the accuracy.Experiments on real networks show that the index we proposed can improve prediction accuracy,compared with seven well-known measures.3.A hybrid motifs method is proposed for directed link prediction.We discuss the relationship between particular quad motifs and triadic motifs in similarity calculation.Then,the relationship between motif method and existing method for undirected network is discussed.Finally,the concept of motifs connectivity is introduced and a hybrid motifs index is proposed.Experiments on nine real data sets show that hybrid method performs better than classical methods,triadic and quad motifs methods.