Data

Tools

Indexes

Applications

Experiments

Open Source Science

LaplacianOpt

A Julia/JuMP Package for Maximizing Algebraic Connectivity of Undirected Weighted Graphs

https://github.com/harshangrjn/laplacianopt.jl

Science Score: 67.0%

This score indicates how likely this project is to be science-related based on various indicators:

  • ✓
    CITATION.cff file
    Found CITATION.cff file
  • ✓
    codemeta.json file
    Found codemeta.json file
  • ✓
    .zenodo.json file
    Found .zenodo.json file
  • ✓
    DOI references
    Found 6 DOI reference(s) in README
  • ○
    Academic publication links
  • ✓
    Committers with academic emails
    2 of 6 committers (33.3%) from academic institutions
  • ○
    Institutional organization owner
  • ○
    JOSS paper metadata
  • ○
    Scientific vocabulary similarity
    Low similarity (15.1%) to scientific vocabulary

Keywords

algebraic-connectivity discrete-optimization fiedler-vector graph-algorithms laplacian-matrix mixed-integer-optimization optimization robust-networks semidefinite-programming

Keywords from Contributors

interpretability standardization hack
Last synced: 4 months ago · JSON representation ·

Repository

A Julia/JuMP Package for Maximizing Algebraic Connectivity of Undirected Weighted Graphs

Basic Info
  • Host: GitHub
  • Owner: harshangrjn
  • License: mit
  • Language: Julia
  • Default Branch: master
  • Homepage:
  • Size: 5.56 MB
Statistics
  • Stars: 26
  • Watchers: 5
  • Forks: 0
  • Open Issues: 0
  • Releases: 22
Topics
algebraic-connectivity discrete-optimization fiedler-vector graph-algorithms laplacian-matrix mixed-integer-optimization optimization robust-networks semidefinite-programming
Created over 4 years ago · Last pushed 8 months ago
Metadata Files
Readme Changelog License Citation

README.md


A Julia Package for Maximizing Algebraic Connectivity of Graphs

Status: CI codecov Documentation version

LaplacianOpt

LaplacianOpt is a Julia package which implements polyhedral relaxation-based algorithms for the maximimum algebraic connectivity augmentation problem on weighted graph Laplacians. More specifically, given a weighted base graph with existing edges (could be empty), a set of candidate weighted edges for augmentation, and an augmentation budget (K), this package finds a set of K edges to augment to the base graph such that the resulting graph has maximum algebraic conenctivity with optimality guarantees. For example, given a base graph with N vertices and 0 edges, set of candidate edges which form a complete graph, and K = (N-1), this packages finds a spanning tree with maximum algebraic connectivity.

Algebraic connectivity is the second smallest eigenvalue of the graph Laplacian. The magnitude of this value reflects how well connected the overall graph is. This connectivity measure has been used in analyzing the robustness and synchronizability of complex networks, and in graph sparsification techniques.

Usage

  • Clone the repository.
  • Open a terminal in the repo folder and run julia --project=..
  • Hit ] to open the project environment and run test to run unit tests. If you see an error because of missing packages, run resolve.

Check the "examples" folder on how to use this package.

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]: ```bibtex @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} } ```

Owner

  • Name: Harsha Nagarajan
  • Login: harshangrjn
  • Kind: user
  • Location: Los Alamos
  • Company: Los Alamos National Laboratory

Citation (CITATION.bib) 

@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}
}

GitHub Events

Total
  • Release event: 1
  • Watch event: 2
  • Delete event: 1
  • Issue comment event: 4
  • Push event: 15
  • Pull request event: 4
  • Create event: 4
Last Year
  • Release event: 1
  • Watch event: 2
  • Delete event: 1
  • Issue comment event: 4
  • Push event: 15
  • Pull request event: 4
  • Create event: 4

Committers

Last synced: over 1 year ago

All Time
  • Total Commits: 177
  • Total Committers: 6
  • Avg Commits per committer: 29.5
  • Development Distribution Score (DDS): 0.181
Past Year
  • Commits: 51
  • Committers: 3
  • Avg Commits per committer: 17.0
  • Development Distribution Score (DDS): 0.529
Top Committers
Name Email Commits
harshangrjn h****n@g****m 145
Neelkamal18 n****8@g****m 22
harsha h****a@p****v 5
harsha h****a@l****v 3
Harsha Nagarajan h****a@l****n 1
github-actions[bot] 4****] 1
Committer Domains (Top 20 + Academic)
loft1802660.lan: 1 loft2002964.lanl.gov: 1 pn2000056.lanl.gov: 1

Issues and Pull Requests

Last synced: 4 months ago

All Time
  • Total issues: 15
  • Total pull requests: 39
  • Average time to close issues: 17 days
  • Average time to close pull requests: 17 days
  • Total issue authors: 2
  • Total pull request authors: 4
  • Average comments per issue: 4.87
  • Average comments per pull request: 0.05
  • Merged pull requests: 13
  • Bot issues: 0
  • Bot pull requests: 27
Past Year
  • Issues: 0
  • Pull requests: 3
  • Average time to close issues: N/A
  • Average time to close pull requests: about 6 hours
  • Issue authors: 0
  • Pull request authors: 2
  • Average comments per issue: 0
  • Average comments per pull request: 0.33
  • Merged pull requests: 3
  • Bot issues: 0
  • Bot pull requests: 1
View more stats
Top Authors
Issue Authors
  • harshangrjn (14)
  • JuliaTagBot (1)
Pull Request Authors
  • github-actions[bot] (26)
  • harshangrjn (12)
  • Neelkamal18 (3)
  • dependabot[bot] (3)
Top Labels
Issue Labels
Pull Request Labels

Packages

  • Total packages: 1
  • Total downloads: unknown
  • Total dependent packages: 0
  • Total dependent repositories: 0
  • Total versions: 23
juliahub.com: LaplacianOpt

A Julia/JuMP Package for Maximizing Algebraic Connectivity of Undirected Weighted Graphs

  • Versions: 23
  • Dependent Packages: 0
  • Dependent Repositories: 0
Rankings
Dependent repos count: 9.9%
Stargazers count: 23.4%
Average: 28.2%
Dependent packages count: 38.9%
Forks count: 40.4%
Last synced: 4 months ago