In this article we present the Hayastan Shakarian (HS), a robustness index for complex networks. HS measures the impact of a network disconnection (edge) while comparing the sizes of the remaining connected components. Strictly speaking, the Hayastan Shakarian index is defined as edge removal that produces the maximal inverse of the size of the largest connected component divided by the sum of the sizes of the remaining ones. We tested our index in attack strategies where the nodes are disconnected in decreasing order of a specified metric. We considered using the Hayastan Shakarian cut (disconnecting the edge with max HS) and other well-known strategies as the higher betweenness centrality disconnection. All strategies were compared regarding the behavior of the robustness (R-index) during the attacks. In an attempt to simulate the internet backbone, the attacks were performed in complex networks with power-law degree distributions (scale-free networks). Preliminary results show that attacks based on disconnecting using the Hayastan Shakarian cut are more dangerous (decreasing the robustness) than the same attacks based on other centrality measures. We believe that the Hayastan Shakarian cut, as well as other measures based on the size of the largest connected component, provides a good addition to other robustness metrics for complex networks.
Another interesting edge-based metrics are: the increase of distances in a network caused by the deletion of vertices and edges @cite_14 ; the mean connectivity @cite_12 , that is, the probability that a network is disconnected by the random deletion of edges; the average connected distance (the average length of the shortest paths between connected pairs of nodes in the network) and the fragmentation (the decay of a network in terms of the size of its connected components after random edge disconnections) @cite_20 ; the balance-cut resilience, that is, the capacity of a minimum cut such that the two resulting vertex sets contain approximately the same number (similar to the HS-index but aiming to divide the network only in halves @cite_4 , not in equal sized connected components); the effective diameter ( '' @cite_9 ); and the Dynamic Network Robustness (DYNER) @cite_1 , where a backup path between nodes after a node disconnection and its length is used as a robustness metric in communication networks.
@cite_14 @cite_4 @cite_9 @cite_1 @cite_12 @cite_20
2134239708 2163252320 1571874655 2065769502
Two new measures of network performance, namely, the incremental distance sequence and the incremental diameter sequence, are introduced for application in network topology design. These sequences can be defined for both vertex deletions and edge deletions. A complete characterization of the vertex-deleted incremental distance sequence is presented. Proof of this characterization is constructive in nature. A condition for the feasibility of an edge-deleted incremental distance sequence and a procedure for realizing such a sequence are given. Interrelationships between the elements of incremental distance sequences and incremental diameter sequences are studied. Using these results, it is shown that a graph that has a specified diameter and a specified maximum increase in diameters for deletions of vertex sets of given cardinalities can be designed. > Following the long-held belief that the Internet is hierarchical, the network topology generators most widely used by the Internet research community, Transit-Stub and Tiers, create networks with a deliberately hierarchical structure. However, in 1999 a seminal paper by revealed that the Internet's degree distribution is a power-law. Because the degree distributions produced by the Transit-Stub and Tiers generators are not power-laws, the research community has largely dismissed them as inadequate and proposed new network generators that attempt to generate graphs with power-law degree distributions.Contrary to much of the current literature on network topology generators, this paper starts with the assumption that it is more important for network generators to accurately model the large-scale structure of the Internet (such as its hierarchical structure) than to faithfully imitate its local properties (such as the degree distribution). The purpose of this paper is to determine, using various topology metrics, which network generators better represent this large-scale structure. We find, much to our surprise, that network generators based on the degree distribution more accurately capture the large-scale structure of measured topologies. We then seek an explanation for this result by examining the nature of hierarchy in the Internet more closely; we find that degree-based generators produce a form of hierarchy that closely resembles the loosely hierarchical nature of the Internet. In this paper we apply data mining analysis to study the topology of the Internet thus creating a new processing framework To the best of our knowledge this is one of the rst studies that focus on the Internet topology at the router level i e each node is a router The size K nodes and the nature of the graph are such that new analysis methods have to be employed First we suggest computationally expensive metrics to characterize topological properties Then we present an e cient approximation algorithm that makes the calculation of these metrics possible Finally we demonstrate the initial results of our framework For example we show that we can identify central routers and poorly connected or even isolated nodes We also nd that the Internet is surprisingly resilient to random link and router failures having only small changes in the connectivity for fewer than failures Our framework seems a promising step towards understanding and characterizing the Internet topology and possible other real communication graphs such as web graphs Many complex systems display a surprising degree of tolerance against errors. For example, relatively simple organisms grow, persist and reproduce despite drastic pharmaceutical or environmental interventions, an error tolerance attributed to the robustness of the underlying metabolic network1. Complex communication networks2 display a surprising degree of robustness: although key components regularly malfunction, local failures rarely lead to the loss of the global information-carrying ability of the network. The stability of these and other complex systems is often attributed to the redundant wiring of the functional web defined by the systems' components. Here we demonstrate that error tolerance is not shared by all redundant systems: it is displayed only by a class of inhomogeneously wired networks, called scale-free networks, which include the World-Wide Web3,4,5, the Internet6, social networks7 and cells8. We find that such networks display an unexpected degree of robustness, the ability of their nodes to communicate being unaffected even by unrealistically high failure rates. However, error tolerance comes at a high price in that these networks are extremely vulnerable to attacks (that is, to the selection and removal of a few nodes that play a vital role in maintaining the network's connectivity). Such error tolerance and attack vulnerability are generic properties of communication networks.