3d International ICST Conference on Bio-Inspired Models of Network, Information, and Computing Systems

Research Article

Algebraic connectivity optimization via link addition

Download271 downloads
        author={Huijuan Wang and Piet  Van Mieghem},
        title={Algebraic connectivity optimization via link addition},
        proceedings={3d International ICST Conference on Bio-Inspired Models of Network, Information, and Computing Systems},
        keywords={Algebraic connectivity synchronization optimization link addition},
  • Huijuan Wang
    Piet Van Mieghem
    Year: 2010
    Algebraic connectivity optimization via link addition
    DOI: 10.4108/ICST.BIONETICS2008.4691
Huijuan Wang1,*, Piet Van Mieghem1,*
  • 1: Delft University of Technology, P.O. Box 5031, 2600 GA Delft, The Netherlands
*Contact email: h.wang@tudelft.nl, P.F.A.VanMieghem@tudelft.nl


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.