ModularityPruning

ModularityPruning is a pruning tool to identify small subsets of network partitions that are significant from the perspective of stochastic block model inference. It:

• Works for single-layer and multi-layer networks
• Supports both directed and undirected networks
• Supports weighted networks via the weight edge attribute
• Restricts focus to a fixed number of communities when desired
• Contains a faster and more robust implementation of the CHAMP (Convex Hull of Admissible Modularity Partitions) algorithm (see CHAMP_2D and CHAMP_3D)

See the documentation or the journal article at https://doi.org/10.1038/s41598-022-20142-6 for more information.

Significantly more details can be found in the article's Supplementary Information.

Note: support for weighted and directed networks is an extension beyond the original publication.

Installation

This project is on PyPI and can be installed with

pip install modularitypruning
# OR
pip3 install modularitypruning

Alternatively, you can install it from this repository directly:

git clone https://github.com/ragibson/ModularityPruning
cd ModularityPruning
pip install .

For modularitypruning development, it is best to use a strict editable install so that pytest and mypy can pick up changes immediately.

pip install --editable . --config-settings editable_mode=strict

Basic Usage

This package interfaces directly with python-igraph. A simple example of its usage is

import igraph as ig
from modularitypruning import prune_to_stable_partitions
from modularitypruning.leiden_utilities import repeated_leiden_from_gammas
import numpy as np

# get Karate Club graph in igraph
G = ig.Graph.Famous("Zachary")

# run leiden 1000 times on this graph from gamma=0 to gamma=2
partitions = repeated_leiden_from_gammas(G, np.linspace(0, 2, 1000))

# prune to the stable partitions from gamma=0 to gamma=2
stable_partitions = prune_to_stable_partitions(G, partitions, 0, 2)
print(stable_partitions)

This prints

[(0, 0, 0, 0, 1, 1, 1, 0, 2, 2, 1, 0, 0, 0, 2, 2, 1, 0, 2, 0, 2, 0, 2, 3, 3, 3, 2, 3, 3, 2, 2, 3, 2, 2)]

which is the stable 4-community split of the Karate Club network.

More Information

The issues (which contains some potential future work) and figure generation runtimes README may also be of interest.