Node importance for dynamical process on networks: a multiscale characterization

Defining the importance of nodes in a complex network has been a fundamental problem in analyzing the structural organization of a network, as well as the dynamical processes on it. Traditionally, the measures of node importance usually depend either on the local neighborhood or global properties of a network. Many real-world networks, however, demonstrate finely detailed structure at various organization levels, such as hierarchy and modularity. In this paper, we propose a multiscale node-importance measure that can characterize the importance of the nodes at varying topological scale. This is achieved by introducing a kernel function whose bandwidth dictates the ranges of interaction, and meanwhile, by taking into account the interactions from all the paths a node is involved. We demonstrate that the scale here is closely related to the physical parameters of the dynamical processes on networks, and that our node-importance measure can characterize more precisely the node influence under different physical parameters of the dynamical process. We use epidemic spreading on networks as an example to show that our multiscale node-importance measure is more effective than other measures.     

Networks that optimize a trade-off between efficiency and dynamical resilience

In this Letter we study networks that have been optimized to realize a trade-off between communication efficiency and dynamical resilience. While the first is related to the average shortest pathlength, we argue that the second can be measured by the largest eigenvalue of the adjacency matrix of the network. Best efficiency is realized in star-like configurations, while enhanced resilience is related to the avoidance of short loops and degree homogeneity. Thus crucially, very efficient networks are not resilient while very resilient networks lack in efficiency. Networks that realize a trade-off between both limiting cases exhibit core-periphery structures, where the average degree of core nodes decreases but core size increases as the weight is gradually shifted from a strong requirement for efficiency and limited resilience towards a smaller requirement for efficiency and a strong demand for resilience. We argue that both, efficiency and resilience are important requirements for network design and highlight how networks can be constructed that allow for both.     

Identification of unstable individuals in dynamic networks

To identify the unstable individuals of networks is of great importance for information mining and security management. Exploring a broad range of steady-state dynamical processes including biochemical dynamics, epidemic processes,birth–death processes and regulatory dynamics, we propose a new index from the microscopic perspective to measure the stability of network nodes based on the local correlation matrix. The proposed index describes the stability of each node based on the activity change of the node after its neighbor is disturbed. Simulation and comparison results show our index can identify the most unstable nodes in the network with various dynamical behaviors, which would actually create a richer way and a novel insight of exploring the problem of network controlling and optimization.     

How complex a dynamical network can be?

Positive Lyapunov exponents measure the asymptotic exponential divergence of nearby trajectories of a dynamical system. Not only they quantify how chaotic a dynamical system is, but since their sum is an upper bound for the rate of information production, they also provide a convenient way to quantify the complexity of a dynamical network. We conjecture based on numerical evidences that for a large class of dynamical networks composed by equal nodes, the sum of the positive Lyapunov exponents is bounded by the sum of all the positive Lyapunov exponents of both the synchronization manifold and its transversal directions, the last quantity being in principle easier to compute than the latter. As applications of our conjecture we: (i) show that a dynamical network composed of equal nodes and whose nodes are fully linearly connected produces more information than similar networks but whose nodes are connected with any other possible connecting topology; (ii) show how one can calculate upper bounds for the information production of realistic networks whose nodes have parameter mismatches, randomly chosen; (iii) discuss how to predict the behavior of a large dynamical network by knowing the information provided by a system composed of only two coupled nodes.     

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

本文研究复杂网络动力学模型的无向网络牵制控制的优化选点及节点组重要性排序问题.根据牵制控制的同步准则,网络的牵制控制同步取决于网络的Laplacian删后矩阵的最小特征值.因此,通过合理选择受控节点集得到一个较大的Laplacian删后矩阵最小特征值,是牵制控制优化选点问题的核心所在.基于Laplacian删后矩阵最小...     

Sample-to-sample fluctuations in real-network ensembles

