Search

We prove that transport in the phase space of the "most strongly chaotic" dynamical systems has three different stages. Consider a finite Markov partition (coarse graining) $\xi$ of the phase space of such a system. In the first short times interval there is a hierarchy with respect to the values of the first passage probabilities for the elements of $\xi$ and therefore finite time predictions can be made about which element of the Markov partition trajectories will be most likely to hit first at a given moment. In the third long times interval, which goes to infinity, there is an opposite hierarchy of the first passage probabilities for the elements of $\xi$ and therefore again finite time predictions can be made. In the second intermediate times interval there is no hierarchy in the set of all elements of the Markov partition. We also obtain estimates on the length of the short times interval and show that its length is growing with refinement of the Markov partition which shows that practically only this interval should be taken into account in many cases. These results demonstrate that finite time predictions for the evolution of strongly chaotic dynamical systems are possible. In particular, one can predict that an orbit is more likely to first enter one subset of phase space than another at a given moment in time. Moreover, these results suggest an algorithm which accelerates the process of escape through "holes" in the phase space of dynamical systems with strongly chaotic behavior.

It is well known that typical Hamiltonian systems have divided phase space consisting of regions with regular dynamics on KAM tori and region(s) with chaotic dynamics called chaotic sea(s). This complex structure makes rigorous analysis of such systems virtually impossible and significantly complicates numerical exploration of their dynamical properties. In this paper we outline a new approach for the analysis of Hamiltonian systems with divided phase space. These systems are approximated by a sequence of Hamiltonian systems having an increasing (but finite) number of KAM islands. The islands in the approximating systems are sub-islands of the islands in the initial system with an infinite number of KAM-islands. We apply this approach to two-dimensional billiards and demonstrate that it works. In particular the statistical characteristics of the approximating systems tend to the ones for the whole system when the number of islands in the approximating systems grows. Therefore our approach opens up a new way for numerical and analytical studies of the dynamics of Hamiltonian systems with divided phase space., Comment: 8 pages (RevTex), 9 figures; version as accepted by Experimental Mathematics

Some basic aspects of the recently discovered phenomenon of local immunodeficiency (Skums et al. [1]) generated by antigenic cooperation in cross-immunoreactivity (CR) networks are investigated. We prove that local immunodeficiency (LI) that is stable under perturbations already occurs in very small networks and under general conditions on their parameters. Therefore our results are applicable not only to Hepatitis C where CR networks are known to be large (Skums et al. [1]), but also to other diseases with CR. A major necessary feature of such networks is the non-homogeneity of their topology. It is also shown that one can construct larger CR networks with stable LI by using small networks with stable LI as their building blocks. Our results imply that stable LI occurs in networks with quite general topology. In particular, the scale-free property of a CR network, assumed in Skums et al. [1], is not required.

The method of isospectral network reduction allows one the ability to reduce a network while preserving the network’s spectral structure. In this paper we describe a number of recent applications of the theory of isospectral reductions. This includes finding hidden structures, specifically latent symmetries, in networks, uncovering different network hierarchies, and simultaneously determining different network cores. We also specify how such reductions can be interpreted as dynamical systems and describe the type of dynamics such systems have. Additionally, we show how the recent theory of equitable decompositions can be paired with the method of isospectral reductions to decompose networks.

This paper analyzes the role of neutral viruses in the phenomenon of local immunodeficiency. We show that, even in the absence of altruistic viruses, neutral viruses can support the existence of persistent viruses and thus local immunodeficiency. However, in all such cases neutral viruses can maintain only bounded (relatively small) concentration of persistent viruses. Moreover, in all such cases the state of local immunodeficiency could only be marginally stable, while it is known that altruistic viruses can maintain stable local immunodeficiency. We also present an absolutely minimal cross-immunoreactivity network where a stable and robust state of local immunodeficiency can be maintained. It is now a challenge to synthetic biology to build such small networks with stable local immunodeficiency. Another important challenge for biology is to understand which types of viruses can play a role of persistent, altruistic and neutral ones and whether a role which a given virus plays depends on the structure (topology) of a given cross-immunoreactivity network.

We consider chaotic (hyperbolic) dynamical systems which have a generating Markov partition. Then, open dynamical systems are built by making one element of a Markov partition a hole through which orbits escape. We compare various estimates of the escape rate which correspond to a physical picture of leaking in the entire phase space. Moreover, we uncover a reason why the escape rate is faster than expected, which is the convexity of the function defining escape rate. Exact computations are present for the skewed tent map and Arnold's cat map., 14 pages, 1 figure

