Network reconstructions with partially available data

Abstract

Many practical systems in natural and social sciences can be described by dynamical networks. Day by day we have measured and accumulated huge amounts of data from these networks, which can be used by us to further our understanding of the world. The structures of the networks producing these data are often unknown. Consequently, understanding the structures of these networks from available data turns to be one of the central issues in interdisciplinary fields, which is called the network reconstruction problem. In this paper, we considered problems of network reconstructions using partially available data and some situations where data availabilities are not sufficient for conventional network reconstructions. Furthermore, we proposed to infer subnetwork with data of the subnetwork available only and other nodes of the entire network hidden; to depict group-group interactions in networks with averages of groups of node variables available; and to perform network reconstructions with known data of node variables only when networks are driven by both unknown internal fast-varying noises and unknown external slowly-varying signals. All these situations are expected to be common in practical systems and the methods and results may be useful for real world applications.

Graphical abstract

Keywords

network reconstruction / dynamics / data analysis

1 Introduction

Many natural and social systems have been described by dynamical networks [1-3]. Typically, the outputs of these networks can be measured, while the network structures underlying these data productions are unknown [4, 5]. Therefore, inferring network structures from available data, i.e., network reconstruction, turns to be an important task in diverse fields, in particular in various interdisciplinary fields [6-12].

There have been various methods proposed for the implementation of network reconstructions in diverse fields, and most of them are based on the measurable data of the variables of all nodes in the targeted networks. The existing methods can be classified into several broad categories [13-16]: Bayesian networks and probabilistic graphical models, which maximize a scoring function over alternative network models [17, 18]; regression techniques, which fit the data to a priori models [19]; integrative bioinformatics approaches, which combine data from a number of independent experimental clues [20, 21]; statistical methods, which rely on a variety of measures of pairwise correlations or mutual information and other methods [22, 13].

However, it often occurs in practice that the data of networks cannot be fully measured, namely, we process only partial data. There are three typical such situations. First, for a large network of N nodes (N\gg 1) we can measure only outputs of n nodes in a subnetwork () while the remaining nodes of the network cannot be touched or even are not known [Fig. 1(a)]. Second, for a large network we cannot measure variable data of all individual nodes, instead, we can measure only averages of groups of node variables [Fig. 1(b)]. Third, networks are often driven by various external forces [see Fig. 1(c)] which however are often unknown on one hand, and they can essentially affect the network evolutions and data productions on the other hand. The problem proposed here is how much the network reconstructions can be performed with these partially available data. All nodes in a connected network evolve as a whole dynamical system due to the interactions (links) between nodes and external drivings on these nodes, and no nodes can be separately studied by neglecting influences from other nodes and background drivings. Thus, the problem of extracting as much as possible information of network structure from partially available data is definitely interesting.

In this paper, we show that there are some systematical approaches to analyze partial data of dynamical networks and make effective inferences of certain aspects of network structures. The paper is organized as follows. In Section 2, we introduce our model of noise-driven dynamical networks and a method of network reconstruction with output data of all network nodes. In Section 3, we show how to infer subnetworks with data of the subnetwork nodes measured only. The facts influencing the validity of subnetwork reconstructions are discussed. In Section 4, the problem how to use measured data of various groups of nodes to infer the interactions between these groups is considered. In Section 5, we perform network reconstructions with available data of node variables when networks are driven by both unknown internal fast-varying noises and unknown external slowly-varying signals. In conclusion part, we emphasize the practical significance of network reconstructions with partially available node data, and anticipate its possible applications.

2 Model and network reconstruction

We consider a model of noise-driven dynamical network [23]

\begin{array}{}\text{(1a)}& \dot{x}(t)=\widehat{A}x(t)+\Gamma (t)\mathrm{,}\end{array}

\begin{array}{}\text{(1b)}& \langle {\Gamma }_i(t){\Gamma }_j(t^{\prime })\rangle =Q_{ij}\delta (t-t^{\prime })\mathrm{,}\end{array}

