Maximum entropy estimation is of broad interest for inferring properties of systems across many disciplines. Using a recently introduced technique for estimating the maximum entropy of a set of random discrete variables when conditioning on bivariate mutual informations and univariate entropies, we show how this can be used to estimate the direct network connectivity between interacting units from observed activity. As a generic example, we consider phase oscillators and show that our approach is typically superior to simply using the mutual information. In addition, we propose a nonparametric formulation of connected informations, used to test the explanatory power of a network description in general. We give an illustrative example showing how this agrees with the existing parametric formulation, and demonstrate its applicability and advantages for resting-state human brain networks, for which we also discuss its direct effective connectivity. Finally, we generalize to continuous random variables and vastly expand the types of information-theoretic quantities one can condition on. This allows us to establish significant advantages of this approach over existing ones. Not only does our method perform favorably in the undersampled regime, where existing methods fail, but it also can be dramatically less computationally expensive as the cardinality of the variables increases.

Complexity Science Group Department of Physics and Astronomy University of Calgary Calgary Alberta T2N 1N4 Canada

Institute for Clinical and Experimental Medicine Videnska 1958 9 140 21 Prague Czech Republic

Institute of Computer Science The Czech Academy of Sciences Pod vodarenskou vezi 2 18207 Prague Czech Republic

Institute of Psychology The Czech Academy of Sciences Prague Czech Republic

National Institute of Mental Health Topolová 748 250 67 Klecany Czech Republic

Zobrazit více v PubMed

Jaynes ET. Information theory and statistical mechanics. Phys. Rev. 1957;106:620. doi: 10.1103/PhysRev.106.620. DOI

Hlaváč ková-Schindler K, Paluš M, Vejmelka M, Bhattacharya J. Causality detection based on information-theoretic approaches in time series analysis. Phys. Rep. 2007;441:1–46. doi: 10.1016/j.physrep.2006.12.004. DOI

Timme M, Casadiego J. Revealing networks from dynamics: an introduction. J. Phys. A Math. Theor. 2014;47:343001. doi: 10.1088/1751-8113/47/34/343001. DOI

Mader W, Mader M, Timmer J, Thiel M, Schelter B. Networks: On the relation of bi- and multivariate measures. Sci. Rep. 2015;5:10805. doi: 10.1038/srep10805. PubMed DOI PMC

Eguiluz VM, Chialvo DR, Cecchi GA, Baliki M, Apkarian AV. Scale-free brain functional networks. Phys. Rev. Lett. 2005;94:018102. doi: 10.1103/PhysRevLett.94.018102. PubMed DOI

Kugiumtzis D. Direct-coupling information measure from nonuniform embedding. Phys. Rev. E. 2013;87:062918. doi: 10.1103/PhysRevE.87.062918. PubMed DOI

Staniek M, Lehnertz K. Symbolic transfer entropy. Phys. Rev. Lett. 2008;100:158101. doi: 10.1103/PhysRevLett.100.158101. PubMed DOI

Bullmore E, Sporns O. Complex brain networks: graph theoretical analysis of structural and functional systems. Nature Reviews Neuroscience. 2009;10:186. doi: 10.1038/nrn2575. PubMed DOI

Lehnertz K, et al. Evolving networks in the human epileptic brain. Physica D. 2014;267:7–15. doi: 10.1016/j.physd.2013.06.009. DOI

Dickten H, Porz S, Elger CE, Lehnertz K. Weighted and directed interactions in evolving large-scale epileptic brain networks. Sci. Rep. 2016;6:34824. doi: 10.1038/srep34824. PubMed DOI PMC

Margolin AA, et al. Aracne: an algorithm for the reconstruction of gene regulatory networks in a mammalian cellular context. BMC Bioinformatics. 2006;7:S7. doi: 10.1186/1471-2105-7-S1-S7. PubMed DOI PMC

