Multivariate analysis of spatially heterogeneous phase synchronisation in complex systems: application to self-organised control of material flows in networks

Networks of interacting components are a class of complex systems that has attracted considerable interest over the last decades. In particular, if the dynamics of the autonomous components is characterised by an oscillatory behaviour, different types of synchronisation can be observed in dependence on the type and strength of interactions. In this contribution, we study the transition from non-synchronised to synchronised phase dynamics in complex networks. The most common approach to quantify the degree of phase synchronisation in such systems is the consideration of measures of phase coherence which are averaged over all pairs of interacting components. However, this approach implicitly assumes a spatially homogeneous synchronisation process, which is typically not present in complex networks. As a potential alternative, two novel methods of multivariate phase synchronisation analysis are considered: synchronisation cluster analysis (SCA) and the linear variance decay (LVD) dimension method. The strengths and weaknesses of the traditional as well as both new approaches are briefly illustrated for a Kuramoto model with long-range coupling. As a practical application, we study how spatial heterogeneity influences the transition to phase synchronisation in traffic networks where intersecting material flows are subjected to a self-organised decentralised control. We find that the network performance and the degree of phase synchronisation are closely related to each other and decrease significantly in the case of structural heterogeneities. The influences of the different parameters of our control approach on the synchronisation process are systematically studied, yielding a sequence of Arnold tongues which correspond to different locking modes.     

复杂网络牵制控制优化选点算法及节点组重要性排序

本文研究复杂网络动力学模型的无向网络牵制控制的优化选点及节点组重要性排序问题.根据牵制控制的同步准则,网络的牵制控制同步取决于网络的Laplacian删后矩阵的最小特征值.因此,通过合理选择受控节点集得到一个较大的Laplacian删后矩阵最小特征值,是牵制控制优化选点问题的核心所在.基于Laplacian删后矩阵最小特征值的图谱性质,本文提出了多个受控节点选取的递归迭代算法,该算法适用于任意类型的网络.通过BA无标度网络、NW小世界网络及一些实际网络中的仿真实验表明:该算法在控制节点数较少时,能有效找到最优受控节点集.最后讨论了在复杂网络牵制控制背景下节点组重要性排序问题,提出节点组的重要性排序与受控节点的数目有关.     

Searchability of Central Nodes in Networks

Social networks are discrete systems with a large amount of heterogeneity among nodes (individuals). Measures of centrality aim at a quantification of nodes’ importance for structure and function. Here we ask to which extent the most central nodes can be found by purely local search. We find that many networks have close-to-optimal searchability under eigenvector centrality, outperforming searches for degree and betweenness. Searchability of the strongest spreaders in epidemic dynamics tends to be substantially larger for supercritical than for subcritical spreading.     

Projective-anticipating, projective, and projective-lag synchronization of time-delayed chaotic systems on random networks

We study projective-anticipating, projective, and projective-lag synchronization of time-delayed chaotic systems on random networks. We relax some limitations of previous work, where projective-anticipating and projective-lag synchronization can be achieved only on two coupled chaotic systems. In this paper, we realize projective-anticipating and projective-lag synchronization on complex dynamical networks composed of a large number of interconnected components. At the same time, although previous work studied projective synchronization on complex dynamical networks, the dynamics of the nodes are coupled partially linear chaotic systems. In this paper, the dynamics of the nodes of the complex networks are time-delayed chaotic systems without the limitation of the partial linearity. Based on the Lyapunov stability theory, we suggest a generic method to achieve the projective-anticipating, projective, and projective-lag synchronization of time-delayed chaotic systems on random dynamical networks, and we find both its existence and sufficient stability conditions. The validity of the proposed method is demonstrated and verified by examining specific examples using Ikeda and Mackey-Glass systems on Erdos-Renyi networks.     

Weighted complex network analysis of travel routes on the Singapore public transportation system

