Algebraic connectivity optimization via link addition

Significant research effort has been devoted to the topological features of complex networks to enhance the performance of dynamic processes implemented on these networks. In this work, we investigate how to optimize a network for a given dynamic process via a minor topological modification. The algebraic connectivity a(G) of a network G characterizes the performance of e.g. synchronization of dynamic processes at the nodes of the network G and random walks on networks which models e.g. the dispersion phenomena. We confine ourselves to the problem: "Where to add a link in a network G such that the algebraic connectivity is increased the most?" Exhaustive searching for the optimal link addition is computationally infeasible. Hence, we propose two strategies: 1. adding a link between the minimal degree node and a random other node; 2. adding a link between a node pair with the maximal |u{i}-u{j}|, the absolute difference between the i-th and j-th elements of the Fiedler vector of G. Strategy 1 and 2 are compared with random link addition in three classes of networks: the Erdös-Rényi random graph, the BA model and the k-ary tree. The Fiedler vector based strategy 2 performs better than strategy 1. However, strategy 1 requires only local information, i.e. node degree.