Runge J, et al. Identifying causal gateways and mediators in complex spatio-temporal systems. Nat. Commun. 2015;6:8502. doi: 10.1038/ncomms9502. PubMed DOI PMC

Tirabassi G, Sevilla-Escoboza R, Buldú JM, Masoller C. Inferring the connectivity of coupled oscillators from time-series statistical similarity analysis. Sci. Rep. 2015;5:10829. doi: 10.1038/srep10829. PubMed DOI PMC

Zhang J, Small M. Complex network from pseudoperiodic time series: Topology versus dynamics. Phys. Rev. Lett. 2006;96:238701. doi: 10.1103/PhysRevLett.96.238701. PubMed DOI

Lacasa L, Luque B, Ballesteros F, Luque J, Nuño JC. From time series to complex networks: The visibility graph. Proc. Natl. Acad. Sci. 2008;105:4972–4975. doi: 10.1073/pnas.0709247105. PubMed DOI PMC

Marwan N, Donges JF, Zou Y, Donner RV, Kurths J. Complex network approach for recurrence analysis of time series. Physics Letters A. 2009;373:4246–4254. doi: 10.1016/j.physleta.2009.09.042. DOI

Gao Z-K, Jin N-D. A directed weighted complex network for characterizing chaotic dynamics from time series. Nonlinear Analysis: Real World Applications. 2012;13:947–952. doi: 10.1016/j.nonrwa.2011.08.029. DOI

Gao Z-K, et al. Multiscale complex network for analyzing experimental multivariate time series. EPL (Europhysics Letters) 2015;109:30005. doi: 10.1209/0295-5075/109/30005. DOI

Gao Z-K, Small M, Kurths J. Complex network analysis of time series. EPL (Europhysics Letters) 2016;116:50001. doi: 10.1209/0295-5075/116/50001. DOI

Lezon TR, Banavar JR, Cieplak M, Maritan A, Fedoroff NV. Using the principle of entropy maximization to infer genetic interaction networks from gene expression patterns. Proc. Natl. Acad. Sci. 2006;103:19033–19038. doi: 10.1073/pnas.0609152103. PubMed DOI PMC

Margolin A, Wang K, Califano A, Nemenman I. Multivariate dependence and genetic networks inference. IET Sys. Bio. 2010;4:428–440. doi: 10.1049/iet-syb.2010.0009. PubMed DOI

Volkov I, Banavar JR, Hubbell SP, Maritan A. Inferring species interactions in tropical forests. Proc. Natl. Acad. Sci. 2009;106:13854–13859. doi: 10.1073/pnas.0903244106. PubMed DOI PMC

Xi N, Muneepeerakul R, Azaele S, Wang Y. Maximum entropy model for business cycle synchronization. Physica A. 2014;413:189–194. doi: 10.1016/j.physa.2014.07.005. DOI

Schneidman E, Berry MJ, Segev R, Bialek W. Weak pairwise correlations imply strongly correlated network states in a neural population. Nature. 2006;440:1007–1012. doi: 10.1038/nature04701. PubMed DOI PMC

Wood K, Nishida S, Sontag ED, Cluzel P. Mechanism-independent method for predicting response to multidrug combinations in bacteria. Proc. Natl. Acad. Sci. 2012;109:12254–12259. doi: 10.1073/pnas.1201281109. PubMed DOI PMC

Stephens GJ, Bialek W. Statistical mechanics of letters in words. Phys. Rev. E. 2010;81:066119. doi: 10.1103/PhysRevE.81.066119. PubMed DOI PMC

Lee ED, Broedersz CP, Bialek W. Statistical mechanics of the us supreme court. J. Stat. Phys. 2013;160:1–27.

Bialek W, et al. Statistical mechanics for natural flocks of birds. Proc. Natl. Acad. Sci. 2012;109:4786–4791. doi: 10.1073/pnas.1118633109. PubMed DOI PMC

