Percolation of interdependent network of networks

Complex networks appear in almost every aspect of science and technology. Previous work in network theory has focused primarily on analyzing single networks that do not interact with other networks, despite the fact that many real-world networks interact with and depend on each other. Very recently an analytical framework for studying the percolation properties of interacting networks has been introduced. Here we review the analytical framework and the results for percolation laws for a Network Of Networks (NONs) formed by n interdependent random networks. The percolation properties of a network of networks differ greatly from those of single isolated networks. In particular, because the constituent networks of a NON are connected by node dependencies, a NON is subject to cascading failure. When there is strong interdependent coupling between networks, the percolation transition is discontinuous (first-order) phase transition, unlike the well-known continuous second-order transition in single isolated networks. Moreover, although networks with broader degree distributions, e.g., scale-free networks, are more robust when analyzed as single networks, they become more vulnerable in a NON. We also review the effect of space embedding on network vulnerability. It is shown that for spatially embedded networks any finite fraction of dependency nodes will lead to abrupt transition.     

城市公共交通复合系统抗毁性仿真研究

运用复杂网络理论,对以成都市为例的城市公共交通复合系统网络以及两子系统网络进行了相关拓扑特性与抗毁性分析。分析结果显示,以成都市为例的地铁-公交复合网络及其子网络均为具有无标度特性的小世界网络,在L、P两种空间中均表现出随机袭击下的鲁棒性与蓄意袭击下的脆弱性,且节点的抗毁性低于边的抗毁性;同时在相同袭击条件下,复合网络的抗毁性均优于地铁子网络与地面公交子网络。     

Recent advances on failure and recovery in networks of networks

Until recently, network science has focused on the properties of single isolated networks that do not interact or depend on other networks. However it has now been recognized that many real-networks, such as power grids, transportation systems, and communication infrastructures interact and depend on other networks. Here, we will present a review of the framework developed in recent years for studying the vulnerability and recovery of networks composed of interdependent networks. In interdependent networks, when nodes in one network fail, they cause dependent nodes in other networks to also fail. This is also the case when some nodes, like for example certain people, play a role in two networks, i.e. in a multiplex. Dependency relations may act recursively and can lead to cascades of failures concluding in sudden fragmentation of the system. We review the analytical solutions for the critical threshold and the giant component of a network of n interdependent networks. The general theory and behavior of interdependent networks has many novel features that are not present in classical network theory. Interdependent networks embedded in space are significantly more vulnerable compared to non-embedded networks. In particular, small localized attacks may lead to cascading failures and catastrophic consequences. Finally, when recovery of components is possible, global spontaneous recovery of the networks and hysteresis phenomena occur. The theory developed for this process points to an optimal repairing strategy for a network of networks. Understanding realistic effects present in networks of networks is required in order to move towards determining system vulnerability.     

Single or multiple synchronization transitions in scale-free neuronal networks with electrical or chemical coupling

In this paper, we have studied time delay- and coupling strength-induced synchronization transitions in scale-free modified Hodgkin–Huxley (MHH) neuron networks with gap-junctions and chemical synaptic coupling. It is shown that the synchronization transitions are much different for these two coupling types. For gap-junctions, the neurons exhibit a single synchronization transition with time delay and coupling strength, while for chemical synapses, there are multiple synchronization transitions with time delay, and the synchronization transition with coupling strength is dependent on the time delay lengths. For short delays we observe a single synchronization transition, whereas for long delays the neurons exhibit multiple synchronization transitions as the coupling strength is varied. These results show that gap junctions and chemical synapses have different impacts on the pattern formation and synchronization transitions of the scale-free MHH neuronal networks, and chemical synapses, compared to gap junctions, may play a dominant and more active function in the firing activity of the networks. These findings would be helpful for further understanding the roles of gap junctions and chemical synapses in the firing dynamics of neuronal networks.     

eNelator: A simulation system for large-scale vulnerability analysis of species-, disease- and process-specific protein networks

