Supra Matrix Function Centralities

These centrality measures operate directly on the supra-adjacency matrix of a multilayer network using matrix functions. They provide global measures of node-layer pair importance based on walks, paths, and communication patterns across the entire network structure.

The supra-adjacency matrix \(A_{\text{supra}}\) is an \(n \times n\) matrix whose rows and columns correspond to node-layer pairs (n = number_of_nodes × number_of_layers). All formulas below follow the node-layer ordering returned by net.get_nodes().

Overview

Matrix function centralities extend classical centrality concepts to multilayer networks by:

Operating on the full supra-adjacency matrix that captures both intra-layer and inter-layer connections
Using matrix functions (exponential, matrix inversion) to account for all paths simultaneously
Producing scores that can be normalized for comparisons across networks
Supporting both sparse and dense computation for efficiency, depending on \(n\) and sparsity

These measures are particularly useful for:

Identifying influential node-layer pairs in multiplex networks
Analyzing information flow across network layers
Comparing node importance across different network structures
Understanding long-range dependencies in multilayer systems

Available Methods

Communicability Centrality

Communicability centrality measures the weighted sum of all walks between nodes, with exponentially decaying weights for longer walks. It is computed from the matrix exponential of the supra-adjacency matrix.

Mathematical Definition:

\[c_i = \sum_j (e^{A_{\text{supra}}})_{ij}\]

where \(A_{\text{supra}}\) is the supra-adjacency matrix.

Best for:

Measuring node importance based on all possible paths
Accounting for redundancy in communication channels
Networks where multiple paths contribute to influence
Global network analysis

Complexity: Uses sparse matrix exponential multiplication when use_sparse=True and \(n^2 \ge 10{,}000\) (roughly \(O(\text{nnz} \times k)\) for \(k\) Krylov iterations). Falls back to dense \(O(n^3)\) computation for smaller matrices, where \(n\) is the total number of node-layer pairs and \(\text{nnz}\) is the number of nonzeros.

Reference: Estrada, E., & Hatano, N. (2008). Communicability in complex networks. Physical Review E, 77(3), 036111.

py3plex.algorithms.multilayer_algorithms.supra_matrix_function_centrality.communicability_centrality(supra_matrix: spmatrix, normalize: bool = True, use_sparse: bool = True, max_iter: int = 100, tol: float = 1e-06) → ndarray

Compute communicability centrality for each node-layer pair.

Communicability centrality measures the weighted sum of all walks between nodes, with exponentially decaying weights for longer walks. It is computed as the row sum of the matrix exponential:

c_i = sum_j (exp(A))_ij

This implementation uses scipy.sparse.linalg.expm_multiply for efficient sparse matrix exponential computation.

Parameters:

supra_matrix – Sparse supra-adjacency matrix (n x n).
normalize – If True, normalize output to sum to 1.
use_sparse – If True, use sparse matrix operations. Falls back to dense for matrices smaller than 10000 elements.
max_iter – Maximum number of iterations for sparse approximation (currently unused).
tol – Tolerance for convergence (currently unused).

Returns:

Communicability centrality scores for each node-layer pair (n,).

Return type:

np.ndarray

Raises:

Py3plexMatrixError – If matrix is invalid (non-square, empty, etc.).

Example

>>> from py3plex.core import random_generators
>>> net = random_generators.random_multiplex_ER(50, 3, 0.1)
>>> A = net.get_supra_adjacency_matrix()
>>> comm = communicability_centrality(A)
>>> print(f"Communicability centrality computed for {len(comm)} node-layer pairs")

Katz Centrality

Katz centrality measures node influence by accounting for all paths with exponentially decaying weights, controlled by an attenuation parameter \(\alpha\). It includes an exogenous influence term \(\beta \mathbf{1}\) so every node-layer pair keeps a baseline score.

Mathematical Definition:

\[x = (I - \alpha A_{\text{supra}})^{-1} \mathbf{1}\]

where \(\alpha < 1/\lambda_{\max}(A_{\text{supra}})\) is the attenuation parameter and \(\mathbf{1}\) is a vector of ones. The implementation normalizes the resulting scores to sum to 1.

Best for:

Controlling the influence of distant connections via \(\alpha\)
Networks with clear source-sink patterns
Comparing with PageRank and eigenvector centrality
Tunable sensitivity to network topology