Marre O, El Boustani S, Frégnac Y, Destexhe A. Prediction of spatiotemporal patterns of neural activity from pairwise correlations. Phys. Rev. Lett. 2009;102:138101. doi: 10.1103/PhysRevLett.102.138101. PubMed DOI

Martin EA, Hlinka J, Davidsen J. Pairwise network information and nonlinear correlations. Phys. Rev. E. 2016;94:040301(R). doi: 10.1103/PhysRevE.94.040301. PubMed DOI

Schneidman E, Still S, Berry MJ, Bialek W, et al. Network information and connected correlations. Phys. Rev. Lett. 2003;91:238701. doi: 10.1103/PhysRevLett.91.238701. PubMed DOI

Watanabe T, et al. A pairwise maximum entropy model accurately describes resting-state human brain networks. Nat. Commun. 2013;4:1370. doi: 10.1038/ncomms2388. PubMed DOI PMC

Cover, T. M. & Thomas, J. A. Elements of Information Theory (John Wiley & Sons, 2006).

Yeung, R. W. Information Theory and Network Coding (Springer, 2008).

Frenzel S, Pompe B. Partial mutual information for coupling analysis of multivariate time series. Phys. Rev. Lett. 2007;99:204101. doi: 10.1103/PhysRevLett.99.204101. PubMed DOI

Kuramoto, Y. Self-entrainment of a population of coupled non-linear oscillators. In International symposium on mathematical problems in theoretical physics, 420–422 (Springer, 1975).

Erdös P, Rényi A. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 1960;5:17–61.

Rijsbergen, C. J. Information retrieval. online bookhttp://www.dcs.gla.ac.uk/Keith/Chapter.7/Ch.7.html (Butterworth-Heinemann, 1979).

Schreiber T, Schmitz A. Improved surrogate data for nonlinearity tests. Phys. Rev. Lett. 1996;77:635. doi: 10.1103/PhysRevLett.77.635. PubMed DOI

Nemenman I. Coincidences and estimation of entropies of random variables with large cardinalities. Entropy. 2011;13:2013–2023. doi: 10.3390/e13122013. DOI

Tzourio-Mazoyer N, et al. Automated anatomical labeling of activations in SPM using a macroscopic anatomical parcellation of the MNI MRI single-subject brain. NeuroImage. 2002;15:273–289. doi: 10.1006/nimg.2001.0978. PubMed DOI

Hlinka J, Paluš M, Vejmelka M, Mantini D, Corbetta M. Functional connectivity in resting-state fMRI: Is linear correlation sufficient? NeuroImage. 2011;54:2218–2225. doi: 10.1016/j.neuroimage.2010.08.042. PubMed DOI PMC

Hartman D, Hlinka J, Paluš M, Mantini D, Corbetta M. The role of nonlinearity in computing graph-theoretical properties of resting-state functional magnetic resonance imaging brain networks. Chaos. 2011;21:013119. doi: 10.1063/1.3553181. PubMed DOI PMC

Yeh FC, et al. Maximum entropy approaches to living neural networks. Entropy. 2010;12:89–106. doi: 10.3390/e12010089. DOI

Darroch JN, Ratcliff D. Generalized iterative scaling for log-linear models. Ann. Math. Stat. 1972;43:1470–1480. doi: 10.1214/aoms/1177692379. DOI

Vershynin R. Beyond hirsch conjecture: Walks on random polytopes and smoothed complexity of the simplex method. SIAM J. Comput. 2009;39:646–678. doi: 10.1137/070683386. DOI

Hlinka J, Hartman D, Palus M. Small-world topology of functional connectivity in randomly connected dynamical systems. Chaos. 2012;22:033107. doi: 10.1063/1.4732541. PubMed DOI

Hlinka J, et al. Small-world bias of correlation networks: From brain to climate. Chaos. 2017;27:035812. doi: 10.1063/1.4977951. PubMed DOI