  We propose an axiomatic approach for design and performance analysis of noisy
linear consensus networks by introducing a notion of systemic performance
measure. This class of measures are spectral functions of Laplacian eigenvalues
of the network that are monotone, convex, and orthogonally invariant with
respect to the Laplacian matrix of the network. It is shown that several
existing gold-standard and widely used performance measures in the literature
belong to this new class of measures. We build upon this new notion and
investigate a general form of combinatorial problem of growing a linear
consensus network via minimizing a given systemic performance measure. Two
efficient polynomial-time approximation algorithms are devised to tackle this
network synthesis problem: a linearization-based method and a simple greedy
algorithm based on rank-one updates. Several theoretical fundamental limits on
the best achievable performance for the combinatorial problem is derived that
assist us to evaluate optimality gaps of our proposed algorithms. A detailed
complexity analysis confirms the effectiveness and viability of our algorithms
to handle large-scale consensus networks.
