Network Reconstruction Based On Ordinary Differential Equation

Network reconstruction, also known as network inference, means to infer the causal or correlated interactions between nodes from their measured states. These interactions between nodes always refer to the network structure formulated by these nodes. Many network analysis technics such as community detection, information diffusion and opinion dynamic rely on the precise knowledge about the network structures,which, however, are not available in most of the networks, such as gene networks. Network topology not only helps understand the inner mechanism, but also benefits to predict or change the dynamic behavior. Thus, identifying the network structure from observed states is important in complex network study.The thesis first introduces some basic concepts in network reconstruction and extensively reviews existing algorithms. Then, two network reconstruction algorithms are proposed based on differential equation models. The main contributions of this thesis are summarized as follows:1. We transform the network reconstruction to be a signal recovery problem by means of compressive sensing. In the literature, the sensing matrix is determined by the network dynamic and measured states of nodes, which might violates the restriction on the coherence of the sensing matrix for exact recovery. We propose random projection and zero component analysis to preprocess the sensing matrix in order to reduce the coherence of the sensing matrix. These two data whitening technics are implemented in three different ways with different space complexity required, performing transformation on diagonal blocks, on multiple diagonal blocks and on the whole of the sensing matrix, which offers tradeoff between space and time complexity. Numerical simulations suggest that these proposed methods are effective to improve the quality of the reconstructed networks and comparisons are made among these methods and the ways they are implemented.2. We study a Bayesian approach to recover the network structure by means of a hybrid approach combining both sparsity and structure balance. Both sparsity and structure balance are proposed to be structure energy terms of exponential random graph model(ERGM) here. We simplify ERGM prior to make maximum a posteriori estimation to be easy enough yet capable of capturing sparsity and structure balance property of networks and the loss function with regulations is obtained. With a heuristic relaxed form of structure balance potential, a proximal gradient based method is derived to solve the case where the control input can be quantized continuously and a binary iterative hard thresholding(BIHT) is proposed to solve the discrete case. This offer an alternative approach to deal with ERGM as the prior distribution of networks for network reconstruction problems. The effectiveness of the proposed method is demonstrated via simulation. In summary, ERGM can provide new insights into designing case specific prior distribution of network structure for network reconstruction based on the Bayesian methods.