Clustering Network Populations

Tutorial

Code to perform clustering network populations derived in “Compressing network populations with modal networks reveals structural diversity” (Kirkley et al., 2023, https://arxiv.org/pdf/2209.13827).

Inputs a list of edge sets corresponding to a population of node-aligned graphs, and requires input parameters:

edgesets: List of edge sets. The s-th set contains all the edges (i, j) in the s-th network in the sample (do not include the other direction (j, i) if the network is undirected). The order of edgesets within the dataset only matters for contiguous clustering, where we want the edgesets to be in the order of the samples in time.
N: Number of nodes in each network (including isolated nodes not showing up in the edge sets).
K0: Initial number of clusters (for discontiguous clustering, usually K0 = 1 works well; for contiguous clustering, it does not matter).
n_fails: Number of failed reassign/merge/split/merge-split moves before terminating the algorithm.
bipartite: ‘None’ for unipartite network populations, list containing [# of nodes of type 1, # of nodes of type 2] otherwise.
directed: Set to True when sets of edges input are directed.
max_runs: Maximum number of allowed moves in the MCMC method, independent of the number of failed moves.

Outputs a clustering result of the form C, A, L where:

C: Dictionary with items (cluster label):(set of list indices corresponding to edge sets in the cluster).
A: Dictionary with items (cluster label):(set of edges corresponding to the mode of the cluster).
L: Inverse compression ratio, which is the description length after clustering divided by the description length of naive transmission.

Algorithm minimizes the following Minimum Description Length (MDL) clustering objective over mode edge sets $\{\mathcal{A}^{(k)}\}$ and cluster assignments $\{C_k\}$ for the input edge sets:

$\mathcal{L}(\mathcal{D}) = \sum_{k=1}^{K} \mathcal{L}_k\left(\mathcal{A}^{(k)}, C_k\right),$

where

$\mathcal{L}_k\left(\mathcal{A}^{(k)}, C_k\right) = \mathcal{L}\left(\mathcal{A}^{(k)}\right) + S \log\left(\frac{S}{S_k}\right) + \ell_k$

is the cluster-level description length of Eq. 14 in https://arxiv.org/pdf/2209.13827.

Inputs:

edgesets: List of edge sets. The s-th set contains all the edges (i, j) in the s-th network in the sample (do not include the other direction (j, i) if the network is undirected). The order of edgesets within the dataset only matters for contiguous clustering, where we want the edgesets to be in the order of the samples in time.
N: Number of nodes in each network (including isolated nodes not showing up in the edge sets).
K0: Initial number of clusters (for discontiguous clustering, usually K0 = 1 works well; for contiguous clustering, it does not matter).
n_fails: Number of failed reassign/merge/split/merge-split moves before terminating the algorithm.
bipartite: ‘None’ for unipartite network populations, list containing [# of nodes of type 1, # of nodes of type 2] otherwise.
directed: Set to True when sets of edges input are directed.
max_runs: Maximum number of allowed moves in the MCMC method, independent of the number of failed moves.

Outputs of class methods ‘run_sims’ (unconstrained description length optimization) and ‘dynamic_contiguous’ (optimization restricted to contiguous clusters):

C: Dictionary with items (cluster label):(set of list indices corresponding to edge sets in the cluster).
A: Dictionary with items (cluster label):(set of edges corresponding to the mode of the cluster).
L: Inverse compression ratio, which is the description length after clustering divided by the description length of naive transmission.

For discontiguous clustering, use:

MDLobj = MDL_populations(edgesets, N, K0, n_fails, bipartite, directed, max_runs)
MDLobj.initialize_clusters()
C, A, L = MDLobj.run_sims()

For contiguous clustering, use:

MDLobj = MDL_populations(edgesets, N, K0=(anything), n_fails=(anything), bipartite, directed)
C, A, L = MDLobj.dynamic_contiguous()

MDL Population Clustering

This module contains the code for the MDL (Minimum Description Length) network population clustering algorithm.

Functions

All of the following functions are provided in this module and have the same general usage as described below.

Functions
Function	Description
generate_synthetic(S, N, modes, alphas, betas, pis)	Generate synthetic networks from the heterogeneous network population generative model in https://arxiv.org/abs/2107.07489.
generate_synthetic.ind2ij(ind, N)	Convert index to edge indices.
remap_keys(Dict)	Remap dict keys to first K integers.
MDL_populations.__init__(edgesets, N, K0=1, n_fails=100, bipartite=None, directed=False, max_runs=np.inf)	Initialize the MDL_populations class.
MDL_populations.initialize_clusters()	Initialize K0 random clusters and find their modes as well as the total description length of this configuration.
MDL_populations.random_key()	Generate random key for new cluster.
MDL_populations.logchoose(N, K)	Compute the logarithm of the binomial coefficient.
MDL_populations.logmult(Ns)	Compute the logarithm of the multinomial coefficient.
MDL_populations.generate_Ek(cluster)	Tally edge counts for networks in the cluster.
MDL_populations.update_mode(Ek, Sk)	Generate mode from cluster edge counts by greedily removing least common edges in the cluster.
MDL_populations.Lk(Ak, Ek, Sk)	Compute cluster description length as a function of mode, edge counts, and size of the cluster.
MDL_populations.move1(k=None)	Reassign randomly chosen network to the best cluster.
MDL_populations.move2()	Merge two randomly chosen clusters.
MDL_populations.move3()	Split randomly chosen cluster in two and perform K-means type algorithm to get these clusters and modes.
MDL_populations.move4()	Merge two randomly chosen clusters then split them.
MDL_populations.run_sims()	Run discontiguous (unconstrained) merge split simulations to identify modes and clusters that minimize the description length.
MDL_populations.dynamic_contiguous()	Minimize description length while constraining clusters to be contiguous in time.
MDL_populations.evaluate_partition(partition, contiguous=False)	Evaluate description length of an arbitrary input partition.

Reference

function generate_synthetic(S, N, modes, alphas, betas, pis) [source]

Description: Generate synthetic networks from the heterogeneous population model.

Parameters:

(S, N, modes, alphas, betas, pis)

S: Number of synthetic networks to generate.
N: Number of nodes in each network.
modes: List of modes for the population model.
alphas: List of probabilities for true positive edges in each mode.
betas: List of probabilities for false positive edges in each mode.
pis: List of mixture weights for each mode.

Returns:

nets: List of generated networks.
cluster_labels: List of cluster labels for the generated networks.

function generate_synthetic.ind2ij(ind, N) [source]

Description: Convert index to edge indices.

Parameters:

(ind, N)

ind: Index of the edge.
N: Number of nodes in the network.

Returns:

tuple: Edge indices (i, j).

function remap_keys(Dict) [source]

Description: Remap dict keys to first K integers.

Parameters:

(Dict)

Dict: Dictionary to remap.

Returns:

Dict: Remapped dictionary.

class MDL_populations.__init__(edgesets, N, K0=1, n_fails=100, bipartite=None, directed=False, max_runs=np.inf) [source]

Description: Initialize the MDL_populations class.

Parameters:

(edgesets, N, K0=1, n_fails=100, bipartite=None, directed=False, max_runs=np.inf)

edgesets: List of sets. The s-th set contains all the edges (i, j) in the s-th network in the sample (do not include the other direction (j, i) if the network is undirected).
N: Number of nodes in each network.
K0: Initial number of clusters (for discontiguous clustering, usually K0 = 1 works well; for contiguous clustering, it does not matter).
n_fails: Number of failed reassign/merge/split/merge-split moves before terminating the algorithm.
bipartite: 'None' for unipartite network populations, array [# of nodes of type 1, # of nodes of type 2] otherwise.
directed: Boolean indicating whether edgesets contain directed edges.
max_runs: Maximum number of allowed moves, regardless of the number of fails.

function MDL_populations.initialize_clusters() [source]

Description: Initialize K0 random clusters and find their modes as well as the total description length of this configuration.

function MDL_populations.random_key() [source]

Description: Generate random key for new cluster.

function MDL_populations.logchoose(N, K) [source]

Description: Compute the logarithm of the binomial coefficient.

Parameters:

(N, K)

N: Total number of items.
K: Number of chosen items.

Returns:

float: Logarithm of the binomial coefficient.

function MDL_populations.logmult(Ns) [source]

Description: Compute the logarithm of the multinomial coefficient with the denominator Ns[0]!Ns[1]!….

Parameters:

(Ns)

Ns: List of counts for the multinomial coefficient.

Returns:

float: Logarithm of the multinomial coefficient.

function MDL_populations.generate_Ek(cluster) [source]

Description: Tally edge counts for networks in the cluster.

Parameters:

(cluster)

cluster: Set of network indices in the cluster.

Returns:

Ek: Dictionary of edge counts for the cluster.

function MDL_populations.update_mode(Ek, Sk) [source]

Description: Generate mode from cluster edge counts by greedily removing least common edges in the cluster.

Parameters:

(Ek, Sk)

Ek: Dictionary of edge counts for the cluster.
Sk: Size of the cluster.

Returns:

Ak: Set of edges corresponding to the mode of the cluster.

function MDL_populations.Lk(Ak, Ek, Sk) [source]

Description: Compute cluster description length as a function of mode, edge counts, and size of the cluster.

Parameters:

(Ak, Ek, Sk)

Ak: Set of edges corresponding to the mode of the cluster.
Ek: Dictionary of edge counts for the cluster.
Sk: Size of the cluster.

Returns:

float: Cluster description length.

function MDL_populations.move1(k=None) [source]

Description: Reassign randomly chosen network to the best cluster.

Parameters:

(k=None)

k: Cluster index (optional).

Returns:

bool: Whether the move was accepted.
float: Change in description length.

function MDL_populations.move2() [source]

Description: Merge two randomly chosen clusters.

Returns:

bool: Whether the move was accepted.
float: Change in description length.

function MDL_populations.move3() [source]

Description: Split randomly chosen cluster in two and perform K-means type algorithm to get these clusters and modes.

Returns:

bool: Whether the move was accepted.
float: Change in description length.

function MDL_populations.move4() [source]

Description: Merge two randomly chosen clusters then split them.

Returns:

bool: Whether the move was accepted.
float: Change in description length.

function MDL_populations.run_sims() [source]

Description: Run discontiguous (unconstrained) merge split simulations to identify modes and clusters that minimize the description length.

Returns:

C: Dictionary with items (cluster label):(set of indices corresponding to networks in the cluster).
A: Dictionary with items (cluster label):(set of edges corresponding to the mode of the cluster).
L: Inverse compression ratio (description length after clustering)/(description length of naive transmission).

function MDL_populations.dynamic_contiguous() [source]

Description: Minimize description length while constraining clusters to be contiguous in time.

Returns:

C: Dictionary with items (cluster label):(set of indices corresponding to networks in the cluster).
A: Dictionary with items (cluster label):(set of edges corresponding to the mode of the cluster).
L: Inverse compression ratio (description length after clustering)/(description length of naive transmission).

function MDL_populations.evaluate_partition(partition, contiguous=False) [source]

Description: Evaluate description length of partition. ‘Contiguous=True’ removes the cluster label entropy term from description length.

Parameters:

(partition, contiguous=False)

partition: List of cluster labels for each network.
contiguous: Boolean indicating whether to remove cluster label entropy term.

Returns:

float: Description length of the partition.

Demo

Example Code

Step 1: Import necessary libraries

import numpy as np
import matplotlib.pyplot as plt
from paninipy.population_clustering import generate_synthetic, MDL_populations
import networkx as nx

Step 2: Function to visualize synthetic clusters

def visualize_synthetic_clusters(nets, cluster_labels, node_num):
    num_plots = len(nets)
    cols = 3
    rows = (num_plots // cols) + (num_plots % cols > 0)
    fig, axes = plt.subplots(rows, cols, figsize=(15, 10))
    pos_rectangular = {}
    half_N = (node_num + 1) // 2
    for i in range(node_num):
        if i < half_N:
            pos_rectangular[i] = (i, 1)
        else:
            pos_rectangular[i] = (i - half_N, 0)

    for i, (net, cluster_label) in enumerate(zip(nets, cluster_labels)):
        row, col = divmod(i, cols)
        ax = axes[row, col] if rows > 1 else axes[col]
        G = nx.Graph()
        G.add_nodes_from(range(node_num))
        G.add_edges_from(net)

        nx.draw(G, pos_rectangular, with_labels=True, ax=ax, node_size=300, node_color='skyblue', font_weight='bold')
        ax.set_title(f'Network {i+1} (Mode {cluster_label})')

    for j in range(i + 1, rows * cols):
        fig.delaxes(axes.flatten()[j])

    plt.tight_layout()
    plt.savefig('synthetic_network_clusters.png', bbox_inches='tight', dpi=200)
    plt.show()

Step 3: Generate synthetic data

mode_example = [{(0, 1), (0, 4), (0, 5), (1, 4), (1, 5), (1, 2), (3, 7), (6, 7)},
    {(0, 1), (0, 4), (1, 2), (1, 5), (1, 6), (2, 5), (2, 6), (2, 3), (5, 6)},
    {(1, 5), (4, 5), (5, 6), (2, 3), (2, 6), (3, 6), (3, 7), (2, 7), (6, 7)}]

node_num = 8
network_num = 100
nets, cluster_labels = generate_synthetic(
    S=network_num,
    N=node_num,
    modes=mode_example,
    alphas=[1, 1, 1],
    betas=[0.1, 0.1, 0.1],
    pis=[0.33, 0.33, 0.34]
)

Step 4: Visualize the synthetic networks

visualize_synthetic_clusters(nets, cluster_labels, node_num)

Step 5: Run the MDL network population clustering algorithm

mdl_pop = MDL_populations(edgesets=nets, N=node_num, K0=1, n_fails=100, directed=False, max_runs=np.inf)
mdl_pop.initialize_clusters()
clusters, modes, L = mdl_pop.run_sims()

Step 6: Function to visualize clustered networks

def visualize_clusters(modes, clusters, L, N, network_num, filename='MDL_population_clusters.png'):
    num_clusters = len(modes)
    fig, ax = plt.subplots(1, num_clusters, figsize=(15, 8))

    if num_clusters == 1:
        ax = [ax]

    pos_rectangular = {}
    half_N = (N + 1) // 2
    for i in range(N):
        if i < half_N:
            pos_rectangular[i] = (i, 1)
        else:
            pos_rectangular[i] = (i - half_N, 0)

    for i, (k, edges) in enumerate(modes.items()):
        G = nx.Graph()
        G.add_nodes_from(range(N))
        G.add_edges_from(edges)

        degrees = dict(G.degree())
        max_degree = max(degrees.values()) if degrees else 1
        nx.draw(G, pos_rectangular, ax=ax[i], with_labels=True, node_size=300, node_color='skyblue', font_size=8, font_weight='bold', edge_color='black', width=1.5)

        num_networks = len(clusters.get(k, []))
        ax[i].set_title(f'Cluster {k}: {num_networks} networks', fontsize=10)
        ax[i].axis('off')

    plt.suptitle(f'{network_num} Synthetic Networks, Inverse Compression Ratio: {L:.3f}', fontsize=12)
    plt.tight_layout(rect=[0, 0.03, 1, 0.95])
    plt.savefig(filename, bbox_inches='tight', dpi=200)
    plt.show()

Step 7: Visualize the clustered networks

visualize_clusters(nets, clusters, L, node_num, network_num)

Example Output

Nine sample networks from the specified synthetic population, with cluster labels. The index of the network sample and the mode it was generated from are indicated along with each sample.

MDL population clustering result. Planted and inferred cluster modes using discontiguous MDL clustering algorithm by the run_sims() method. Colors indicate the correspondence between the true and inferred modes. The mixture probability $\pi_k$ of generating from each planted mode as well as the number of networks within each inferred mode’s cluster are indicated.

Paper source

If you use this algorithm in your work, please cite:

A. Kirkley, A. Rojas, M. Rosvall, and J-G. Young, Compressing network populations with modal networks reveals structural diversity. Communications Physics 6, 148 (2023). Paper: https://arxiv.org/abs/2209.13827