with

\begin{array}{}\text{(1b)}& \begin{array}{l}x(t)=[x_1(t),x_2(t),\cdots ,x_N{(t)}^{]\text{T}},\hfill \\ \Gamma (t)=[{\Gamma }_1(t),{\Gamma }_2(t),\cdots ,{\Gamma }_N{(t)}^{]\text{T}},\hfill \\ \widehat{A}=[A_{ij}].\hfill \end{array}\end{array}

For simplicity we investigate linear networks with A_{ij} being constant and white noise approximation. The extension to nonlinear networks and colored noise with finite correlation time can be realized by applying high-order correlations and matrix iterations [24, 25].

In Ref. [23] authors suggested a method of double-correlation-matrix and noise-decorrelation (DCMND) to infer network Eq. (1) with fully available data of x(t) as

\begin{array}{}\text{(2)}& \widehat{A}=\widehat{B}(-\tau )\widehat{C}{(-\tau )}^{-1}\mathrm{,}\end{array}

where

\begin{array}{}\text{(2)}& \begin{array}{l}\widehat{C}(-\tau )=\langle x(t)x{(}^{t-\tau )\text{T}}\rangle =\frac{1}{L\text{}-\text{}q}{\displaystyle \sum _{k=q+1}^L}x(t_k)x^{\text{T}}(t_{k-q}),\hfill \\ \widehat{B}(-\tau )=\langle \dot{x}(t)x{(}^{t-\tau )\text{T}}\rangle =\frac{1}{L\text{}-\text{}q}{\displaystyle \sum _{k=q+1}^L}\dot{x}(t_k)x^{\text{T}}(t_{k-q}),\hfill \\ \dot{x}(t_k)=\frac{x(t_{k+1})-x(t_k)}{\text{Δ}t},\tau =q\text{Δ}t,\hfill \end{array}\end{array}

and all data

are measurable and available for the computation of network reconstruction. In Eq. (2) τ is chosen as

where {\tau }_{\text{noise}} and {\tau }_{\text{dynamics}} are noise correlation time and characteristic time of deterministic dynamics of the networks, respectively. Here, we consider white noise of {\tau }_{\text{noise}}=0. From Eq. (1) to Eq. (2) we used the white noise approximation leading to noise decorrelation \langle {\Gamma }_i(t)x_j(t-\tau )\rangle \approx 0 because any node variable at early time x_j(t-\tau ) cannot be correlated with noise of later time {\Gamma }_i(t). An example of network reconstruction by using Eq. (2) is presented in Fig. 2(a).

3 Reconstruction of subnetworks with variable data of subnetwork nodes

Realistic networks may be very large (N\gg 1) and many nodes of networks may not be measured and even not known, as shown in Fig. 1(a). The problem is how much information about the network structure can be extracted with partially measured data. Precisely, can we reconstruct the subnetworks linked by the partial nodes of which the data can be measured? From the first glance the answer may be negative, because all the interactions to subnetwork nodes from nodes off the subnetworks are unknown and thus cannot be taken into account. On the other hand, these off-subnetwork nodes may essentially influence the dynamics of subnetwork nodes. Assuming only n of the N nodes randomly chosen are measured, we apply formula of Eq. (2) to infer the n-node subnetworks with the available node data, i.e., with measured data we extend formula Eq. (2) to

\begin{array}{}\text{(5b)}& {\widehat{A}}_s={\widehat{B}}_s{\widehat{C}}_s^{-1}\mathrm{,}\end{array}

