Graph operations and synchronization of complex networks

Controllability of N-Duplication Corona Product Networks With Laplacian Dynamics

This article studies the controllability of a new composite network generated by two smaller scale factor networks via the Corona product with Laplacian dynamics. First, the eigenvalues and corresponding eigenvectors of a new composite network-the -duplication Corona product network-are derived by some properties of its factor networks. Second, a necessary and sufficient algebra-based criterion for the controllability of such network is established based on the Popov-Belevitch-Hautus (PBH) test. Furthermore, the weights on edges between the different factor networks are considered. Finally, several examples are presented to demonstrate the effectiveness of our results applied to the unmanned aerial vehicle (UAV) formation.

Maximizing synchronizability of networks with community structure based on node similarity

In reality, numerous networks have a community structure characterized by dense intra-community connections and sparse inter-community connections. In this article, strategies are proposed to enhance synchronizability of such networks by rewiring a certain number of inter-community links, where the research scope is complete synchronization on undirected and diffusively coupled dynamic networks. First, we explore the effect of adding links between unconnected nodes with different similarity levels on network synchronizability and find that preferentially adding links between nodes with lower similarity can improve network synchronizability more than that with higher similarity, where node similarity is measured by our improved Asymmetric Katz (AKatz) and Asymmetric Leicht-Holme-Newman (ALHNII) methods from the perspective of link prediction. Additional simulations demonstrate that the node similarity-based link-addition strategy is more effective in enhancing network synchronizability than the node centrality-based methods. Furthermore, we apply the node similarity-based link-addition or deletion strategy as the valid criteria to the rewiring process of inter-community links and then propose a Node Similarity-Based Rewiring Optimization (NSBRO) algorithm, where the optimization process is realized by a modified simulated annealing technique. Simulations show that our proposed method performs better in optimizing synchronization of such networks compared with other centrality-based heuristic methods. Finally, simulations on the Rössler system indicate that the network structure optimized by the NSBRO algorithm also leads to better synchronizability of coupled oscillators.

Multiparametric EEG analysis of brain network dynamics during neonatal seizures

BACKGROUND

One of the most challenging issues in paediatric neurology is the diagnosis of neonatal seizures, whose delayed treatment may affect the neurodevelopment of the newborn. Formulation of the correct diagnosis is conditioned by the high number of perceptually or automatically detected false positives.

NEW METHOD

New methodologies are proposed to assess neonatal seizures trend over time. Our approach is based on the analysis of standardized trends of two properties of the brain network: the Synchronizabilty (S) and the degree of phase synchronicity given by the Circular Omega Complexity (COC). Qualitative and quantitative methods based on network dynamics allow differentiating seizure events from interictal periods and seizure-free patients.

RESULTS

