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_29: A novel distributed algorithm for constructing random overlay networks that are composed of d Hamilton cycles is presented. The protocol is completely decentralized as no globally-known server is required. The constructed topologies are expanders with O(log sub d n) diameter with high probability. Our construction is highly scalable because both the processing and the space requirements at each node grow logarithmically with the network size. A new node can join the network in O(log sub d n) time with O(d log sub d n) messages. A node can leave in O(1) time with O(d) messages. The protocol is robust against an offline adversary selecting the sequence of the join and leave operations. We also discuss a layered construction of the random expander networks in which any node can be located in O(log n) time. The random expander networks have applications in community discovery, distributed lookup service, and dynamic connectivity.
  @cite_5: Abstract An algorithm is presented which randomly selects a labelled graph with specified vertex degrees from a distribution which is arbitrarily close to uniform. The algorithm is based on simulation of a rapidly convergent stochastic process, and runs in polynomial time for a wide class of degree sequences, including all regular sequences and all n -vertex sequences with no degree exceeding √ n 2. The algorithm can be extended to cover the selection of a graph with given degree sequence which avoids a specified set of edges. One consequence of this extension is the existence of a polynomial-time algorithm for selecting an f -factor in a sufficiently dense graph. A companion algorithm for counting degree-constrained graphs is also presented; this algorithm has exactly the same range of validity as the one for selection.
  @cite_16: Let Δ and n be natural numbers such that Δn = 2m is even and Δ ⩽ (2 log n )1 2 - 1. Then as n →, the number of labelled Δ-regular graphs on n vertices is asymptotic to e − λ − λ 2 ( 2 m ) ! m ! 2 m ( Δ ! ) m where λ = (Δ -1) 2. As a consequence of the method we determine the asymptotic distribution of the number of short cycles in graphs with a given degree sequence, and give analogous formulae for hypergraphs.
  @cite_25: 
  @cite_17: We present a practical algorithm for generating random regular graphs. For all d growing as a small power of n, the d-regular graphs on n vertices are generated approximately uniformly at random, in the sense that all d-regular graphs on n vertices have in the limit the same probability as n → ∞. The expected runtime for these ds is O(nd2).
summary: A random @math -regular graph with @math nodes can be constructed by generating @math copies for each node, picking a uniform random perfect matching on the @math copies, and connecting any two nodes if the matching contains an edge between their copies (e.g., @cite_16 @cite_17 ). In @cite_29 , the authors present a distributed scheme for incrementally building random @math -regular multi-graphs with @math Hamiltonian cycles. Alternatively, some graph processes may be designed to transform an initial @math -regular graph into a random @math -regular graph by inducing a Markov chain with a uniform limiting distribution over the set of @math -regular graphs (e.g., @cite_5 @cite_25 ). The method in this paper is also based on designing a graph process with a uniform limiting distribution over the set of @math -regular graphs. Compared to the similar works in the literature, the proposed scheme is applicable to the most generic case, and it is decentralized. The initial graph is not required to satisfy some strong properties such as being regular or having an integer average degree. Furthermore, the global transformation is achieved via only some local graph operations.