Complexity: Sparse linear solve scales with matrix sparsity (approximately \(O(\text{nnz} \times k)\) for iterative solvers) or \(O(n^3)\) for dense matrices, where \(n\) is the total number of node-layer pairs.

Reference: Katz, L. (1953). A new status index derived from sociometric analysis. Psychometrika, 18(1), 39-43.

py3plex.algorithms.multilayer_algorithms.supra_matrix_function_centrality.katz_centrality(supra_matrix: spmatrix, alpha: float | None = None, beta: float = 1.0, tol: float = 1e-06) → ndarray

Compute Katz centrality for each node-layer pair.

Katz centrality measures node influence by accounting for all paths with exponentially decaying weights. It is computed as:

x = (I - alpha * A)^{-1} * beta * 1

where alpha < 1/lambda_max(A) to ensure convergence. If alpha is not provided, it defaults to 0.85 / lambda_max(A).

Parameters:

supra_matrix – Sparse supra-adjacency matrix (n x n).
alpha – Attenuation parameter. Must be less than 1/spectral_radius(A). If None, defaults to 0.85 / lambda_max(A).
beta – Weight of exogenous influence (typically 1.0).
tol – Tolerance for eigenvalue computation.

Returns:

Katz centrality scores for each node-layer pair (n,).: Normalized to sum to 1.

Return type:

np.ndarray

Raises:

Py3plexMatrixError – If matrix is invalid or alpha is out of valid range.

Example

>>> from py3plex.core import random_generators
>>> net = random_generators.random_multiplex_ER(50, 3, 0.1)
>>> A = net.get_supra_adjacency_matrix()
>>> katz = katz_centrality(A)
>>> print(f"Katz centrality computed for {len(katz)} node-layer pairs")
>>> # With custom alpha
>>> katz_custom = katz_centrality(A, alpha=0.05)

Usage Examples

Basic Usage

Compute both centrality measures on a multiplex network:

from py3plex.core import random_generators
from py3plex.algorithms.multilayer_algorithms.supra_matrix_function_centrality import (
    communicability_centrality,
    katz_centrality,
)

# Create a random multiplex network
net = random_generators.random_multiplex_ER(50, 3, 0.1)

# Get the supra-adjacency matrix (ordering matches net.get_nodes())
A = net.get_supra_adjacency_matrix()

# Compute communicability centrality
comm_scores = communicability_centrality(A, normalize=True)
print(f"Communicability centrality computed for {len(comm_scores)} node-layer pairs")
print(f"Top 5 node-layer pairs: {sorted(enumerate(comm_scores), key=lambda x: x[1], reverse=True)[:5]}")

# Compute Katz centrality with automatic alpha
katz_scores = katz_centrality(A, alpha=None)
print(f"Katz centrality computed for {len(katz_scores)} node-layer pairs")
print(f"Normalization check: sum = {katz_scores.sum():.6f}")

Advanced Usage

Control computation parameters and compare results:

from py3plex.core import random_generators
from py3plex.algorithms.multilayer_algorithms.supra_matrix_function_centrality import (
    communicability_centrality,
    katz_centrality,
)
import numpy as np

# Create a network
net = random_generators.random_multiplex_ER(100, 4, 0.08)
A = net.get_supra_adjacency_matrix()

# Communicability with sparse computation
comm_sparse = communicability_centrality(
    A,
    normalize=True,
    use_sparse=True,  # Force sparse computation
    max_iter=100,
    tol=1e-6
)

# Katz with custom alpha and beta
katz_custom = katz_centrality(
    A,
    alpha=0.05,      # Small attenuation for long-range effects
    beta=1.0,        # Uniform exogenous influence
    tol=1e-6
)

# Compare correlation between methods
correlation = np.corrcoef(comm_sparse, katz_custom)[0, 1]
print(f"Correlation between communicability and Katz: {correlation:.3f}")

# Find nodes with high communicability but low Katz
diff = comm_sparse - katz_custom
divergent_nodes = np.argsort(np.abs(diff))[-10:]
print(f"Node-layer pairs with largest differences: {divergent_nodes}")

Loading from Network Files

Apply to real network data:

from py3plex.core import multinet
from py3plex.algorithms.multilayer_algorithms.supra_matrix_function_centrality import (
    communicability_centrality,
    katz_centrality,
)
import numpy as np

# Load a multiplex network from edge list
net = multinet.multi_layer_network().load_network(
    "data/example_multiplex.edgelist",
    input_type="multiplex_edges"
)

