Percolation Process-Based Link Prediction Research For Complex Networks

Nowadays,complex network research has become a framework and paradigm for analyzing complex systems and processing large-scale complex data.As one of the core issues in the field of complex network research,link prediction research has always been regarded as an important means to understand the structure and evolution of the network and predict the future behavior of the network,and it is also a long-term focus in the field of network science.Link prediction refers to predicting the connection relationship between nodes and links that may appear in the future by analyzing the information of existing nodes and links in the network.At present,an important class of link prediction methods use the topology similarity of nodes for prediction.However,existing studies have shown that the generation and disappearance of links in the network will be affected by the global structure of the network.Considering that the percolation process in the percolation theory reflects the physical process of the fluid infiltrating the porous medium,and describes the global structural characteristics of the medium to a certain extent,a link prediction method based on percolation process is proposed to realize link prediction based on the global structural characteristics of the network in this study.The validity of the method is confirmed by the link prediction experiment based on the method on the empirical network.The proposed link prediction method based on percolation process is not only an important supplement to link prediction based on network topology,but also has both theoretical research significance and practical application value.The main work of this thesis is as follows.1.Considering that the percolation process can describe the global structural characteristics of the percolation network to a certain extent,and link prediction can be performed based on the global structural characteristics of the network,a link prediction method based on percolation process —percolation(PERC)method is proposed,and the complexity of the method is analyzed theoretically.Aiming at the uneven distribution of local similarity indicators in the empirical network,a standardized data processing procedure is proposed.In addition,in order to combine the global structural characteristics and local similarity of the network for link prediction,a total of four comprehensive prediction indicators are constructed based on the PERC index and the processed local similarity indicators.2.The link prediction experiments are carried out on the empirical network based on local similarity methods,PERC method,and comprehensive prediction methods,and the result comparison and theoretical analysis are completed.The effectiveness of the PERC method is verified and the approach relationship between it and the local similarity methods is demonstrated.The difference of prediction effect before and after data processing is analyzed and the validity of the data processing process is confirmed.3.The influence of network structure(clustering coefficient,assortativity)on the prediction effect of PERC method and comprehensive prediction methods is studied.The results verify the positive promotion effect of the clustering coefficient of the network on the two types of methods and give a theoretical analysis.The study also found a staged difference in the impact of assortativity of network on the two types of methods,in which a hypothetical explanation was given for the positive impact of when the network is assortative.