We study the symmetry properties of the spectra of normalized Laplacians on signed graphs. We find a new machinery that generates symmetric spectra for signed graphs, which includes bipartiteness of unsigned graphs as a special case. Moreover, we prove a fundamental connection between the symmetry of the spectrum and the existence of damped two-periodic solutions for the discrete-time heat equation on the graph.
We introduce a family of multi-way Cheeger-type constants ${h_k^{sigma}, k=1,2,ldots, n}$ on a signed graph $Gamma=(G,sigma)$ such that $h_k^{sigma}=0$ if and only if $Gamma$ has $k$ balanced connected components. These constants are switching invariant and bring together in a unified viewpoint a number of important graph-theoretical concepts, including the classical Cheeger constant, those measures of bipartiteness introduced by Desai-Rao, Trevisan, Bauer-Jost, respectively, on unsigned graphs,, and the frustration index (originally called the line index of balance by Harary) on signed graphs. We further unify the (higher-order or improved) Cheeger and dual Cheeger inequalities for unsigned graphs as well as the underlying algorithmic proof techniques by establishing their correspondi
We use symbolic dynamics to study discrete-time dynamical systems with multiple time delays. We exploit the concept of avoiding sets, which arise from specific non-generating partitions of the phase space and restrict the occurrence of certain symbol sequences related to the characteristics of the dynamics. In particular, we show that the resulting forbidden sequences are closely related to the time delays in the system. We present two applications to coupled map lattices, namely (1) detecting synchronization and (2) determining unknown values of the transmission delays in networks with possibly directed and weighted connections and measurement noise. The method is applicable to multi-dimensional as well as set-valued maps, and to networks with time-varying delays and connection structure.
We study synchronization of non-diffusively coupled map networks with arbitrary network topologies, where the connections between different units are, in general, not symmetric and can carry both positive and negative weights. We show that, in contrast to diffusively coupled networks, the synchronous behavior of a non-diffusively coupled network can be dramatically different from the behavior of its constituent units. In particular, we show that chaos can emerge as synchronized behavior although the dynamics of individual units are very simple. Conversely, individually chaotic units can display simple behavior when the network synchronizes. We give a synchronization criterion that depends on the spectrum of the generalized graph Laplacian, as well as the dynamical properties of the individual units and the interaction function. This general result will be applied to coupled systems of tent and logistic maps and to two models of neuronal dynamics. Our approach yields an analytical understanding of how simple model neurons can produce complex collective behavior through the coordination of their actions.
We consider complete synchronization of identical maps coupled through a general interaction function and in a general network topology where the edges may be directed and may carry both positive and negative weights. We define mixed transverse exponents and derive sufficient conditions for local complete synchronization. The general non-diffusive coupling scheme can lead to new synchronous behavior, in networks of identical units, that cannot be produced by single units in isolation. In particular, we show that synchronous chaos can emerge in networks of simple units. Conversely, in networks of chaotic units simple synchronous dynamics can emerge; that is, chaos can be suppressed through synchrony.
The stability of functional differential equations under delayed feedback is investigated near a Hopf bifurcation. Necessary and sufficient conditions are derived for the stability of the equilibrium solution using averaging theory. The results are used to compare delayed versus undelayed feedback, as well as discrete versus distributed delays. Conditions are obtained for which delayed feedback with partial state information can yield stability where undelayed feedback is ineffective. Furthermore, it is shown that if the feedback is stabilizing (respectively, destabilizing), then a discrete delay is locally the most stabilizing (resp., destabilizing) one among delay distributions having the same mean. The result also holds globally if one considers delays that are symmetrically distributed about their mean.
Complexity of dynamical networks can arise not only from the complexity of the topological structure but also from the time evolution of the topology. In this paper, we study the synchronous motion of coupled maps in time-varying complex networks both analytically and numerically. The temporal variation is rather general and formalized as being driven by a metric dynamical system. Four network models are discussed in detail in which the interconnections between vertices vary through time randomly. These models are 1) i.i.d. sequences of random graphs with fixed wiring probability, 2) groups of graphs with random switches between the individual graphs, 3) graphs with temporary random failures of nodes, and 4) the meet-for-dinner model where the vertices are randomly grouped. We show that the temporal variation and randomness of the connection topology can enhance synchronizability in many cases; however, there are also instances where they reduce synchronizability. In analytical terms, the Hajnal diameter of the coupling matrix sequence is presented as a measure for the synchronizability of the graph topology. In topological terms, the decisive criterion for synchronization of coupled chaotic maps is that the union of the time-varying graphs contains a spanning tree.
Time-delay systems are, in many ways, a natural set of dynamical systems for natural scientists to study because they form an interface between abstract mathematics and data. However, they are complicated because past states must be sensibly incorporated into the dynamical system. The primary goal of this paper is to begin to isolate and understand the effects of adding time-delay coordinates to a dynamical system. The key results include (i) an analytical understanding regarding extreme points of a time-delay dynamical system framework including an invariance of entropy and the variance of the Kaplan-Yorke formula with simple time re-scalings; (ii) computational results from a time-delay mapping that forms a path between dynamical systems dependent upon the most distant and the most recent past; (iii) the observation that non-trivial mixing of past states can lead to high-dimensional, high-entropy dynamics that are not easily reduced to low-dimensional dynamical systems; (iv) the observed phase transition (bifurcation) between low-dimensional, reducible dynamics and high or infinite-dimensional dynamics; and (v) a convergent scaling of the distribution of Lyapunov exponents, suggesting that the infinite limit of delay coordinates in systems such are the ones we study will result in a continuous or (dense) point spectrum.
We consider synchronization of weighted networks, possibly with asymmetrical connections. We show that the synchronizability of the networks cannot be directly inferred from their statistical properties. Small local changes in the network structure can sensitively affect the eigenvalues relevant for synchronization, while the gross statistical network properties remain essentially unchanged. Consequently, commonly used statistical properties, including the degree distribution, degree homogeneity, average degree, average distance, degree correlation, and clustering coefficient, can fail to characterize the synchronizability of networks.