Recently were introduced physical billiards where a moving particle is a hard sphere rather than a point as in standard mathematical billiards. It has been shown that in the same billiard tables the physical billiards may have totally different dynamics than mathematical billiards. This difference appears if the boundary of a billiard table has visible singularities (internal corners if the billiard table is two-dimensional), i.e. the particle may collide with these singular points. Here, we consider the collision of a hard ball with a visible singular point and demonstrate that the motion of the smooth ball after collision with a visible singular point is indeed the one that was used in the studies of physical billiards. So such collision is equivalent to the elastic reflection of hard ball's center off a sphere with the center at the singular point and the same radius as the radius of the moving particle., 8 pages, 4 figures

Fractals are geometric objects that are self-similar at different scales and whose geometric dimensions differ from so-called fractal dimensions. Fractals describe complex continuous structures in nature. Although indications of self-similarity and fractality of complex networks has been previously observed, it is challenging to adapt the machinery from the theory of fractality of continuous objects to discrete objects such as networks. In this article, we identify and study fractal networks using the innate methods of graph theory and combinatorics. We establish analogues of topological (Lebesgue) and fractal (Hausdorff) dimensions for graphs and demonstrate that they are naturally related to known graph-theoretical characteristics: rank dimension and product dimension. Our approach reveals how self-similarity and fractality of a network are defined by a pattern of overlaps between densely connected network communities. It allows us to identify fractal graphs, explore the relations between graph fractality, graph colourings and graph descriptive complexity, and analyse the fractality of several classes of graphs and network models, as well as of a number of real-life networks. We demonstrate the application of our framework in evolutionary biology and virology by analysing networks of viral strains sampled at different stages of evolution inside their hosts. Our methodology revealed gradual self-organization of intra-host viral populations over the course of infection and their adaptation to the host environment. The obtained results lay a foundation for studying fractal properties of complex networks using combinatorial methods and algorithms.

Background RNA viruses mutate at extremely high rates, forming an intra-host viral population of closely related variants, which allows them to evade the host’s immune system and makes them particularly dangerous. Viral outbreaks pose a significant threat for public health, and, in order to deal with it, it is critical to infer transmission clusters, i.e., decide whether two viral samples belong to the same outbreak. Next-generation sequencing (NGS) can significantly help in tackling outbreak-related problems. While NGS data is first obtained as short reads, existing methods rely on assembled sequences. This requires reconstruction of the entire viral population, which is complicated, error-prone and time-consuming. Results The experimental validation using sequencing data from HCV outbreaks shows that the proposed algorithm can successfully identify genetic relatedness between viral populations, infer transmission direction, transmission clusters and outbreak sources, as well as decide whether the source is present in the sequenced outbreak sample and identify it. Conclusions Introduced algorithm allows to cluster genetically related samples, infer transmission directions and predict sources of outbreaks. Validation on experimental data demonstrated that algorithm is able to reconstruct various transmission characteristics. Advantage of the method is the ability to bypass cumbersome read assembly, thus eliminating the chance to introduce new errors, and saving processing time by allowing to use raw NGS reads.

We consider a physical Ehrenfests' Wind-Tree model where a moving particle is a hard ball rather than (mathematical) point particle. We demonstrate that a physical periodic Wind-Tree model is dynamically richer than a physical or mathematical periodic Lorentz gas. Namely, the physical Wind-Tree model may have diffusive behavior as the Lorentz gas does, but it has more superdiffusive regimes than the Lorentz gas. The new superdiffusive regime where the diffusion coefficient D(t)~(ln t)^2 of dynamics seems to be never observed before in any model., Comment: 21 pages, 9 figures

One of the most important features observed in real networks is that, as a network’s topology evolves so does the network’s ability to perform various complex tasks. To explain this, it has also been observed that as a network grows certain subnetworks begin to specialize the function(s) they perform. Herein, we introduce a class of models of network growth based on this notion of specialization and show that as a network is specialized using this method its topology becomes increasingly sparse, modular and hierarchical, each of which are important properties observed in real networks. This procedure is also highly flexible in that a network can be specialized over any subset of its elements. This flexibility allows those studying specific networks the ability to search for mechanisms that describe their growth. For example, we find that by randomly selecting these elements a network’s topology acquires some of the most well-known properties of real networks including the small-world property, disassortativity and a right-skewed degree distribution. Beyond this, we show how this model can be used to generate networks with real-world like clustering coefficients and power-law degree distributions, respectively. As far as the authors know, this is the first such class of models that can create an increasingly modular and hierarchical network topology with these properties.