# Get supra-adjacency matrix (rows/cols correspond to node-layer pairs)
A = net.get_supra_adjacency_matrix()

# Compute centralities
comm_scores = communicability_centrality(A, normalize=True)
katz_scores = katz_centrality(A, alpha=None)

# Get node-layer mapping to interpret results
node_layer_pairs = list(net.get_nodes())
top_k = 10

print(f"Top {top_k} nodes by communicability centrality:")
for idx in np.argsort(comm_scores)[-top_k:][::-1]:
    node, layer = node_layer_pairs[idx]
    print(f"  Node {node} in layer {layer}: {comm_scores[idx]:.6f}")

Performance Considerations

Matrix Size and Sparsity

Small networks (< 100 node-layer pairs): Dense computation is often faster
Medium networks (100-1000 pairs): Sparse computation recommended unless the matrix is very dense
Large networks (> 1000 pairs): Use sparse computation only; dense methods quickly become infeasible

When use_sparse=True is set for communicability centrality, the implementation switches to sparse matrix exponential for matrices with \(n^2 \ge 10{,}000\); smaller matrices use dense computation even when use_sparse=True.

Memory Usage

Communicability: Requires storage for the sparse matrix plus a few working vectors (\(O(\text{nnz} + n)\)) or \(O(n^2)\) for dense matrices
Katz: Sparse solves store the matrix and factorization/iterates (\(O(\text{nnz} + n)\)); dense solves need \(O(n^2)\) memory

Computation Time

Runtime grows with both \(n\) and density. Dense computations scale cubically in \(n\); sparse methods scale with \(\text{nnz}\) and the number of iterations required for convergence. For very large or dense networks:

Use higher tolerance values (e.g., tol=1e-4) to reduce iterations
Focus on specific layers rather than the full supra-matrix
Consider cheaper centrality measures (e.g., degree or PageRank)

Parameter Guidelines

Communicability Centrality

normalize=True: Recommended when comparing across networks
use_sparse=True: Recommended for networks with > 100 node-layer pairs or appreciable sparsity; small matrices fall back to dense
max_iter and tol: Reserved for sparse approximation hooks; currently unused by the implementation

Katz Centrality

alpha=None: Auto-compute as \(0.85 / \lambda_{\max}\) with fallback to 0.01 if eigenvalue estimation fails or the matrix is near-zero
alpha=0.01-0.1: Manual values for custom attenuation; must satisfy \(\alpha < 1/\lambda_{\max}\)
beta=1.0: Default uniform exogenous influence (rarely needs changing)
tol=1e-6: Eigenvalue computation tolerance (increase if eigenvalue estimation is slow or unstable)

Common Issues and Solutions

Matrix Not Square

Error: Py3plexMatrixError: Matrix must be square

Solution: Ensure you’re passing the supra-adjacency matrix from get_supra_adjacency_matrix(), not an edge list or other format.

Alpha Too Large

Error: Py3plexMatrixError: Alpha must be less than 1/lambda_max

Solution: Use alpha=None for automatic computation, or manually compute lambda_max and choose a smaller alpha.

Memory Error

Error: MemoryError during computation

Solution:

Use use_sparse=True for communicability centrality
Ensure your network is not too dense
Consider analyzing individual layers separately
Increase available system memory

Uniform Output

Symptom: All centrality values are identical

Cause: The supra-adjacency matrix is effectively zero, so the computation returns a uniform distribution.

Resolution: Check that edges were loaded correctly and that get_supra_adjacency_matrix() returned expected weights.

References

Estrada, E., & Hatano, N. (2008). Communicability in complex networks. Physical Review E, 77(3), 036111.
Katz, L. (1953). A new status index derived from sociometric analysis. Psychometrika, 18(1), 39-43.
De Domenico, M., Solé-Ribalta, A., Cozzo, E., Kivelä, M., Moreno, Y., Porter, M. A., … & Arenas, A. (2013). Mathematical formulation of multilayer networks. Physical Review X, 3(4), 041022.

Supra Matrix Function Centralities

Overview

Available Methods

Communicability Centrality

Katz Centrality

Usage Examples

Basic Usage

Advanced Usage

Loading from Network Files

Performance Considerations

Matrix Size and Sparsity

Memory Usage

Computation Time

Parameter Guidelines

Communicability Centrality

Katz Centrality

Common Issues and Solutions

Matrix Not Square

Alpha Too Large

Memory Error

Uniform Output

See Also

References