where {\widehat{A}}_s, {\widehat{B}}_s, and {\widehat{C}}_s have the same meaning as Eq. (2) with all matrix elements computed by measurable variables of subnetwork nodes. In Figs. 2(b)–(d) we compare the subnetwork {\widehat{A}}_s elements computed by Eq. (5) with the true interactions of the network. We find the approximate validity of the algorithm of Eq. (5) and the inference accuracy depends on the size of subnetworks. Increasing the size of measurable subnetworks can, of course, increases the precision of subnetwork reconstruction. The results of Fig. 2(d) is really surprising: in a network of N=200 with rather dense interactions (each node accepts up to 20 interactions from other nodes), the reconstruction computation Eq. (5) can still work when only variable data of 2 nodes of the network are available. Moreover, the qualitative behaviors of a individual interaction from node A to node B can be inferred with rather high probability when all other (up to 19) interactions to node B are not taken into account.

4 Network reconstruction with data of groups of nodes

Another situation schematically described in Fig. 1(b) is very commonly encountered in practical experiments of dynamical networks where we cannot measure the outputs of individual nodes, instead, we can measure only the average outputs of various groups of node variables. Namely, we actually measure data y(t) as

\begin{array}{}\text{(6a)}& y_i(t)=\frac{1}{m_i}{\displaystyle \sum _g}{x}_i^g(t)\mathrm{,}i=\mathrm{1,2,}\cdots \mathrm{,}n\mathrm{,}\end{array}

\begin{array}{}\text{(6b)}& N={\displaystyle \sum _{i=1}^n}{m}_i\mathrm{,}\end{array}

where x_i^g represent ith group, summation over g in Eq. (6a) goes through all nodes in the ith group, say, over m_i nodes.

With y_i(t)\mathrm{,}i=\mathrm{1,2,}\cdots \mathrm{,}n available, we are facing a situation, similar to while different from that of Eq. (5a). The same problem is that in both Eq. (5a) and Eq. (6a) only partial information of the output data of networks are available, and the difference is that in the former case we have variable data of partial nodes (or say, data of subnetworks), while in the latter situation we do have some information of whole networks, but in the sense of coarse grain measurements. Here, we suggest to use the DCMND formula of Eq. (2) to perform network reconstruction to infer group-group interactions, i.e., the average interactions between nodes of different groups. Precisely, we use formula

\begin{array}{}\text{(7)}& {\widehat{A}}_g={\widehat{B}}_g{\widehat{C}}_g^{-1}\end{array}

to compute network structure {\widehat{A}}_g with

\begin{array}{}\text{(7)}& \begin{array}{l}{\widehat{B}}_g=\langle \dot{y}(t)y{(}^{t-\tau )\text{T}}\rangle ,\hfill \\ {\widehat{C}}_g=\langle y(t)y{(}^{t-\tau )\text{T}}\rangle .\hfill \end{array}\end{array}

In Eq. (2) A_{ij} represents the interaction from node j to node i. We expect that A_{g\mathrm{,}ij} denotes the total interactions from all nodes of group j to all nodes of group i, i.e.,

\begin{array}{}\text{(8)}& A_{g\mathrm{,}ij}=\frac{1}{m_i}{\displaystyle \sum _{\mu }^{m_i}}{\displaystyle \sum _{\nu }^{m_j}}{A}_{g\mathrm{,}\mu \nu }\mathrm{,}\end{array}

where the summations of \mu \mathrm{,}\nu over all m_i nodes of the ith group and all m_j nodes of the jth group, respectively.

In Fig. 3 we plot A_{g\mathrm{,}ij} vs. A_{g\mathrm{,}ij}^{\prime } for different group distributions, where A_{g\mathrm{,}ij} represent actual interaction between groups while A_{g\mathrm{,}ij}^{\prime } are group interaction inferred by Eq. (7) based on the available data of Eq. (6a). It is shown that computation errors increase as sizes of groups increase, and the method fails when the group sizes are comparable with the size of the total network.

5 Network reconstruction under unknown external drivings

