Link Prediction Based On Link Dependency

Along with the development of modern technology, complex network plays more andmore important role in social life. Complex network is a large mesh structure makes up by bya large number of individuals and links happened between various relations. Internet, goodstransportation network, telephone network, the mail network that we pay attention every day,students network and network to make friends, even biological networks and protein networkwhich you invisible to the naked eye can’t see, these various kinds of network are incomplicated network under definition. So the research and analysis of complicated networkare important to development science and technology and improve people’s quality of life.Link prediction as data mining`s important research direction in complicated networkhad been paid attention by a large number of subjects from the experts and scholars. Linkprediction is used to predict which links will happen at next time in the complex network,which includes have never been links and the link appeared again and again. Many expertsand scholars in this field put forward a lot of good algorithm and different perspectives, suchas local similarity based on the Common Neighbors algorithm, Salton algorithm, Adamic-Adar algorithms; Based on the path of similarity LP algorithm, Katz algorithm, etc. Thesealgorithms have a common characteristic that the algorithm all based on the degree ofsimilarity between nodes. The more high similarity between two nodes the bigger probabilitythey link.In this paper the author reference a lot of link forecast analysis related articles, fullystudied the network of the complicated structure characteristics and the related content aredeeply analyzed. Based on the works the paper put forward on the concept of link dependency,put a new angle to link forecast and analysis.This paper first introduces the data mining and the complex network backgroundknowledge, and then introduced the current research status of link prediction algorithm, andgives the advantages and disadvantages of these studies, and finally put forward the conceptof link dependency. It transferred the focus from relationship between each nodes to therelationship between each links, and then improved the link dependency algorithm.The work of this paper content two aspects:(1) put forward link dependency, get LPLD algorithm. The traditional link predictionmainly depends on the similarity of the node. However complicated network is composed bya large number of nodes and links, simple analysis on node will certainly lose another aspectsof the information. This paper defines the link dependency this new concept. Linkdependency is the degree of one link interdependence with other links. According to this concept, this paper puts forward a LPLD algorithm to link prediction.The algorithm countsthe link dependency degree of each link in the whole network, and then analysis thedependency matrix, finally concluded that predicted link. The contrast test proved the LPLDalgorithm is suit for link prediction, which suggests that LPLD algorithm can effectivelypredict the link, in a large number of real data sets, such as dolphins network data, companyE-mail data and coauthor network data.(2) Improving link dependency and puts forward LPILD algorithm.The link dependency is based on two adjacent links.However, experiment analysis that two links which are not adjacent have similarityrelationship. Although the relationship between non-adjacent links is not important thanadjacent links, it is not allow to ignore. So this paper puts forward the improved linkdependency. Improved link dependency include the non-adjacent links and the adjacent links.Based on this improvement, we put forward LPILD algorithm, And make some comparisonwith other algorithm on a large number of real data set.Experimental results show that theLPILD algorithm`s prediction accuracy is higher than other algorithm and LPLD algorithm,can be effectively used in link prediction.