Isospectral transformations (IT) of matrices and networks allow for compression of either object while keeping all the information about their eigenvalues and eigenvectors. We analyze here what happens to generalized eigenvectors under isospectral transformations and to what extent the initial network can be reconstructed from its compressed image under IT. We also generalize and essentially simplify the proof that eigenvectors are invariant under isospectral transformations and generalize and clarify the notion of spectral equivalence of networks.

We explain and justify that the only mechanisms of chaotic dynamics for billiards are dispersing and defocusing. We also introduce boomerang billiards which dynamics demonstrate that two rather broadly accepted views about some features of nonlinear dynamics are actually wrong. Namely correlations in billiards having focusing components of the boundary can decay exponentially, and continuous time correlations for a billiard flow may decay faster than discrete time correlations for a billiard map.

We review the current state of a fundamental problem of rigorous derivation of transport processes in classical statistical mechanics from classical mechanics. Such derivations for diffusion and momentum transport (viscosities) were obtained for minimal models of these processes involving one and two particles respectively. However, a minimal model which demonstrates heat conductivity contains three particles. Its rigorous analysis is currently out of reach for existing mathematical techniques. The gas of localized balls is widely accepted as a basis for a simplest model for derivation of Fourier’s law. We suggest a modification of the localized balls gas and argue that this gas of localized activated balls is a good candidate to rigorously prove Fourier’s law. In particular, hyperbolicity is derived for a reduced version of this model.

One of the hallmarks of real networks is their ability to perform increasingly complex tasks as their topology evolves. To explain this, it has been observed that as a network grows certain subsets of the network begin to specialize the function(s) they perform. A recent model of network growth based on this notion of specialization has been able to reproduce some of the most well-known topological features found in real-world networks including right-skewed degree distributions, the small world property, modular as well as hierarchical topology, etc. Here we describe how specialization under this model also effects the spectral properties of a network. This allows us to give conditions under which a network is able to maintain its dynamics as its topology evolves. Specifically, we show that if a network is intrinsically stable, which is a stronger version of the standard notion of global stability, then the network maintains this type of dynamics as the network evolves. This is one of the first steps toward unifying the rigorous study of the two types of dynamics exhibited by networks. These are the \emph{dynamics of} a network, which is the study of the topological evolution of the network's structure, modeled here by the process of network specialization, and the \emph{dynamics on} a network, which is the changing state of the network elements, where the type of dynamics we consider is global stability. The main examples we apply our results to are recurrent neural networks, which are the basis of certain types of machine learning algorithms., Comment: 40 pages, 8 figures

In the recently developed theory of isospectral transformations of networks isospectral compressions are performed with respect to some chosen characteristics (attributes) of the network’s nodes (edges). Each isospectral compression (when a certain characteristic is fixed) defines a dynamical system on the space of all networks. It is shown that any orbit of such dynamical system which starts at any finite network (as the initial point of this orbit) converges to an attractor. This attractor is a smaller network where the chosen characteristic has the same value for all nodes (or edges). We demonstrate that isospectral compressions of one and the same network defined by different characteristics of nodes (or edges) may converge to the same as well as to different attractors. It is also shown that a collection of networks may be spectrally equivalent with respect to some network characteristic but nonequivalent with respect to another. These results suggest a new constructive approach which allows us to analyze and compare the topologies of different networks.

We employ the recently developed theory of isospectral network reductions to analyze multi-mode social networks. This procedure allows us to uncover the hierarchical structure of the networks we consider as well as the hierarchical structure of each mode of the network. Additionally, by performing a dynamical analysis of these networks we are able to analyze the evolution of their structure allowing us to find a number of other network features. We apply both of these approaches to the Southern Women Data Set, one of the most studied social networks and demonstrate that these techniques provide new information, which complements previous findings., 17 pages, 5 figures, 5 tables

Motivation Genomic analysis has become one of the major tools for disease outbreak investigations. However, existing computational frameworks for inference of transmission history from viral genomic data often do not consider intra-host diversity of pathogens and heavily rely on additional epidemiological data, such as sampling times and exposure intervals. This impedes genomic analysis of outbreaks of highly mutable viruses associated with chronic infections, such as human immunodeficiency virus and hepatitis C virus, whose transmissions are often carried out through minor intra-host variants, while the additional epidemiological information often is either unavailable or has a limited use. Results The proposed framework QUasispecies Evolution, Network-based Transmission INference (QUENTIN) addresses the above challenges by evolutionary analysis of intra-host viral populations sampled by deep sequencing and Bayesian inference using general properties of social networks relevant to infection dissemination. This method allows inference of transmission direction even without the supporting case-specific epidemiological information, identify transmission clusters and reconstruct transmission history. QUENTIN was validated on experimental and simulated data, and applied to investigate HCV transmission within a community of hosts with high-risk behavior. It is available at https://github.com/skumsp/QUENTIN. Supplementary information Supplementary data are available at Bioinformatics online.