The identification of vulnerabilities in protein networks is a promising approach to predicting potential therapeutic targets. Different methods have been applied to domain-specific applications, with an emphasis on single-node deletions. There is a need to further assess significant associations between vulnerability, functional essentiality and topological features across species, processes and diseases. This requires the development of open, user-friendly systems to generate and test existing hypotheses about the vulnerability of networks in the face of dysfunctional components. We implemented methodologies to estimate the vulnerability of different networks to the dysfunction of different combinations of components, under random and directed attack scenarios. To demonstrate the relevance of our approaches and software, published protein–protein interaction (PPI) networks from Saccharomyces cerevisiae, Escherichia coli and Homo sapiens were analyzed. A PPI network implicated in the development of human heart failure, and signaling networks relevant to Caspase3 and P53 regulation were also investigated. Known essential proteins (individually or in groups) have no detectable effects on network stability. Some of the most vulnerable proteins are neither essential nor hubs. Known diagnostic biomarkers have little effect on the communication efficiency of the disease network. Predictions made on the signaling networks are consistent with recent experimental evidence. Our system, which integrates other quantitative measures, can assist in the identification of potential drug targets and systems-level properties. The system for large-scale analysis of random and directed attacks is freely available, as a Cytoscape plugin, on request from the authors.     

An individual-based modeling framework for infectious disease spreading in clustered complex networks

We introduce an individual-based model with dynamical equations for susceptible-infected-susceptible (SIS) epidemics on clustered networks. Linking the mean-field and quenched mean-field models, a general method for deriving a cluster approximation for three-node loops in complex networks is proposed. The underlying epidemic threshold condition is derived by using the quasi-static approximation. Our method thus extends the pair quenched mean-field (pQMF) approach for SIS disease spreading in unclustered networks to the scenario of epidemic outbreaks in clustered systems with abundant transitive relationships.We found that clustering can significantly alter the epidemic threshold, depending nontrivially on topological details of the underlying population structure. The validity of our method is verified through the existence of bounded solutions to the clustered pQMF model equations, and is further attested via stochastic simulations on homogeneous small-world artificial networks and growing scale-free synthetic networks with tunable clustering, as well as on real-world complex networked systems. Our method has vital implications for the future policy development and implementation of intervention measures in highly clustered networks, especially in the early stages of an epidemic in which clustering can decisively alter the growth of a contagious outbreak.     

Vulnerability of complex networks

We consider normalized average edge betweenness of a network as a metric of network vulnerability. We suggest that normalized average edge betweenness together with is relative difference when certain number of nodes and/or edges are removed from the network is a measure of network vulnerability, called vulnerability index. Vulnerability index is calculated for four synthetic networks: Erdős–Rényi (ER) random networks, Barabási–Albert (BA) model of scale-free networks, Watts–Strogatz (WS) model of small-world networks, and geometric random networks. Real-world networks for which vulnerability index is calculated include: two human brain networks, three urban networks, one collaboration network, and two power grid networks. We find that WS model of small-world networks and biological networks (human brain networks) are the most robust networks among all networks studied in the paper.     

Cascade-robustness optimization of coupling preference in interconnected networks

Recently, the robustness of interconnected networks has attracted extensive attentions, one of which is to investigate the influence of coupling preference. In this paper, the memetic algorithm (MA) is employed to optimize the coupling links of interconnected networks. Afterwards, a comparison is made between MA optimized coupling strategy and traditional assortative, disassortative and random coupling preferences. It is found that the MA optimized coupling strategy with a moderate assortative value shows an outstanding performance against cascading failures on both synthetic scale-free interconnected networks and real-world networks. We then provide an explanation for this phenomenon from a micro-scope point of view and propose a coupling coefficient index to quantify the coupling preference. Our work is helpful for the design of robust interconnected networks.     

On the topologic structure of economic complex networks: Empirical evidence from large scale payment network of Estonia

