On Maximizing Algebraic Connectivity of Networks for Various Engineering Applications Conference Paper uri icon

abstract

  • © 2015 EUCA. We discuss a simplified version of an open problem in system realization theory which has several important practical applications in complex networks. Particularly, we focus on algebraic connectivity (λ2) of the Laplacian of the network as an objective for maximization. We show that the maximum value of forced response of a linear mechanical (spring-mass) system can be minimized when the λ2 of the corresponding stiffness matrix is maximized. In the case of motion control problems related to vehicle localization with noisy measurements, we show that the λ2 plays a vital role to control their positions towards a desired formation. In UAV adhoc infrastructure networks, we show that the λ2 of the information flow graph governs the stability of the rigid formation with respect to disturbance attenuation. In the context of UAV adhoc communication networks, we also provide a physical interpretation for the maximization of λ2 via the closely related Cheeger constant or the isoperimetric number. We further discuss a Fiedler vector based mixed-integer linear programing formulation for the problem of maximizing λ2 and obtain optimal solutions and upper bounds based on cutting plane methods. Computational results corroborate the performance of proposed algorithms.

author list (cited authors)

  • Nagarajan, H., Rathinam, S., & Darbha, S.

citation count

  • 8

publication date

  • July 2015

publisher