The dynamics of most real networks are time delayed. These time delays are important as they can often have a destabilizing effect on the network’s dynamics. Here we introduce the notion of intrinsic stability, which is stronger than the standard notion of stability used in the study of network dynamics or more generally in the study of multidimensional systems. The difference between a stable and an intrinsically stable network is that an intrinsically stable network maintains its (intrinsic) stability as nondistributed time-delays are incorporated into or removed from the network. Importantly, determining whether a network is intrinsic stability is fairly easy for concrete systems. Therefore, one can analyze the stability of a time-delayed network by analyzing the stability of the much simpler undelayed version of the network. One can simplify this analysis even further by removing the network’s implicit time-delays, which further reduces the network to a lower-dimensional system which can be used to gain improved stability estimates of the original unreduced network. A network can also be expanded in ways that preserves its intrinsic stability, which suggests how a network with an evolving structure can maintain its stability as it grows. Thus, intrinsic stability is the property that ensures the stability not only of a network but also of its reductions, expansions, and its time-delayed variants. We illustrate these results and techniques on various examples of Cohen–Grossberg neural networks.

We briefly review a history of the impact of the famous 1963 paper by E Lorenz on hydrodynamics, physics and mathematics communities on both sides of the iron curtain. This paper was an attempt to apply the ideas and methods of dynamical systems theory to the problem of weather forecast. Its major discovery was the phenomenon of chaos in dissipative dynamical systems which makes such forecasts rather problematic, if at all possible. In this connection we present some recent results which demonstrate that both a short-term and a long-term forecast are actually possible for the most chaotic dynamical (as well as for the most random, like IID and Markov chain) systems. Moreover, there is a sharp transition between the time interval where one may use a short-term forecast and the times where a long-term forecast is applicable. Finally we discuss how these findings could be incorporated into the forecast strategy outlined in the Lorenz's paper.

In standard (mathematical) billiards a point particle moves uniformly in a billiard table with elastic reflections off the boundary. We show that in transition from mathematical billiards to physical billiards, where a finite size hard sphere moves at the same billiard table, virtually anything may happen. Namely a non-chaotic billiard may become chaotic and vice versa. Moreover, both these transitions may occur softly, i.e. for any (arbitrarily small) positive value of the radius of a physical particle, as well, as by a "hard" transition when radius of the physical particle must exceed some critical strictly positive value. Such transitions may change a phase portrait of a mathematical billiard locally as well as completely (globally). These results are somewhat unexpected because for all standard examples of billiards their dynamics remains absolutely the same after transition from a point particle to a finite size ("physical") particle. Moreover we show that a character of dynamics may change several times when the size of particle is increasing.

We consider sticky sets in the phase space of circular mushroom billiards, which are referred to in physics literature as MUPOs (marginally unstable periodic orbits). An exact description of the set of parameters (widths of the mushrooms’ stems) without or with a finite set of MUPOs is given. It is shown that there exist a continuum of MUPOless parameters. We also estimate from above a number of MUPOs which exist for widths of the mushroom’s stem which correspond to rational numbers and present a simple approach for finding mushroom billiards without MUPOs.

This paper deals with the global stability of time-delayed dynamical networks. We show that for a time-delayed dynamical network with non-distributed delays the network and the corresponding non-delayed network are both either globally stable or unstable. We demonstrate that this may not be the case if the network's delays are distributed. The main tool in our analysis is a new procedure of dynamical network restrictions. This procedure is useful in that it allows for improved estimates of a dynamical network's global stability. Moreover, it is a computationally simpler and much more effective means of analyzing the stability of dynamical networks than the procedure of isospectral network expansions introduced in [Isospectral graph transformations, spectral equivalence, and global stability of dynamical networks. Nonlinearity, 25 (2012) 211-254]. The effectiveness of our approach is illustrated by applications to various classes of Cohen-Grossberg neural networks., Comment: 32 pages, 9 figures

In this paper, we study coupled map networks over arbitrary finite graphs. An estimate from below for a topological entropy of a perturbed coupled map network is obtained via a topological entropy of an unperturbed network by making use of the covering relations for coupled map networks. The result is quite general; in particular, nonlinear coupling is allowed and no assumptions of hyperbolicity of the local dynamics are made.

