Network Randomization

Graph randomization algorithms for network analysis.

This module provides various methods for randomizing graphs while preserving certain structural properties like in-degree, out-degree, and mutual degree (IOM), degree sequences, etc.

driada.network.randomization.adj_random_rewiring_iom_preserving(a, is_weighted, r=10, logger=None, enable_progressbar=True, random_state=None)

Randomly rewire graph preserving in/out/mutual degrees.

This method rewires edges while preserving three key properties for each node: - In-degree: number of incoming edges - Out-degree: number of outgoing edges - Mutual degree: number of bidirectional (reciprocal) connections

It handles symmetric (bidirectional) and non-symmetric (unidirectional) components separately to maintain these local connectivity patterns.

Parameters:

• a (Union[np.ndarray, sp.spmatrix]) – Input adjacency matrix (sparse or dense).

• is_weighted (bool) – Whether the graph is weighted.

• r (int, default=10) – Number of rewiring iterations per edge (higher values = more randomization).

• logger (logging.Logger, optional) – Logger for tracking progress.

• enable_progressbar (bool, default=True) – Whether to show progress bar.

• random_state (int, optional) – Random seed for reproducibility.

Returns:

Randomized adjacency matrix.

Return type:

scipy.sparse.csr_matrix

Notes

The algorithm separates the adjacency matrix into symmetric (bidirectional) and non-symmetric (unidirectional) components, rewires each separately, then recombines them. This ensures preservation of in-degree, out-degree, and mutual degree for each node.

Examples

>>> import numpy as np
>>> adj = np.array([[0, 1, 1], [0, 0, 1], [1, 0, 0]])
>>> rewired = adj_random_rewiring_iom_preserving(adj, is_weighted=False, r=10)
>>> # Verify degrees are preserved
>>> np.sum(adj, axis=0) == np.sum(rewired.toarray(), axis=0)  # in-degrees
array([ True,  True,  True])

References

Sporns, O., & Kötter, R. (2004). Motifs in brain networks. PLoS biology, 2(11), e369.

See also

random_rewiring_complete_graph

For complete graphs

random_rewiring_dense_graph

For dense graphs with gap filling

driada.network.randomization.random_rewiring_complete_graph(a, p=1.0, logger=None, random_state=None)

Randomize edge weights in a complete graph.

This function shuffles edge weights while preserving the complete graph structure. It’s useful for testing null models where connectivity is fixed but weights vary.

Parameters:

• a (Union[np.ndarray, sp.spmatrix]) – Complete adjacency matrix. All off-diagonal entries must be non-zero.

• p (float, default=1.0) – Proportion of edges to shuffle (0 to 1).

• logger (logging.Logger, optional) – Logger for tracking progress.

• random_state (int, optional) – Random seed for reproducibility.

Returns:

Randomized adjacency matrix with shuffled edge weights.

Return type:

numpy.ndarray

Raises:

ValueError – If graph is not complete. If p is not between 0 and 1.

Notes

This function preserves the complete graph structure (all edges present) but randomly redistributes the edge weights. For symmetric graphs, symmetry is preserved.

Examples

>>> import numpy as np
>>> # Create a complete weighted graph
>>> n = 4
>>> a = np.random.rand(n, n)
>>> np.fill_diagonal(a, 0)  # No self-loops
>>> # Randomize weights
>>> randomized = random_rewiring_complete_graph(a, p=0.5)
>>> # Check that it's still complete
>>> np.all((randomized > 0) == (a > 0))  # Same structure
True

driada.network.randomization.random_rewiring_dense_graph(a, logger=None, random_state=None, gap_fill_weight=0.0001)

Randomize edge weights for dense (nearly complete) graphs.

This function handles graphs that are almost complete by using a “gap filling” technique. It adds small weights to missing edges, performs randomization, then removes them. Currently only supports symmetric graphs.

Parameters:

• a (Union[np.ndarray, sp.spmatrix]) – Dense adjacency matrix. Must be symmetric.

• logger (logging.Logger, optional) – Logger for tracking progress.

• random_state (int, optional) – Random seed for reproducibility.

• gap_fill_weight (float, default=0.0001) – Small positive weight to temporarily fill gaps.

Returns:

Randomized adjacency matrix with preserved degree sequence.

