Optimizing algebraic connectivity by edge rewiring

Robustness in complex networks is an ongoing research effort that seeks to improve the connectivity of networks against attacks and failures. Among other measures, algebraic connectivity has been used to characterize processes such as damped oscillation of liquids in connected pipes. Similar characterizations include the number of edges necessary to disconnect a network: the larger the algebraic connectivity, the larger the number of edges required to disconnect a network and hence, the more robust a network. In this paper, we answer the question, ‘Which edge can we rewire to have the largest increase in algebraic connectivity?’. Furthermore, we extend the rewiring of a single edge to rewiring multiple edges to realize the maximal increase in algebraic connectivity. The answer to this question above can provide insights to decision makers within various domains such as communication and transportation networks, who seek an efficient solution to optimize the connectivity and thus increase the robustness of their networks. Most importantly, our analytical and numerical results not only provide insights to the number of edges to rewire, but also the location in the network where these edges would effectuate the maximal increase in algebraic connectivity and therefore, enable a maximal increase in robustness.