Via the process of isospectral graph reduction the adjacency matrix of a graph can be reduced to a smaller matrix while its spectrum is preserved up to some known set. It is then possible to estimate the spectrum of the original matrix by considering Gershgorin-type estimates associated with the reduced matrix. The main result of this paper is that eigenvalue estimates associated with Gershgorin, Brauer, Brualdi, and Varga improve as the matrix size is reduced. Moreover, given that such estimates improve with each successive reduction, it is also possible to estimate the eigenvalues of a matrix with increasing accuracy by repeated use of this process., 32 pages

In this paper we present a general procedure that allows for the reduction or expansion of any network (considered as a weighted graph). This procedure maintains the spectrum of the network's adjacency matrix up to a set of eigenvalues known beforehand from its graph structure. This procedure can be used to establish new equivalence relations on the class of all weighted graphs (networks) where two graphs are equivalent if they can be reduced to the same graph. Additionally, dynamical networks (or any finite dimensional, discrete time dynamical system) can be analysed using isospectral transformations. By doing so we obtain stronger results regarding the global stability (strong synchronization) of dynamical networks when compared with other standard methods.

It is well known that the distributions of hitting times in Markov chains are quite irregular, unless the limit as time tends to infinity is considered. We show that nevertheless for a typical finite irreducible Markov chain and for nondegenerate initial distributions the tails of the distributions of the hitting times for the states of a Markov chain can be ordered, i.e., they do not overlap after a certain finite moment of time. If one considers instead each state of a Markov chain as a source rather than a sink then again the states can generically be ordered according to their efficiency. The mechanisms underlying these two orderings are essentially different though., 12 pages, 1 figure

We investigated the biological significance of path lengths in 12 protein-protein interaction (PPI) networks. We put forward three predictions, based on the idea that biological complexity influences path lengths. First, at the network level, path lengths are generally longer in PPIs than in random networks. Second, this pattern is more pronounced in more complex organisms. Third, within a PPI network, path lengths of individual proteins are biologically significant. We found that in 11 of the 12 species, average path lengths in PPI networks are significantly longer than those in randomly rewired networks. The PPI network of the malaria parasite Plasmodium falciparum, however, does not exhibit deviation from rewired networks. Furthermore, eukaryotic PPIs exhibit significantly greater deviation from randomly rewired networks than prokaryotic PPIs. Thus our study highlights the potentially meaningful variation in path lengths of PPI networks. Moreover, node eccentricity, defined as the longest path from a protein to others, is significantly correlated with the levels of gene expression and dispensability in the yeast PPI network. We conclude that biological complexity influences both global and local properties of path lengths in PPI networks. Investigating variation of path lengths may provide new tools to analyze the evolution of functional modules in biological systems.

A natural question of how the survival probability depends upon a position of a hole was seemingly never addressed in the theory of open dynamical systems. We found that this dependency could be very essential. The main results are related to the holes with equal sizes (measure) in the phase space of strongly chaotic maps. Take in each hole a periodic point of minimal period. Then the faster escape occurs through the hole where this minimal period assumes its maximal value. The results are valid for all finite times (starting with the minimal period) which is unusual in dynamical systems theory where typically statements are asymptotic when time tends to infinity. It seems obvious that the bigger the hole is the faster is the escape through that hole. Our results demonstrate that generally it is not true, and that specific features of the dynamics may play a role comparable to the size of the hole.

Dynamical networks are characterized by 1) their topology (structure of the graph of interactions among the elements of a network); 2) the interactions between the elements of the network; 3) the intrinsic (local) dynamics of the elements of the network. A general approach to studying the commulative effect of all these three factors on the evolution of networks of a very general type has been developed in [1]. Besides, in this paper there were obtained sufficient conditions for a global stability (generalized strong synchronization) of networks with an arbitrary topology and the dynamics which is a composition (action of one after another) of a local dynamics of the elements of a network and of the interactions between these elements. Here we extend the results of [1] on global stability (generalized strong synchronization) to the case of a general dynamics in discrete time dynamical networks and to general dynamical networks with continuous time.

We study the process of escape of orbits through a hole in the phase space of a dynamical system generated by a chaotic map of an interval. If this hole is an element of Markov partition we are able to use the machinery of symbolic dynamics and estimate the probability of an orbit to escape at the instant of time n in terms of the topological pressure over corresponding symbolic dynamical systems. We obtain exact formulae allowing us to compare different holes according to their ability to support escaping flow of orbits. These results are applicable to the classification of vertices of dynamical networks in terms of the loads on nodes and edges of a network.