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_44: An important property of networked systems is their robustness against removal of network nodes, through either random node failure or targeted attack. Although design methods have been proposed for creating, ab initio, a network that has optimal robustness according to a given measure, one is often instead faced with an existing network that cannot feasibly be substantially modified or redesigned, yet whose robustness can be improved by a lesser degree of modification. We present empirical results that show how robustness, as measured either by the size of the largest connected component or by the shortest path length between pairs of nodes, is affected by several different strategies that alter the network by rewiring a fraction of the edges or by adding new edges. We find that a modest alteration of an initially ‘scale-free’ network can usefully improve robustness against attack, particularly when the fraction of attacked nodes is small, and we identify modification schemes that are most effective for this purpose.
  @cite_15: Abstract Robustness of networked systems against noise corruption and structural changes in an underlying network topology is a critical issue for a reliable performance. In this paper, we investigate this issue of robustness in networked systems both from structural and functional viewpoints. Structural robustness deals with the effect of changes in a graph structure due to link or edge failures, while functional robustness addresses how well a system behaves in the presence of noise. We discuss that both of these aspects are inter-related, and can be measured through a common graph invariant. A graph process is introduced where edges are added to an existing graph in a step-wise manner to maximize robustness. Moreover, a relationship between the symmetry of an underlying network structure and robustness is also discussed.
  @cite_7: Terrorist attacks on transportation networks have traumatized modern societies. With a single blast, it has become possible to paralyze airline traffic, electric power supply, ground transportation or Internet communication. How and at which cost can one restructure the network such that it will become more robust against a malicious attack? We introduce a new measure for robustness and use it to devise a method to mitigate economically and efficiently this risk. We demonstrate its efficiency on the European electricity system and on the Internet as well as on complex networks models. We show that with small changes in the network structure (low cost) the robustness of diverse networks can be improved dramatically whereas their functionality remains unchanged. Our results are useful not only for improving significantly with low cost the robustness of existing infrastructures but also for designing economically robust network systems.
summary: In the literature, there are many works related to the construction of robust interaction graphs. Some of these works consider how a robustness measure can be improved via some modifications to the graph topology. For instance, such improvement can be achieved by rewiring a small percentage of the existing edges (e.g., @cite_7 ) or adding a small number of edges to the graph (e.g., @cite_44 @cite_15 ).