This paper presents the first topological analysis of the economic structure of an entire country based on payments data obtained from Swedbank. This data set is exclusive in its kind because around 80% of Estonia's bank transactions are done through Swedbank; hence, the economic structure of the country can be reconstructed. Scale-free networks are commonly observed in a wide array of different contexts such as nature and society. In this paper, the nodes are comprised by customers of the bank (legal entities) and the links are established by payments between these nodes. We study the scaling-free and structural properties of this network. We also describe its topology, components and behaviors. We show that this network shares typical structural characteristics known in other complex networks: degree distributions follow a power law, low clustering coefficient and low average shortest path length. We identify the key nodes of the network and perform simulations of resiliency against random and targeted attacks of the nodes with two different approaches. With this, we find that by identifying and studying the links between the nodes is possible to perform vulnerability analysis of the Estonian economy with respect to economic shocks.     

General results on preferential attachment and clustering coefficient

This is a review paper that covers some recent results on the behavior of the clustering coefficient in preferential attachment networks and scale-free networks in general. The paper focuses on general approaches to network science. In other words, instead of discussing different fully specified random graph models, we describe some generic results which hold for classes of models. Namely, we first discuss a generalized class of preferential attachment models which includes many classical models. It turns out that some properties can be analyzed for the whole class without specifying the model. Such properties are the degree distribution and the global and average local clustering coefficients. Finally, we discuss some surprising results on the behavior of the global clustering coefficient in scale-free networks. Here we do not assume any underlying model.     

Broad-scale small-world network topology induces optimal synchronization of flexible oscillators

The discovery of small-world and scale-free properties of many man-made and natural complex networks has attracted increasing attention. Of particular interest is how the structural properties of a network facilitate and constrain its dynamical behavior. In this paper we study the synchronization of weakly coupled limit-cycle oscillators in dependence on the network topology as well as the dynamical features of individual oscillators. We show that flexible oscillators, characterized by near zero values of divergence, express maximal correlation in broad-scale small-world networks, whereas the non-flexible (rigid) oscillators are best correlated in more heterogeneous scale-free networks. We found that the synchronization behavior is governed by the interplay between the networks global efficiency and the mutual frequency adaptation. The latter differs for flexible and rigid oscillators. The results are discussed in terms of evolutionary advantages of broad-scale small-world networks in biological systems.     

Application of modal analysis in assessing attack vulnerability of complex networks

In this paper we propose an alternative way to study robustness and vulnerability of complex networks, applying a modal analysis. The modal weights of the network nodes are considered as a measure for their busyness, which is further used for preferential removal of nodes and attack simulation. Analyses of the attack vulnerability are carried out for several generic graphs, generated according to ER and BA algorithms, as well as for some examples of manmade networks. It was found that a modal weight based attack causes significant disintegration of manmade networks by removing a small fraction of the busiest nodes, comparable to the one based on the node degree and betweenness centrality.     

Network robustness and irreversibility of information diffusion in Complex networks

Complex networks are characterized based on a newly proposed parameter, “degree of diffusion α”. It defines the ratio of information adopters to non-adopters within a diffusion process over consecutive penetration depths. Furthermore, the perfectness of a social network is evaluated by exploring different variations of α such as the reverse diffusion (α_reverse) and the random-kill-diffusion (RKD) processes. The analysis of α_reverse and RKD processes shows information diffusion irreversibility in small-world and scale-free but not in random networks. It also shows that random networks are more stable toward attacks, resulting a complete information diffusion process over the entire network. Finally, a real Complex network example, represented as a “virtual friendship network” was analyzed and found to share properties of both random and small-world networks. Therefore, it is characterized to be somewhere between random and small-world network models or in other words, it is a randomized small-world network model.     

Generating hierarchial scale-free graphs from fractals

Motivated by the hierarchial network model of E. Ravasz, A.-L. Barabási, and T. Vicsek, we introduce deterministic scale-free networks derived from a graph directed self-similar fractal Λ. With rigorous mathematical results we verify that our model captures some of the most important features of many real networks: the scale-free and the high clustering properties. We also prove that the diameter is the logarithm of the size of the system. We point out a connection between the power law exponent of the degree distribution and some intrinsic geometric measure theoretical properties of the underlying fractal. Using our (deterministic) fractal Λ we generate random graph sequence sharing similar properties.     

