Inferring the internal interaction patterns of a complex dynamical system is a challenging problem. Traditional methods often rely on examining the correlations among the dynamical units. However, in systems such as transcription networks, one unit's variable is also correlated with the rate of change of another unit's variable. Inspired by this, we introduce the concept of derivative-variable correlation, and use it to design a new method of reconstructing complex systems (networks) from dynamical time series. Using a tunable observable as a parameter, the reconstruction of any system with known interaction functions is formulated via a simple matrix equation. We suggest a procedure aimed at optimizing the reconstruction from the time series of length comparable to the characteristic dynamical time scale. Our method also provides a reliable precision estimate. We illustrate the method's implementation via elementary dynamical models, and demonstrate its robustness to both model error and observation error.
COBISS.SI-ID: 2048303635
Two ordered Hamiltonian paths in the n-dimensional hypercube $Q_n$ are said to be independent if $i$-th vertices of the paths are distinct for every $1 \leq i \leq 2^n$. Similarly, two $s$-starting Hamiltonian cycles are independent if the $i$-th vertices of the cycle are distinct for every $2 \leq i \leq 2^n$. A set $S$ of Hamiltonian paths ($s$-starting Hamiltonian cycles) are mutually independent if every two paths (cycles, respectively) from $S$ are independent. We show that for $n$ pairs of adjacent vertices $w_i$ and $b_i$, there are $n$ mutually independent Hamiltonian paths with endvertices $w_i$, $b_i$ in $Q_n$. We also show that $Q_n$ contains $n-f$ fault-free mutually independent $s$-starting Hamiltonian cycles, for every set of $f \leq n-2$ faulty edges in $Q_n$ and every vertex $s$. This improves previously known results on the numbers of mutually independent Hamiltonian paths and cycles in the hypercube with faulty edges.
COBISS.SI-ID: 26622247
Sophisticated methods for analysing complex networks promise to be of great benefit to almost all scientific disciplines, yet they elude us. In this work, we make fundamental methodological advances to rectify this. We discover that the interaction between a small number of roles, played by nodes in a network, can characterize a network%s structure and also provide a clear real-world interpretation. Given this insight, we develop a framework for analysing and comparing networks, which outperforms all existing ones. We demonstrate its strength by uncovering novel relationships between seemingly unrelated networks, such as Facebook, metabolic, and protein structure networks. We also use it to track the dynamics of the world trade network, showing that a countrys role of a broker between non-trading countries indicates economic prosperity, whereas peripheral roles are associated with poverty. This result, though intuitive, has escaped all existing frameworks. Finally, our approach translates network topology into everyday language, bringing network analysis closer to domain scientists.
COBISS.SI-ID: 2048292371
Motivated by questions about square-free monomial ideals in polynomial rings, C. A. Francisco et al. [Discrete Math. 310, No. 15--16, 2176--2182 (2010)] conjectured that for every positive integer $k$ and every $k$-critical (i.e., critically $k$-chromatic) graph, there is a set of vertices whose replication produces a ($k+1$)-critical graph. (The replication of a set $W$ of vertices of a graph is the operation that adds a copy of each vertex $w$ in $W$, one at a time, and connects it to $w$ and all its neighbours.) We disprove the conjecture by providing an infinite family of counterexamples. Furthermore, the smallest member of the family answers a question of Herzog and Hibi concerning the depth functions of square-free monomial ideals in polynomial rings, and a related question on the persistence property of such ideals.
COBISS.SI-ID: 16920665
We present an application and analysis of a visualization method for measure-preserving dynamical systems introduced by I. Mezić and A. Banaszuk [Physica D 197, 101 (2004)], based on frequency analysis and Koopman operator theory. This extends our earlier work on visualization of ergodic partition [Z. Levnajić and I. Mezić, Chaos 20, 033114 (2010)]. Our method employs the concept of Fourier time average [I. Mezić and A. Banaszuk, Physica D 197, 101 (2004)], and is realized as a computational algorithm for visualization of periodic and quasi-periodic sets in the phase space. The complement of periodic phase space partition contains chaotic zone, and we show how to identify it. The range of method's applicability is illustrated using well-known Chirikov standard map, while its potential in illuminating higher-dimensional dynamics is presented by studying the Froeschlé map and the Extended Standard Map.
COBISS.SI-ID: 2048289026