Return type:

numpy.ndarray

Raises:

ValueError – If gap_fill_weight is not positive. If matrix is not symmetric.

Examples

>>> import numpy as np
>>> # Create a dense symmetric graph
>>> a = np.array([[0, 2, 3], [2, 0, 1], [3, 1, 0]])
>>> randomized = random_rewiring_dense_graph(a, random_state=42)
>>> # Verify degree sequence is preserved
>>> np.allclose(np.sum(a, axis=0), np.sum(randomized, axis=0))
True

driada.network.randomization.get_single_double_edges_lists(g)

Separate edges into single and double (bidirectional) lists.

This function analyzes a directed graph and categorizes edges based on whether they are unidirectional (single) or bidirectional (double). For undirected graphs, all edges are considered bidirectional.

Parameters:

g (Union[nx.Graph, nx.DiGraph]) – Input graph. Can be directed or undirected.

Return type:

Tuple[List[Tuple[int, int]], List[Tuple[int, int]]]

Returns:

• single_edges (List[Tuple[int, int]]) – List of unidirectional edges as (source, target) tuples.

• double_edges (List[Tuple[int, int]]) – List of bidirectional edges as (source, target) tuples. For bidirectional edges, only one direction is included.

Notes

The algorithm works by: 1. Converting to undirected to find all edge pairs 2. Checking original graph for directionality 3. Classifying edges as single or double based on reciprocity

Examples

>>> import networkx as nx
>>> G = nx.DiGraph([(0, 1), (1, 0), (1, 2)])
>>> single, double = get_single_double_edges_lists(G)
>>> print(f"Single edges: {single}")  # [(1, 2)]
Single edges: [(1, 2)]
>>> print(f"Double edges: {double}")  # [(0, 1)]
Double edges: [(0, 1)]

driada.network.randomization.random_rewiring_IOM_preserving(G, r=10)

DEPRECATED: Use adj_random_rewiring_iom_preserving() instead.

Legacy NetworkX-based implementation of In-degree, Out-degree, and Mutual degree (IOM) preserving randomization. This function is slower and less efficient than the adjacency matrix version.

Parameters:

• G (networkx.Graph) – Input graph

• r (int, default=10) – Number of rewiring iterations per edge

Returns:

Randomized graph

Return type:

networkx.Graph

Warning

This function is deprecated and will be removed in v2.0. Use adj_random_rewiring_iom_preserving() with nx.adjacency_matrix() instead.

driada.network.randomization.randomize_graph(adjacency, method='iom', iterations=None, preserve_weights=True, p=1.0, logger=None, enable_progressbar=True, random_state=None, **kwargs)

Unified interface for graph randomization.

This function provides a single entry point for all graph randomization methods, making it easier to switch between different algorithms.

Parameters:

• adjacency (array-like) – Input adjacency matrix (sparse or dense)

• method (str, default='iom') – Randomization method to use: - ‘iom’: In-Out-Motif preserving (for general graphs) - ‘complete’: Complete graph randomization (weights only) - ‘dense’: Dense graph randomization (with gap filling)

• iterations (int, optional) – Number of rewiring iterations (method-specific) Default: 10 * number of edges for ‘iom’

• preserve_weights (bool, default=True) – Whether to preserve edge weights

• p (float, default=1.0) – Proportion of edges to shuffle (for ‘complete’ method)

• logger (logging.Logger, optional) – Logger for tracking progress

• enable_progressbar (bool, default=True) – Whether to show progress bar

• random_state (int, optional) – Random seed for reproducibility

• **kwargs – Additional method-specific parameters

Returns:

Randomized adjacency matrix (same format as input)

Return type:

array-like

Raises:

ValueError – If unknown method is specified

Examples

>>> import numpy as np
>>> from driada.network.randomization import randomize_graph
>>>
>>> # Create a simple adjacency matrix
>>> adj = np.array([[0, 1, 1], [1, 0, 1], [1, 1, 0]])
>>>
>>> # Randomize using IOM preservation
>>> rand_adj = randomize_graph(adj, method='iom', random_state=42)
>>>
>>> # Randomize complete graph weights
>>> rand_adj = randomize_graph(adj, method='complete', p=0.5)

Methods for generating randomized null models of networks while preserving specific properties.