Designing Well-connected Networks via Convex Optimization (PhD Thesis)

Abstract:

This thesis studies several optimization problems related to designing well-connected networks. We first discuss two optimization problems where the variables are weights, or probabilities, on the edges of the network graph. The first is designing randomized gossip algorithms for fast distributed averaging on an arbitrary network. We show that the averaging time depends on the second largest eigenvalue of the stochastic matrix characterizing the averaging algorithm, and pose the problem of finding the fastest such algorithm as a semidefinite program (SDP). The second problem is to find the reversible random walk with the smallest average commute time on a given graph. Using the relation between effective resistance and commute time, we show that this is a convex optimization problem as well, and can be formulated as an SDP. The convexity of these problems has both theoretical and practical implications: they can be efficiently solved numerically, and we can exploit convexity to derive interesting analytical results for these problems. We next study two problems related to the algebraic connectivity of a graph, which is the second smallest eigenvalue of the graph Laplacian. First we consider the problem of adding edges to an unweighted graph to increase its algebraic connectivity. The problem of choosing the best $k$ edges of a given set of $m$ candidate edges is combinatorial; we describe a heuristic for adding edges based on the Fiedler vector which performs very well, and is easily computed even for very large graphs. Second, we study the problem of computing upper bounds on the algebraic connectivity over a family of graphs. We show that an upper bound can be computed as the solution to a convex optimization problem. By observing that it suffices to optimize over the subset of matrices invariant under the symmetry group of the set of graphs, we can solve the optimization problem analytically for families of graphs with large enough symmetry groups.