The structure and properties of public transportation networks have great implications for urban planning, public policies and infectious disease control. We contribute a complex weighted network analysis of travel routes on the Singapore rail and bus transportation systems. We study the two networks using both topological and dynamical analyses. Our results provide additional evidence that a dynamical study adds to the information gained by traditional topological analysis, providing a richer view of complex weighted networks. For example, while initial topological measures showed that the rail network is almost fully connected, dynamical measures highlighted hub nodes that experience disproportionately large traffic. The dynamical assortativity of the bus networks also differed from its topological counterpart. In addition, inspection of the weighted eigenvector centralities highlighted a significant difference in traffic flows for both networks during weekdays and weekends, suggesting the importance of adding a temporal perspective missing from many previous studies.     

New structures in complex systems

Networks represent a major modelling tool in complex systems and the natural sciences. When considering systems of interacting units, networks can only model pair interactions as represented by edges between nodes. This is a severe limitation when one tries to model higher order interactions, like triple interactions etc. Some higher order interactions may be reduced to systems of pair interactions, but as we will illustrate there are, for example, triple interactions which are not reducible to pair interactions for quite deep mathematical reasons (Borromean structures). Therefore there is a need for a new kind of structure extending and encompassing networks in such a way that we can describe and model truly higher order structures. We suggest that this can be done by the concept of a Hyperstructure as introduced in [1]. Hyperstructures encompass networks and hierarchies and incorporate the phenomenon of levelwise emergence. They represent a design principle for higher order structures. It is natural to ask how hyperstructures occur in the natural sciences and complex systems and how they may be synthesized. We will discuss this, and relate it to recent work in synthetic chemistry, nuclear physics, quantum mechanical many body systems and ultracold gases. Furthermore, we will introduce the notion of hyperstructured (higher order) molecular architectures and hyperstructured (higher order) materials. We will present suggestions and conjectures on these matters.     

Oscillatory Dynamics and Oscillation Death in Complex Networks Consisting of Both Excitatory and Inhibitory Nodes

In neural networks, both excitatory and inhibitory cells play important roles in determining the functions of systems. Various dynamical networks have been proposed as artificial neural networks to study the properties of biological systems where the influences of excitatory nodes have been extensively investigated while those of inhibitory nodes have been studied much less. In this paper, we consider a model of oscillatory networks of excitable Boolean maps consisting of both excitatory and inhibitory nodes, focusing on the roles of inhibitory nodes. We find that inhibitory nodes in sparse networks (small average connection degree) play decisive roles in weakening oscillations, and oscillation death occurs after continual weakening of oscillation for sufficiently high inhibitory node density. In the sharp contrast, increasing inhibitory nodes in dense networks may result in the increase of oscillation amplitude and sudden oscillation death at much lower inhibitory node density and the nearly highest excitation activities. Mechanism under these peculiar behaviors of dense networks is explained by the competition of the duplex effects of inhibitory nodes.     

Complex Networks from Chaotic Time Series on Riemannian Manifold

Complex networks are important paradigms for analyzing the complex systems as they allow understanding the structural properties of systems composed of different interacting entities.In this work we propose a reliable method for constructing complex networks from chaotic time series.We first estimate the covariance matrices,then a geodesic-based distance between the covariance matrices is introduced.Consequently the network can be constructed on a Riemannian manifold where the nodes and edges correspond to the covariance matrix and geodesic-based distance,respectively.The proposed method provides us with an intrinsic geometry viewpoint to understand the time series.     

The prescribed output pattern regulates the modular structure of flow networks

Modules are common functional and structural properties of many social, technical andbiological networks. Especially for biological systems it is important to understand howmodularity is related to function and how modularity evolves. It is known thattime-varying or spatially organized goals can lead to modularity in a simulated evolutionof signaling networks. Here, we study a minimal model of material flow in networks. Wediscuss the relation between the shared use of nodes, i.e., the cooperativity of modules,and the orthogonality of a prescribed output pattern. We study the persistence ofcooperativity through an evolution of robustness against local damages. We expect theresults to be valid for a large class of flow-based biological and technical networks.     

