Multi-Layer Usage

Note that this documentation page only includes the functions intended for multi-layer network analysis.

For single-layer usage, see Usage.

modularitypruning

prune_to_multilayer_stable_partitions(G_intralayer, G_interlayer, layer_vec, model, parts, gamma_start, gamma_end, omega_start, omega_end, restrict_num_communities=None, single_threaded=False)

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

There are three network layer topology models available, all from Pamfil et al.

  • “temporal”: Interlayer edges always connect copies of a node from one layer to the next, often representing interactions that change over time.

  • “multilevel”: Interlayer edges connect a hierarchy of monolayer networks from one layer to the next. This is more general than temporal networks, as nodes can connect arbitrarily to nodes in the next layer. These often represent inclusion relationships, such as cities to counties, counties to states, and states to countries.

  • “multiplex”: Each layer represents a type of interaction, making the entire multilayer network akin to an edge-colored multigraph (each type of edge has its own layer). This model is unique in that there is no natural ordering of layers, and the resulting theory requires some analytical simplifications, making the resulting parameter estimation the least robust of the three models.

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

NOTE: This method will truncate omega estimates to omega_end - 1e-3 (and raise a warning) if needed to properly identify stable partitions with very large or infinite interlayer coupling estimates (e.g., when all membership labels persist across layers). If omega_end is set too low, these partitions may be incorrectly identified as stable. Conversely, some partitions with large omega estimates might be misclassified as not stable. Therefore, be cautious of returned partitions with little or no community structure differences across layers.

Parameters:

  • G_intralayer (igraph.Graph) – intralayer graph of interest

  • G_interlayer (igraph.Graph) – interlayer graph of interest

  • layer_vec (list[int]) – list of each vertex’s layer membership

  • model (str) – network layer topology (temporal, multilevel, multiplex)

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

  • gamma_start (float) – starting gamma value for CHAMP

  • gamma_end (float) – ending gamma value for CHAMP

  • omega_start (float) – starting omega value for CHAMP

  • omega_end (float) – ending omega 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_3D(G_intralayer, G_interlayer, layer_vec, all_parts, gamma_0, gamma_f, omega_0, omega_f)

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

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

Parameters:

  • G_intralayer (igraph.Graph) – intralayer graph of interest

  • G_interlayer (igraph.Graph) – interlayer graph of interest

  • layer_vec (list[int]) – list of each vertex’s layer membership

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

  • gamma_0 (float) – starting gamma value for CHAMP

  • gamma_f (float) – ending gamma value for CHAMP

  • omega_0 (float) – starting omega value for CHAMP

  • omega_f (float) – ending omega value for CHAMP

Returns:

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

  • list of polygon vertices in (gamma, omega) plane for the partition’s domain of optimality

  • community membership tuple for the partition

Return type:

