Research On Link Prediction On Directed Graphs

With the development of the social of science and technology,the research of link prediction in complex networks has important realistic and theoretical research significance.It has become a hot research topic in recent years,widely used in a variety of areas,such as computer science,social science,complex system and so on.Link prediction uses the known topological structure of the network to predict the missing and future possible links.This prediction includes not only for unknown links(the actual link exists but has not been detected in our network)but also contains the future links(the link does not currently exist in the network,but should exist or may exist in the future).Link prediction research can not only promote the development of network science and information science theory,but also has great practical value,for example,guide the protein interaction experiments,online social recommendation,find link that plays a particularly important role in the traffic transport network etc.In the real world,most of the current link prediction algorithms are based on undirected networks,but now many social networks are directed.The social network is being integrated into people's daily life in recent years,Facebook,Twitter,Sina,micro-blog and other social networking sites emerge in an endless stream,become an important way of information sharing and dissemination of information.For Twitter like In social networks,such asTwitter,the users usualy have directed relations.Therefore,in addition to predicting the link connections,it is necessary to predict the direction of the links.Based on the characteristics of the directed networks,we combine topology structure and similarity between different types of relations to design more accurate and efficient link prediction algorithm.In this paper,the main research work and achievements are as follows:(1)We propose an algorithm for one-source link prediction in the directed networks based on sampling in the paper.By setting the appropriate size of the sampling,the error of similarity can be restricted to a given threshold range.Then,a sample set of paths is generated based on the set sampling size.Then,the similarity score of a given vertex is calculated based on the sampling path.For each section in each path,the corresponding value is added to the Katz index to obtain the approximate Katz index.Because only the information on the paths of the sampling set is required in computing the similarity score,the time cost for computation in this algorithm is greatly reduced.Experimental results on real networks show that our algorithm can achieve high accuracy prediction results.(2)We propose a link prediction algorithm for the directed networks based on genetic algorithm.We intend to encode the ordering of vertices as an individual representation of genetic algorithms.We first randomly generated a number of initial individuals,each individual represents a sorting scheme.After calculating the fitness of the sorting scheme,the algorithm uses roulette wheel to select a new round of the selected set of individuals,and then reuses the crossover and mutation operations to produce a new generation of groups.Repeat the above operation until convergence to the optimal solution.We intend to obtain the sorting points of the vertices through the genetic algorithm,and then determine the direction of the links between them by comparing the sorting of the two vertices.Experimental results on real networks show that our algorithm can find the optimal approximate ordering of vertices in directed networks to solve the direction prediction of links between vertices.Our algorithm can achieve high accuracy prediction results.(3)We propose an algorithm for vertex sorting of directed graphs based on spanning tree.We try to find a sorting method which can assign a rank for each node such that for any directed link the rank of the start node is smaller than that of the end node.To compute such rank for the nodes,we generate a corresponding undirected graph for the directed graph.For each vertex,we observe the spanning tree rooted at this node in undirected graph and the directed graph.Finally,the ranking value of the vertex is measured by the difference between the two spanning trees.Experimental results show that our algorithm can obtain optimized vertex sorting and achieve good quality predicting results.