Complex Systems and Networks

Networks represent patterns of interactions between components of complex systems present in nature, science, technology and society. Furthermore, graph theory allows to perform insightful analysis for different kinds of data by representing the instances as nodes of a weighted network, where the weights characterize similarity between the data points. In this chapter we describe a number of algorithms to perform cluster analysis, that is finding groups of similar items (called clusters or communities) and understand their evolution over time. These algorithms are designed in a kernel-based framework: the original data are mapped into an high dimensional feature space; linear models are designed in this space; complex nonlinear relationships between the data in the original input space can then be detected. Applications like fault detection in industrial machines, community detection of static and evolving networks, image segmentation, incremental time-series clustering and text clustering are considered.

There is increasing motivation to study bipartite complex networks as a separate category and, in particular, to investigate their community structure. We outline recent work in the area and focus on two high-performing algorithms for unipartite networks, the modularity-based Louvain and the flow-based Infomap. We survey modifications of modularity-based algorithms to adapt them to the bipartite case. As Infomap cannot be applied to bipartite networks for theoretical reasons, our solution is to work with the primary projected network. We apply both algorithms to four projected networks of increasing size and complexity. Our results support the conclusion that the clusters found by Infomap are meaningful and better represent ground truth in the bipartite network than those found by Louvain.

The present chapter is devoted to review some literatures on the modeling infectious disease on complex networks. From the following several aspects we give a brief summary about solving the problem of the disease spread: Modeling approaches of epidemic dynamics on complex networks, Application of percolation theory in propagation dynamics, Epidemic models in complex network with demographics and Epidemic spreading on multilayer networks. In the first section, the Node-based and Edge-based mean-field modeling approaches on complex networks are reviewed and compared respectively, and the second section reviews the application of bond percolation in the single network (undirected graphs, directed graphs, bipartite graphs and clustered networks) and coupled networks (overlap networks and interconnected networks), then gives a review about the disease epidemics and site or bond percolation or both site and bond percolation in small-world networks. Following, we present an overview on some of recent studies on epidemic dynamics with demographics and epidemic processes on multilayer networks in the last two section, respectively.

Critical infrastructures for transmitting materials, electricity and information between distant places, can be represented as spatial networks. The resilience of spatial networks usually shows unprecedented complexity, leading to the catastrophic cascading failures in the network under various local perturbations. From the viewpoint of physics, the cascading failure process of these networks can be considered as a phase transition, which is characterized by threshold and critical exponents. In this chapter, we first review our research on the definition and measurement of the dimension of these spatial networks, which is essential for determining the critical properties of the phase transition in the network failure process according to statistical physics. Secondly, we review our research on the dynamical organization of flow on these spatial networks, which can help to locate the relation between the flow and overload in the cascading failures. Thirdly, we review our research results on the failure propagation behaviors in the cascading failures, showing long-range decay of spatial correlation between component failures. Finally, we review our research on the modeling of self-healing against cascading failures and discuss the challenges in the reliability engineering for evaluating and improving the resilience of spatial networks.

In this chapter, hyper-networks and colored networks corresponding to hyper-graphs and colored graphs in mathematics are presented, which can be used to model real large-scale systems, such as neuronal networks, metabolic networks, social relationship networks, scientific collaboration networks, and so on. Firstly, similarly to the BA scale-free network, both growth and preferential attachment mechanisms are adopted to generate some evolving hyper-network models, including uniform and nonuniform hyper-networks. Secondly, a uniform dynamical hyper-network model is built and its synchronization is investigated using joint-degree matrix. Thirdly, a colored network with same-dimensional node dynamics is presented. The synchronization and control of both edge-colored and colored networks are studied. Finally, a general colored network with different-dimensional node dynamics is presented and its generalized matrix projective synchronization is achieved by applying open-plus-closed-loop control.

This paper is devoted to the design of new chaotic Pseudo Random Number Generator (CPRNG). Exploring several topologies of network of 1-D coupled chaotic mapping, we focus first on two dimensional networks. Two coupled maps are studied: \(\textit{TTL}^{RC}\) non-alternative, and \(\textit{TTL}^{SC}\) alternative. The primary idea of the novel maps has been based on an original coupling of the tent and logistic maps to achieve excellent random properties and homogeneous/uniform/density in the phase plane, thus guaranteeing maximum security when used for chaos base cryptography. In this aim a new nonlinear CPRNG: \(\textit{MTTL}_{2}^{SC}\) is proposed. In addition, we explore higher dimension and the proposed ring coupling with injection mechanism enables to achieve the strongest security requirements.