Branching structure and maximum degree of an evolving random tree

We introduce the concept of an evolving random tree. The proposed model is a combination of a preferential attachment model and a uniform model. We consider the branch structure and maximum degree of the evolving random tree, which can partially explain the robustness under random attack and the vulnerability to targeted attack in the world wide web.     

Epidemic spreading of an SEIRS model in scale-free networks

An SEIRS epidemic model on the scale-free networks is presented, where the active contact number of each vertex is assumed to be either constant or proportional to its degree for this model. Using the analytical method, we obtain the two threshold values for above two cases and find that the threshold value for constant contact is independent of the topology of the underlying networks. The existence of positive equilibrium is determined by threshold value. For a finite size of scale-free network, we prove the local stability of disease-free equilibrium and the permanence of the disease on the network. Furthermore, we investigate two major immunization strategies, random immunization and targeted immunization, some similar results are obtained. The simulation shows the positive equilibrium is stable.     

Analysis of Linux kernel as a complex network

Operating system (OS) acts as an intermediary between software and hardware in computer-based systems. In this paper, we analyze the core of the typical Linux OS, Linux kernel, as a complex network to investigate its underlying design principles. It is found that the Linux Kernel Network (LKN) is a directed network and its out-degree follows an exponential distribution while the in-degree follows a power-law distribution. The correlation between topology and functions is also explored, by which we find that LKN is a highly modularized network with 12 key communities. Moreover, we investigate the robustness of LKN under random failures and intentional attacks. The result shows that the failure of the large in-degree nodes providing basic services will do more damage on the whole system. Our work may shed some light on the design of complex software systems.     

Wavelength assignment for reducing in-band crosstalk attack propagation in optical networks: ILP formulations and heuristic algorithms

Today’s Transparent Optical Networks (TONs) are highly vulnerable to various physical-layer attacks, such as high-power jamming, which can cause severe service disruption or even service denial. The transparency of TONs enables certain attacks to propagate through the network, not only increasing their damage proportions, but also making source identification and attack localization more difficult. High-power jamming attacks causing in-band crosstalk in switches are amongst the most malicious of such attacks. In this paper, we propose a wavelength assignment scheme to reduce their damage assuming limited attack propagation capabilities. This complements our previous work in Furdek et al. (M. Furdek, N. Skorin-Kapov, M. Grbac, Attack-aware wavelength assignment for localization of in-band crosstalk attack propagation, IEEE/OSA Journal of Optical Communications and Networking 2 (11) (2010) 1000–1009) where we investigated infinite jamming attack propagation to find an upper bound on the network vulnerability to such attacks. Here, we consider a more realistic scenario where crosstalk attacks can spread only via primary and/or secondary attackers and define new objective criteria for wavelength assignment, called the PAR (Primary Attack Radius) and SAR (Secondary Attack Radius), accordingly. We formulate the problem variants as integer linear programs (ILPs) with the objectives of minimizing the PAR and SAR values. Due to the intractability of the ILP formulations, for larger instances we propose GRASP (Greedy Randomized Adaptive Search Procedure) heuristic algorithms to find suboptimal solutions in reasonable time. Results show that these approaches can obtain solutions using the same number of wavelengths as classical wavelength assignment, while significantly reducing jamming attack damage proportions in optical networks.     

Effective measurement of network vulnerability under random and intentional attacks

The study of the security and stability of complex networks plays a central role in reducing the risk and consequences of attacks or disfunctions of any type. The concept of vulnerability helps to measure the response of complex networks subjected to attacks on vertices and edges and it allows to spot the critical component of a network in order to improve its security. We introduce an accurate and computable definition of network vulnerability which is directly connected with its topology and we analyze its basic properties. We discuss the relationship of the vulnerability with other parameters of the network and we illustrate this with some examples.