Effect of clustering on attack vulnerability of interdependent scale-free networks

In order to deeply understand the complex interdependent systems, it is of great concern to take clustering coefficient, which is an important feature of many real-world systems, into account. Previous study mainly focused on the impact of clustering on interdependent networks under random attacks, while we extend the study to the case of the more realistic attacking strategy, targeted attack. A system composed of two interdependent scale-free networks with tunable clustering is provided. The effects of coupling strength and coupling preference on attack vulnerability are explored. Numerical simulation results demonstrate that interdependent links between two networks make the entire system much more fragile to attacks. Also, it is found that clustering significantly increases the vulnerability of interdependent scale-free networks. Moreover, for fully coupled network, disassortative coupling is found to be most vulnerable to random attacks, while the random and assortative coupling have little difference. Additionally, enhancing coupling strength can greatly enhance the fragility of interdependent networks against targeted attacks. These results can not only improve the deep understanding of structural complexity of complex systems, but also provide insights into the guidance of designing resilient infrastructures.     

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.     

A network efficiency measure with application to critical infrastructure networks

In this paper, we demonstrate how a new network performance/efficiency measure, which captures demands, flows, costs, and behavior on networks, can be used to assess the importance of network components and their rankings. We provide new results regarding the measure, which we refer to as the Nagurney–Qiang measure, or, simply, the N–Q measure, and a previously proposed one, which did not explicitly consider demands and flows. We apply both measures to such critical infrastructure networks as transportation networks and the Internet and further explore the new measure through an application to an electric power generation and distribution network in the form of a supply chain. The Nagurney and Qiang network performance/efficiency measure that captures flows and behavior can identify which network components, that is, nodes and links, have the greatest impact in terms of their removal and, hence, are important from both vulnerability as well as security standpoints.     

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.     

Integrity of Total Graphs via Certain Parameters

Communication networks have been characterized by high levels of service reliability. Links cuts, node interruptions, software errors or hardware failures, and transmission failures at various points can interrupt service for long periods of time. In communication networks, greater degrees of stability or less vulnerability is required. The vulnerability of communication network measures the resistance of the network to the disruption of operation after the failure of certain stations or communication links. If we think of a graph G as modeling a network, many graph-theoretic parameters can be used to describe the stability of communication networks, including connectivity, integrity, and tenacity. We consider two graphs with the same connectivity, but with unequal orders of theirs largest components. Then these two graphs must be different in respect to stability. How can we measure that property? The idea behind the answer is the concept of integrity, which is different from connectivity. Total graphs constitute a large class of graphs. In this paper, we study the integrity of total graphs via some graph parameters.

     

A Fast Algorithm For Finding A Maximum Free Multiflow In An Inner Eulerian Network And Some Generalizations

be a network, where is an undirected graph with nodes and edges, is a set of specified nodes of , called terminals, and each edge of has a nonnegative integer capacity . If the total capacity of edges with one end at is even for every non-terminal node , then is called inner Eulerian. A free multiflow is a collection of flows between arbitrary pairs of terminals such that the total flow through each edge does not exceed its capacity. In this paper we first generalize a method in Karzanov [11] to find a maximum integer free multiflow in an inner Eulerian network, in time, where is the complexity of finding a maximum flow between two terminals. Next we extend our algorithm to solve the so-called laminar locking problem on multiflows, also in time. We then consider analogs of the above problems in inner balanced directed networks, which means that for each non-terminal node , the sums of capacities of arcs entering and leaving are the same. We show that for such a network a maximum integer free multiflow can be constructed in time, and then extend this result to the corresponding locking problem. Received: March 24, 1997     

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.     

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.     

Fixed point optimization algorithm and its application to network bandwidth allocation

A convex optimization problem for a strictly convex objective function over the fixed point set of a nonexpansive mapping includes a network bandwidth allocation problem, which is one of the central issues in modern communication networks. We devised an iterative algorithm, called a fixed point optimization algorithm, for solving the convex optimization problem and conducted a convergence analysis on the algorithm. The analysis guarantees that the algorithm, with slowly diminishing step-size sequences, weakly converges to a unique solution to the problem. Moreover, we apply the proposed algorithm to a network bandwidth allocation problem and show its effectiveness.     

Community Structures of Networks

We present an approach to studying the community structures of networks by using linear programming (LP). Starting with a network in terms of (a) a collection of nodes and (b) a collection of edges connecting some of these nodes, we use a new LP-based method for simultaneously (i) finding, at minimal cost, a second edge set by deleting existing and inserting additional edges so that the network becomes a disjoint union of cliques and (ii) appropriately calibrating the costs for doing so. We provide examples that suggest that, in practice, this approach provides a surprisingly good strategy for detecting community structures in given networks.      

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.     

On duality and fractionality of multicommodity flows in directed networks

In this paper we address a topological approach to multiflow (multicommodity flow) problems in directed networks. Given a terminal weight μ, we define a metrized polyhedral complex, called the directed tight span T_μ, and prove that the dual of the μ-weighted maximum multiflow problem reduces to a facility location problem on T_μ. Also, in case where the network is Eulerian, it further reduces to a facility location problem on the tropical polytope spanned by μ. By utilizing this duality, we establish the classifications of terminal weights admitting a combinatorial min–max relation (i) for every network and (ii) for every Eulerian network. Our result includes the Lomonosov–Frank theorem for directed free multiflows and Ibaraki–Karzanov–Nagamochi’s directed multiflow locking theorem as special cases.     

突发事件对交通网络的影响评估指标和方法

