Research And Application Of Complex Network Reconstruction And Link Prediction Algorithms

Topological is one of the properties of complex network which does not depend on the specific position of nodes and the specific shape of edges,and its corresponding structure is called the topology of network.Any complex system can be represented by a network with interacting individuals.Therefore,the network is everywhere in the real world.The topology of complex network is the basis for us to understand the characteristics of the network,the behavior of nodes and the interaction between nodes.It is also significant for many fields such as the statistical characteristics study of complex networks,node feature extraction,node classification / clustering and so on.For physicists,the goal of studying complex networks is to understand the impact of network topology on physical processes,which shows the importance of network topology.However,in the real world,the topology of complex networks is often incomplete,noisy or even completely unknown,which greatly hinders the further study of complex networks.To solve these problems,this dissertation aims to study how to predict or reconstruct the network topology when the network topology is missing or completely unknown.Various types of network such as static networks,evolutionary networks,dynamic networks and so on are involving in our study.The main work is as follows:This dissertation proposes a complex network reconstruction algorithm based on regression methods.The dynamic behavior of nodes affects the topology of the network and vice versa.Therefore,the network topology can be reconstructed from the observed node dynamics.By expanding the dynamic behavior of each node in power series,the general expression of the relationship between each node and all the other nodes can be obtained.Thus,the network reconstruction problem can be transformed into a signal reconstruction problem.For the signal reconstruction problem,it can be solved by four common regression methods,namely least squares,ridge regression,lasso and elastic net.The experimental results show that the four regression methods can completely reconstruct the network topology under certain conditions.In addition,combined with the characteristics of the four regression methods and the results of network reconstruction,the internal mechanism of network reconstruction is analyzed in detail,which gives some advices about regression methods to readers when dealing with similar problems.Different systems need to construct the different models with the special network reconstruction methods.That is,it is necessary to know some prior information of dynamic systems,which limits the expansion of traditional methods.Therefore,a complex network reconstruction method based on auto-encode is proposed.Auto-encode method is a hot spot in the research of deep learning,and it is a kind of unsupervised learning framework.The topology of the network is reconstructed by encoding the observed values of the nodes,and then the reconstructed topology is decoded to obtain the information of the nodes.Finally,the parameters of the auto-encode model are iteratively learned by constraining the input observation values and the decoded ones.This unsupervised learning method can reconstruct the network structure without any prior knowledge.The topology of the network can be reconstructed from the node dynamics or other observation data.In turn,the network structure will affect the node dynamics.So what is the impact of the change of the node information on the evolution of the network? This dissertation reveals a series of rules between the change of node degree and network structure,and extends it to the practical application of link prediction of complex network by studying the evolution mechanism of complex network.When the network structure changes,such as deleting or adding edges,we study the change trend of the node degree.Then we find five rules and prove them in theory.With these rules,a new similarity criterion based on the change of node degree is proposed to measure the similarity between nodes.This similarity criterion can be used to predict the links in the network.The experimental results show that it has obvious advantages for the link prediction of scale-free networks compared with the current common link prediction algorithms based on similarity.There are a lot of dynamic networks in the real world.The topologies of them are changing time by time.Inspired by the research results of the last work,a link prediction method based on node ranking for dynamic networks is proposed.Dynamic networks evolve with time,that is,the network structure will change time by time,such as the increase or decrease of nodes,the increase or decrease of connected edges,and so on.Therefore,it is very meaningful and challenging to predict the links which will occur in the future.Node ranking can characterize the extent of node attracting other nodes,so the relationship between node pairs derived from node ranking can be used to measure the degree of mutual attraction between node pairs.Thus,the similarity matrix of each time network can be constructed.Due to the different evolution rules of different dynamic networks,an adaptive weighted moving time series prediction method is proposed to estimate the similarity between node pairs in the future network.In addition to dynamic networks,scale-free networks which conform to the laws of the real world evolving over time are easy to simulate and obtain.Therefore,this dissertation presents a link prediction method for scale-free networks that evolves over time.Scale-free network generally refers to the complex network whose node degree distribution follows power-law distribution.In the real world,many networks,such as the world wide web and metabolic network,are scale-free networks.Even many of them are evolving over time.However,the link prediction of time-varying scale-free networks has not attracted enough attention.Therefore,based on the node ranking information,a method is proposed to predict the possibility of edge connection between new nodes and existing nodes in the time-varying scale-free networks in the future.