Now we come to the situation shown in Fig. 1(c). It has been known that a fast-noise-driven network Eq. (1) can be analytically inferred by the so called DCMND method Eq. (2). In many practical cases, internal noises come from microscopic world, having very short characteristic time, and can be approximated by white noises. It is emphasized that the formula Eq. (2) is exact for white noise driving and sufficiently fast measurements \text{Δ}t\to 0 and large numbers of data samples L\to \infty. In Sections 3 and 4, we considered network reconstructions with variable data of partial nodes [Fig. 1(a)] and data of groups of nodes [Fig. 1(b)], respectively. It is very common that network nodes can be driven not only by internal fast noises, but also by external background, of which the dynamics can be written as

\begin{array}{}\text{(9)}& \dot{x}(t)=\widehat{A}x(t)+\Gamma (t)+S(t)\mathrm{,}\end{array}

where S(t) comes from the world of scale larger than that of networks under study, and thus has slower evolution than the latter

\begin{array}{}\text{(10)}& \dot{S}(t)\ll 1.\end{array}

S(t) is usually unknown while it essentially influences the data production of networks as well as influences the network reconstruction computation. Multiplying both sides of Eq. (9) by x(t-\tau ) and computing the corresponding correlation matrices, we can derive

\begin{array}{}\text{(11a)}& \widehat{B}(-\tau )=\widehat{A}\widehat{C}(-\tau )+\widehat{S}(-\tau )\mathrm{,}\end{array}

\begin{array}{}\text{(11b)}& \widehat{S}(-\tau )=\langle S(t)x{(t-\tau )}^T\rangle \mathrm{,}\end{array}

where \widehat{B} and \widehat{C} have the same meaning as Eq. (2).

In Fig. 4(a) we infer the structure of a network Eq. (9) by using the conventional DCMND method Eq. (2), disregarding the existence of the slow external driving S(t) in Eq. (9). The results show that Eq. (2) fails under the presence of S(t). If we have no information about S(t), the network reconstruction is impossible since the number of unknown variables are always more than the number of equations. However, the general condition of slowly-varying signal Eq. (10) can be of great help to make the problem solvable. We can differentiate Eq. (9) as

\begin{array}{}\text{(12)}& \text{Δ}\dot{x}=\widehat{A}\text{Δ}x+\text{Δ}\Gamma +\text{Δ}S\mathrm{.}\end{array}

For any variable z(t), \text{Δ}z(t) is defined as

Multiplying Eq. (12) by x(t-\tau ) and computing the corresponding correlations, we have

\begin{array}{}\text{(12)}& \text{Δ}\widehat{B}=\widehat{A}\text{Δ}\widehat{C}+\langle \text{Δ}\Gamma (t)x{(t-\tau )}^{\text{T}}\rangle +\langle \text{Δ}S(t)x{(t-\tau )}^{\text{T}}\rangle \mathrm{,}\end{array}

which can be further simplified to

\begin{array}{}\text{(13a)}& \text{Δ}\widehat{B}=\widehat{A}\text{Δ}\widehat{C}\mathrm{,}\end{array}

\begin{array}{}\text{(13b)}& \widehat{A}=\text{Δ}\widehat{B}\text{Δ}{\widehat{C}}^{-1}\mathrm{,}\end{array}

From Eq. (11b) to Eq. (13b) we have considered properties of fast-varying noises of \Gamma (t) (\langle \text{Δ}\Gamma (t)x{(t-\tau )}^{\text{T}}\rangle \approx 0) and slowly-varying signal S(t) [Eq. (10), \langle \text{Δ}S(t)x{(t-\tau )}^{\text{T}}\rangle \approx 0].

In Fig. 4(b) we do the same as Fig. 4(a) with the modified DCMND Eq. (13b) applied. The results are fairly good. In computing network structure \widehat{A} we assume to know nothing about S(t) (and matrix \widehat{S}) in Eq. (11a) but only its slowly-varying property of Eq. (10). An interesting point is that \widehat{S} in Eq. (11a) itself can be inferred after \widehat{A} computed from Eq. (13b)