A thermal flux-diffusing model for complex networks and its applications in community structure detection

We introduce a thermal flux-diffusing model for complex networks. Based on this model, we propose a physical method to detect the communities in the complex networks. The method allows us to obtain the temperature distribution of nodes in time that scales linearly with the network size. Then, the local community enclosing a given node can be easily detected for the reason that the dense connections in the local communities lead to the temperatures of nodes in the same community being close to each other. The community structure of a network can be recursively detected by randomly choosing the nodes outside the detected local communities. In the experiments, we apply our method to a set of benchmarking networks with known pre-determined community structures. The experiment results show that our method has higher accuracy and precision than most existing globe methods and is better than the other existing local methods in the selection of the initial node. Finally, several real-world networks are investigated.     

Cascading Failures of Complex Networks Based on Two-Step Degree

We propose a new concept, two-step degree. Defining it as the capacity of a node of complex networks, we establish a novel capacity-load model of cascading failures of complex networks where the capacity of nodes decreases during the process of cascading failures. For scale-free networks, we find that the average two-step degree increases with the increase of the heterogeneity of the degree distribution, showing that the average two- step degree can be used for measuring the heterogeneity of the degree distribution of complex networks. In addition, under the condition that the average degree of a node is given, we can design a scale-free network with the optimal robustness to random failures by maximizing the average two-step degree.     

耦合含时滞的相互依存网络的局部自适应异质同步

针对由两个子网络构成的耦合含时滞的相互依存网络,研究其局部自适应异质同步问题.时滞同时存在于两个子网络的内部耦合项和子网络间的一对一相互依赖耦合项中,且网络的耦合关系满足非线性特性和光滑性.基于李雅普诺夫稳定性理论、线性矩阵不等式方法和自适应控制技术,通过对子网络设置合适的控制器,提出了使得相互依存网络的子网络分别同步到异质孤立系统的充分条件.针对小世界网络和无标度网络构成的相互依存网络进行数值模拟,验证了提出理论的正确性和有效性.     

Oscillation sources and wave propagation paths in complex networks consisting of excitable nodes

Self-sustained oscillations in complex networks consisting of nonoscillatory nodes have attracted long-standing interest in diverse natural and social systems. We study the self-sustained periodic oscillations in random networks consisting of excitable nodes. We reveal the underlying dynamic structure by applying a dominant phase-advanced driving method. The oscillation sources and wave propagation paths can be illustrated clearly via the dynamic structure revealed. Then we are able to control the oscillations with surprisingly high efficiency based on our understanding.     

Road traffic: A case study of flow and path-dependency in weighted directed networks

How much can we tell about flows through networks just from their topological properties? Whereas flow distributions of river basins, trees or cardiovascular systems come naturally to mind, more complex topologies are not so immediate, especially if the network is large and heterogeneously directed. Our study is motivated by the question of how the distribution of path-dependent trails in directed networks is correlated to the distribution of network flows. As an example we have studied the path-dependencies in closed trails in four metropolitan areas in England and the USA and computed their global and spatial correlations with measured traffic flows. We have found that the heterogeneous distribution of traffic intensity is mirrored by the distribution of agglomerate path-dependency and that high traffic roads are packed along corridors at short-to-medium trail lengths from the ensemble of nodes.     

Towards an Efficient and Exact Algorithm for Dynamic Dedicated Path Protection