近年来,由于自然灾害,不断地环境恶化以及不可预测的灾害侵袭,突发事件时有发生,突发事件可能对交通网络产生非常严重的影响。本文给出了一些指标来表征突发事件对交通网络的影响程度。这些指标适用于用户最优、系统最优以及效率损失等情形。 我们给出了这些指标的性质并讨论了在用户最优、系统最优以及效率损失等情形下的指标之间的关系。交通网络的数值算例表明了关于突发事件的指标的合理性。突发事件对交通网络的影响程度评估对于道路规划、道路维护以及网络脆弱性分析均有重要意义。     

Two-edge connected subgraphs with bounded rings: Polyhedral results and Branch-and-Cut

We consider the network design problem which consists in determining at minimum cost a 2-edge connected network such that the shortest cycle (a “ring”) to which each edge belongs, does not exceed a given length K. We identify a class of inequalities, called cycle inequalities, valid for the problem and show that these inequalities together with the so-called cut inequalities yield an integer programming formulation of the problem in the space of the natural design variables. We then study the polytope associated with that problem and describe further classes of valid inequalities. We give necessary and sufficient conditions for these inequalities to be facet defining. We study the separation problem associated with these inequalities. In particular, we show that the cycle inequalities can be separated in polynomial time when K≤4. We develop a Branch-and-Cut algorithm based on these results and present extensive computational results.     

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

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

A scoring mechanism for the rank aggregation of network robustness

To date, a number of metrics have been proposed to quantify inherent robustness of network topology against failures. However, each single metric usually only offers a limited view of network vulnerability to different types of random failures and targeted attacks. When applied to certain network configurations, different metrics rank network topology robustness in different orders which is rather inconsistent, and no single metric fully characterizes network robustness against different modes of failure. To overcome such inconsistency, this work proposes a multi-metric approach as the basis of evaluating aggregate ranking of network topology robustness. This is based on simultaneous utilization of a minimal set of distinct robustness metrics that are standardized so to give way to a direct comparison of vulnerability across networks with different sizes and configurations, hence leading to an initial scoring of inherent topology robustness. Subsequently, based on the inputs of initial scoring a rank aggregation method is employed to allocate an overall ranking of robustness to each network topology. A discussion is presented in support of the presented multi-metric approach and its applications to more realistically assess and rank network topology robustness.     

Network Design Via Iterative Rounding Of Setpair Relaxations

A typical problem in network design is to find a minimum-cost sub-network H of a given network G such that H satisfies some prespecified connectivity requirements. Our focus is on approximation algorithms for designing networks that satisfy vertex connectivity requirements. Our main tool is a linear programming relaxation of the following setpair formulation due to Frank and Jordan: a setpair consists of two subsets of vertices (of the given network G); each setpair has an integer requirement, and the goal is to find a minimum-cost subset of the edges of G sucht hat each setpair is covered by at least as many edges as its requirement. We introduce the notion of skew bisupermodular functions and use it to prove that the basic solutions of the linear program are characterized by “non-crossing families” of setpairs. This allows us to apply Jain’s iterative rounding method to find approximately optimal integer solutions. We give two applications. (1) In the k-vertex connectivity problem we are given a (directed or undirected) graph G=(V,E) with non-negative edge costs, and the task is to find a minimum-cost spanning subgraph H such that H is k-vertex connected. Let n=|V|, and let ε<1 be a positive number such that k≤(1−ε)n. We give an -approximation algorithm for both problems (directed or undirected), improving on the previous best approximation guarantees for k in the range . (2)We give a 2-approximation algorithm for the element connectivity problem, matching the previous best approximation guarantee due to Fleischer, Jain and Williamson. * Supported in part by NSERC researchgran t OGP0138432. † Supported in part by NSF Career Award CCR-9875024.     

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.     

On the planar integer two-flow problem

We consider the two-commodity flow problem and give a good characterization of the optimum flow if the augmented network (with both source-sink edges added) is planar. We show that max flow ≧ min cut −1, and describe the structure of those networks for which equality holds.     

Viral conductance: Quantifying the robustness of networks with respect to spread of epidemics

In this paper, we propose a novel measure, viral conductance (VC), to assess the robustness of complex networks with respect to the spread of SIS epidemics. In contrast to classical measures that assess the robustness of networks based on the epidemic threshold above which an epidemic takes place, the new measure incorporates the fraction of infected nodes at steady state for all possible effective infection strengths. Through examples, we show that VC provides more insight about the robustness of networks than does the epidemic threshold. We also address the paradoxical robustness of Barabási–Albert preferential attachment networks. Even though this class of networks is characterized by a vanishing epidemic threshold, the epidemic requires high effective infection strength to cause a major outbreak. On the contrary, in homogeneous networks the effective infection strength does not need to be very much beyond the epidemic threshold to cause a major outbreak. To overcome computational complexities, we propose a heuristic to compute the VC for large networks with high accuracy. Simulations show that the heuristic gives an accurate approximation of the exact value of the VC. Moreover, we derive upper and lower bounds of the new measure. We also apply the new measure to assess the robustness of different types of network structures, i.e. Watts–Strogatz small world, Barabási–Albert, correlated preferential attachment, Internet AS-level, and social networks. The extensive simulations show that in Watts–Strogatz small world networks, the increase in probability of rewiring decreases the robustness of networks. Additionally, VC confirms that the irregularity in node degrees decreases the robustness of the network. Furthermore, the new measure reveals insights about design and mitigation strategies of infrastructure and social networks.