\begin{array}{}\text{(14)}& \widehat{S}=\widehat{B}-\widehat{A}\widehat{C}\mathrm{.}\end{array}

In Fig. 4(c) we plot actual \widehat{S} with that inferred by Eqs. (13) and (14), {\widehat{S}}^{\prime }, and find that \widehat{S} is very well reconstructed by {\widehat{S}}^{\prime }. Second, with the condition Eq. (10) we can solve \widehat{Q}. In Ref. [23] we have analyzed how to infer noise statistics matrix \widehat{Q} in Eq. (1b) by computing matrix {\widehat{B}}_s with different time lags. This method can be directly applied to more complicated model Eq. (9), due to the slow variation of signal S(t) Eq. (10). The statistical properties of \Gamma (t) can be thus computed as

\begin{array}{}\text{(15b)}& B_{ij}(\tau )=\langle {\dot{x}}_i(t+\tau )x_j(t)\rangle \mathrm{,}\end{array}

where \widehat{B}(\tau ) and \widehat{B}(-\tau ) can be explicitly computed from the measurable x(t) data. In Fig. 4(d) actual Q_{ij} are plotted vs. Q_{ij}^{\prime } computed by Eq. (15a) with available data. The reconstructions of noise statistics work satisfactorily. For a short summary, all parameters in Eq. (9) are unknown, with the output data of node variables only we can infer all networks structure \widehat{A}, noise statistic \widehat{Q} and signal statistics \widehat{S}. It is very interesting to emphasize that the modified DCMND method is capable not only to infer network structure \widehat{A} with both noise statistics \widehat{Q} and driving signal \widehat{S} unknown, but also to specify \widehat{S} and \widehat{Q}, which are very important for us to understand the background of our networks. These results are obtained by only two assumptions, fast unknown noise Eq. (4) and slow unknown signal Eq. (10).

In Fig. 4 we consider homogeneous random networks. The algorithm can be directly applied to other structures of networks, such as small-world and scale-free networks. In Fig. 5 we do exactly the same as in Fig. 4 with scale-free network considered. All results justify the validity of the modified DCMND method.

6 Conclusion

In conclusion, we have studied the problem of network reconstruction with partially available data, including subnetwork reconstruction in large networks with data of subnetwork nodes only; inference of interactions between groups of nodes with average data of groups of nodes only; and reconstruction of dynamical networks driven by both unknown fast-varying and unknown slowly-varying signals. In all these cases we extend the method of double-correlation-matrix and noise-decorrelation (DCMND), and solve the problems approximately with various modified formulas. Though the extended methods are not accurate, their validity are justified by extensive numerical computations, and the conditions for proper approximations are well understood. In particular, all these extended cases represent typical existing practical situations, and the results are expected to be applicable for solving the problems of network reconstructions in practical systems.

References

[1] D. J. Watts and S. H. Strogatz, Collective dynamics of small-world networks, Nature 393(6684), 440 (1998)

[2] A. L. Barabási and R. Albert, Emergence of scaling in random networks, Science 286(5439), 509 (1999)

[3] A. L. Barabási and Z. N. Oltvai, Network biology: Understanding the cell’s functional organization, Nat. Rev. Genet. 5(2), 101 (2004)

[4] A. M. Feist, M. J. Herrgard, I. Thiele, J. L. Reed, and B. O. Palsson, Reconstruction of biochemical networks in microorganisms, Nat. Rev. Microbiol. 7(2), 129 (2008)

[5] R. De Smet and K. Marchal, Advantages and limitations of current network inference methods, Nat. Rev. Microbiol. 8, 717 (2010)

[6] M. K. S. Yeung, J. Tegner, and J. J. Collins, Reverse engineering gene networks using singular value decomposition and robust regression, Proc. Natl. Acad. Sci. USA 99(9), 6163 (2002)

[7] J. M. Stuart, E. Segal, D. Koller, and S. K. Kim, A genecoexpression network for global discovery of conserved genetic modules, Science 302(5643), 249 (2003)

