Nonbacktracking Random Walks And Local Bayesian-based Link Prediction On Complex Networks

Complex network as a theoretical framework has attracted much attention because many real systems can be represented by it.As the most basic kind of dynamics,studying on the random walk on complex networks has promoted the development of probability theory,computational science,statistical physics and other disciplines.Also,it has been applied to many practical problems,such as routing strategies on computer networks,the detection of meso-scale structures such as the detections of community structures and core-peripheral structures,link prediction,opinion dynamics and other issues.At the same time,the problem of link prediction based on complex networks has also become a hot issue in the fields of biology,computer science,and social sciences.For example,in bioinformatics,it has been used to predict "protein-protein" interactions(PPI).In security-related applications,it can be used to identify hidden groups of terrorists and criminals.Furthermore,link prediction algorithms can help to analyze the development of social networks.This dissertation mainly focuses on:(1)Based on the general random walk,a nonbacktracking random walk on a complex network is studied through a second-order Markov model,and the precise expression of the steady-state occupation probability of a node and the calculation formula for the average first arrival time are derived.Compared with the general random walk results,it is found that the steady-state occupation probability of the nodes for the two random walk models is exactly the same,but the mean first-passage time of the nonbacktracking random walk is shorter than the mean first-passage time of the general random walk.This shows that nonbacktracking random walk is more efficient in network search,routing and other issues,which means that it may be of great help to solve the problem of link prediction.(2)We also propose an extended local na?ve Bayes(ELNB)model to implement link prediction in complex networks.Firstly,an extended clustering coefficient(ECC)is defined to represent the posterior connection probability in ELNB model,which is composed of the link clustering coefficient(LCC)and node clustering coefficient(NCC).This method not only overcomes the shortcoming of the common neighbor similarity index each common neighbor of two nodes which contribute equally to the connection likelihood,but also guarantees that the contributions of a common neighbor on the connection likelihood of different pair nodes in its neighbor set which are different.Through the indepth analysis,it is found that the link clustering coefficient(LCC)gives rise to a positive effect on link prediction,on the contrary,the node clustering coefficient(NCC)often yields a negative effect.Therefore,it can find the optimal parameter in ELNB yielding the highest accuracy of link prediction.More importantly,we prove that,while an extended clustering coefficient(ECC)is different from traditional clustering coefficient(CC)in the micro-scale,they are the same in the meso-and macro-scales.As a result,an extended clustering coefficient(ECC)is a new and effective index to characterize the micro-structure of networks while remains the invariance property in meso-and macro-scales.