Link Prediction And Predictability From The Perspective Of Topology Structures In Complex Networks

Link prediction is a hot research topic in the complex network field.Its basic idea is to use observable information of complex network to predict possible connections in a network.On a theoretical level,the link prediction of complex network provides a unified research framework for uncovering the generative mechanisms of network structures,and a comparison platform for designing link prediction algorithms.In practical applications,link prediction provides guidance and reduces costs for large number of exploratory experiments by predicting the network structure in advance.With the explosive development of scientific knowledge and research technology,the link prediction of complex networks has encountered new opportunities and challenges.Many research problems remain to be solved.For example,how to give full play to the cross advantages of complexity science and provide new link prediction schemes combining cutting-edge scientific theories? How can we extend the link prediction to even more complex networks? For massive complex networks,based on network topology,can we develop a unified indicator to characterize the links predictability of networks? Based on these issues,in this paper,from the perspective of topology structure in complex networks,researches have been conducted on the intersection of link prediction theories,the expansion of research objects of link prediction,and the links predictability of networks.The main contributions and innovation points are as follows.(1)In order to fully utilize the sparse characteristics of general complex networks.With the low-rank representation method,this paper proposes a novel low-rank representation objective function,which uses a fully connected network adjacency matrix as the base matrix and takes the nuclear norm of the reconstruction network as a penalty term.The representation coefficients of the network structures are then utilized to develop a link prediction algorithm LRNP.Additionally,the concept of a refined network is introduced,and an optimized link prediction algorithm OLRNP is designed based on the refined network constructed by removing a suitable proportion of weakly coupled links in the network.The numerical experiments indicate that the proposed algorithm LRNP has excellent convergence and outperforms classical benchmark algorithms in terms of link prediction performance.Moreover,the optimized algorithm OLRNP can significantly improve the link prediction accuracy of the original complex network.(2)In order to use the higher-order structure information contained in the network for link prediction,this paper presents a novel link prediction framework based on a hypergraph multi-view attention neural network.Firstly,a hypergraph modeling method NSLR for real-world complex networks is proposed using network structure representation,which overcomes the difficulties of hypergraph modeling without node attributes.Secondly,we put forward a hypergraph multi-view attention neural network HMANN with the inductive learning paradigm,which constructs a neural network based on attention mechanisms at both the node and hyperedge levels.And then,we come up with the link prediction algorithm NSLR-HMANN-based.The numerical experiments demonstrate that the NSLR-HMANN-based algorithm can effectively capture high-order structural information in networks and significantly improve link prediction performance.Furthermore,the ablation experiments of this paper fully validate the feasibility and effectiveness of the key design parts in the NSLR-HMANNbased algorithm.(3)For the link prediction of networks with more complex types,this paper proposes a weight allocation method for the local structures of heterogeneous complex networks,and constructs embedding learning objective function for heterogeneous complex networks with structural weights.We utilize negative sampling strategy and logistic regression to update the node embedding vectors,converting the possibility of the existence of links between nodes into the similarity of node embedding vectors.Experimental results show that the proposed link prediction algorithm SWMetapath2 vec for heterogeneous complex networks is competitive in performance and has strong robustness against parameters and sparse networks.(4)For the predictability problem of complex network links,this paper first analyzes the scientific and rational aspects of using network energy to characterize the links predictability of networks,and proposes two indexes successively to measure the predictability of network links from the perspective of network energy.Secondly,we construct a modified maximum likelihood probability model,deduce the possibility of the existence of potential links in the observable network,and propose a new link prediction algorithm LCPA.Experimental results illustrate that the LCPA link prediction algorithm significantly outperforms the benchmark algorithms,and can reveal the generation mechanism of ER random networks very well.At the same time,there is a clear relationship between the proposed indexes and the precision of the algorithm LCPA,which represents that these two indexes can effectively measure the link predictability.Further,there is a significant linear relationship between the second index and the link predictability.