Reconstruction,Prediction And Mining Of Structures In Complex Networks

A complex dynamical system in the real world can be described by a simple structure of network,so we can analyze the nature of the system by studying the network structure.This involves two questions:how to get and analyze the network structure?Therefore,this paper will study the reconstruc-tion,prediction and mining of network structure.The specific contents are as follows:(1)When the dynamic process is known,we propose a theoretical frame-work to fully reconstruct network structure via mean-field based maximum likelihood estimation approach(MM)from the data regarding the discrete-time dynamical processes.Such a framework consists of three steps:the first step is to establish the likelihood function of the dynamical process on network-s;in the second step,the parameters of the dynamic process will be solved via mean-field based maximum likelihood estimation approach;in the third step,the problem of network reconstruction is transformed into a solvable lin-ear system of equations,where the solutions of the linear system of equations uncover the neighbors of each node,thereby recovering the full structure of the network.The result,s on both artificial and empirical networks confirm that our method is reliable and efficient.(2)Finally,the problem of reconstruction of multi-layer networks can also be solved by mean-field based maximum likelihood estimation approach.we carry out a detailed analysis to elucidate the impacts of structural and dynam-ical parameters as well as noise on the reconstruction accuracy and robustness.(3)When the dynamic process is unknown,exploiting the expectation-maximization(EM)algorithm,we develop a method to ascertain the neigh-bors of any node in the network based solely on binary data,thereby recovering the full topology of the network.The results on both artificial and empir-ical networks confirm that our method is reliable and efficient.Our method does not require any a priori knowledge of the detailed dynamical processes,is parameter-free,and is capable of accurate reconstruction even in the presence of noise.(4)When there is no time series and only the final nodal states is known,we develop a maximum likelihood estimation-based framework to accurately in-fer the interaction topology.This method can reconstruct the network from various binary final state(whether rumors have been received,whether infec-tious diseases,etc.),additional information,such as the first arrival time of each signal at each node,can improve the reconstruction accuracy.We derive a mathematical theory for our framework and validate its performance.Finally,by analyzing the influence of random disturbance on network reconstruction,grouping prediction is used to improve the robustness of the algorithm.(5)In the aspect of link prediction of network,by analyzing different real networks,we find that the structural features of different networks are remark-ably different.In particular,even in the same network,their inner structural features are utterly different.Therefore,a logistic function combing multiple structural features is defined,then the weight of each feature in the logistic function is adaptively determined by exploiting the known structure informa-tion.Last,we use the“learnt”logistic function to predict the connection probabilities of missing links.According to our experimental results,we find that the performance of our adaptive fusion model is better than many simi-larity indices.(6)In the aspect of network structure mining,this paper mainly studies the problem of core-periphery(CP)structure detection.Firstly,we propose an effective algorithm for detecting CP structure based on a 3-tuple motif.In this algorithm,the first step,we define a 3-tuple motif in terms of the patterns of edges as well as the property of nodes;in the third step,a motif adjacency matrix is constructed based on the 3-tuple motif;in the third step,the problem is converted to find a cluster that minimizes the smallest motif conduct,ance.Our algorithm works well in different CP structures:including single or multiple CP structure,and local or global CP structures.(7)We analyze the stochastic block model in dealing with the detection of CP structure and community structure,and get some shortcomings.That is to say,the approximation of BP algorithm in inference has serious irrationality in the detection of CP structure.So,we propose an improved BP algorith-m to solve the problem in the original BP algorithm without increasing any computational complexity.By comparing the improved BP algorithm with the original BP algorithm on community detection and CP detection,we find that the two algorithms yield the same performance on the community detection when the network is sparse,for the community structure in dense networks or CP structure in networks,our improved BP algorithm is much better and more stable.