Network modeling based on ensemble averages tacitly assumes that the networks meant to be modeled are typical in the ensemble. Previous research on network eigenvalues, which govern a range of dynamical phenomena, has shown that this is indeed the case for uncorrelated networks with minimum degree ≥ 3. Here, we focus on real networks, which generally have both structural correlations and low-degree nodes. We show that: (i) the ensemble distribution of the dynamically most important eigenvalues can be not only broad and far apart from the real eigenvalue but also highly structured, often with a multimodal rather than a bell-shaped form; (ii) these interesting properties are found to be due to low-degree nodes, mainly those with degree ≤ 3, and network communities, which is a common form of structural correlation found in real networks. In addition to having implications for ensemble-based approaches, this shows that low-degree nodes may have a stronger influence on collective dynamics than previously anticipated from the study of computer-generated networks.     

New approach to synchronization in asymmetrically coupled networks

Global exponentially synchronization in asymmetrically coupled networks is investigated in this Letter. We extend eigenvalue based method to synchronization in symmetrically coupled network to synchronization in asymmetrically coupled network. A new stability criterion of eigenvalue based is derived. In this criterion, both a term that is the second largest eigenvalue of a symmetrical matrix and a term that is the largest value of sum of column of asymmetrical coupling matrix play a key role. Comparing with existing results, the advantage of our synchronization stability result is that it can analytical be applied to the asymmetrically coupled networks and overcome the complexity on calculating eigenvalues of coupling asymmetric matrix. Therefore, this condition is very convenient to use. Moreover, a necessary condition of this synchronization stability criterion is also given by the elements of the coupling asymmetric matrix, which can conveniently be used in judging the synchronization stability condition without calculating the eigenvalues of coupling matrix.     

Synchronization in networks of spatially extended systems

Synchronization processes in networks of spatially extended dynamical systems are analytically and numerically studied. We focus on the relevant case of networks whose elements (or nodes) are spatially extended dynamical systems, with the nodes being connected with each other by scalar signals. The stability of the synchronous spatio-temporal state for a generic network is analytically assessed by means of an extension of the master stability function approach. We find an excellent agreement between the theoretical predictions and the data obtained by means of numerical calculations. The efficiency and reliability of this method is illustrated numerically with networks of beam-plasma chaotic systems (Pierce diodes). We discuss also how the revealed regularities are expected to take place in other relevant physical and biological circumstances.     

Consensus on de Bruijn graphs

We study the consensus dynamics with or without time-delays on directed and undirected de Bruijn graphs. Our results show that consensus on an undirected de Bruijn graph has a lower converging speed and larger time-delay tolerance in comparison with that on an undirected scale-free network. Although there is not much difference between the eigenvalue ratios of the two undirected networks, we found that their dynamical properties are remarkably different; consequently, it is seemingly more informative to consider the second smallest and the largest eigenvalues separately rather than considering their ratio in the study of synchronization of a coupled oscillators network. Moreover, our study on directed de Bruijn graphs reveals that properly setting directions on edges can improve the converging speed and time-delay tolerance simultaneously.     

Bootstrapping Topological Properties and Systemic Risk of Complex Networks Using the Fitness Model

In this paper we present a novel method to reconstruct global topological properties of a complex network starting from limited information. We assume to know for all the nodes a non-topological quantity that we interpret as fitness. In contrast, we assume to know the degree, i.e. the number of connections, only for a subset of the nodes in the network. We then use a fitness model, calibrated on the subset of nodes for which degrees are known, in order to generate ensembles of networks. Here, we focus on topological properties that are relevant for processes of contagion and distress propagation in networks, i.e. network density and k-core structure, and we study how well these properties can be estimated as a function of the size of the subset of nodes utilized for the calibration. Finally, we also study how well the resilience to distress propagation in the network can be estimated using our method. We perform a first test on ensembles of synthetic networks generated with the Exponential Random Graph model, which allows to apply common tools from statistical mechanics. We then perform a second test on empirical networks taken from economic and financial contexts. In both cases, we find that a subset as small as 10 % of nodes can be enough to estimate the properties of the network along with its resilience with an error of 5 %.     