list of tuple[list[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]

multilayer_leiden(G_intralayer, G_interlayer, layer_vec, gamma, omega, optimiser=None, return_partition=False)

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

WARNING: Optimization can be EXTREMELY slow for large numbers of layers! Leidenalg does not properly implement multilayer optimization.

Parameters:

  • G_intralayer (igraph.Graph) – intralayer graph of interest

  • G_interlayer (igraph.Graph) – interlayer graph of interest

  • layer_vec (list[int]) – list of each vertex’s layer membership

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

  • omega (float) – omega (interlayer resolution parameter) to run Leiden at

  • optimiser (leidenalg.Optimiser) – if not None, use passed-in (potentially custom) leidenalg optimiser

  • 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.RBConfigurationVertexPartitionWeightedLayers

repeated_parallel_leiden_from_gammas_omegas(G_intralayer, G_interlayer, layer_vec, gammas, omegas, show_progress=True)

Runs leidenalg at each gamma and omega in gammas and omegas, using all CPU cores available.

WARNING: Optimization can be EXTREMELY slow for large numbers of layers! Leidenalg does not properly implement multilayer optimization.

Parameters:

  • G_intralayer (igraph.Graph) – intralayer graph of interest

  • G_interlayer (igraph.Graph) – interlayer graph of interest

  • layer_vec (list[int]) – list of each vertex’s layer membership

  • gammas (list[float]) – list of gammas to run leidenalg at

  • omegas (list[float]) – list of omegas to run leidenalg at

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

Returns:

a set of all unique partitions encountered

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_multilayer_resolution_parameter_estimation(G_intralayer, G_interlayer, layer_vec, gamma=1.0, omega=1.0, gamma_tol=0.01, omega_tol=0.05, omega_max=1000, max_iter=25, model='temporal', verbose=False)

Multilayer variant of ALG. 1 from “Relating modularity maximization and stochastic block models in multilayer networks.” The nested functions here are just used to match the pseudocode in the paper.

Parameters:

  • G_intralayer (igraph.Graph) – intralayer graph of interest

  • G_interlayer (igraph.Graph) – interlayer graph of interest

  • layer_vec (list[int]) – list of each vertex’s layer membership

  • gamma (float) – starting gamma value

  • omega (float) – starting omega value

  • gamma_tol (float) – convergence tolerance for gamma

  • omega_tol (float) – convergence tolerance for omega

  • omega_max (float) – maximum allowed value for omega

  • max_iter (int) – maximum number of iterations

  • model (str) – network layer topology (temporal, multilevel, multiplex)

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

Returns:

  • gamma to which the iteration converged

  • omega to which the iteration converged

  • the resulting partition

Return type:

tuple[float, float, tuple[int]]

modularitypruning.parameter_estimation_utilities

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

estimate_multilayer_SBM_parameters(G_intralayer, G_interlayer, layer_vec, partition, model, N=None, T=None, Nt=None, m_t=None)

Estimates multilayer SBM parameters from a graph and a partition

Parameters:

  • G_intralayer (igraph.Graph) – intralayer graph of interest

  • G_interlayer (igraph.Graph) – interlayer graph of interest

  • layer_vec (list[int]) – list of each vertex’s layer membership

  • partition (leidenalg.RBConfigurationVertexPartition) – partition of interest

  • model (str) – network layer topology (temporal, multilevel, multiplex)

  • N (int) – number of nodes per layer (automatically computed if None)

  • T (int) – number of layers in input graph (automatically computed if None)

  • Nt (int) – vector of nodes per layer (automatically computed if None)

  • m_t (int) – vector of total edge weights per layer (automatically computed if None)

Returns:

theta_in, theta_out, p, K

Return type:

float, float, float, int

gamma_omega_estimate(G_intralayer, G_interlayer, layer_vec, membership, omega_max=1000, model='temporal', N=None, T=None, Nt=None, m_t=None)

Returns the (gamma, omega) estimate for a multilayer network and a partition

Parameters:

  • G_intralayer (igraph.Graph) – intralayer graph of interest

  • G_interlayer (igraph.Graph) – interlayer graph of interest

  • layer_vec (list[int]) – list of each vertex’s layer membership

  • membership (tuple[int]) – partition membership vector

  • omega_max (float) – maximum allowed value for omega

  • model (str) – network layer topology (temporal, multilevel, multiplex)

  • N (int) – number of nodes per layer (automatically computed if None)

  • T (int) – number of layers in input graph (automatically computed if None)

  • Nt (int) – vector of nodes per layer (automatically computed if None)

  • m_t (int) – vector of total edge weights per layer (automatically computed if None)

Returns:

gamma estimate, omega estimate

Return type:

float, float

omega_function_from_model(model, omega_max, T)

Returns an appropriate function (depending on the model) for computing omega from multilayer SBM parameters

Specifically, it will return versions of temporal_multilevel_omega_estimate_from_parameters() or multiplex_omega_estimate_from_parameters().

Parameters:

  • model (str) – network layer topology (temporal, multilevel, multiplex)

  • omega_max (float) – maximum allowed value for omega

  • T (int) – number of layers in input graph (automatically computed if None)

Returns:

an “update_omega” function

Return type:

function

temporal_multilevel_omega_estimate_from_parameters(theta_in, theta_out, p, K, omega_max=1000)

Returns the omega estimate for a temporal or multilevel multilayer model

Parameters:

  • theta_in (float) – SBM parameter

  • theta_out (float) – SBM parameter

  • p (float) – SBM parameter

  • K (int) – number of blocks in SBM

  • omega_max (float) – maximum allowed value for omega

Returns:

omega estimate

Return type:

float

multiplex_omega_estimate_from_parameters(theta_in, theta_out, p, K, T, omega_max=1000)

Returns the omega estimate for a multiplex multilayer model

Parameters:

  • theta_in (float) – SBM parameter

  • theta_out (float) – SBM parameter

  • p (float) – SBM parameter

  • K (int) – number of blocks in SBM

  • T (int) – number of layers in SBM

  • omega_max (float) – maximum allowed value for omega

Returns:

omega estimate

Return type:

float

domains_to_gamma_omega_estimates(G_intralayer, G_interlayer, layer_vec, domains, model='temporal')

Compute (gamma, omega) estimates as in gamma_omega_estimate(), given domains of optimality from CHAMP_3D().

Parameters:

  • G_intralayer (igraph.Graph) – intralayer graph of interest

  • G_interlayer (igraph.Graph) – interlayer graph of interest

  • layer_vec (list[int]) – list of each vertex’s layer membership

  • domains (list of tuple[list[float], tuple[int]]) – list of (domain_vertices, membership) tuples as returned from CHAMP_3D()

  • model (str) – network layer topology (temporal, multilevel, multiplex)

Returns:

a copy of input domains with the corresponding gamma and omega estimates appended to each tuple

Return type:

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

gamma_omega_estimates_to_stable_partitions(domains_with_estimates, return_membership_only=False)

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

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

Parameters:

domains_with_estimates (list[tuple]) – list of (domain_vertices, membership, gamma_estimate, omega_estimate) tuples as returned from CHAMP_3D()

Returns:

list of community membership tuples of the stable partitions

Return type:

list of tuple[int]

prune_to_multilayer_stable_partitions(G_intralayer, G_interlayer, layer_vec, model, parts, gamma_start, gamma_end, omega_start, omega_end, restrict_num_communities=None, single_threaded=False)

See description in modularitypruning.

modularitypruning.plotting

See Plotting Examples.