Font Size: a A A

Link Prediction Methods Based On Topological Properties And Path

Posted on:2018-09-01Degree:MasterType:Thesis
Country:ChinaCandidate:Z YangFull Text:PDF
GTID:2310330533457862Subject:computer science and Technology
Abstract/Summary:PDF Full Text Request
We are in a world of many complex systems,such as our biosphere,our society and so on.These complex systems permeating in our life can be abstracted as complex networks.In these networks,nodes represent objects in the real world and the edges represent the relationship between objects.The network contains a large amount of information,which will be changing with the evolution of the network.Network evolution of complex networks has been a hotspot nowadays,in which link prediction is one of the key problems.Link prediction is a mining of the hidden information in the network,and to predict the direction of the evolution of the network.Specifically,by using a variety of information in the network,it is to search the missing edges and predict the potential connected edges in a network.The traditional method of processing link prediction is to classify the nodes edges according to their attributes by the methods of machine learning.In the era of data explosion,the size of the network becomes larger and larger,and the methods based on machine learning have not been able to provide good prediction accuracy.We therefore turn our attention to the structural information of the network.At present,the link prediction algorithm based on similarity is a high degree of attention,and these algorithms have better prediction results and relatively low time complexity.Therefore,this thesis focuses on how to improve the results of link prediction on the basis of similarity algorithm.Network topology is an important structure in the network and a key factor of the network properties.The way to evaluate network topology is network clustering coefficient and community structures.In the thesis,first,the clustering coefficient is applied to the similarity index to improve the accuracy of the prediction results.Generally,in the network with high clustering coefficient,different similarity index can obtain satisfactory results,especially CN index,AA index and RA index.Therefore,we combined the clustering coefficient of nodes with the similarity index based on local structure,and carried out experiments on several networks.Next,community structure is another important topological structure of the network.The internal nodes in a community structure are closely linked,while nodes between different community structures are linked relatively sparsely.So the characteristics of community structure and similarity between nodes has natural connection.Hence,the characteristics are linked to similar associations in the index.We defined the degree of closeness between nodes,proposed a class of similarity index based on the density of nodes,carried out experiments on a number of real networks,and verified the effectiveness of the algorithm based on community structure.Finally,the allocation of resources similarity algorithm is a very good performance prediction algorithm.We extended it to the path of higher order and put forward a new resource allocation algorithm based on path,and verified its effectiveness.Through a large number of experiments of the proposed algorithm.The results show that they can enhance the accuracy of link prediction results in a certain extent,further study is of great significance to the future network evolution mechanism.
Keywords/Search Tags:complex networks, link prediction, similarity, clustering coefficient, community structure, resources allocation, high order path
PDF Full Text Request
Related items