Generalized projective synchronization of two coupled complex networks of different sizes

We investigate a new generalized projective synchronization between two complex dynamical networks of different sizes. To the best of our knowledge, most of the current studies on projective synchronization have dealt with coupled networks of the same size. By generalized projective synchronization, we mean that the states of the nodes in each network can realize complete synchronization, and the states of a pair of nodes from both networks can achieve projective synchronization. Using the stability theory of the dynamical system, several sufficient conditions for guaranteeing the existence of the generalized projective synchronization under feedback control and adaptive control are obtained. As an example, we use Chua's circuits to demonstrate the effectiveness of our proposed approach.     

Complex networks: Dynamics and security

This paper presents a perspective in the study of complex networks by focusing on how dynamics may affect network security under attacks. In particular, we review two related problems: attack-induced cascading breakdown and range-based attacks on links. A cascade in a network means the failure of a substantial fraction of the entire network in a cascading manner, which can be induced by the failure of or attacks on only a few nodes. These have been reported for the internet and for the power grid (e.g., the August 10, 1996 failure of the western United States power grid). We study a mechanism for cascades in complex networks by constructing a model incorporating the flows of information and physical quantities in the network. Using this model we can also show that the cascading phenomenon can be understood as a phase transition in terms of the key parameter characterizing the node capacity. For a parameter value below the phase-transition point, cascading failures can cause the network to disintegrate almost entirely. We will show how to obtain a theoretical estimate for the phase-transition point. The second problem is motivated by the fact that most existing works on the security of complex networks consider attacks on nodes rather than on links. We address attacks on links. Our investigation leads to the finding that many scale-free networks are more sensitive to attacks on short-range than on long-range links. Considering that the small-world phenomenon in complex networks has been identified as being due to the presence of long-range links, i.e., links connecting nodes that would otherwise be separated by a long node-to-node distance, our result, besides its importance concerning network efficiency and security, has the striking implication that the small-world property of scale-free networks is mainly due to short-range links.     

Cascading failure in multilayer networks with dynamic dependency groups

The cascading failure often occurs in real networks. It is significant to analyze the cascading failure in the complex network research. The dependency relation can change over time. Therefore, in this study, we investigate the cascading failure in multilayer networks with dynamic dependency groups. We construct a model considering the recovery mechanism.In our model, two effects between layers are defined. Under Effect 1, the dependent nodes in other layers will be disabled as long as one node does not belong to the largest connected component in one layer. Under Effect 2, the dependent nodes in other layers will recover when one node belongs to the largest connected component. The theoretical solution of the largest component is deduced and the simulation results verify our theoretical solution. In the simulation, we analyze the influence factors of the network robustness, including the fraction of dependent nodes and the group size, in our model. It shows that increasing the fraction of dependent nodes and the group size will enhance the network robustness under Effect 1. On the contrary, these will reduce the network robustness under Effect 2. Meanwhile, we find that the tightness of the network connection will affect the robustness of networks. Furthermore, setting the average degree of network as 8 is enough to keep the network robust.     

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.     

Information transfer dynamics in fixed-pathways networks

Most complex technological networks are defined in such a way that their global properties are manifested at a dynamical level. An example of this is when internal dynamical processes are constrained to predefined pathways, without the possibility of alternate routes. For instance, large corporation software networks, where several flow processes take place, are typically routed along specific paths. In this work, we propose a model to describe the global characteristics of this kind of processes, where the dynamics depends on the state of the nodes, represented by two possibilities: responsive or blocked. We present numerical simulations that show rich global behavior with unexpected emerging properties. In particular, we show that two different regimes appear as a function of the total network load. Each regime is characterized by developing either a unimodal or a bimodal distribution for the density of responsive nodes, directly related to global efficiency. We provide a detailed explanation for the main characteristics of our results as well as an analysis of the implications for real technological systems.     

Network extreme eigenvalue: from mutimodal to scale-free networks