We present a novel algorithm for dynamic routing with dedicated path protection which, as the presented simulation results suggest, can be efficient and exact. We present the algorithm in the setting of optical networks, but it should be applicable to other networks, where services have to be protected, and where the network resources are finite and discrete, e.g., wireless radio or networks capable of advance resource reservation. To the best of our knowledge, we are the first to propose an algorithm for this long-standing fundamental problem, which can be efficient and exact, as suggested by simulation results. The algorithm can be efficient because it can solve large problems, and it can be exact because its results are optimal, as demonstrated and corroborated by simulations. We offer a worst-case analysis to argue that the search space is polynomially upper bounded. Network operations, management, and control require efficient and exact algorithms, especially now, when greater emphasis is placed on network performance, reliability, softwarization, agility, and return on investment. The proposed algorithm uses our generic Dijkstra algorithm on a search graph generated “on-the-fly” based on the input graph. We corroborated the optimality of the results of the proposed algorithm with brute-force enumeration for networks up to 15 nodes large. We present the extensive simulation results of dedicated-path protection with signal modulation constraints for elastic optical networks of 25, 50, and 100 nodes, and with 160, 320, and 640 spectrum units. We also compare the bandwidth blocking probability with the commonly-used edge-exclusion algorithm. We had 48,600 simulation runs with about 41 million searches.     

A time-series approach to measuring node similarity in networks and its application to community detection

A central concept in network analysis is that of similarity between nodes. In this paper, we introduce a dynamic time-series approach to quantifying the similarity between nodes in networks. The problem of measuring node similarity is exquisitely embedded into the framework of time series for state evolution of nodes. We develop a deterministic parameter-free diffusion model to drive the dynamic evolution of node states, and produce a unique time series for each source node. Then we introduce a measure quantifying how far all the other nodes are located from each source one. Following this measure, a quantity called dissimilarity index is proposed to signify the extent of similarity between nodes. Thereof, our dissimilarity index gives a deep and natural integration between the local and global perspectives of topological structure of networks. Furthermore, we apply our dissimilarity index to unveil community structure in networks, which verifies the proposed dissimilarity index.     

A new local-world evolving network model

In some real complex networks, only a few nodes can obtain the global information about the entire networks, but most of the nodes own only local connections therefore own only local information of the networks. A new local-world evolving network model is proposed in this paper. In the model, not all the nodes obtain local network information, which is different from the local world network model proposed by Li and Chen (LC model). In the LC model, each node has only the local connections therefore owns only local information about the entire networks. Theoretical analysis and numerical simulation show that adjusting the ratio of the number of nodes obtaining the global information of the network to the total number of nodes can effectively control the valuing range for the power-law exponent of the new network. Therefore, if the topological structure of a complex network, especially its exponent of power-law degree distribution, needs controlling, we just add or take away a few nodes which own the global information of the network.     

Minority game for cognitive radios: Cooperating without cooperation

In this paper we report on our preliminary results and recent work on building cognitive wireless networks that achieve resource sharing in a local environment. We emphasize two major issues. First, the cross-layer optimization at the network level requires exchange of information between OSI-layers in the terminal and often among the nodes that form the network. Second, the cooperative behavior among the radios is often believed to require a rich exchange of information. We show in this paper that cooperation can be an emergent phenomenon without any complex signalling. We apply Minority Games to cognitive wireless networks to show that resource sharing can be achieved without detailed information exchange or coordination between strategies. We further argue that Minority Games are not only a useful analysis tool, but a potentially efficient method to develop actual resource sharing algorithms. We conclude the paper by pointing out that also other swarm intelligence type of solutions could be applied to cognitive radio communications.     

On the degree distribution of projected networks mapped from bipartite networks

Many real-world systems can be represented by bipartite networks. In a bipartite network, the nodes are divided into two disjoint sets, and the edges connect nodes that belong to different sets. Given a bipartite network (i.e. two-mode network) it is possible to construct two projected networks (i.e. one-mode networks) where each one is composed of only one set of nodes. While network analyses have focused on unipartite networks, considerably less attention has been paid to the analytical study of bipartite networks. Here, we analytically derive simple mathematical relationships that predict degree distributions of the projected networks by only knowing the structure of the original bipartite network. These analytical results are confirmed by computational simulations using artificial and real-world bipartite networks from a variety of biological and social systems. These findings offer in our view new insights into the structure of real-world bipartite networks.