Usage

Note that this documentation page only includes the functions intended for single-layer network analysis. We expect that this will be the most common use case for our package, but the package also supports multi-layer networks.

For multi-layer usage, see Multi-Layer Usage.

modularitypruning

prune_to_stable_partitions(G, parts, gamma_start, gamma_end, restrict_num_communities=None, single_threaded=False)

Runs our full pruning pipeline on a singlelayer network. Returns the pruned list of stable partitions whose parameter estimates are within the provided gamma_start and gamma_end bounds.

See https://doi.org/10.1038/s41598-022-20142-6 for more details.

Parameters:

  • G (igraph.Graph) – graph of interest

  • parts (iterable[tuple]) – partitions to prune

  • gamma_start (float) – starting gamma value for CHAMP

  • gamma_end (float) – ending gamma value for CHAMP

  • restrict_num_communities (int or None) – if not None, only use input partitions of this many communities

  • single_threaded (bool) – if True, run the CHAMP step in serial

Returns:

list of community membership tuples

Return type:

list[tuple[int]]

modularitypruning.champ_utilities

These functions provide access to the CHAMP method of Weir et al.

CHAMP_2D(G, all_parts, gamma_0, gamma_f, single_threaded=False)

Calculates the pruned set of partitions from CHAMP on gamma_0 \(\leq \gamma \leq\) gamma_f.

See https://doi.org/10.3390/a10030093 for more details.

Parameters:

  • G (igraph.Graph) – graph of interest

  • all_parts (list[tuple] or set[tuple]) – partitions to prune

  • gamma_0 (float) – starting gamma value for CHAMP

  • gamma_f (float) – ending gamma value for CHAMP

  • single_threaded (bool) – if True, run in serial. Otherwise, use all CPU cores to run in parallel

Returns:

list of tuples for the somewhere optimal partitions, containing (in-order)

  • starting gamma value for the partition’s domain of optimality

  • ending gamma value for the partition’s domain of optimality

  • community membership tuple for the partition

Return type:

list of tuple[float, float, tuple[int]]

modularitypruning.leiden_utilities

These functions provide access to the Leiden modularity maximization algorithm and some related utilities. The implementation here is provided by leidenalg.

sorted_tuple(t)

Converts a tuple to a canonical form in which the labels’ first occurrences are sorted (e.g. label 0 will always occur before label 1 in the tuple).

Parameters:

t (tuple[int]) – community membership of a partition

Returns:

a canonical representation of the membership tuple

Return type:

tuple[int]

singlelayer_leiden(G, gamma, return_partition=False)

Run the Leiden modularity maximization algorithm at a single \(\gamma\) value.

Parameters:

  • G (igraph.Graph) – graph of interest

  • gamma (float) – gamma (resolution parameter) to run Leiden at

  • return_partition (bool) – if True, return a leidenalg partition. Otherwise, return a community membership tuple

Returns:

partition from leidenalg

Return type:

tuple[int] or leidenalg.RBConfigurationVertexPartition

repeated_parallel_leiden_from_gammas(G, gammas, show_progress=True)

Runs the Leiden modularity maximization algorithm at each provided \(\gamma\) value, using all CPU cores.

Parameters:

  • G (igraph.Graph) – graph of interest

  • gammas (list[float]) – list of gammas (resolution parameters) to run Leiden at

  • show_progress (bool) – if True, render a progress bar

Returns:

a set of all unique partitions returned by the Leiden algorithm

Return type:

set of tuple[int]

modularitypruning.parameter_estimation

These functions provide the ability to iteratively estimate “correct” values for the resolution parameter in modularity as discussed by Newman and Pamfil et al. Here, we maximize modularity via the Leiden algorithm.

iterative_monolayer_resolution_parameter_estimation(G, gamma=1.0, tol=0.01, max_iter=25, verbose=False, method='leiden')

Monolayer variant of ALG. 1 from “Relating modularity maximization and stochastic block models in multilayer networks.” This is intended to determine an “optimal” value for gamma by repeatedly maximizing modularity and estimating new values for the resolution parameter.

See https://doi.org/10.1137/18M1231304 for more details.

Parameters:

  • G (igraph.Graph) – graph of interest

  • gamma (float) – initialization gamma value

  • tol (float) – convergence tolerance

  • max_iter (int) – maximum number of iterations

  • verbose (bool) – whether or not to print verbose output

  • method (str) – community detection method to use

Returns:

  • gamma to which the iteration converged

  • the resulting partition

Return type:

tuple[float, leidenalg.RBConfigurationVertexPartition]

modularitypruning.parameter_estimation_utilities

These functions provide utilities related to the parameter estimation of Newman and Pamfil et al.

estimate_singlelayer_SBM_parameters(G, partition, m=None)

Estimate singlelayer SBM parameters from a graph and a partition.

See https://doi.org/10.1103/PhysRevE.94.052315 for more details.

Parameters:

  • G (igraph.Graph) – graph of interest

  • partition (leidenalg.RBConfigurationVertexPartition) – partition of interest

  • m (float) – total edge weight of graph (if None, will be computed)

Returns:

SBM parameter estimates \((\omega_{in}, \omega_{out})\)

Return type:

tuple[float, float]

gamma_estimate(G, partition)

Compute the “correct” value of gamma where modularity maximization becomes equivalent to maximum likelihood methods on a degree-corrected, planted partition stochastic block model.

See https://doi.org/10.1103/PhysRevE.94.052315 for more details.

Parameters:

  • G (igraph.Graph) – graph of interest

  • partition (tuple[int] or leidenalg.RBConfigurationVertexPartition) – partition of interest

Returns:

gamma estimate

Return type:

float

gamma_estimate_from_parameters(omega_in, omega_out)

Compute the “correct” value of gamma as in gamma_estimate() from SBM parameters.

Parameters:

  • omega_in (float) – within-community edge propensity of a degree-corrected, planted partition SBM

  • omega_out (float) – within-community edge propensity of a degree-corrected, planted partition SBM

Returns:

gamma estimate

Return type:

float

ranges_to_gamma_estimates(G, ranges)

Compute gamma estimates as in gamma_estimate(), given domains of optimality from CHAMP_2D().

Parameters:

  • G (igraph.Graph) – graph of interest

  • ranges (list of tuple[float, float, tuple[int]]) – list of (gamma_start, gamma_end, membership) tuples as returned from CHAMP_2D()

Returns:

a copy of input ranges with the corresponding gamma estimate appended to each tuple

Return type:

list of tuple[float, float, tuple[int], float]

gamma_estimates_to_stable_partitions(gamma_estimates)

Computes the stable partitions (i.e. those whose gamma estimates are within their domains of optimality), given domains of optimality and gamma estimates from ranges_to_gamma_estimates().

See https://doi.org/10.1038/s41598-022-20142-6 for more details.

Parameters:

gamma_estimates (list[tuple]) – list of (gamma_start, gamma_end, membership, gamma_estimate) tuples as returned from CHAMP_2D()

Returns:

list of community membership tuples of the stable partitions

Return type:

list of tuple[int]

prune_to_stable_partitions(G, parts, gamma_start, gamma_end, restrict_num_communities=None, single_threaded=False)

See description in modularitypruning.

modularitypruning.plotting

See Plotting Examples.