The extreme eigenvalues of adjacency matrices are important indicators on the influence of topological structures to the collective dynamical behavior of complex networks. Recent findings on the ensemble averageability of the extreme eigenvalue have further authenticated its applicability to the study of network dynamics. However, the ensemble average of extreme eigenvalue has only been solved analytically up to the second order correction. Here, we determine the ensemble average of the extreme eigenvalue and characterize its deviation across the ensemble through the discrete form of random scale-free network. Remarkably, the analytical approximation derived from the discrete form shows significant improvement over previous results, which implies a more accurate prediction of the epidemic threshold. In addition, we show that bimodal networks, which are more robust against both random and targeted removal of nodes, are more vulnerable to the spreading of diseases.     

Critical behavior of blind spots in sensor networks

Blind spots in sensor networks, i.e., individual nodes or small groups of nodes isolated from the rest of the network, are of great concern as they may significantly degrade the network's ability to collect and process information. As the operations of many types of sensors in realistic applications rely on short-lifetime power supplies (e.g., batteries), once they are used up ("off"), replacements become necessary ("on"). This off-and-on process can lead to blind spots. An issue of both theoretical and practical interest concerns the dynamical process and the critical behavior associated with the occurrence of blind spots. In particular, there can be various network topologies, and the off-and-on process can be characterized by the probability that a node functions normally, or the occupying probability of a node in the network. The question to be addressed in this paper concerns how the dynamics of blind spots depend on the network topology and on the occupying probability. For regular, random, and mixed networks, we provide theoretical formulas relating the probability of blind spots to the occupying probability, from which the critical point for the occurrence of blind spots can be determined. For scale-free networks, we present a procedure to estimate the critical point. While our theoretical and numerical analyses are presented in the framework of sensor networks, we expect our results to be generally applicable to network partitioning issues in other networks, such as the wireless cellular network, the Internet, or transportation networks, where the issue of blind spots may be of concern.     

Towards the role of social connectivity and aspiration level on evolutionary game

Investigating the evolutionary game dynamics in structured populations is challenging due to the complexity of social interactions. There has been a growing interest in evolutionary game on social networks, particularly concerning how a specific network structure affects the evolution of strategies. Here, we consider a social network of interacting individuals playing the anti-coordination games with mixed strategies, and present a deterministic nonlinear equation for the evolution of strategies where the aspiration level is an incentive in the selection of strategies. We find that with an intermediate aspiration level, there exists an evolutionarily-stable mixed-strategy equilibrium if the cost-to-benefit ratio of altruistic is chosen below a threshold, which is determined by the largest Laplacian eigenvalue of the network. We also give extensive numerical simulations on regular and scale-free networks which confirm the validity of our analytical findings.     

Global synchronization of Chua＇s chaotic delay network by using linear matrix inequality

Global synchronization of Chua‘s chaotic dynamical networks with coupling delays is investigated in this paper.Unlike other approaches, where only local results were obtained, the network is found to be not linearized in this paper.Insteat, the global synchronization is obtained by using the linear matrix inequality theory. Moreover, some quite simple linear-state-error feedback controllers for global synchronization are derived, which can be easily constructed based on the minimum eigenvalue of the coupling matrix. A simulation of Chua‘s chaotic network with global coupling delays in nodes is finally given, which is used to verify the theoretical results of the proposed global synchron izationscheme.     

基于多属性决策的复杂网络节点重要性综合评价方法

复杂网络中的节点重要性评价在实际应用中有着重要意义.现有的一些重要性评价指标如度、介数等存在适用范围有限,评价结果不够全面等缺点,因为节点在复杂网络中的重要性不仅仅受单一因素的影响.为此,本文提出了一种基于多属性决策的复杂网络节点重要性综合评价方法.该方法将复杂网络中的每一个节点看作一个方案,其多个重要性评价指标作为该方案的属性,通过计算每个方案到理想方案的接近程度,最终得到该节点的重要性综合评价结果.该方法不仅可以用于不同类型复杂网络的节点重要性评价,而且便于扩展,实验结果表明了该方法的有效性.