Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.

  

Topology Design for Optimal Network Coherence

Author(s):

T.H. Summers, I. Shames, J. Lygeros, F. Dörfler
Conference/Journal:

Abstract:

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.

Year:

2014
Type of Publication:

(15)Miscellaneous
Supervisor:



File Download:

Request a copy of this publication.
(Uses JavaScript)
% Autogenerated BibTeX entry
@Misc { SumEtal:2014:IFA_5056,
    author={T.H. Summers and I. Shames and J. Lygeros and F. D{\"o}rfler},
    title={{Topology Design for Optimal Network Coherence}},
    month=nov,
    year={2014},
    url={http://control.ee.ethz.ch/index.cgi?page=publications;action=details;id=5056}
}
Permanent link