1
|
Ding X, Kong LW, Zhang HF, Lai YC. Deep-learning reconstruction of complex dynamical networks from incomplete data. CHAOS (WOODBURY, N.Y.) 2024; 34:043115. [PMID: 38574280 DOI: 10.1063/5.0201557] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 01/31/2024] [Accepted: 03/19/2024] [Indexed: 04/06/2024]
Abstract
Reconstructing complex networks and predicting the dynamics are particularly challenging in real-world applications because the available information and data are incomplete. We develop a unified collaborative deep-learning framework consisting of three modules: network inference, state estimation, and dynamical learning. The complete network structure is first inferred and the states of the unobserved nodes are estimated, based on which the dynamical learning module is activated to determine the dynamical evolution rules. An alternating parameter updating strategy is deployed to improve the inference and prediction accuracy. Our framework outperforms baseline methods for synthetic and empirical networks hosting a variety of dynamical processes. A reciprocity emerges between network inference and dynamical prediction: better inference of network structure improves the accuracy of dynamical prediction, and vice versa. We demonstrate the superior performance of our framework on an influenza dataset consisting of 37 US States and a PM2.5 dataset covering 184 cities in China.
Collapse
Affiliation(s)
- Xiao Ding
- The Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education, School of Mathematical Science, Anhui University, Hefei 230601, China
| | - Ling-Wei Kong
- School of Electrical, Computer and Energy Engineering, Arizona State University, Tempe, Arizona 85287, USA
| | - Hai-Feng Zhang
- The Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education, School of Mathematical Science, Anhui University, Hefei 230601, China
| | - Ying-Cheng Lai
- School of Electrical, Computer and Energy Engineering, Arizona State University, Tempe, Arizona 85287, USA
| |
Collapse
|
2
|
Ma C, Lai YC, Li X, Zhang HF. General optimization framework for accurate and efficient reconstruction of symmetric complex networks from dynamical data. Phys Rev E 2023; 108:034304. [PMID: 37849195 DOI: 10.1103/physreve.108.034304] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 09/19/2022] [Accepted: 08/18/2023] [Indexed: 10/19/2023]
Abstract
The challenging problem of network reconstruction from dynamical data can in general be formulated as an optimization task of solving multiple linear equations. Existing approaches are of the two types: Point-by-point (PBP) and global methods. The local PBP method is computationally efficient, but the accuracies of its solutions are somehow low, while a global method has the opposite traits: High accuracy and high computational cost. Taking advantage of the network symmetry, we develop a novel framework integrating the advantages of both the PBP and global methods while avoiding their shortcomings: i.e., high reconstruction accuracy is guaranteed, but the computational cost is orders of magnitude lower than that of the global methods in the literature. The mathematical principle underlying our framework is block coordinate descent (BCD) for solving optimization problems, where the various blocks are determined by the network symmetry. The reconstruction framework is validated by numerical examples with a variety of network structures (i.e., sparse and dense networks) and dynamical processes. Our success is a demonstration that the general principle of exploiting symmetry can be extended to tackling the challenging inverse problem or reverse engineering of complex networks. Since solving a large number of linear equations is key to a plethora of problems in science and engineering, our BCD-based network reconstruction framework will find broader applications.
Collapse
Affiliation(s)
- Chuang Ma
- School of Internet, Anhui University, Hefei 230601, China
| | - Ying-Cheng Lai
- School of Electrical, Computer and Energy Engineering, Arizona State University, Tempe, Arizona 85287, USA
| | - Xiang Li
- The Institute of Complex Networks and Intelligent Systems, Shanghai Research Institute for Intelligent Autonomous Systems, Tongji University, Shanghai 201210, China
| | - Hai-Feng Zhang
- School of Mathematical Science, Anhui University, Hefei 230601, China
| |
Collapse
|
3
|
Song JU, Choi K, Oh SM, Kahng B. Exploring nonlinear dynamics and network structures in Kuramoto systems using machine learning approaches. CHAOS (WOODBURY, N.Y.) 2023; 33:073148. [PMID: 37486666 DOI: 10.1063/5.0153229] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/05/2023] [Accepted: 07/03/2023] [Indexed: 07/25/2023]
Abstract
Recent advances in machine learning (ML) have facilitated its application to a wide range of systems, from complex to quantum. Reservoir computing algorithms have proven particularly effective for studying nonlinear dynamical systems that exhibit collective behaviors, such as synchronizations and chaotic phenomena, some of which still remain unclear. Here, we apply ML approaches to the Kuramoto model to address several intriguing problems, including identifying the transition point and criticality of a hybrid synchronization transition, predicting future chaotic behaviors, and understanding network structures from chaotic patterns. Our proposed method also has further implications, such as inferring the structure of neural networks from electroencephalogram signals. This study, finally, highlights the potential of ML approaches for advancing our understanding of complex systems.
Collapse
Affiliation(s)
- Je Ung Song
- CTP and Department of Physics and Astronomy, Seoul National University, Seoul 08826, Korea
| | - Kwangjong Choi
- CTP and Department of Physics and Astronomy, Seoul National University, Seoul 08826, Korea
| | - Soo Min Oh
- Wireless Information and Network Sciences Laboratory, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
- Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
| | - B Kahng
- Center for Complex Systems and KI for Grid Modernization, Korea Institute of Energy Technology, Naju 58217, Korea
| |
Collapse
|
4
|
Topal I, Eroglu D. Reconstructing Network Dynamics of Coupled Discrete Chaotic Units from Data. PHYSICAL REVIEW LETTERS 2023; 130:117401. [PMID: 37001085 DOI: 10.1103/physrevlett.130.117401] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 09/20/2022] [Revised: 02/17/2023] [Accepted: 02/21/2023] [Indexed: 06/19/2023]
Abstract
Reconstructing network dynamics from data is crucial for predicting the changes in the dynamics of complex systems such as neuron networks; however, previous research has shown that the reconstruction is possible under strong constraints such as the need for lengthy data or small system size. Here, we present a recovery scheme blending theoretical model reduction and sparse recovery to identify the governing equations and the interactions of weakly coupled chaotic maps on complex networks, easing unrealistic constraints for real-world applications. Learning dynamics and connectivity lead to detecting critical transitions for parameter changes. We apply our technique to realistic neuronal systems with and without noise on a real mouse neocortex and artificial networks.
Collapse
Affiliation(s)
- Irem Topal
- Faculty of Engineering and Natural Sciences, Kadir Has University, 34083 Istanbul, Turkey
| | - Deniz Eroglu
- Faculty of Engineering and Natural Sciences, Kadir Has University, 34083 Istanbul, Turkey
| |
Collapse
|
5
|
Wu K, Wang C, Liu J. Evolutionary Multitasking Multilayer Network Reconstruction. IEEE TRANSACTIONS ON CYBERNETICS 2022; 52:12854-12868. [PMID: 34270441 DOI: 10.1109/tcyb.2021.3090769] [Citation(s) in RCA: 6] [Impact Index Per Article: 3.0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 06/13/2023]
Abstract
Due to the multilayer nature of real-world systems, the problem of inferring multilayer network structures from nonlinear and complex dynamical systems is prominent in many fields, including engineering, biological, physical, and computer sciences. Many network reconstruction methods have been proposed to address this problem, but none of them consider the similarities among network reconstruction tasks at different component layers, which are inspired by topology correlations and dynamic couplings among different component layers. This article develops an evolutionary multitasking multilayer network reconstruction framework to make use of the correlations among different component layers to improve the reconstruction performance; we refer to this framework as EM2MNR. In EM2MNR, the multilayer network reconstruction problem is first established as a multitasking multilayer network reconstruction problem, where the goal of each task is to reconstruct the network structure of a component layer. In addition, multitasking multilayer network reconstruction problems are high dimensional, but existing evolutionary multitasking algorithms may have poor performance when dealing with optimization problems with a high-dimensional search space. Inspired by the sparsity of multilayer networks, EM2MNR employs the restricted Boltzmann machine to extract low effective features from the original decision space and then decides whether to conduct knowledge transfer on these features. To verify the performance of EM2MNR, this article also designs a test suite for multilayer network reconstruction problems. The experimental results demonstrate the significant improvement obtained by the proposed EM2MNR framework on 96 multilayer network reconstruction problems.
Collapse
|
6
|
Peel L, Peixoto TP, De Domenico M. Statistical inference links data and theory in network science. Nat Commun 2022; 13:6794. [PMID: 36357376 PMCID: PMC9649740 DOI: 10.1038/s41467-022-34267-9] [Citation(s) in RCA: 11] [Impact Index Per Article: 5.5] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/01/2021] [Accepted: 10/18/2022] [Indexed: 11/11/2022] Open
Abstract
The number of network science applications across many different fields has been rapidly increasing. Surprisingly, the development of theory and domain-specific applications often occur in isolation, risking an effective disconnect between theoretical and methodological advances and the way network science is employed in practice. Here we address this risk constructively, discussing good practices to guarantee more successful applications and reproducible results. We endorse designing statistically grounded methodologies to address challenges in network science. This approach allows one to explain observational data in terms of generative models, naturally deal with intrinsic uncertainties, and strengthen the link between theory and applications. Theoretical models and structures recovered from measured data serve for analysis of complex networks. The authors discuss here existing gaps between theoretical methods and real-world applied networks, and potential ways to improve the interplay between theory and applications.
Collapse
|
7
|
Predicting network dynamics without requiring the knowledge of the interaction graph. Proc Natl Acad Sci U S A 2022; 119:e2205517119. [PMID: 36279454 PMCID: PMC9636954 DOI: 10.1073/pnas.2205517119] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/18/2022] Open
Abstract
A network consists of two interdependent parts: the network topology or graph, consisting of the links between nodes and the network dynamics, specified by some governing equations. A crucial challenge is the prediction of dynamics on networks, such as forecasting the spread of an infectious disease on a human contact network. Unfortunately, an accurate prediction of the dynamics seems hardly feasible, because the network is often complicated and unknown. In this work, given past observations of the dynamics on a fixed graph, we show the contrary: Even without knowing the network topology, we can predict the dynamics. Specifically, for a general class of deterministic governing equations, we propose a two-step prediction algorithm. First, we obtain a surrogate network by fitting past observations of every nodal state to the dynamical model. Second, we iterate the governing equations on the surrogate network to predict the dynamics. Surprisingly, even though there is no similarity between the surrogate topology and the true topology, the predictions are accurate, for a considerable prediction time horizon, for a broad range of observation times, and in the presence of a reasonable noise level. The true topology is not needed for predicting dynamics on networks, since the dynamics evolve in a subspace of astonishingly low dimension compared to the size and heterogeneity of the graph. Our results constitute a fresh perspective on the broad field of nonlinear dynamics on complex networks.
Collapse
|
8
|
Robin V, Bodein A, Scott-Boyer MP, Leclercq M, Périn O, Droit A. Overview of methods for characterization and visualization of a protein–protein interaction network in a multi-omics integration context. Front Mol Biosci 2022; 9:962799. [PMID: 36158572 PMCID: PMC9494275 DOI: 10.3389/fmolb.2022.962799] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/06/2022] [Accepted: 08/16/2022] [Indexed: 11/26/2022] Open
Abstract
At the heart of the cellular machinery through the regulation of cellular functions, protein–protein interactions (PPIs) have a significant role. PPIs can be analyzed with network approaches. Construction of a PPI network requires prediction of the interactions. All PPIs form a network. Different biases such as lack of data, recurrence of information, and false interactions make the network unstable. Integrated strategies allow solving these different challenges. These approaches have shown encouraging results for the understanding of molecular mechanisms, drug action mechanisms, and identification of target genes. In order to give more importance to an interaction, it is evaluated by different confidence scores. These scores allow the filtration of the network and thus facilitate the representation of the network, essential steps to the identification and understanding of molecular mechanisms. In this review, we will discuss the main computational methods for predicting PPI, including ones confirming an interaction as well as the integration of PPIs into a network, and we will discuss visualization of these complex data.
Collapse
Affiliation(s)
- Vivian Robin
- Molecular Medicine Department, CHU de Québec Research Center, Université Laval, Québec, QC, Canada
| | - Antoine Bodein
- Molecular Medicine Department, CHU de Québec Research Center, Université Laval, Québec, QC, Canada
| | - Marie-Pier Scott-Boyer
- Molecular Medicine Department, CHU de Québec Research Center, Université Laval, Québec, QC, Canada
| | - Mickaël Leclercq
- Molecular Medicine Department, CHU de Québec Research Center, Université Laval, Québec, QC, Canada
| | - Olivier Périn
- Digital Sciences Department, L'Oréal Advanced Research, Aulnay-sous-bois, France
| | - Arnaud Droit
- Molecular Medicine Department, CHU de Québec Research Center, Université Laval, Québec, QC, Canada
- *Correspondence: Arnaud Droit,
| |
Collapse
|
9
|
Zhang Y, Guo Y, Zhang Z, Chen M, Wang S, Zhang J. Universal framework for reconstructing complex networks and node dynamics from discrete or continuous dynamics data. Phys Rev E 2022; 106:034315. [PMID: 36266816 DOI: 10.1103/physreve.106.034315] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/20/2021] [Accepted: 06/15/2022] [Indexed: 06/16/2023]
Abstract
Many dynamical processes of complex systems can be understood as the dynamics of a group of nodes interacting on a given network structure. However, finding such interaction structure and node dynamics from time series of node behaviors is tough. Conventional methods focus on either network structure inference task or dynamics reconstruction problem, very few of them can work well on both. This paper proposes a universal framework for reconstructing network structure and node dynamics at the same time from observed time-series data of nodes. We use a differentiable Bernoulli sampling process to generate a candidate network structure, and we use neural networks to simulate the node dynamics based on the candidate network. We then adjust all the parameters with a stochastic gradient descent algorithm to maximize the likelihood function defined on the data. The experiments show that our model can recover various network structures and node dynamics at the same time with high accuracy. It can also work well on binary, discrete, and continuous time-series data, and the reconstruction results are robust against noise and missing information.
Collapse
Affiliation(s)
- Yan Zhang
- School of Systems Science, Beijing Normal University, Beijing 100875, China
| | - Yu Guo
- Software Institute, Nanjing University, Nanjing 210093, China
| | - Zhang Zhang
- School of Systems Science, Beijing Normal University, Beijing 100875, China
| | - Mengyuan Chen
- China TravelSky Mobile Technology Co., Ltd, Beijing 100029, China
| | - Shuo Wang
- School of Systems Science, Beijing Normal University, Beijing 100875, China
| | - Jiang Zhang
- School of Systems Science, Beijing Normal University, Beijing 100875, China; Swarma Research, Beijing 102308, China
| |
Collapse
|
10
|
Network structure from a characterization of interactions in complex systems. Sci Rep 2022; 12:11742. [PMID: 35817803 PMCID: PMC9273794 DOI: 10.1038/s41598-022-14397-2] [Citation(s) in RCA: 6] [Impact Index Per Article: 3.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/31/2022] [Accepted: 06/06/2022] [Indexed: 11/29/2022] Open
Abstract
Many natural and man-made complex dynamical systems can be represented by networks with vertices representing system units and edges the coupling between vertices. If edges of such a structural network are inaccessible, a widely used approach is to identify them with interactions between vertices, thereby setting up a functional network. However, it is an unsolved issue if and to what extent important properties of a functional network on the global and the local scale match those of the corresponding structural network. We address this issue by deriving functional networks from characterizing interactions in paradigmatic oscillator networks with widely-used time-series-analysis techniques for various factors that alter the collective network dynamics. Surprisingly, we find that particularly key constituents of functional networks—as identified with betweenness and eigenvector centrality—coincide with ground truth to a high degree, while global topological and spectral properties—clustering coefficient, average shortest path length, assortativity, and synchronizability—clearly deviate. We obtain similar concurrences for an empirical network. Our findings are of relevance for various scientific fields and call for conceptual and methodological refinements to further our understanding of the relationship between structure and function of complex dynamical systems.
Collapse
|
11
|
Haj Ali S, Hütt MT. Inferring missing edges in a graph from observed collective patterns. Phys Rev E 2022; 105:064610. [PMID: 35854582 DOI: 10.1103/physreve.105.064610] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 02/10/2022] [Accepted: 05/26/2022] [Indexed: 06/15/2023]
Abstract
Many real-life networks are incomplete. Dynamical observations can allow estimating missing edges. Such procedures, often summarized under the term 'network inference', typically evaluate the statistical correlations among pairs of nodes to determine connectivity. Here, we offer an alternative approach: completing an incomplete network by observing its collective behavior. We illustrate this approach for the case of patterns emerging in reaction-diffusion systems on graphs, where collective behaviors can be associated with eigenvectors of the network's Laplacian matrix. Our method combines a partial spectral decomposition of the network's Laplacian matrix with eigenvalue assignment by matching the patterns to the eigenvectors of the incomplete graph. We show that knowledge of a few collective patterns can allow the prediction of missing edges and that this result holds across a range of network architectures. We present a numerical case study using activator-inhibitor dynamics and we illustrate that the main requirement for the observed patterns is that they are not confined to subsets of nodes, but involve the whole network.
Collapse
Affiliation(s)
- Selim Haj Ali
- Department of Life Sciences and Chemistry, Jacobs University Bremen, D-28759 Bremen, Germany
| | - Marc-Thorsten Hütt
- Department of Life Sciences and Chemistry, Jacobs University Bremen, D-28759 Bremen, Germany
| |
Collapse
|
12
|
The brainstem connectome database. Sci Data 2022; 9:168. [PMID: 35414055 PMCID: PMC9005652 DOI: 10.1038/s41597-022-01219-3] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/29/2020] [Accepted: 02/25/2022] [Indexed: 11/29/2022] Open
Abstract
Connectivity data of the nervous system and subdivisions, such as the brainstem, cerebral cortex and subcortical nuclei, are necessary to understand connectional structures, predict effects of connectional disorders and simulate network dynamics. For that purpose, a database was built and analyzed which comprises all known directed and weighted connections within the rat brainstem. A longterm metastudy of original research publications describing tract tracing results form the foundation of the brainstem connectome (BC) database which can be analyzed directly in the framework neuroVIISAS. The BC database can be accessed directly by connectivity tables, a web-based tool and the framework. Analysis of global and local network properties, a motif analysis, and a community analysis of the brainstem connectome provides insight into its network organization. For example, we found that BC is a scale-free network with a small-world connectivity. The Louvain modularity and weighted stochastic block matching resulted in partially matching of functions and connectivity. BC modeling was performed to demonstrate signal propagation through the somatosensory pathway which is affected in Multiple sclerosis. Measurement(s) | brainstem | Technology Type(s) | tract tracing metastudy | Factor Type(s) | brain region | Sample Characteristic - Organism | Rattus rattus | Sample Characteristic - Environment | Experimental setup | Sample Characteristic - Location | Germany |
Collapse
|
13
|
Smirnov DA. Generative formalism of causality quantifiers for processes. Phys Rev E 2022; 105:034209. [PMID: 35428131 DOI: 10.1103/physreve.105.034209] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/08/2020] [Accepted: 03/01/2022] [Indexed: 06/14/2023]
Abstract
The concept of dynamical causal effect (DCE) is generalized and equipped with a formalism which allows one to formulate in a unified manner and interrelate a variety of causality quantifiers used in time series analysis. An elementary DCE from a subsystem Y to a subsystem X is defined within the stochastic dynamical systems framework as a response of a future X state to an appropriate variation of an initial (X,Y)-state distribution or a certain parameter of Y or of the coupling element Y→X; this response is quantified in a probabilistic sense via a certain distinction functional; elementary DCEs are assembled over a set of initial variations via an assemblage functional. To include all those aspects, a "triple brackets formula" for the general DCE is suggested and serves as a first principle to produce specific causality quantifiers as realizations of the general DCE. As an application, transfer entropy and Liang-Kleeman information flow are related surprisingly as opposite limit cases in a family of DCEs; it is shown that their "nats per time unit" may differ drastically. The suggested DCE viewpoint links any formal causality quantifier to "intervention-effect" experiments, i.e., future responses to initial variations, and so provides its dynamical interpretation, opening a way to its further physical interpretations in studies of physical systems.
Collapse
Affiliation(s)
- Dmitry A Smirnov
- Saratov Branch, Kotelnikov Institute of Radio Engineering and Electronics of the Russian Academy of Sciences, 38 Zelyonaya St., Saratov 410019, Russia
| |
Collapse
|
14
|
CoSpar identifies early cell fate biases from single-cell transcriptomic and lineage information. Nat Biotechnol 2022; 40:1066-1074. [DOI: 10.1038/s41587-022-01209-1] [Citation(s) in RCA: 8] [Impact Index Per Article: 4.0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/06/2021] [Accepted: 01/04/2022] [Indexed: 02/06/2023]
|
15
|
Sattari S, Basak US, James RG, Perrin LW, Crutchfield JP, Komatsuzaki T. Modes of information flow in collective cohesion. SCIENCE ADVANCES 2022; 8:eabj1720. [PMID: 35138896 PMCID: PMC8827646 DOI: 10.1126/sciadv.abj1720] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/25/2021] [Accepted: 12/20/2021] [Indexed: 05/23/2023]
Abstract
Pairwise interactions are fundamental drivers of collective behavior-responsible for group cohesion. The abiding question is how each individual influences the collective. However, time-delayed mutual information and transfer entropy, commonly used to quantify mutual influence in aggregated individuals, can result in misleading interpretations. Here, we show that these information measures have substantial pitfalls in measuring information flow between agents from their trajectories. We decompose the information measures into three distinct modes of information flow to expose the role of individual and group memory in collective behavior. It is found that decomposed information modes between a single pair of agents reveal the nature of mutual influence involving many-body nonadditive interactions without conditioning on additional agents. The pairwise decomposed modes of information flow facilitate an improved diagnosis of mutual influence in collectives.
Collapse
Affiliation(s)
- Sulimon Sattari
- Research Center of Mathematics for Social Creativity, Research Institute for Electronic Science, Hokkaido University Kita 20, Nishi 10, Kita-ku, Sapporo, Hokkaido 001-0020, Japan
| | - Udoy S. Basak
- Research Center of Mathematics for Social Creativity, Research Institute for Electronic Science, Hokkaido University Kita 20, Nishi 10, Kita-ku, Sapporo, Hokkaido 001-0020, Japan
- Pabna University of Science and Technology, Pabna 6600, Bangladesh
| | - Ryan G. James
- Reddit Inc., 420 Taylor Street, San Francisco, CA 94102, USA
- Department of Physics, Complexity Sciences Center, University of California, Davis, Davis, CA 95616, USA
| | - Louis W. Perrin
- Research Center of Mathematics for Social Creativity, Research Institute for Electronic Science, Hokkaido University Kita 20, Nishi 10, Kita-ku, Sapporo, Hokkaido 001-0020, Japan
- École Normale Supérieure de Rennes, Robert Schumann, Campus de, Av. de Ker Lann, 35170 Bruz, France
| | - James P. Crutchfield
- Department of Physics, Complexity Sciences Center, University of California, Davis, Davis, CA 95616, USA
| | - Tamiki Komatsuzaki
- Research Center of Mathematics for Social Creativity, Research Institute for Electronic Science, Hokkaido University Kita 20, Nishi 10, Kita-ku, Sapporo, Hokkaido 001-0020, Japan
- Institute for Chemical Reaction Design and Discovery (WPI-ICReDD), Hokkaido University Kita 21 Nishi 10, Kita-ku, Sapporo, Hokkaido 001-0021, Japan
- Graduate School of Chemical Sciences and Engineering Materials Chemistry and Energy Course, Hokkaido University Kita 13, Nishi 8, Kita-ku Sapporo, Hokkaido 060-0812, Japan
| |
Collapse
|
16
|
|
17
|
Raimondo S, De Domenico M. Measuring topological descriptors of complex networks under uncertainty. Phys Rev E 2021; 103:022311. [PMID: 33735966 DOI: 10.1103/physreve.103.022311] [Citation(s) in RCA: 4] [Impact Index Per Article: 1.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/04/2020] [Accepted: 01/13/2021] [Indexed: 11/07/2022]
Abstract
Revealing the structural features of a complex system from the observed collective dynamics is a fundamental problem in network science. To compute the various topological descriptors commonly used to characterize the structure of a complex system (e.g., the degree, the clustering coefficient, etc.), it is usually necessary to completely reconstruct the network of relations between the subsystems. Several methods are available to detect the existence of interactions between the nodes of a network. By observing some physical quantities through time, the structural relationships are inferred using various discriminating statistics (e.g., correlations, mutual information, etc.). In this setting, the uncertainty about the existence of the edges is reflected in the uncertainty about the topological descriptors. In this study, we propose a methodological framework to evaluate this uncertainty, replacing the topological descriptors, even at the level of a single node, with appropriate probability distributions, eluding the reconstruction phase. Our theoretical framework agrees with the numerical experiments performed on a large set of synthetic and real-world networks. Our results provide a grounded framework for the analysis and the interpretation of widely used topological descriptors, such as degree centrality, clustering, and clusters, in scenarios in which the existence of network connectivity is statistically inferred or when the probabilities of existence π_{ij} of the edges are known. To this purpose, we also provide a simple and mathematically grounded process to transform the discriminating statistics into the probabilities π_{ij}.
Collapse
Affiliation(s)
- Sebastian Raimondo
- CoMuNe Lab, Center for Information and Communication Technology, Fondazione Bruno Kessler, Via Sommarive 18, 38123 Povo (TN), Italy and Department of Mathematics, University of Trento, Via Sommarive 9, 38123 Povo (TN), Italy
| | - Manlio De Domenico
- CoMuNe Lab, Center for Information and Communication Technology, Fondazione Bruno Kessler, Via Sommarive 18, 38123 Povo (TN), Italy
| |
Collapse
|
18
|
Lehnertz K, Bröhl T, Rings T. The Human Organism as an Integrated Interaction Network: Recent Conceptual and Methodological Challenges. Front Physiol 2020; 11:598694. [PMID: 33408639 PMCID: PMC7779628 DOI: 10.3389/fphys.2020.598694] [Citation(s) in RCA: 17] [Impact Index Per Article: 4.3] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/25/2020] [Accepted: 11/30/2020] [Indexed: 12/30/2022] Open
Abstract
The field of Network Physiology aims to advance our understanding of how physiological systems and sub-systems interact to generate a variety of behaviors and distinct physiological states, to optimize the organism's functioning, and to maintain health. Within this framework, which considers the human organism as an integrated network, vertices are associated with organs while edges represent time-varying interactions between vertices. Likewise, vertices may represent networks on smaller spatial scales leading to a complex mixture of interacting homogeneous and inhomogeneous networks of networks. Lacking adequate analytic tools and a theoretical framework to probe interactions within and among diverse physiological systems, current approaches focus on inferring properties of time-varying interactions-namely strength, direction, and functional form-from time-locked recordings of physiological observables. To this end, a variety of bivariate or, in general, multivariate time-series-analysis techniques, which are derived from diverse mathematical and physical concepts, are employed and the resulting time-dependent networks can then be further characterized with methods from network theory. Despite the many promising new developments, there are still problems that evade from a satisfactory solution. Here we address several important challenges that could aid in finding new perspectives and inspire the development of theoretic and analytical concepts to deal with these challenges and in studying the complex interactions between physiological systems.
Collapse
Affiliation(s)
- Klaus Lehnertz
- Department of Epileptology, University of Bonn Medical Centre, Bonn, Germany
- Helmholtz Institute for Radiation and Nuclear Physics, University of Bonn, Bonn, Germany
- Interdisciplinary Center for Complex Systems, University of Bonn, Bonn, Germany
| | - Timo Bröhl
- Department of Epileptology, University of Bonn Medical Centre, Bonn, Germany
- Helmholtz Institute for Radiation and Nuclear Physics, University of Bonn, Bonn, Germany
| | - Thorsten Rings
- Department of Epileptology, University of Bonn Medical Centre, Bonn, Germany
- Helmholtz Institute for Radiation and Nuclear Physics, University of Bonn, Bonn, Germany
| |
Collapse
|
19
|
Porfiri M. Validity and Limitations of the Detection Matrix to Determine Hidden Units and Network Size from Perceptible Dynamics. PHYSICAL REVIEW LETTERS 2020; 124:168301. [PMID: 32383942 DOI: 10.1103/physrevlett.124.168301] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 11/06/2019] [Revised: 03/04/2020] [Accepted: 03/20/2020] [Indexed: 06/11/2023]
Abstract
Determining the size of a network dynamical system from the time series of some accessible units is a critical problem in network science. Recent work by Haehne et al. [Phys. Rev. Lett. 122, 158301 (2019).PRLTAO0031-900710.1103/PhysRevLett.122.158301] has presented a model-free approach to address this problem, by studying the rank of a detection matrix that collates sampled time series of perceptible nodes from independent experiments. Here, we unveil a profound connection between the rank of the detection matrix and the control-theoretic notion of observability, upon which we conclude when and how it is feasible to exactly infer the size of a network dynamical system.
Collapse
Affiliation(s)
- Maurizio Porfiri
- Department of Mechanical and Aerospace Engineering and Department of Biomedical Engineering, New York University, Tandon School of Engineering, Brooklyn, New York 11201, USA
| |
Collapse
|
20
|
Fujii K, Takeishi N, Hojo M, Inaba Y, Kawahara Y. Physically-interpretable classification of biological network dynamics for complex collective motions. Sci Rep 2020; 10:3005. [PMID: 32080208 PMCID: PMC7033192 DOI: 10.1038/s41598-020-58064-w] [Citation(s) in RCA: 6] [Impact Index Per Article: 1.5] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/23/2019] [Accepted: 12/13/2019] [Indexed: 11/09/2022] Open
Abstract
Understanding biological network dynamics is a fundamental issue in various scientific and engineering fields. Network theory is capable of revealing the relationship between elements and their propagation; however, for complex collective motions, the network properties often transiently and complexly change. A fundamental question addressed here pertains to the classification of collective motion network based on physically-interpretable dynamical properties. Here we apply a data-driven spectral analysis called graph dynamic mode decomposition, which obtains the dynamical properties for collective motion classification. Using a ballgame as an example, we classified the strategic collective motions in different global behaviours and discovered that, in addition to the physical properties, the contextual node information was critical for classification. Furthermore, we discovered the label-specific stronger spectra in the relationship among the nearest agents, providing physical and semantic interpretations. Our approach contributes to the understanding of principles of biological complex network dynamics from the perspective of nonlinear dynamical systems.
Collapse
Affiliation(s)
- Keisuke Fujii
- Graduate School of Informatics, Nagoya University, Nagoya, Japan. .,RIKEN Center for Advanced Intelligence Project, Tokyo, Japan.
| | - Naoya Takeishi
- RIKEN Center for Advanced Intelligence Project, Tokyo, Japan
| | - Motokazu Hojo
- RIKEN Center for Advanced Intelligence Project, Tokyo, Japan
| | - Yuki Inaba
- Japan Institute of Sports Sciences, Tokyo, Japan
| | - Yoshinobu Kawahara
- RIKEN Center for Advanced Intelligence Project, Tokyo, Japan.,Institute of Mathematics for Industry, Kyushu University, Fukuoka, Japan
| |
Collapse
|
21
|
Tokuda IT, Levnajic Z, Ishimura K. A practical method for estimating coupling functions in complex dynamical systems. PHILOSOPHICAL TRANSACTIONS. SERIES A, MATHEMATICAL, PHYSICAL, AND ENGINEERING SCIENCES 2019; 377:20190015. [PMID: 31656141 PMCID: PMC6833996 DOI: 10.1098/rsta.2019.0015] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.6] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Accepted: 09/02/2019] [Indexed: 06/10/2023]
Abstract
A foremost challenge in modern network science is the inverse problem of reconstruction (inference) of coupling equations and network topology from the measurements of the network dynamics. Of particular interest are the methods that can operate on real (empirical) data without interfering with the system. One such earlier attempt (Tokuda et al. 2007 Phys. Rev. Lett. 99, 064101. (doi:10.1103/PhysRevLett.99.064101)) was a method suited for general limit-cycle oscillators, yielding both oscillators' natural frequencies and coupling functions between them (phase equations) from empirically measured time series. The present paper reviews the above method in a way comprehensive to domain-scientists other than physics. It also presents applications of the method to (i) detection of the network connectivity, (ii) inference of the phase sensitivity function, (iii) approximation of the interaction among phase-coherent chaotic oscillators, and (iv) experimental data from a forced Van der Pol electric circuit. This reaffirms the range of applicability of the method for reconstructing coupling functions and makes it accessible to a much wider scientific community. This article is part of the theme issue 'Coupling functions: dynamical interaction mechanisms in the physical, biological and social sciences'.
Collapse
Affiliation(s)
- Isao T. Tokuda
- Department of Mechanical Engineering, Ritsumeikan University, Kusatsu, Japan
| | - Zoran Levnajic
- Complex Systems and Data Science Lab, Faculty of Information Studies in Novo Mesto, Novo Mesto, Slovenia
| | - Kazuyoshi Ishimura
- Department of Mechanical Engineering, Ritsumeikan University, Kusatsu, Japan
| |
Collapse
|
22
|
Peixoto TP. Network Reconstruction and Community Detection from Dynamics. PHYSICAL REVIEW LETTERS 2019; 123:128301. [PMID: 31633974 PMCID: PMC7226905 DOI: 10.1103/physrevlett.123.128301] [Citation(s) in RCA: 30] [Impact Index Per Article: 6.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 03/28/2019] [Revised: 05/21/2019] [Indexed: 05/06/2023]
Abstract
We present a scalable nonparametric Bayesian method to perform network reconstruction from observed functional behavior that at the same time infers the communities present in the network. We show that the joint reconstruction with community detection has a synergistic effect, where the edge correlations used to inform the existence of communities are also inherently used to improve the accuracy of the reconstruction which, in turn, can better inform the uncovering of communities. We illustrate the use of our method with observations arising from epidemic models and the Ising model, both on synthetic and empirical networks, as well as on data containing only functional information.
Collapse
Affiliation(s)
- Tiago P Peixoto
- Department of Network and Data Science, Central European University, H-1051 Budapest, Hungary
- ISI Foundation, Via Chisola 5, 10126 Torino, Italy
- Department of Mathematical Sciences, University of Bath, Claverton Down, Bath BA2 7AY, United Kingdom
| |
Collapse
|
23
|
Goetze F, Lai PY. Reconstructing positive and negative couplings in Ising spin networks by sorted local transfer entropy. Phys Rev E 2019; 100:012121. [PMID: 31499780 DOI: 10.1103/physreve.100.012121] [Citation(s) in RCA: 11] [Impact Index Per Article: 2.2] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 02/15/2019] [Indexed: 01/24/2023]
Abstract
We employ the sorted local transfer entropy (SLTE) to reconstruct the coupling strengths of Ising spin networks with positive and negative couplings (J_{ij}), using only the time-series data of the spins. The SLTE method is model-free in the sense that no knowledge of the underlying dynamics of the spin system is required and is applicable to a broad class of systems. Contrary to the inference of coupling from pairwise transfer entropy, our method can reliably distinguish spin pair interactions with positive and negative couplings. The method is tested for the inverse Ising problem for different J_{ij} distributions and various spin dynamics, including synchronous and asynchronous update Glauber dynamics and Kawasaki exchange dynamics. It is found that the pairwise SLTE is proportional to the pairwise coupling strength to a good extent for all cases studied. In addition, the reconstruction works well for both the equilibrium and nonequilibrium cases of the time-series data. Comparison to other inverse Ising problem approaches using mean-field equations is also discussed.
Collapse
Affiliation(s)
- Felix Goetze
- Department of Physics and Center for Complex Systems, National Central University, Chung-Li District, Taoyuan City 320, Taiwan, Republic of China and Molecular Science and Technology Program, Taiwan International Graduate Program, Academia Sinica, Taipei, Taiwan, Republic of China
| | - Pik-Yin Lai
- Department of Physics and Center for Complex Systems, National Central University, Chung-Li District, Taoyuan City 320, Taiwan, Republic of China and Molecular Science and Technology Program, Taiwan International Graduate Program, Academia Sinica, Taipei, Taiwan, Republic of China
| |
Collapse
|
24
|
Leguia MG, Levnajić Z, Todorovski L, Ženko B. Reconstructing dynamical networks via feature ranking. CHAOS (WOODBURY, N.Y.) 2019; 29:093107. [PMID: 31575127 DOI: 10.1063/1.5092170] [Citation(s) in RCA: 4] [Impact Index Per Article: 0.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 02/08/2019] [Accepted: 08/08/2019] [Indexed: 06/10/2023]
Abstract
Empirical data on real complex systems are becoming increasingly available. Parallel to this is the need for new methods of reconstructing (inferring) the structure of networks from time-resolved observations of their node-dynamics. The methods based on physical insights often rely on strong assumptions about the properties and dynamics of the scrutinized network. Here, we use the insights from machine learning to design a new method of network reconstruction that essentially makes no such assumptions. Specifically, we interpret the available trajectories (data) as "features" and use two independent feature ranking approaches-Random Forest and RReliefF-to rank the importance of each node for predicting the value of each other node, which yields the reconstructed adjacency matrix. We show that our method is fairly robust to coupling strength, system size, trajectory length, and noise. We also find that the reconstruction quality strongly depends on the dynamical regime.
Collapse
Affiliation(s)
- Marc G Leguia
- Faculty of Information Studies in Novo Mesto, Ljubljanska cesta 31a, SI-8000 Novo mesto, Slovenia
| | - Zoran Levnajić
- Faculty of Information Studies in Novo Mesto, Ljubljanska cesta 31a, SI-8000 Novo mesto, Slovenia
| | - Ljupčo Todorovski
- Department of Knowledge Technologies, Jožef Stefan Institute, Jamova cesta 39, SI-1000 Ljubljana, Slovenia
| | - Bernard Ženko
- Department of Knowledge Technologies, Jožef Stefan Institute, Jamova cesta 39, SI-1000 Ljubljana, Slovenia
| |
Collapse
|
25
|
Yao Z. Command of Collective Dynamics by Topological Defects in Spherical Crystals. PHYSICAL REVIEW LETTERS 2019; 122:228002. [PMID: 31283259 DOI: 10.1103/physrevlett.122.228002] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.2] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 03/06/2019] [Revised: 04/13/2019] [Indexed: 06/09/2023]
Abstract
Directing individual motions of many constituents to a coherent dynamical state is a fundamental challenge in multiple fields. Here, based on the spherical crystal model, we show that topological defects in particle arrays can be a crucial element in regulating collective dynamics. Specifically, we highlight the defect-driven synchronized breathing modes around disclinations and collective oscillations with strong connection to disruption of crystalline order. This work opens the promising possibility of an organizational principle based on topological defects, and may inspire new strategies for harnessing intriguing collective dynamics in extensive nonequilibrium systems.
Collapse
Affiliation(s)
- Zhenwei Yao
- School of Physics and Astronomy, and Institute of Natural Sciences, Shanghai Jiao Tong University, Shanghai 200240, China
| |
Collapse
|
26
|
Haehne H, Casadiego J, Peinke J, Timme M. Detecting Hidden Units and Network Size from Perceptible Dynamics. PHYSICAL REVIEW LETTERS 2019; 122:158301. [PMID: 31050518 DOI: 10.1103/physrevlett.122.158301] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 07/23/2018] [Revised: 02/12/2019] [Indexed: 06/09/2023]
Abstract
The number of units of a network dynamical system, its size, arguably constitutes its most fundamental property. Many units of a network, however, are typically experimentally inaccessible such that the network size is often unknown. Here we introduce a detection matrix that suitably arranges multiple transient time series from the subset of accessible units to detect network size via matching rank constraints. The proposed method is model-free, applicable across system types and interaction topologies, and applies to nonstationary dynamics near fixed points, as well as periodic and chaotic collective motion. Even if only a small minority of units is perceptible and for systems simultaneously exhibiting nonlinearities, heterogeneities, and noise, exact size detection is feasible. We illustrate applicability for a paradigmatic class of biochemical reaction networks.
Collapse
Affiliation(s)
- Hauke Haehne
- Institute of Physics and ForWind, University of Oldenburg, 26111 Oldenburg, Germany
| | - Jose Casadiego
- Chair for Network Dynamics, Institute for Theoretical Physics and Center for Advancing Electronics Dresden (cfaed), Technical University of Dresden, 01062 Dresden, Germany
| | - Joachim Peinke
- Institute of Physics and ForWind, University of Oldenburg, 26111 Oldenburg, Germany
| | - Marc Timme
- Chair for Network Dynamics, Institute for Theoretical Physics and Center for Advancing Electronics Dresden (cfaed), Technical University of Dresden, 01062 Dresden, Germany
| |
Collapse
|
27
|
Xiang BB, Ma C, Chen HS, Zhang HF. Reconstructing signed networks via Ising dynamics. CHAOS (WOODBURY, N.Y.) 2018; 28:123117. [PMID: 30599526 DOI: 10.1063/1.5053723] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 08/25/2018] [Accepted: 12/03/2018] [Indexed: 06/09/2023]
Abstract
Revealing unknown network structure from observed data is a fundamental inverse problem in network science. Current reconstruction approaches were mainly proposed to infer the unsigned networks. However, many social relationships, such as friends and foes, can be represented as signed social networks that contain positive and negative links. To the best of our knowledge, the method of reconstructing signed networks has not yet been developed. To this purpose, we develop a statistical inference approach to fully reconstruct the signed network structure (positive links, negative links, and nonexistent links) based on the Ising dynamics. By the theoretical analysis, we show that our approach can transfer the problem of maximum likelihood estimation into the problem of solving linear systems of equations, where the solution of the linear system of equations uncovers the neighbors and the signs of links of each node. The experimental results on both synthetic and empirical networks validate the reliability and efficiency of our method. Our study moves the first step toward reconstructing signed networks.
Collapse
Affiliation(s)
- Bing-Bing Xiang
- School of Mathematical Science, Anhui University, Hefei 230601, People's Republic of China
| | - Chuang Ma
- School of Mathematical Science, Anhui University, Hefei 230601, People's Republic of China
| | - Han-Shuang Chen
- School of Physics and Material Science, Anhui University, Hefei 230601, China
| | - Hai-Feng Zhang
- School of Mathematical Science, Anhui University, Hefei 230601, People's Republic of China
| |
Collapse
|
28
|
Basiri F, Casadiego J, Timme M, Witthaut D. Inferring power-grid topology in the face of uncertainties. Phys Rev E 2018; 98:012305. [PMID: 30110818 DOI: 10.1103/physreve.98.012305] [Citation(s) in RCA: 8] [Impact Index Per Article: 1.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/22/2017] [Indexed: 11/07/2022]
Abstract
We develop methods to efficiently reconstruct the topology and line parameters of a power grid from the measurement of nodal variables. We propose two compressed sensing algorithms that minimize the amount of necessary measurement resources by exploiting network sparsity, symmetry of connections, and potential prior knowledge about the connectivity. The algorithms are reciprocal to established state estimation methods, where nodal variables are estimated from few measurements given the network structure. Hence, they enable an advanced grid monitoring where both state and structure of a grid are subject to uncertainties or missing information.
Collapse
Affiliation(s)
- Farnaz Basiri
- Forschungszentrum Jülich, Institute for Energy and Climate Research - Systems Analysis and Technology Evaluation (IEK-STE), 52428 Jülich, Germany
| | - Jose Casadiego
- Chair for Network Dynamics, Center for Advancing Electronics Dresden (cfaed) and Institute of Theoretical Physics, Technical University of Dresden, 01062 Dresden, Germany.,Network Dynamics, Max Planck Institute for Dynamics and Self-Organization (MPIDS), Göttingen 37077, Germany
| | - Marc Timme
- Chair for Network Dynamics, Center for Advancing Electronics Dresden (cfaed) and Institute of Theoretical Physics, Technical University of Dresden, 01062 Dresden, Germany.,Network Dynamics, Max Planck Institute for Dynamics and Self-Organization (MPIDS), Göttingen 37077, Germany.,ETH Zurich Risk Center, 8092 Zurich, Switzerland
| | - Dirk Witthaut
- Forschungszentrum Jülich, Institute for Energy and Climate Research - Systems Analysis and Technology Evaluation (IEK-STE), 52428 Jülich, Germany.,Institute for Theoretical Physics, University of Cologne, 50937 Köln, Germany
| |
Collapse
|
29
|
Casadiego J, Maoutsa D, Timme M. Inferring Network Connectivity from Event Timing Patterns. PHYSICAL REVIEW LETTERS 2018; 121:054101. [PMID: 30118266 DOI: 10.1103/physrevlett.121.054101] [Citation(s) in RCA: 8] [Impact Index Per Article: 1.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 07/14/2017] [Revised: 03/05/2018] [Indexed: 06/08/2023]
Abstract
Reconstructing network connectivity from the collective dynamics of a system typically requires access to its complete continuous-time evolution, although these are often experimentally inaccessible. Here we propose a theory for revealing physical connectivity of networked systems only from the event time series their intrinsic collective dynamics generate. Representing the patterns of event timings in an event space spanned by interevent and cross-event intervals, we reveal which other units directly influence the interevent times of any given unit. For illustration, we linearize an event-space mapping constructed from the spiking patterns in model neural circuits to reveal the presence or absence of synapses between any pair of neurons, as well as whether the coupling acts in an inhibiting or activating (excitatory) manner. The proposed model-independent reconstruction theory is scalable to larger networks and may thus play an important role in the reconstruction of networks from biology to social science and engineering.
Collapse
Affiliation(s)
- Jose Casadiego
- Chair for Network Dynamics, Institute of Theoretical Physics and Center for Advancing Electronics Dresden (cfaed), Technical University of Dresden, 01062 Dresden, Germany
- Network Dynamics, Max Planck Institute for Dynamics and Self-Organization (MPIDS), 37077 Göttingen, Germany
| | - Dimitra Maoutsa
- Network Dynamics, Max Planck Institute for Dynamics and Self-Organization (MPIDS), 37077 Göttingen, Germany
- Artificial Intelligence Group, Department of Software Engineering and Theoretical Computer Science, Technical University of Berlin, 10587 Berlin, Germany
| | - Marc Timme
- Chair for Network Dynamics, Institute of Theoretical Physics and Center for Advancing Electronics Dresden (cfaed), Technical University of Dresden, 01062 Dresden, Germany
- Network Dynamics, Max Planck Institute for Dynamics and Self-Organization (MPIDS), 37077 Göttingen, Germany
- Bernstein Center for Computational Neuroscience (BCCN), 37077 Göttingen, Germany
- Max Planck Institute for the Physics of Complex Systems, 01069 Dresden, Germany
| |
Collapse
|
30
|
Arola-Fernández L, Díaz-Guilera A, Arenas A. Synchronization invariance under network structural transformations. Phys Rev E 2018; 97:060301. [PMID: 30011485 DOI: 10.1103/physreve.97.060301] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 02/09/2018] [Indexed: 06/08/2023]
Abstract
Synchronization processes are ubiquitous despite the many connectivity patterns that complex systems can show. Usually, the emergence of synchrony is a macroscopic observable; however, the microscopic details of the system, as, e.g., the underlying network of interactions, is many times partially or totally unknown. We already know that different interaction structures can give rise to a common functionality, understood as a common macroscopic observable. Building upon this fact, here we propose network transformations that keep the collective behavior of a large system of Kuramoto oscillators invariant. We derive a method based on information theory principles, that allows us to adjust the weights of the structural interactions to map random homogeneous in-degree networks into random heterogeneous networks and vice versa, keeping synchronization values invariant. The results of the proposed transformations reveal an interesting principle; heterogeneous networks can be mapped to homogeneous ones with local information, but the reverse process needs to exploit higher-order information. The formalism provides analytical insight to tackle real complex scenarios when dealing with uncertainty in the measurements of the underlying connectivity structure.
Collapse
Affiliation(s)
- Lluís Arola-Fernández
- Departament d'Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, 43007 Tarragona, Spain
| | - Albert Díaz-Guilera
- Departament de Física Fonamental, Universitat de Barcelona, Martí i Franquès 1, 08028 Barcelona, Spain
- Universitat de Barcelona Institute for Complex Systems (UBICS), Barcelona, Spain
| | - Alex Arenas
- Departament d'Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, 43007 Tarragona, Spain
| |
Collapse
|
31
|
Servadio JL, Convertino M. Optimal information networks: Application for data-driven integrated health in populations. SCIENCE ADVANCES 2018; 4:e1701088. [PMID: 29423440 PMCID: PMC5804584 DOI: 10.1126/sciadv.1701088] [Citation(s) in RCA: 25] [Impact Index Per Article: 4.2] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/12/2017] [Accepted: 01/05/2018] [Indexed: 05/30/2023]
Abstract
Development of composite indicators for integrated health in populations typically relies on a priori assumptions rather than model-free, data-driven evidence. Traditional variable selection processes tend not to consider relatedness and redundancy among variables, instead considering only individual correlations. In addition, a unified method for assessing integrated health statuses of populations is lacking, making systematic comparison among populations impossible. We propose the use of maximum entropy networks (MENets) that use transfer entropy to assess interrelatedness among selected variables considered for inclusion in a composite indicator. We also define optimal information networks (OINs) that are scale-invariant MENets, which use the information in constructed networks for optimal decision-making. Health outcome data from multiple cities in the United States are applied to this method to create a systemic health indicator, representing integrated health in a city.
Collapse
Affiliation(s)
- Joseph L. Servadio
- Division of Environmental Health Sciences, HumNat Lab, University of Minnesota School of Public Health, Minneapolis, MN 55455, USA
| | - Matteo Convertino
- Complexity Group, Information Communication Networks Lab, Division of Frontier Science and Media and Network Technologies, Graduate School of Information Science and Technology, Hokkaido University, Sapporo, Japan
- Global Institution for Collaborative Research and Education (Gi-CoRE) Station for Big Data and Cybersecurity, Hokkaido University, Sapporo, Japan
- Department of Electronics and Information Engineering, Faculty of Engineering, Hokkaido University, Sapporo, Japan
| |
Collapse
|
32
|
Model-free inference of direct network interactions from nonlinear collective dynamics. Nat Commun 2017; 8:2192. [PMID: 29259167 PMCID: PMC5736722 DOI: 10.1038/s41467-017-02288-4] [Citation(s) in RCA: 45] [Impact Index Per Article: 6.4] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/16/2017] [Accepted: 11/17/2017] [Indexed: 12/13/2022] Open
Abstract
The topology of interactions in network dynamical systems fundamentally underlies their function. Accelerating technological progress creates massively available data about collective nonlinear dynamics in physical, biological, and technological systems. Detecting direct interaction patterns from those dynamics still constitutes a major open problem. In particular, current nonlinear dynamics approaches mostly require to know a priori a model of the (often high dimensional) system dynamics. Here we develop a model-independent framework for inferring direct interactions solely from recording the nonlinear collective dynamics generated. Introducing an explicit dependency matrix in combination with a block-orthogonal regression algorithm, the approach works reliably across many dynamical regimes, including transient dynamics toward steady states, periodic and non-periodic dynamics, and chaos. Together with its capabilities to reveal network (two point) as well as hypernetwork (e.g., three point) interactions, this framework may thus open up nonlinear dynamics options of inferring direct interaction patterns across systems where no model is known. Network dynamical systems can represent the interactions involved in the collective dynamics of gene regulatory networks or metabolic circuits. Here Casadiego et al. present a method for inferring these types of interactions directly from observed time series without relying on their model.
Collapse
|
33
|
Lünsmann BJ, Kirst C, Timme M. Transition to reconstructibility in weakly coupled networks. PLoS One 2017; 12:e0186624. [PMID: 29053744 PMCID: PMC5650155 DOI: 10.1371/journal.pone.0186624] [Citation(s) in RCA: 6] [Impact Index Per Article: 0.9] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/28/2017] [Accepted: 10/04/2017] [Indexed: 11/25/2022] Open
Abstract
Across scientific disciplines, thresholded pairwise measures of statistical dependence between time series are taken as proxies for the interactions between the dynamical units of a network. Yet such correlation measures often fail to reflect the underlying physical interactions accurately. Here we systematically study the problem of reconstructing direct physical interaction networks from thresholding correlations. We explicate how local common cause and relay structures, heterogeneous in-degrees and non-local structural properties of the network generally hinder reconstructibility. However, in the limit of weak coupling strengths we prove that stationary systems with dynamics close to a given operating point transition to universal reconstructiblity across all network topologies.
Collapse
Affiliation(s)
- Benedict J. Lünsmann
- Network Dynamics, Max Planck Institute for Dynamics and Self-Organization (MPIDS), 37077 Göttingen, Germany
- Max Planck Institute for the Physics of Complex Systems (MPIPKS), 01187 Dresden, Germany
| | - Christoph Kirst
- Network Dynamics, Max Planck Institute for Dynamics and Self-Organization (MPIDS), 37077 Göttingen, Germany
- Rockefeller University, NY 10065-6399 New York, United States of America
| | - Marc Timme
- Network Dynamics, Max Planck Institute for Dynamics and Self-Organization (MPIDS), 37077 Göttingen, Germany
- Max Planck Institute for the Physics of Complex Systems (MPIPKS), 01187 Dresden, Germany
- Bernstein Center for Computational Neuroscience (BCCN), 37077 Göttingen, Germany
- Chair for Network Dynamics, Center for Advancing Electronics Dresden (cfaed) and Institute for Theoretical Physics, Technical University of Dresden, 01062 Dresden, Germany
- Department of Physics, Technical University of Darmstadt, 64289 Darmstadt, Germany
| |
Collapse
|