A Julia Package for Maximizing Algebraic Connectivity of Graphs

Status:

LaplacianOpt

LaplacianOpt is a Julia package for designing robust weighted graphs by maximizing the algebraic connectivity of their Laplacian matrices. Given a weighted base graph (possibly empty), a set of candidate weighted edges, and an augmentation budget K, LaplacianOpt selects K edges that make the resulting graph as well connected as possible.

Algebraic connectivity is the second smallest eigenvalue of the graph Laplacian. Larger values indicate stronger global connectivity, and this measure is widely used to study robustness, synchronizability, and sparsification of networks.

The package supports mixed-integer formulations, polyhedral relaxations, cutting-plane methods, and heuristic approaches for finding globally optimal and high-quality locally optimal solutions. A common use case is designing sparse but robust measurement networks for robot localization under a limited edge budget; starting from N vertices, no existing edges, a complete candidate graph, and K = N - 1, LaplacianOpt searches for a spanning tree with maximum algebraic connectivity.

Usage

Clone the repository and start Julia in the project environment:

julia --project=.

From the Julia package prompt, instantiate dependencies and run the test suite:

pkg> instantiate
pkg> test

See the examples directory for optimization scripts, input data, plotting utilities, and sample workflows.

Bug reports and support

Please report any issues via the Github issue tracker. All types of issues are welcome and encouraged; this includes bug reports, documentation typos, feature requests, etc.

Acknowledgement

This work was supported by Los Alamos National Laboratory (LANL)'s LDRD Early Career Research Award (20190590ECR) and LANL-TAMU's collaborative research project grant. The primary developer of this package is Harsha Nagarajan (@harshangrjn).

Citing LaplacianOpt

If you find LaplacianOpt.jl useful in your work, we request you to cite the following papers [link-1] [link-2]:

@article{LOpt_TCNS2024,
  title={Optimal robust network design: Formulations and algorithms for maximizing algebraic connectivity},
  author={Somisetty, Neelkamal and Nagarajan, Harsha and Darbha, Swaroop},
  journal={IEEE Transactions on Control of Network Systems},
  url = {https://doi.org/10.1109/TCNS.2024.3431408},
  pages={918--929},
  volume={12},
  number={1},
  year={2024},
  publisher={IEEE}
}

@inproceedings{LOpt_ECC2015,
  title={On maximizing algebraic connectivity of networks for various engineering applications},
  author={Nagarajan, Harsha and Rathinam, Sivakumar and Darbha, Swaroop},
  booktitle={European Control Conference (ECC)},
  pages={1626--1632},
  year={2015},
  organization={IEEE}
}