The distributed finite-time consensus problems for second-order multi-agent systems are studied in Sect. 7.1. Then, in Sect. 7.2, the distributed finite-time containment protocols are designed for second-order multi-agent systems with multiple nonlinear dynamic leaders. Finally, for multiple Euler-Lagrange systems, some finite-time tracking protocols are proposed in Sect. 7.3.

In this chapter, the distributed finite-time containment control problem is investigated for second-order multi-agent systems with external disturbances. By combining finite-time control and finite-time disturbance observer techniques together, a kind of feedforward-feedback composite distributed controllers are proposed. Under these distributed controllers, the effects of the disturbances on the system states are removed in a finite time and the followers globally converge to the convex hull spanned by the leaders in a finite time as well. Simulations illustrate the effectiveness of the proposed control algorithms.

This chapter is concerned with fractional-order consensus problem in multi-agent systems. A brief introduction of fractional-order calculus is given in Sect. 9.1. The design of observer for consensus of a linear fractional-order multi-agent system is discussed in Sect. 9.2. Section 9.3 considers a multi-agent system consisting of second-order leader and fractional-order followers where a necessary and sufficient condition of tracking consensus is derived by using only the relative local position information of neighboring agents. The stabilization consensus problem of uncertain fractional-order multi-agent system is investigated in Sect. 9.4.

In this chapter, we prove analytically and numerically aided by computer simulations, that the Parrondo game can be implemented numerically to control and anticontrol chaos of a large class of nonlinear continuous-time and discrete-time systems. The game states that alternating loosing gains of two games, one can actually obtain a winning game, i.e.: “losing \(+\) losing \(=\) winning” or, in other words: “two ugly parents can have beautiful children” (Zeilberger, on receiving the 1998 Leroy P. Steele Prize). For this purpose, the Parameter Switching (PS) algorithm is implemented. The PS algorithm switches the control parameter of the underlying system, within a set of values as the system evolves. The obtained attractor matches the attractor obtained by replacing the parameter with the average of switched values. The systems to which the PS algorithm based Parrondo’s game applies are continuous-time of integer or fractional order ones such as: Lorenz system, Chen system, Chua system, Rössler system, to name just a few, and also discrete-time systems and fractals. Compared with some other works on switch systems, the PS algorithm utilized in this chapter is a convergent algorithm which allows to approximate any desired dynamic to arbitrary accuracy.

In natural flocks/swarms, it is very appealing that low-level individual intelligence and communication can yield advanced coordinated collective behaviors such as congregation, synchronization and migration. Firstly, we seek to understand the role of predictive mechanisms in the forming and evolving of flocks/swarms by using both numerical simulations and mathematical analyses. Secondly, by incorporating some predictive mechanism into a few pinning nodes, we show that convergence procedure to consensus can be substantially accelerated in networks of interconnected dynamic agents while physically maintaining the network topology. Such an acceleration stems from the compression mechanism of the eigenspectrum of the state matrix conferred by the predictive mechanism. Thirdly, some model predictive control protocols are developed to achieve consensus for a class of discrete-time double-integrator multi-agent systems with input constraints. Associated sufficient conditions such as that the proximity net has a directed spanning tree and that the sampling period is sufficiently small are proposed. Moreover, the control horizon is extended to larger than one, which endows sufficient degrees of freedom to accelerate the convergence to consensus.

This chapter reviews several approaches to study convergence of networks of nonlinear dynamical systems based on the use of contraction theory. Rather than studying the properties of the collective asymptotic solution of interest, the strategy focuses on finding sufficient conditions for any pair of trajectories of two agents in the network to converge towards each other. The key tool is the study, in an appropriate metric, of the matrix measure of the agents’ or network Jacobian. The effectiveness of the proposed approach is illustrated via a set of representative examples.

Temporal complex networks are ubiquitous in human daily life whose topologies evolve with time, such as communication networks and transportation networks. Investigations on the structural controllability of temporal complex networks show the properties and performances of controllability when the weights of edges in temporal networks are arbitrary values rather than exact ones. There are two frameworks proposed in this chapter to analyze the structural controllability of temporal networks. In the first framework, a temporal network is treated as a sequence of characteristic subgraphs with different characteristic time stamps. After finding the maximum characteristic subgraph set from these subgraphs, priority maximum methods are applied to improve the controlling efficiency by which temporal information of the network remains. On the other hand, in the later framework, a temporal network is represented by time-ordered graph (TOG). Instead of calculating the rank of controllability matrix directly, finding and classifying temporal trees of the time-ordered graph provides an effective way to estimate the controlling centrality of a node in the network.

