DOE OSTI · 973665
Algebraic connectivity and graph robustness.
Abstract
Recent papers have used Fiedler's definition of algebraic connectivity to show that network robustness, as measured by node-connectivity and edge-connectivity, can be increased by increasing the algebraic connectivity of the network. By the definition of algebraic connectivity, the second smallest eigenvalue of the graph Laplacian is a lower bound on the node-connectivity. In this paper we show that for circular random lattice graphs and mesh graphs algebraic connectivity is a conservative lower bound, and that increases in algebraic connectivity actually correspond to a decrease in node-connectivity. This means that the networks are actually less robust with respect to node-connectivity as the algebraic connectivity increases. However, an increase in algebraic connectivity seems to correlate well with a decrease in the characteristic path length of these networks - which would result in quicker communication through the network. Applications of these results are then discussed for perimeter security.
Explore related subjects
Keep this discovery
Explore connections, maps & timelines
Feddema, John Todd, Byrne, Raymond Harry, Abdallah, Chaouki T. 2009-07-01. Algebraic connectivity and graph robustness.. https://doi.org/10.2172/973665
Cite the original work for its findings. Save a collection to share your selection of sources.