Structure Analysis And Link Prediction In Complex Networks

Complex network analysis is a significant means of studying complex systems.A mass of researches on topological structures of complex networks reveal out a lot of interesting characters emerging in real-world systems.These characters,which usually determine the systems' functions,affect many theoretical researches related to complex networks.Therein,link prediction,an important research direction,is rich of meaning and value in both theoretical and application aspects.From the theoretical aspect,link prediction research and network structure analysis promote each other,that is significative to reveal out network evolution mechanisms.From the application aspect,link prediction algorithms can be directly applied to predict future links in online social networks.It also has a particular close connection to recommender systems which is another significant technology of information filtering.Focusing on complex networks,this thesis firstly studied network structures from the macro-level,meso-level and micro-level respectively;then applied these results to get more accurate predictions of missing links;and further applied link prediction algorithms to recommender systems.By employing the common theory and methodology in both computer science and statistical physics,this study revealed out some interesting and effective features of network structures,discussed the differences between link prediction and recommender system,and at last extracted the “information backbone” of networks.The problems studied by this thesis are briefly depicted as follows:(1)At the macro-level,we examined the effects of different mechanisms to realworld networks.Focusing on the problem of evaluating network models,we put forward a new method based on likelihood analysis.This method does not need to examine any structural features,which breaks through the flaw of the traditional method.Moreover,it is the first model which is utilized to quantify the contributions of multiple mechanisms as networks evolve.(2)At the meso-level,we utilized a new method to find and verify a significant structure of directed networks.In specific,we introduced Potential Theory and combined it with Clustering and Homophily.Then we obtained a significant structure named Bifan which meets all these rules,and at last verified its effectiveness through experiments on dozens of real world networks.Thus a new method was raised to mine important structures motivated by studying this problem,that is “analyzing structure features ?inferring promising structures ? verification through experiments”.(3)At the micro-level,we focused on the centrality indices of nodes.Through studying the centrality of employees in their social networks,we employed the logistic regression model to analyze their career movements.Degree and Coreness are both found to be related indicators.In a further step,we first found degree,H-index and coreness of nodes are closely correlated with each other.In specific,by applying an operator ? to the degrees of nodes' neighbors,we can get nodes' H-index values.Then through iteratively applying ? to H-index values of nodes' neighbors,we can get nodes' coreness values in a finite number of steps.During the iterative procedure,each value can be considered as a good centrality index of nodes.(4)By analyzing the results of network structures,we aimed to promote link prediction algorithms.From the micro-level,we harnessed the differences between nodes' clustering performances,and then proposed a new algorithm based on na¨?ve bayes theory.It not only improves the precisions by 5.7%,but also helps to find some odd pairs of nodes which are disjoint but have many common neighbors.From the meso-level,we are motivated by the Most Reliable Route Problem in communication networks,and then proposed an algorithm to predict missing links in weighted networks.The experimental results on real-world networks show that it is overall the best and most stable one.(5)We applied link prediction model to study network evolution and recommender systems respectively.In the former application,we discussed the fault of link prediction model,and as well the advantage of likelihood-based model.In the latter case,we found the activities of customers and the popularity of objects can directly affect the recommendation performance,and the recommendation accuracy can be improved if the dissimilar customers of each target customer can be well treated.Thus,we guess that some information is not only redundant but also misleading to recommender systems.Based on this,we examined the effect to recommendation by removing some links according to structure aware strategy and time aware strategy,and then proposed an innovative concept named information backbone.In the experiments,the information backbone only needs28% links.Furthermore,we proposed a temporal recommender system motivated by this idea,which can update the scores of objects automatically without repeated calculations.