Growing Well-Connected Graphs

Procedings IEEE Conference on Decision and Control, pages 6605–6611, December 2006.

• growing_fast_graphs.pdf

The algebraic connectivity of a graph is the second smallest eigenvalue of the graph Laplacian, and is a measure of how well connected the graph is. We study the problem of adding edges (from a set of candidate edges) to a graph so as to maximize its algebraic connectivity. This is a difficult combinatorial optimization, so we seek a heuristic for approximately solving the problem. The standard convex relaxation of the problem can be expressed as a semidefinite program (SDP); for modest sized problems, this yields a cheaply computable upper bound on the optimal value, as well as a heuristic for choosing the edges to be added. We describe a new greedy heuristic for the problem. The heuristic is based on the Fiedler vector, and therefore can be applied to very large graphs.