text: Multi-agent networks are often modeled as interaction graphs, where the nodes represent the agents and the edges denote some direct interactions. The robustness of a multi-agent network to perturbations such as failures, noise, or malicious attacks largely depends on the corresponding graph. In many applications, networks are desired to have well-connected interaction graphs with relatively small number of links. One family of such graphs is the random regular graphs. In this paper, we present a decentralized scheme for transforming any connected interaction graph with a possibly non-integer average degree of @math into a connected random @math -regular graph for some @math . Accordingly, the agents improve the robustness of the network while maintaining a similar number of links as the initial configuration by locally adding or removing some edges.
  @cite_18: The most highly connected proteins in the cell are the most important for its survival. Proteins are traditionally identified on the basis of their individual actions as catalysts, signalling molecules, or building blocks in cells and microorganisms. But our post-genomic view is expanding the protein's role into an element in a network of protein–protein interactions as well, in which it has a contextual or cellular function within functional modules1,2. Here we provide quantitative support for this idea by demonstrating that the phenotypic consequence of a single gene deletion in the yeast Saccharomyces cerevisiae is affected to a large extent by the topological position of its protein product in the complex hierarchical web of molecular interactions.
  @cite_26: This paper argues that in the presence of intersectoral input-output linkages, microeconomic idiosyncratic shocks may lead to aggregate fluctuations. In particular, it shows that, as the economy becomes more disaggregated, the rate at which aggregate volatility decays is determined by the structure of the network capturing such linkages. Our main results provide a characterization of this relationship in terms of the importance of different sectors as suppliers to their immediate customers as well as their role as indirect suppliers to chains of downstream sectors. Such higher-order interconnections capture the possibility of "cascade effects" whereby productivity shocks to a sector propagate not only to its immediate downstream customers, but also indirectly to the rest of the economy. Our results highlight that sizable aggregate volatility is obtained from sectoral idiosyncratic shocks only if there exists significant asymmetry in the roles that sectors play as suppliers to others, and that the "sparseness" of the input-output matrix is unrelated to the nature of aggregate fluctuations.
  @cite_37: 
  @cite_9: Centrality measures, or at least popular interpretations of these measures, make implicit assumptions about the manner in which traffic flows through a network. For example, some measures count only geodesic paths, apparently assuming that whatever flows through the network only moves along the shortest possible paths. This paper lays out a typology of network flows based on two dimensions of variation, namely the kinds of trajectories that traffic may follow (geodesics, paths, trails, or walks) and the method of spread (broadcast, serial replication, or transfer). Measures of centrality are then matched to the kinds of flows that they are appropriate for. Simulations are used to examine the relationship between type of flow and the differential importance of nodes with respect to key measurements such as speed of reception of traffic and frequency of receiving traffic. It is shown that the off-the-shelf formulas for centrality measures are fully applicable only for the specific flow processes they are designed for, and that when they are applied to other flow processes they get the “wrong” answer. It is noted that the most commonly used centrality measures are not appropriate for most of the flows we are routinely interested in. A key claim made in this paper is that centrality measures can be regarded as generating expected values for certain kinds of node outcomes (such as speed and frequency of reception) given implicit models of how traffic flows, and that this provides a new and useful way of thinking about centrality. © 2004 Elsevier B.V. All rights reserved.
  @cite_21: We study the response of complex networks subject to attacks on vertices and edges. Several existing complex network models as well as real-world networks of scientific collaborations and Internet traffic are numerically investigated, and the network performance is quantitatively measured by the average inverse geodesic length and the size of the largest connected subgraph. For each case of attacks on vertices and edges, four different attacking strategies are used: removals by the descending order of the degree and the betweenness centrality, calculated for either the initial network or the current network during the removal procedure. It is found that the removals by the recalculated degrees and betweenness centralities are often more harmful than the attack strategies based on the initial network, suggesting that the network structure changes as important vertices or edges are removed. Furthermore, the correlation between the betweenness centrality and the degree in complex networks is studied.
  @cite_0: Centrality measures are used in network science to rank the relative importance of nodes and edges of a graph. Here we define new measures of centrality for power grid structure that are based on its functionality. We show that the relative importance analysis based on centrality in graph theory can be generalized to power grid network with its electrical parameters taken into account. In the paper we experiment with the proposed electrical centrality measures on the NYISO-2935 system and the IEEE 300-bus system. We analyze the centrality distribution in order to identify important nodes or branches in the system which are of essential importance in terms of system vulnerability. We also present and discuss a number of interesting discoveries regarding the importance rank of power grid nodes and branches.
summary: In some applications, the robustness of a graph is related to the centrality measures such as the degree, betweenness, closeness, and eigenvector centralities. Loosely speaking, the centrality measures capture the relative importances of the nodes in a graph. Detailed reviews on the centrality measures and their applications can be found in @cite_9 @cite_37 and the references therein. Typically, the perturbations applied to the nodes with higher centrality scores have a stronger impact on the overall system (e.g., @cite_26 @cite_18 @cite_21 @cite_0 ). Hence, graphs with unbalanced centrality distributions are usually vulnerable to such worst-case perturbations.