Topology design for optimal network coherence
Topology design for optimal network coherence
复制标题
DOI：
10.1109/ecc.2015.7330605
复制
发表时间：
2014-11
期刊：
影响因子：
--
通讯作者：
T. Summers;I. Shames;J. Lygeros;F. Dörfler
中科院分区：
文献类型：
--
作者：
T. Summers;I. Shames;J. Lygeros;F. Dörfler
我们考虑一个网络拓扑设计问题，其中一个初始的无向图底层的网络是给定的，目标是选择一组边缘添加到图中，以优化所得到的网络的一致性。我们表明，网络的一致性是一个子模块功能的网络拓扑结构。因此，一个简单的贪婪算法保证产生接近最佳的边缘集选择。我们还表明，快速秩更新的拉普拉斯伪逆使用广义的谢尔曼-莫里森公式和加速的贪婪算法的变种，可以加快算法在实践中的几个数量级。这些使我们的算法能够扩展到远远超出凸松弛算法可以处理的网络大小。
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.