Based on the paper Twice-Ramanujan Sparsifiers we have implemented a spectral sparsification algorithm that produces graphs with the number of edges being almost linear.
You can check out the full description of the algorithm on the repository website.
In a python (>=3.9) environment, run the following commands:
git clone https://github.com/HamidrezaKmK/twice-ramanujan-sparsifiers.git # clone the repository
cd src
pip install -r requirements.txt # install dependenciesThis project is licensed under the MIT License - see the LICENSE file for details