1
|
Zamora-López G, Gilson M. An integrative dynamical perspective for graph theory and the analysis of complex networks. CHAOS (WOODBURY, N.Y.) 2024; 34:041501. [PMID: 38625080 DOI: 10.1063/5.0202241] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 07/01/2023] [Accepted: 02/25/2024] [Indexed: 04/17/2024]
Abstract
Built upon the shoulders of graph theory, the field of complex networks has become a central tool for studying real systems across various fields of research. Represented as graphs, different systems can be studied using the same analysis methods, which allows for their comparison. Here, we challenge the widespread idea that graph theory is a universal analysis tool, uniformly applicable to any kind of network data. Instead, we show that many classical graph metrics-including degree, clustering coefficient, and geodesic distance-arise from a common hidden propagation model: the discrete cascade. From this perspective, graph metrics are no longer regarded as combinatorial measures of the graph but as spatiotemporal properties of the network dynamics unfolded at different temporal scales. Once graph theory is seen as a model-based (and not a purely data-driven) analysis tool, we can freely or intentionally replace the discrete cascade by other canonical propagation models and define new network metrics. This opens the opportunity to design-explicitly and transparently-dedicated analyses for different types of real networks by choosing a propagation model that matches their individual constraints. In this way, we take stand that network topology cannot always be abstracted independently from network dynamics but shall be jointly studied, which is key for the interpretability of the analyses. The model-based perspective here proposed serves to integrate into a common context both the classical graph analysis and the more recent network metrics defined in the literature which were, directly or indirectly, inspired by propagation phenomena on networks.
Collapse
Affiliation(s)
- Gorka Zamora-López
- Center for Brain and Cognition, Pompeu Fabra University, 08005 Barcelona, Spain
- Department of Information and Communication Technologies, Pompeu Fabra University, 08018 Barcelona, Spain
| | - Matthieu Gilson
- Institut des Neurosciences de la Timone, CNRS-AMU, 13005 Marseille, France
- Institut des Neurosciences des Systemes, INSERM-AMU, 13005 Marseille, France
| |
Collapse
|
2
|
Zhao Y, Gu C, Yang H. Visibility-graphlet approach to the output series of a Hodgkin-Huxley neuron. CHAOS (WOODBURY, N.Y.) 2021; 31:043102. [PMID: 34251267 DOI: 10.1063/5.0018359] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 06/14/2020] [Accepted: 03/10/2021] [Indexed: 06/13/2023]
Abstract
The output signals of neurons that are exposed to external stimuli are of great importance for brain functionality. Traditional time-series analysis methods have provided encouraging results; however, the associated patterns and their correlations in the output signals of neurons are masked by statistical procedures. Here, graphlets are employed to extract the local temporal patterns and the transitions between them from the output signals when neurons are exposed to external stimuli with selected stimulating periods. A transition network is defined where the node is the graphlet and the direct link is the transition between two successive graphlets. The transition-network structure is affected by the simulating periods. When the stimulating period moves close to an integer multiple of the neuronal intrinsic period, only the backbone or core survives, while the other linkages disappear. Interestingly, the size of the backbone (number of nodes) equals the multiple. The transition-network structure is conservative within each stimulating region, which is defined as the range between two successive integer multiples. Nevertheless, the backbone or detailed structure is significantly altered between different stimulating regions. This alternation is induced primarily from a total of 12 active linkages. Hence, the transition network shows the structure of cross correlations in the output time-series for a single neuron.
Collapse
Affiliation(s)
- Yuanying Zhao
- Business School, University of Shanghai for Science and Technology, Shanghai 200093, People's Republic of China
| | - Changgui Gu
- Business School, University of Shanghai for Science and Technology, Shanghai 200093, People's Republic of China
| | - Huijie Yang
- Business School, University of Shanghai for Science and Technology, Shanghai 200093, People's Republic of China
| |
Collapse
|
3
|
Mutua S, Gu C, Yang H. Visibility graphlet approach to chaotic time series. CHAOS (WOODBURY, N.Y.) 2016; 26:053107. [PMID: 27249947 DOI: 10.1063/1.4951681] [Citation(s) in RCA: 5] [Impact Index Per Article: 0.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 06/05/2023]
Abstract
Many novel methods have been proposed for mapping time series into complex networks. Although some dynamical behaviors can be effectively captured by existing approaches, the preservation and tracking of the temporal behaviors of a chaotic system remains an open problem. In this work, we extended the visibility graphlet approach to investigate both discrete and continuous chaotic time series. We applied visibility graphlets to capture the reconstructed local states, so that each is treated as a node and tracked downstream to create a temporal chain link. Our empirical findings show that the approach accurately captures the dynamical properties of chaotic systems. Networks constructed from periodic dynamic phases all converge to regular networks and to unique network structures for each model in the chaotic zones. Furthermore, our results show that the characterization of chaotic and non-chaotic zones in the Lorenz system corresponds to the maximal Lyapunov exponent, thus providing a simple and straightforward way to analyze chaotic systems.
Collapse
Affiliation(s)
- Stephen Mutua
- Business School, University of Shanghai for Science and Technology, Shanghai 200093, People's Republic of China
| | - Changgui Gu
- Business School, University of Shanghai for Science and Technology, Shanghai 200093, People's Republic of China
| | - Huijie Yang
- Business School, University of Shanghai for Science and Technology, Shanghai 200093, People's Republic of China
| |
Collapse
|
4
|
Stephen M, Gu C, Yang H. Visibility Graph Based Time Series Analysis. PLoS One 2015; 10:e0143015. [PMID: 26571115 PMCID: PMC4646626 DOI: 10.1371/journal.pone.0143015] [Citation(s) in RCA: 27] [Impact Index Per Article: 3.0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/23/2015] [Accepted: 10/29/2015] [Indexed: 11/19/2022] Open
Abstract
Network based time series analysis has made considerable achievements in the recent years. By mapping mono/multivariate time series into networks, one can investigate both it's microscopic and macroscopic behaviors. However, most proposed approaches lead to the construction of static networks consequently providing limited information on evolutionary behaviors. In the present paper we propose a method called visibility graph based time series analysis, in which series segments are mapped to visibility graphs as being descriptions of the corresponding states and the successively occurring states are linked. This procedure converts a time series to a temporal network and at the same time a network of networks. Findings from empirical records for stock markets in USA (S&P500 and Nasdaq) and artificial series generated by means of fractional Gaussian motions show that the method can provide us rich information benefiting short-term and long-term predictions. Theoretically, we propose a method to investigate time series from the viewpoint of network of networks.
Collapse
Affiliation(s)
- Mutua Stephen
- Business School, University of Shanghai for Science and Technology, Shanghai 200093, China
- Computer Science Department, Masinde Muliro University of Science and Technology, P.O. Box 190-50100, Kakamega, Kenya
| | - Changgui Gu
- Business School, University of Shanghai for Science and Technology, Shanghai 200093, China
| | - Huijie Yang
- Business School, University of Shanghai for Science and Technology, Shanghai 200093, China
| |
Collapse
|
5
|
Judd K. Networked dynamical systems with linear coupling: synchronisation patterns, coherence and other behaviours. CHAOS (WOODBURY, N.Y.) 2013; 23:043112. [PMID: 24387551 DOI: 10.1063/1.4826697] [Citation(s) in RCA: 5] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 06/03/2023]
Abstract
Many physical and biochemical systems are well modelled as a network of identical non-linear dynamical elements with linear coupling between them. An important question is how network structure affects chaotic dynamics, for example, by patterns of synchronisation and coherence. It is shown that small networks can be characterised precisely into patterns of exact synchronisation and large networks characterised by partial synchronisation at the local and global scale. Exact synchronisation modes are explained using tools of symmetry groups and invariance, and partial synchronisation is explained by finite-time shadowing of exact synchronisation modes.
Collapse
Affiliation(s)
- Kevin Judd
- School of Mathematics and Statistics, University of Western Australia, Perth, Western Australia, 6009
| |
Collapse
|
6
|
Newton PK, Mason J, Bethel K, Bazhenova L, Nieva J, Norton L, Kuhn P. Spreaders and sponges define metastasis in lung cancer: a Markov chain Monte Carlo mathematical model. Cancer Res 2013; 73:2760-9. [PMID: 23447576 PMCID: PMC3644026 DOI: 10.1158/0008-5472.can-12-4488] [Citation(s) in RCA: 62] [Impact Index Per Article: 5.6] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/16/2022]
Abstract
The classic view of metastatic cancer progression is that it is a unidirectional process initiated at the primary tumor site, progressing to variably distant metastatic sites in a fairly predictable, although not perfectly understood, fashion. A Markov chain Monte Carlo mathematical approach can determine a pathway diagram that classifies metastatic tumors as "spreaders" or "sponges" and orders the timescales of progression from site to site. In light of recent experimental evidence highlighting the potential significance of self-seeding of primary tumors, we use a Markov chain Monte Carlo (MCMC) approach, based on large autopsy data sets, to quantify the stochastic, systemic, and often multidirectional aspects of cancer progression. We quantify three types of multidirectional mechanisms of progression: (i) self-seeding of the primary tumor, (ii) reseeding of the primary tumor from a metastatic site (primary reseeding), and (iii) reseeding of metastatic tumors (metastasis reseeding). The model shows that the combined characteristics of the primary and the first metastatic site to which it spreads largely determine the future pathways and timescales of systemic disease.
Collapse
Affiliation(s)
- Paul K Newton
- Department of Aerospace & Mechanical Engineering, Viterbi School of Engineering, University of Southern California, Los Angles 90089, USA.
| | | | | | | | | | | | | |
Collapse
|
7
|
Li P, Zhang K, Xu X, Zhang J, Small M. Reexamination of explosive synchronization in scale-free networks: the effect of disassortativity. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2013; 87:042803. [PMID: 23679469 DOI: 10.1103/physreve.87.042803] [Citation(s) in RCA: 12] [Impact Index Per Article: 1.1] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 06/19/2012] [Revised: 02/25/2013] [Indexed: 06/02/2023]
Abstract
Previous work [J. Gómez-Gardeñes, S. Gómez, A. Arenas, and Y. Moreno, Phys. Rev. Lett. 106, 128701 (2011)] has reported that explosive synchronization can be achieved in heterogeneous networks with a microscopic correlation between the structural and dynamical properties of the networks. This phenomenon, however, cannot be observed in all heterogeneous networks even if this structure-dynamics correlation is preserved. It is therefore of particular interest to identify the general topological factors that can induce the first order synchronization transition and to understand the underlying mechanisms. Here we investigate this issue using the scenario of the smooth transformation from homogeneous Erdös-Rènyi networks to heterogeneous Barabàsi-Albert networks. Specifically, we scrutinize how local and global properties of the network change during this process, and how these properties are associated with the emergence of explosive synchronization. We find that the local degree-degree correlation in the network contributes primarily to explosive synchronization, other than the global topological property or starlike subgraphs. We furthermore demonstrate that the degree of disassortative mixing also has a great effect in the presence of explosive synchronization.
Collapse
Affiliation(s)
- Ping Li
- Center for Networked Systems, School of Computer Science, Southwest Petroleum University, Chengdu 610500, PR China.
| | | | | | | | | |
Collapse
|
8
|
Leyva I, Navas A, Sendiña-Nadal I, Buldú JM, Almendral JA, Boccaletti S. Synchronization waves in geometric networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2011; 84:065101. [PMID: 22304141 DOI: 10.1103/physreve.84.065101] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.2] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 09/07/2011] [Indexed: 05/31/2023]
Abstract
We report synchronization of networked excitable nodes embedded in a metric space, where the connectivity properties are mostly determined by the distance between units. Such a high clustered structure, combined with the lack of long-range connections, prevents full synchronization and yields instead the emergence of synchronization waves. We show that this regime is optimal for information transmission through the system, as it enhances the options of reconstructing the topology from the dynamics. Measurements of topological and functional centralities reveal that the wave-synchronization state allows detection of the most structurally relevant nodes from a single observation of the dynamics, without any a priori information on the model equations ruling the evolution of the ensemble.
Collapse
Affiliation(s)
- I Leyva
- Complex Systems Group, Rey Juan Carlos University, Móstoles E-28999, Madrid, Spain
| | | | | | | | | | | |
Collapse
|
9
|
Zhuo Z, Cai SM, Fu ZQ, Zhang J. Hierarchical organization of brain functional networks during visual tasks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2011; 84:031923. [PMID: 22060419 DOI: 10.1103/physreve.84.031923] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.2] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 01/24/2011] [Revised: 08/14/2011] [Indexed: 05/31/2023]
Abstract
The functional network of the brain is known to demonstrate modular structure over different hierarchical scales. In this paper, we systematically investigated the hierarchical modular organizations of the brain functional networks that are derived from the extent of phase synchronization among high-resolution EEG time series during a visual task. In particular, we compare the modular structure of the functional network from EEG channels with that of the anatomical parcellation of the brain cortex. Our results show that the modular architectures of brain functional networks correspond well to those from the anatomical structures over different levels of hierarchy. Most importantly, we find that the consistency between the modular structures of the functional network and the anatomical network becomes more pronounced in terms of vision, sensory, vision-temporal, motor cortices during the visual task, which implies that the strong modularity in these areas forms the functional basis for the visual task. The structure-function relationship further reveals that the phase synchronization of EEG time series in the same anatomical group is much stronger than that of EEG time series from different anatomical groups during the task and that the hierarchical organization of functional brain network may be a consequence of functional segmentation of the brain cortex.
Collapse
Affiliation(s)
- Zhao Zhuo
- Department of Electronic Science and Technology, University of Science and Technology of China, Hefei, Anhui 230026, People's Republic of China
| | | | | | | |
Collapse
|
10
|
Campbell C, Thakar J, Albert R. Network analysis reveals cross-links of the immune pathways activated by bacteria and allergen. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2011; 84:031929. [PMID: 22060425 DOI: 10.1103/physreve.84.031929] [Citation(s) in RCA: 7] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/26/2011] [Indexed: 05/31/2023]
Abstract
Many biological networks are characterized by directed edges that represent either activating (positive) or inhibiting (negative) regulation. Most graph-theoretical methods used to study biological networks either disregard this important feature, or study the role of edge sign only in the context of small subgraphs called motifs. Here, we develop path-based measures which capture, on continuous scales spanning negative and positive values, both the long- and short-range regulatory relationships among node pairs. These measures also allow the quantification of each node's overall influence on the whole network and its susceptibility to regulation by the rest of the network. We apply the measures to a network representation of the mammalian immune response to simultaneous attack by allergen and respiratory bacteria. Although allergen and bacteria elicit different immune pathways, there is significant overlap (cross-talk) and feedback between these pathways. We identify key immune components in this cross-talk; particularly revealing the importance of natural killer cells as a key regulatory target in the cross-talk.
Collapse
Affiliation(s)
- Colin Campbell
- Department of Physics, Pennsylvania State University, University Park, Pennsylvania 16803, USA.
| | | | | |
Collapse
|
11
|
Yuan WJ, Zhou C. Interplay between structure and dynamics in adaptive complex networks: emergence and amplification of modularity by adaptive dynamics. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2011; 84:016116. [PMID: 21867266 DOI: 10.1103/physreve.84.016116] [Citation(s) in RCA: 9] [Impact Index Per Article: 0.7] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 12/01/2010] [Revised: 05/27/2011] [Indexed: 05/23/2023]
Abstract
Many real networks display modular organization, which can influence dynamical clustering on the networks. Therefore, there have been proposals put forth recently to detect network communities by using dynamical clustering. In this paper, we study how the feedback from dynamical clusters can shape the network connection weights with a weight-adaptation scheme motivated from Hebbian learning in neural systems. We show that such a scheme generically leads to the formation of community structure in globally coupled chaotic oscillators. The number of communities in the adaptive network depends on coupling strength c and adaptation strength r. In a modular network, the adaptation scheme will enhance the intramodule connection weights and weaken the intermodule connection strengths, generating effectively separated dynamical clusters that coincide with the communities of the network. In this sense, the modularity of the network is amplified by the adaptation. Thus, for a network with a strong community structure, the adaptation scheme can evidently reflect its community structure by the resulting amplified weighted network. For a network with a weak community structure, the statistical properties of synchronization clusters from different realizations can be used to amplify the modularity of the communities so that they can be detected reliably by the other traditional algorithms.
Collapse
Affiliation(s)
- Wu-Jie Yuan
- Department of Physics, Hong Kong Baptist University, Kowloon Tong, Hong Kong, China
| | | |
Collapse
|
12
|
Levnajić Z. Emergent multistability and frustration in phase-repulsive networks of oscillators. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2011; 84:016231. [PMID: 21867297 DOI: 10.1103/physreve.84.016231] [Citation(s) in RCA: 7] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/04/2011] [Indexed: 05/31/2023]
Abstract
The collective dynamics of oscillator networks with phase-repulsive coupling is studied, considering various network sizes and topologies. The notion of link frustration is introduced to characterize and quantify the network dynamical states. In opposition to widely studied phase-attractive case, the properties of final dynamical states in our model critically depend on the network topology. In particular, each network's total frustration value is intimately related to its topology. Moreover, phase-repulsive networks in general display multiple final frustration states, whose statistical and stability properties are uniquely identifying them.
Collapse
Affiliation(s)
- Zoran Levnajić
- Department of Physics and Astronomy, University of Potsdam, Potsdam, Germany
| |
Collapse
|
13
|
Zeng A, Lü L. Coarse graining for synchronization in directed networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2011; 83:056123. [PMID: 21728621 DOI: 10.1103/physreve.83.056123] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.2] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 11/30/2010] [Revised: 02/21/2011] [Indexed: 05/31/2023]
Abstract
Coarse-graining model is a promising way to analyze and visualize large-scale networks. The coarse-grained networks are required to preserve statistical properties as well as the dynamic behaviors of the initial networks. Some methods have been proposed and found effective in undirected networks, while the study on coarse-graining directed networks lacks of consideration. In this paper we proposed a path-based coarse-graining (PCG) method to coarse grain the directed networks. Performing the linear stability analysis of synchronization and numerical simulation of the Kuramoto model on four kinds of directed networks, including tree networks and variants of Barabási-Albert networks, Watts-Strogatz networks, and Erdös-Rényi networks, we find our method can effectively preserve the network synchronizability.
Collapse
Affiliation(s)
- An Zeng
- Department of Physics, University of Fribourg, Chemin du Musée 3, CH-1700 Fribourg, Switzerland
| | | |
Collapse
|
14
|
Zhang J, Xu XK, Li P, Zhang K, Small M. Node importance for dynamical process on networks: a multiscale characterization. CHAOS (WOODBURY, N.Y.) 2011; 21:016107. [PMID: 21456849 DOI: 10.1063/1.3553644] [Citation(s) in RCA: 7] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 05/30/2023]
Abstract
Defining the importance of nodes in a complex network has been a fundamental problem in analyzing the structural organization of a network, as well as the dynamical processes on it. Traditionally, the measures of node importance usually depend either on the local neighborhood or global properties of a network. Many real-world networks, however, demonstrate finely detailed structure at various organization levels, such as hierarchy and modularity. In this paper, we propose a multiscale node-importance measure that can characterize the importance of the nodes at varying topological scale. This is achieved by introducing a kernel function whose bandwidth dictates the ranges of interaction, and meanwhile, by taking into account the interactions from all the paths a node is involved. We demonstrate that the scale here is closely related to the physical parameters of the dynamical processes on networks, and that our node-importance measure can characterize more precisely the node influence under different physical parameters of the dynamical process. We use epidemic spreading on networks as an example to show that our multiscale node-importance measure is more effective than other measures.
Collapse
Affiliation(s)
- Jie Zhang
- Centre for Computational Systems Biology, Fudan University, Shanghai 200433, People's Republic of China
| | | | | | | | | |
Collapse
|