  We consider a network topology design problem in which an initial undirected
graph underlying the network is given and the objective is to select a set of
edges to add to the graph to optimize the coherence of the resulting network.
We show that network coherence is a submodular function of the network
topology. As a consequence, a simple greedy algorithm is guaranteed to produce
near optimal edge set selections. We also show that fast rank one updates of
the Laplacian pseudoinverse using generalizations of the Sherman-Morrison
formula and an accelerated variant of the greedy algorithm can speed up the
algorithm by several orders of magnitude in practice. These allow our
algorithms to scale to network sizes far beyond those that can be handled by
convex relaxation heuristics.
