Link Prediction Methods For Network Evolution And Connection Mechanism

A network is an abstract representation of a complex system in the world,where nodes represent basic entities and connections represent interactions among these entities.Usually,the network is evolving,which is reflected in both the changes of the network topology and functions.It is always an important concern of network science to explore the causes of network topology changes and the relationship between the changes and network functions.Although people have done a lot of work,it is not clear which kind of mechanism has caused these network changes.In this work,the connection mechanism and the evolution process of the network are studied.This purpose is to explain the root cause of the connection change in the evolution process of the network,and infer the relationship between the network topological changes and the network functions.Traditionally,researchers have interpreted the rules of network formation by constructing network models,which can generate synthetic networks similar with realworld networks.Such models include the small-world model,scale-free model,hierarchical model,et.al.However,previous models tend to construct networks from the perspective of network generation,and pay little attention to the relationship between the network topological changes and the functional changes in the long-term evolution process.In addition,the connection mechanisms in these models are simple,and they cannot explain the complex connection mechanisms.At the same time,the rapid development of information technology and intelligent communication devices,has promoted information propagation among network entities.This promotion further results in the complexity,dynamics,and un-interpretation of information networks such as mobile communication networks,the Internet,global infrastructure networks,Internet of Things,social networks,and biological networks.The in-depth exploration of connection mechanisms,organizational patterns,evolution rules and dynamic behaviors in these networks under the new situation not only brings unprecedented opportunities but also brings severe challenges to researchers.Firstly,considering the important value of connection mechanism inference and evolution analysis for understanding specific network applications,researchers in different fields have conducted in-depth research.However,the diversity of data types and attributes of different types of applications brings new challenges to the tasks of network connection mechanism inference and evolution analysis.How to extract key physical attribute factors of one specific application,and further integrate the factors into the existing topology connection mechanism,so that the network mechanism model suitable for the application have attracted people's attention.Secondly,The research on the network connection mechanism should not simply consider the network topology construction.More importantly,it should understand the relationship between the structural changes and the functional performance of the network in the long-term evolution process.Thirdly,another challenge with regard to network evolution and connectivity mechanisms is how to add constraints or control factors to the acquired evolution mechanism to achieve the desired functional performance.This is also the ultimate goal of the human design system.Moreover,the traditional research on network connection mechanism mainly pay attention to the modeling and analysis of static networks,but the studies of temporal topology prediction are more challenging.Finally,due to the diversity of network types and the complexity of the network structures,it is impossible to characterize the connection pattern of such networks using only a single network connection mechanism.The combination of multiple connection mechanisms is more acceptable.The core problem in the above problems is the research on the network connection mechanism,and the link prediction provides a lot of alternatives and implementation ideas for solving this problem.Link prediction refers to calculating the probability of the existence of a link between two nodes in the network according to the network structure and attributes.It includes not only the prediction of unknown and future links but also the fault existing edges.Studies have shown that link prediction is an important way to understand the connection mechanism of complex systems.If the principle of the link prediction algorithm is consistent with the mechanism for the formation or evolution of a given network,the algorithm will be able to provide accurate prediction results.Therefore,the potential network connection mechanism can be evaluated based on the prediction results of the corresponding link prediction algorithm.At present,research on link prediction algorithms has achieved a series of important developments,including topological similarity methods,the learning method based on network attributes,the static network methods and the temporal network methods.These methods provide a broad methodological reference and solutions for studying the connection mechanism of the network.Therefore,to solve the above-mentioned challenges in the research of network evolution and connection mechanism,this dissertation studies the evolution mechanism of different types of networks,such as biological networks,information networks and infrastructure networks,based on the link prediction methods.This research studies the evolution mechanisms of biological networks,information networks,and infrastructure networks,respectively.The corresponding networks selected in these types include human brain functional networks,wireless sensor networks,and the Internet,and corresponding network evolution models are proposed.This work analyzes the impact of both different types of data and physical factors on the model connection mechanism and provides important reference and practical value for designing a reasonable complex system and realizing the control of the system.The main research contributions of this dissertation are summarized as follows:1.This work discusses the relationship between the connection mechanism and functional performance in the network evolution process.This part of the work studies the connection mechanism of the human brain functional network in the category of biological networks.Specifically,both the connection mechanisms of the normal aging process and the Alzheimer's disease(AD)development process were studied,and the relationship between the changed network structures and the dynamic brain functions was analyzed.Firstly,this dissertation analyzes the changes of structure and attributes in the real human brain functional network in the above two processes.Secondly,according to the discovered characteristics of evolving brain networks,both topological structures and anatomical distance are used to define the connection probability between two brain nodes.Thus,the evolution models for inferring the evolution mechanisms of the brain network in both two processes are proposed,respectively.Furthermore,to evaluate the similarity between the model generated networks and the real data networks,a similarity index for testing the proximity between networks is designed.Finally,the corresponding experimental results show that compared with the traditional model,the proposed models can accurately simulate the real data networks in terms of network efficiency,clustering coefficient,modularity,and degree distribution.The research on the evolution mechanism of brain networks has contributed to the understanding of the changes in human brain cognitive functions according to the changes in network structures.2.This dissertation studies the impact of the control of network evolution mechanisms on the performance of network functions and select the large-scale wireless sensor network(WSNs)of the information network to do this research.The topology of WSNs is constructed by designing a reasonable connection mechanism,and the fault-tolerance and energy-efficiency are realized through corresponding control strategies.Firstly,the strategy for building the scale-free(SF)topology is introduced into the construction of the WSNs to improve its fault-tolerance.Secondly,different from the previous models who calculate the connection probability between two nodes with the consideration of only the node degree,the proposed models adopt the local structural features when building connections,so that it can achieve an improvement of the energy-efficiency.Then,in the proposed models,the energy consumption among the nodes is balanced by controlling the residual energy and limiting the maximum degree of the nodes.Besides,this part of the work also explores the degree distribution of networks generated by the models and present the theoretical derivations of it.Finally,the experimental results demonstrate that the proposed models can generate SF-WSNs topologies with better fault-tolerance and higher energy-efficiency by comparing with a candidate clusteringbased algorithm and other two SF enhancing algorithms.3.The traditional network mechanism models usually consider only the static topology of the network at a certain moment when calculating the connection probability between nodes.However,the real networks are often temporal,it is necessary to explore the connection mechanism of this kind of networks.The Internet is a typical large-scale temporal system.It largely determines the development of today's social networks.So it is important to study the connection mechanism of the Internet during its evolution process.Firstly,the evolution characteristics of Internet topology are quantitatively analyzed from multiple attributes.Secondly,a temporal Internet evolution model is proposed,with the consideration of both the internal structural characteristics of the network and the dynamic behavior characteristics between the temporal networks.The model adopts the link prediction method of matrix decomposition to calculate the similarity between two nodes.Then,the block coordinate descent is utilized to optimize the proposed model and the solution process of the optimal solution is given.Finally,the experimental results show that the proposed model has better prediction performance than other comparison methods.These findings make contributions to the architecture design,construction and macro topology detection of the Internet.4.The network connection mechanisms in the real world are often complex and are likely to be driven by multiple rules.It may not be possible to inferences such a complex connection mechanism of a network by using only a single link prediction algorithm.To this end,a hybrid link prediction model based on multiple mechanisms is proposed.Firstly,the hybrid mechanism strategy of the proposed model and network construction steps are described in detail.Secondly,distributions of four global attributes are defined to measure the similarity between the synthetic networks generated by the models and the real data networks.Thirdly,the hybrid link prediction method is abstracted into a multi-objective optimization problem on the four target attributes,and an improved non-dominated sorting genetic algorithm is used to find the optimal combination of hybrid models.Finally,the effectiveness and universality of the proposed algorithm are verified through experiments on a large number of data with different types.