[8] E. Segal, M. Shapira, A. Regev, D. Pe’er, D. Botstein, D. Koller, and N. Friedman, Module networks: Identifying regulatory modules and their condition-specific regulators from gene expression data, Nat. Genet. 34(2), 166 (2003)

[9] Z. Hu, P. J. Killion, and V. R. Iyer, Genetic reconstruction of a functional transcriptional regulatory network, Nat. Genet. 39(5), 683 (2007)

[10] T. R. Lezon, J. R. Banavar, M. Cieplak, A. Maritan, and N. V. Fedoroff, Using the principle of entropy maximization to infer genetic interaction networks from gene expression patterns, Proc. Natl. Acad. Sci. USA 103(50), 19033 (2006)

[11] B. Barzel and A. L. Barabasi, Network link prediction by global silencing of indirect correlations, Nat. Biotechnol. 31(8), 720 (2013)

[12] S. Feizi, D. Marbach, M. Medard, and M. Kellis, Network deconvolution as a general method to distinguish direct dependencies in networks, Nat. Biotechnol. 31(8), 726 (2013)

[13] K. Basso, A. A. Margolin, G. Stolovitzky, U. Klein, R. Dalla-Favera, and A. Califano, Reverse engineering of regulatory networks in human b cells, Nat. Genet. 37(4), 382 (2005)

[14] M. Bansal, V. Belcastro, A. Ambesi-Impiombato, and D. di Bernardo, How to infer gene networks from expression profiles, Mol. Syst. Biol. 3, 78 (2007)

[15] D. Marbach, J. C. Costello, R. Kuffner, N. M. Vega, R. J. Prill, et al., Wisdom of crowds for robust gene network inference, Nat. Methods 9(8), 796 (2012)

[16] A. F. Villaverde, J. Ross, and J. R. Banga, Reverse engineering cellular networks with information theoretic methods, Cells 2(2), 306 (2013)

[17] R. Jansen, H. Yu, D. Greenbaum, Y. Kluger, N. J. Krogan, et al., A bayesian networks approach for predicting protein-protein interactions from genomic data, Science 302(5644), 449 (2003)

[18] N. Friedman, Inferring cellular networks using probabilistic graphical models, Science 303(5659), 799 (2004)

[19] A. C. Haury, F. Mordelet, P. Vera-Licona, and J. P. Vert, Tigress: Trustful inference of gene regulation using stability selection, BMC Syst. Biol. 6(1), 145 (2012)

[20] T. S. Gardner, D. di Bernardo, D. Lorenz, and J. J. Collins, Inferring genetic networks and identifying compound mode of action via expression profiling, Science 301(5629), 102 (2003)

[21] M. W. Covert, E. M. Knight, J. L. Reed, M. J. Herrgard, and B. O. Palsson, Integrating highthroughput and computational data elucidates bacterial networks, Nature 429(6987), 92 (2004)

[22] M. B. Eisen, P. T. Spellman, P. O. Brown, and D. Botstein, Cluster analysis and display of genomewide expression patterns, Proc. Natl. Acad. Sci. USA 95(25), 14863 (1998)

[23] Z. Zhang, Z. Zheng, H. Niu, Y. Mi, S. Wu, and G. Hu, Solving the inverse problem of noise-driven dynamic networks, Phys. Rev. E 91(1), 012814 (2015)

[24] Y. Chen, S. Wang, Z. Zheng, Z. Zhang, and G. Hu, Depicting network structures from variable data produced by unknown colored-noise driven dynamics, Europhys. Lett. 113(1), 18005 (2016)

[25] Y. Chen, Z. Zhang, T. Chen, S. Wang, and G. Hu, Depict noise-driven nonlinear dynamic networks from output data by using high-order correlations, arXiv: 1605.05513

Rights & permissions

Higher Education Press and Springer-Verlag Berlin Heidelberg 2017