We consider a class of complex networks whose nodes assume one of several possible states at any time and may change their states from time to time. Such networks, referred to as transition networks in this chapter, represent practical networks of rumor spreading, disease spreading, language evolution, and so on. Here, we derive a general analytical model describing the dynamics of a transition network and derive a simulation algorithm for studying the network evolutionary behavior. By using this model, we can analytically compute the probability that (1) the next transition will happen at a given time; (2) a particular transition will occur; (3) a particular transition will occur with a specific link. This model, derived at a microscopic level, can reveal the transition dynamics of every node. A numerical simulation is taken as an “experiment” or “realization” of the model. We use this model to study the disease propagation dynamics in four different prototypical networks, namely, the regular nearest-neighbor (RN) network, the classical Erdös-Renyí (ER) random graph, the Watts-Strogátz small-world (SW) network, and the Barabási-Albert (BA) scalefree network. We find that the disease propagation dynamics in these four networks generally have different properties but they do share some common features. Furthermore, we utilize the transition network model to predict user growth in the Facebook network. Simulation shows that our model agrees with the historical data. The study can provide a useful tool for a more thorough understanding of the dynamics of transition networks.

Deflection routing is a viable contention resolution scheme in buffer-less network architectures where contention is the main source of information loss. In recent years, various reinforcement learning-based deflection routing algorithms have been proposed. However, performance of these algorithms has not been evaluated in larger networks that resemble the autonomous system-level view of the Internet. In this Chapter, we compare performance of three reinforcement learning-based deflection routing algorithms by using the National Science Foundation network topology and topologies generated using Waxman and Barabási-Albert algorithms. We examine the scalability of these deflection routing algorithms by increasing the network size while keeping the network load constant.

Recommender systems has become increasingly important in online community for providing personalized services and products to users. Traditionally, performance of recommender algorithms has been evaluated based on accuracy and the focus of the research was on providing accurate recommendation lists. However, recently diversity and novelty of recommendation lists have been introduced as key issues in designing recommender systems. In general, novelty/diversity and accuracy do not go hand in hand. Therefore, designing models answering novelty/diversity-accuracy dilemma is one of the challenging problems in the context of practical recommender systems. In this paper, we first introduce the diversity-accuracy challenge in recommender systems, and then present two recommendation algorithms which approach the problem from two perspectives. The first model is a filtering algorithm to select candidate items which incorporates timing information of ratings to improve both accuracy and novelty of recommender systems. The filter can be applied as adds-on to any recommender algorithm. The second model is a probabilistic model which resolves the dilemma and provides adjustable level of accuracy and diversity that can be tuned by a single parameter.

Networked evolutionary games provide an appropriate tool for investigating competition and diffusion of behavioral traits in structured biological and social populations. A core challenge in networked evolutionary game theory is the strategy selection problem: Given several strategies, which one is favored by the population? This chapter is to explore and analyze the strategy selection problem in several typical evolutionary dynamic models of networked games. In detail, firstly the concept of networked games is introduced together with several typical evolutionary dynamics models, including the birth-death process, the death-birth process, and the imitation dynamics. Then, several results of strategy selection conditions are reported for evolutionary dynamics of both two-player multi-strategy games and multi-player two-strategy games on networks. Moreover, these results are applied to the prisoner’s dilemma game, the volunteer’s dilemma game, and the public goods game to investigate the cooperation conditions in networked populations. The main aim of this chapter is to characterize the effect of interacting networks on strategy selection and more specifically on the evolution of cooperation.

With rapid accumulation of high-throughput data, network has become one of key paradigms in computational biology for analyzing biological systems. In the past fifteen years, many types of molecular networks have been extensively investigated, demonstrating great potentials to discover basic functions and reveal essential mechanisms. More recently, network has played many new roles in multiple networked data and data types. In this chapter, we aim to survey the recent developments on topics related to biological networks and network-based data integration, with the special emphasis on the computational aspect. The contents of this survey covers network-based cancer stratification and cancer driver discovery from mutation data, network-based discovery of disease modules, multiple similarity network fusion, network-regularized data integration, module detection in multi-layer networks, topological analysis of a disease-age gene network, comparative analysis of multiple transcriptional-factor networks, etc.