The methods were tested on a public dataset of labelled neonatal seizures. COC shows significant differences among seizure and non-seizure events (p-value <0.001, Cohen's d 0.86). Combining S and COC in standardized temporal instants provided a reliable description of the physiological behaviour of the brain's network during neonatal seizures.

COMPARISON WITH EXISTING METHOD(S)

Few of the existing network methods propose an operative way for carrying their analytical approach into the diagnostic process of neonatal seizures. Our methods offer a simple representation of brain network dynamics easily implementable and understandable also by less experienced staff.

CONCLUSIONS

Our findings confirm the usefulness of the evaluation of brain network dynamics over time for a better understanding and interpretation of the complex mechanisms behind neonatal seizures. The proposed methods could also reliably support existing seizure detectors as a post-processing step in doubtful cases.

Functional connectivity of major depression disorder using ongoing EEG during music perception

OBJECTIVE

The functional connectivity (FC) of major depression disorder (MDD) has not been well studied under naturalistic and continuous stimuli conditions. In this study, we investigated the frequency-specific FC of MDD patients exposed to conditions of music perception using ongoing electroencephalogram (EEG).

METHODS

First, we applied the phase lag index (PLI) method to calculate the connectivity matrices and graph theory-based methods to measure the topology of brain networks across different frequency bands. Then, classification methods were adopted to identify the most discriminate frequency band for the diagnosis of MDD.

RESULTS

During music perception, MDD patients exhibited a decreased connectivity pattern in the delta band but an increased connectivity pattern in the beta band. Healthy people showed a left hemisphere-dominant phenomenon, but MDD patients did not show such a lateralized effect. Support vector machine (SVM) achieved the best classification performance in the beta frequency band with an accuracy of 89.7%, sensitivity of 89.4% and specificity of 89.9%.

CONCLUSIONS

MDD patients exhibited an altered FC in delta and beta bands, and the beta band showed a superiority in the diagnosis of MDD.

SIGNIFICANCE

Our study provided a promising reference for the diagnosis of MDD, and revealed a new perspective for understanding the topology of MDD brain networks during music perception.

Association schemes perspective of microbubble cluster in ultrasonic fields

Dynamics of a cluster of chaotic oscillators on a network are studied using coupled maps. By introducing the association schemes, we obtain coupling strength in the adjacency matrices form, which satisfies Markov matrices property. We remark that in general, the stability region of the cluster of oscillators at the synchronization state is characterized by Lyapunov exponent which can be defined based on the N-coupled map. As a detailed physical example, dynamics of microbubble cluster in an ultrasonic field are studied using coupled maps. Microbubble cluster dynamics have an indicative highly active nonlinear phenomenon, were not easy to be explained. In this paper, a cluster of microbubbles with a thin elastic shell based on the modified Keller-Herring equation in an ultrasonic field is demonstrated in the framework of the globally coupled map. On the other hand, a relation between the microbubble elements is replaced by a relation between the vertices. Based on this method, the stability region of microbubbles pulsations at complete synchronization state has been obtained analytically. In this way, distances between microbubbles as coupling strength play the crucial role. In the stability region, we thus observe that the problem of study of dynamics of N-microbubble oscillators reduce to that of a single microbubble. Therefore, the important parameters of the isolated microbubble such as applied pressure, driving frequency and the initial radius have effective behavior on the synchronization state.

Design of coupling parameters for inducing amplitude death in Cartesian product networks of delayed coupled oscillators

The present study investigates amplitude death in Cartesian product networks of two subnetworks, where each subnetwork has a different coupling delay. The property of the Cartesian product helps us to analyze the stability of amplitude death. Our analysis reveals that amplitude death can occur for long coupling delays if there is a suitable difference in the coupling delays in the two subnetworks. Furthermore, based on the edge theorem in robust control theory, we propose two design procedures of coupling parameters for inducing amplitude death in the Cartesian product networks. Our procedures do not require any information of topologies of the subnetworks. The validity of these procedures is numerically confirmed.

Turing instabilities on Cartesian product networks

The problem of Turing instabilities for a reaction-diffusion system defined on a complex Cartesian product network is considered. To this end we operate in the linear regime and expand the time dependent perturbation on a basis formed by the tensor product of the eigenvectors of the discrete Laplacian operators, associated to each of the individual networks that build the Cartesian product. The dispersion relation which controls the onset of the instability depends on a set of discrete wavelengths, the eigenvalues of the aforementioned Laplacians. Patterns can develop on the Cartesian network, if they are supported on at least one of its constitutive sub-graphs. Multiplex networks are also obtained under specific prescriptions. In this case, the criteria for the instability reduce to compact explicit formulae. Numerical simulations carried out for the Mimura-Murray reaction kinetics confirm the adequacy of the proposed theory.

Simulation of the Dynamics of Bacterial Quorum Sensing

Quorum sensing (QS) is a signaling mechanism that pathogenic bacteria use to communicate and synchronize the production of exofactors to attack their hosts. Understanding and controlling QS is an important step towards a possible solution to the growing problem of antibiotic resistance. QS is a cooperative effort of a bacterial population in which some of the bacteria do not participate. This phenomenon is usually studied using game theory and the non-participating bacteria are modeled as cheaters that exploit the production of common goods (exofactors) by other bacteria. Here, we take a different approach to study the QS dynamics of a growing bacterial population. We model the bacterial population as a growing graph and use spectral graph theory to compute the evolution of its synchronizability. We also treat each bacterium as a source of signaling molecules and use the diffusion equation to compute the signaling molecule distribution. We formulate a cost function based on Lagrangian dynamics that combines the time-like synchronization with the space-like diffusion of signaling molecules. Our results show that the presence of non-participating bacteria improves the homogeneity of the signaling molecule distribution preventing thus an early onset of exofactor production and has a positive effect on the optimization of QS signaling and on attack synchronization.

Regular synchrony lattices for product coupled cell networks

There are several ways for constructing (bigger) networks from smaller networks. We consider here the cartesian and the Kronecker (tensor) product networks. Our main aim is to determine a relation between the lattices of synchrony subspaces for a product network and the component networks of the product. In this sense, we show how to obtain the lattice of regular synchrony subspaces for a product network from the lattices of synchrony subspaces for the component networks. Specifically, we prove that a tensor of subspaces is of synchrony for the product network if and only if the subspaces involved in the tensor are synchrony subspaces for the component networks of the product. We also show that, in general, there are (irregular) synchrony subspaces for the product network that are not described by the synchrony subspaces for the component networks, concluding that, in general, it is not possible to obtain the all synchrony lattice for the product network from the corresponding lattices for the component networks. We also make the following remark concerning the fact that the cartesian and Kronecker products, as graph operations, are quite different, implying that the associated coupled cell systems have distinct structures. Although, the kinds of dynamics expected to occur are difficult to compare, we establish an inclusion relation between the lattices of synchrony subspaces for the cartesian and Kronecker products.

Rules and limitations of building delay-tolerant topologies for coupled systems

This paper investigates the equilibrium behavior of broadly studied synchronization dynamics of coupled systems, among which shared information is delayed. The underlying relationship is established between graph structures and the largest amount of delay the dynamics can withstand without losing stability. In particular, based on Cartesian product of graphs, we present the rules and limitations for synthesizing the graphs of large-scale systems that can remain stable for as large delays as possible. Examples are provided to demonstrate the results.

Synchronization of chaotic networks with time-delayed couplings: an analytic study

Networks of nonlinear units with time-delayed couplings can synchronize to a common chaotic trajectory. Although the delay time may be very large, the units can synchronize completely without time shift. For networks of coupled Bernoulli maps, analytic results are derived for the stability of the chaotic synchronization manifold. For a single delay time, chaos synchronization is related to the spectral gap of the coupling matrix. For networks with multiple delay times, analytic results are obtained from the theory of polynomials. Finally, the analytic results are compared with networks of iterated tent maps and Lang-Kobayashi equations, which imitate the behavior of networks of semiconductor lasers.

Evolving functional network properties and synchronizability during human epileptic seizures

We assess electrical brain dynamics before, during, and after 100 human epileptic seizures with different anatomical onset locations by statistical and spectral properties of functionally defined networks. We observe a concave-like temporal evolution of characteristic path length and cluster coefficient indicative of a movement from a more random toward a more regular and then back toward a more random functional topology. Surprisingly, synchronizability was significantly decreased during the seizure state but increased already prior to seizure end. Our findings underline the high relevance of studying complex systems from the viewpoint of complex networks, which may help to gain deeper insights into the complicated dynamics underlying epileptic seizures.

Rewiring networks for synchronization

We study the synchronization of identical oscillators diffusively coupled through a network and examine how adding, removing, and moving single edges affects the ability of the network to synchronize. We present algorithms which use methods based on node degrees and based on spectral properties of the network Laplacian for choosing edges that most impact synchronization. We show that rewiring based on the network Laplacian eigenvectors is more effective at enabling synchronization than methods based on node degree for many standard network models. We find an algebraic relationship between the eigenstructure before and after adding an edge and describe an efficient algorithm for computing Laplacian eigenvalues and eigenvectors that uses the network or its complement depending on which is more sparse.

Synchronization properties of network motifs: influence of coupling delay and symmetry

We investigate the effect of coupling delays on the synchronization properties of several network motifs. In particular, we analyze the synchronization patterns of unidirectionally coupled rings, bidirectionally coupled rings, and open chains of Kuramoto oscillators. Our approach includes an analytical and semianalytical study of the existence and stability of different in-phase and out-of-phase periodic solutions, complemented by numerical simulations. The delay is found to act differently on networks possessing different symmetries. While for the unidirectionally coupled ring the coupling delay is mainly observed to induce multistability, its effect on bidirectionally coupled rings is to enhance the most symmetric solution. We also study the influence of feedback and conclude that it also promotes the in-phase solution of the coupled oscillators. We finally discuss the relation between our theoretical results on delay-coupled Kuramoto oscillators and the synchronization properties of networks consisting of real-world delay-coupled oscillators, such as semiconductor laser arrays and neuronal circuits.

Network synchronizability analysis: a graph-theoretic approach

This paper addresses the fundamental problem of complex network synchronizability from a graph-theoretic approach. First, the existing results are briefly reviewed. Then, the relationships between the network synchronizability and network structural parameters (e.g., average distance, degree distribution, and node betweenness centrality) are discussed. The effects of the complementary graph of a given network and some graph operations on the network synchronizability are discussed. A basic theory based on subgraphs and complementary graphs for estimating the network synchronizability is established. Several examples are given to show that adding new edges to a network can either increase or decrease the network synchronizability. To that end, some new results on the estimations of the synchronizability of coalescences are reported. Moreover, a necessary and sufficient condition for a network and its complementary network to have the same synchronizability is derived. Finally, some examples on Chua circuit networks are presented for illustration.

Climate networks around the globe are significantly affected by El Niño

The temperatures in different zones in the world do not show significant changes due to El Niño except when measured in a restricted area in the Pacific Ocean. We find, in contrast, that the dynamics of a climate network based on the same temperature records in various geographical zones in the world is significantly influenced by El Niño. During El Niño many links of the network are broken, and the number of surviving links comprises a specific and sensitive measure for El Niño events. While during non-El Niño periods these links which represent correlations between temperatures in different sites are more stable, fast fluctuations of the correlations observed during El Niño periods cause the links to break.

The application of graph theoretical analysis to complex networks in the brain

Considering the brain as a complex network of interacting dynamical systems offers new insights into higher level brain processes such as memory, planning, and abstract reasoning as well as various types of brain pathophysiology. This viewpoint provides the opportunity to apply new insights in network sciences, such as the discovery of small world and scale free networks, to data on anatomical and functional connectivity in the brain. In this review we start with some background knowledge on the history and recent advances in network theories in general. We emphasize the correlation between the structural properties of networks and the dynamics of these networks. We subsequently demonstrate through evidence from computational studies, in vivo experiments, and functional MRI, EEG and MEG studies in humans, that both the functional and anatomical connectivity of the healthy brain have many features of a small world network, but only to a limited extent of a scale free network. The small world structure of neural networks is hypothesized to reflect an optimal configuration associated with rapid synchronization and information transfer, minimal wiring costs, resilience to certain types of damage, as well as a balance between local processing and global integration. Eventually, we review the current knowledge on the effects of focal and diffuse brain disease on neural network characteristics, and demonstrate increasing evidence that both cognitive and psychiatric disturbances, as well as risk of epileptic seizures, are correlated with (changes in) functional network architectural features.

Graph theoretical analysis of complex networks in the brain

Since the discovery of small-world and scale-free networks the study of complex systems from a network perspective has taken an enormous flight. In recent years many important properties of complex networks have been delineated. In particular, significant progress has been made in understanding the relationship between the structural properties of networks and the nature of dynamics taking place on these networks. For instance, the 'synchronizability' of complex networks of coupled oscillators can be determined by graph spectral analysis. These developments in the theory of complex networks have inspired new applications in the field of neuroscience. Graph analysis has been used in the study of models of neural networks, anatomical connectivity, and functional connectivity based upon fMRI, EEG and MEG. These studies suggest that the human brain can be modelled as a complex network, and may have a small-world structure both at the level of anatomical as well as functional connectivity. This small-world structure is hypothesized to reflect an optimal situation associated with rapid synchronization and information transfer, minimal wiring costs, as well as a balance between local processing and global integration. The topological structure of functional networks is probably restrained by genetic and anatomical factors, but can be modified during tasks. There is also increasing evidence that various types of brain disease such as Alzheimer's disease, schizophrenia, brain tumours and epilepsy may be associated with deviations of the functional network topology from the optimal small-world pattern.

Small-world brain networks

Many complex networks have a small-world topology characterized by dense local clustering or cliquishness of connections between neighboring nodes yet a short path length between any (distant) pair of nodes due to the existence of relatively few long-range connections. This is an attractive model for the organization of brain anatomical and functional networks because a small-world topology can support both segregated/specialized and distributed/integrated information processing. Moreover, small-world networks are economical, tending to minimize wiring costs while supporting high dynamical complexity. The authors introduce some of the key mathematical concepts in graph theory required for small-world analysis and review how these methods have been applied to quantification of cortical connectivity matrices derived from anatomical tract-tracing studies in the macaque monkey and the cat. The evolution of small-world networks is discussed in terms of a selection pressure to deliver cost-effective information-processing systems. The authors illustrate how these techniques and concepts are increasingly being applied to the analysis of human brain functional networks derived from electroencephalography/magnetoencephalography and fMRI experiments. Finally, the authors consider the relevance of small-world models for understanding the emergence of complex behaviors and the resilience of brain systems to pathological attack by disease or aberrant development. They conclude that small-world models provide a powerful and versatile approach to understanding the structure and function of human brain systems.

Small-world networks and disturbed functional connectivity in schizophrenia

Disturbances in "functional connectivity" have been proposed as a major pathophysiological mechanism for schizophrenia, and in particular, for cognitive disorganization. Detection and estimation of these disturbances would be of clinical interest. Here we characterize the spatial pattern of functional connectivity by computing the "synchronization likelihood" (SL) of EEG at rest and during performance of a 2Back working memory task using letters of the alphabet presented on a PC screen in subjects with schizophrenia and healthy controls. The spatial patterns of functional connectivity were then characterized with graph theoretical measures to test whether a disruption of an optimal spatial pattern ("small-world") of the functional connectivity network underlies schizophrenia. Twenty stabilized patients with schizophrenia, who were able to work, and 20 healthy controls participated in the study. During the working memory (WM) task healthy subjects exhibited small-world properties (a combination of local clustering and high overall integration of the functional networks) in the alpha, beta and gamma bands. These properties were not present in the schizophrenia group. These findings are in accordance with a partially inadequate organization of neuronal networks in subjects with schizophrenia. This method could be helpful for diagnosis and evaluation of the severity of the disease, as well as understanding the pathophysiologic mechanisms underlying cognitive dysfunction in schizophrenia.

Using graph theoretical analysis of multi channel EEG to evaluate the neural efficiency hypothesis

Previous studies demonstrated that intelligence is significantly related to an impressive array of psychological, social, biological and genetic factors and that working memory (WM) can be considered as a general cognitive resource strongly related with a wide variety of higher order cognitive competencies and intelligence. Also, evaluating the WM of subjects might allow one to test the neural efficiency hypothesis (NEH). WM typically involves functional interactions between frontal and parietal cortices. We recorded EEG signals to study neuronal interactions during one WM test in individuals who had few years of formal education (LE) as compared to individuals with university degrees (UE). The two groups of individuals differed in the scores they obtained in psychological tests. To quantify the synchronization between EEG channels in several frequency bands, we evaluated the "synchronization likelihood" (SL), which takes into consideration nonlinear processes as well as linear ones. SL was then converted into graphs to estimate the distance from "small-world network" (SWN) organization, i.e., an optimally organized network that would give rise to the data. In comparison to LE subjects, those with university degrees exhibited less prominent SWN properties in most frequency bands during the WM task. This finding supports the NEH and suggests that the connections between brain areas of well-educated subjects engaged in WM tasks are not as well-organized in the sense of SWN.