  We investigate how the graph topology influences the robustness to noise in
undirected linear consensus networks. We measure the structural robustness by
using the smallest possible value of steady state population variance of states
under the noisy consensus dynamics with edge weights from the unit interval. We
derive tight upper and lower bounds on the structural robustness of networks
based on the average distance between nodes and the average node degree. Using
the proposed bounds, we characterize the networks with different types of
robustness scaling under increasing size. Furthermore, we present a fundamental
trade-off between the structural robustness and the average degree of networks.
While this trade-off implies that a desired level of structural robustness can
only be achieved by graphs with a sufficiently large average degree, we also
show that there exist dense graphs with poor structural robustness. We then
show that, random k-regular graphs (the degree of each node is k) with n nodes
typically have near-optimal structural robustness among all the graphs with
size n and average degree k for sufficiently large n and k. We also show that
when k increases properly with n, random k-regular graphs maintain a structural
robustness within a constant factor of the complete graph's while also having
the minimum average degree required for such robustness.
