topolib.analysis package

Submodules

topolib.analysis.metrics module

Metrics module for network topology analysis.

class topolib.analysis.metrics.Metrics

Bases: object

Provides static methods for computing metrics on network topologies.

All methods receive a Topology instance.

node_degree(topology)

Calculates the degree of each node.

average_node_degree(topology)

Calculates the average node degree.

diameter(topology)

DEPRECATED: Use diameter_hops() instead. Calculates the network diameter (in hops).

diameter_hops(topology)

Calculates the network diameter in hops (recommended).

diameter_kms(topology)

Calculates the network diameter in kilometers using physical link lengths.

network_density(topology)

Calculates the network density.

average_shortest_path_length(topology)

DEPRECATED: Use average_shortest_path_length_hops() instead. Calculates the average shortest path length (in hops).

average_shortest_path_length_hops(topology)

Calculates the average shortest path length in hops (recommended).

average_shortest_path_length_kms(topology)

Calculates the average shortest path length in kilometers using physical link lengths.

clustering_coefficient(topology)

Calculates the average clustering coefficient.

edge_betweenness_stats(topology)

Calculates min, mean, and max edge betweenness centrality.

node_betweenness_stats(topology)

Calculates min, mean, and max node betweenness centrality.

global_efficiency(topology)

Calculates the global efficiency.

spectral_radius(topology)

Calculates the spectral radius.

algebraic_connectivity(topology)

Calculates the algebraic connectivity.

weighted_spectral_distribution(topology)

Calculates the weighted spectral distribution.

average_link_length(topology)

Calculates the average physical link length.

betweenness_centrality(topology)

Calculates betweenness centrality for each node.

closeness_centrality(topology)

Calculates closeness centrality for each node.

eigenvector_centrality(topology)

Calculates eigenvector centrality for each node.

edge_betweenness_centrality(topology)

Calculates edge betweenness centrality for each link.

link_length_stats(topology)

Calculates statistics (min, max, avg) of link lengths.

connection_matrix(topology)

Builds the adjacency matrix.

static algebraic_connectivity(topology: Topology) → float

Calculates the algebraic connectivity (second smallest eigenvalue of the Laplacian matrix).

Parameters:

topology (topolib.topology.topology.Topology) – Instance of topolib.topology.topology.Topology.

Returns:

Algebraic connectivity

Return type:

float

static average_link_length(topology: Topology) → float | None

Calculates the average physical link length in the topology.

Parameters:

topology (topolib.topology.topology.Topology) – Instance of topolib.topology.topology.Topology.

Returns:

Average link length

Return type:

float | None

static average_node_degree(topology: Topology) → float

Calculates the average node degree of the topology.

Parameters:

topology (topolib.topology.topology.Topology) – Instance of topolib.topology.topology.Topology.

Returns:

Average node degree

Return type:

float

static average_shortest_path_length(topology: Topology) → float | None

Calculates the average shortest path length between all pairs of nodes in hops.

Deprecated since version This: method is deprecated and will be removed in a future version. Use average_shortest_path_length_hops() instead for explicit hop-based measurement, or average_shortest_path_length_kms() for distance-based measurement. The explicit naming makes the measurement unit clearer.

Parameters:

topology (topolib.topology.topology.Topology) – Instance of topolib.topology.topology.Topology.

Returns:

Average shortest path length in hops, or None if network is disconnected

Return type:

float | None

static average_shortest_path_length_hops(topology: Topology) → float | None

Calculates the average shortest path length between all pairs of nodes in hops.

This method computes the mean of all shortest path lengths in the network, where each path length is measured in number of hops (links traversed).

Note: This is the recommended method for computing average path length in hops. For distance-based measurement, use average_shortest_path_length_kms().

Parameters:

topology (topolib.topology.topology.Topology) – Instance of topolib.topology.topology.Topology.

Returns:

Average shortest path length in hops, or None if network is disconnected

Return type:

float | None

static average_shortest_path_length_kms(topology: Topology) → float | None

Calculates the average shortest path length between all pairs of nodes in kilometers.

Uses the physical distance (length attribute) of links to compute the average shortest path distance.

Parameters:

topology (topolib.topology.topology.Topology) – Instance of topolib.topology.topology.Topology.

Returns:

Average shortest path length in kilometers, or None if network is disconnected

Return type:

float | None

static betweenness_centrality(topology: Topology) → Dict[int, float]

Calculates the betweenness centrality for each node.

Parameters:

topology (topolib.topology.topology.Topology) – Instance of topolib.topology.topology.Topology.

Returns:

Dictionary {node_id: betweenness_centrality}

Return type:

dict[int, float]

static closeness_centrality(topology: Topology) → Dict[int, float]

Calculates the closeness centrality for each node.

Parameters:

topology (topolib.topology.topology.Topology) – Instance of topolib.topology.topology.Topology.

Returns:

Dictionary {node_id: closeness_centrality}

Return type:

dict[int, float]

static clustering_coefficient(topology: Topology) → float

Calculates the average clustering coefficient of the network.

Parameters:

topology (topolib.topology.topology.Topology) – Instance of topolib.topology.topology.Topology.

Returns:

Average clustering coefficient

Return type:

float

static connection_matrix(topology: Topology) → List[List[int]]

Builds the adjacency matrix of the topology.

Parameters:

topology (topolib.topology.topology.Topology) – Instance of topolib.topology.topology.Topology.

Returns:

Adjacency matrix (1 if connected, 0 otherwise).

Return type:

list[list[int]]

static diameter(topology: Topology) → int | None

Calculates the network diameter (longest shortest path) in hops.

Deprecated since version This: method is deprecated and will be removed in a future version. Use diameter_hops() instead for explicit hop-based measurement, or diameter_kms() for distance-based measurement. The explicit naming makes the measurement unit clearer.

Parameters:

topology (topolib.topology.topology.Topology) – Instance of topolib.topology.topology.Topology.

Returns:

Network diameter in hops, or None if network is disconnected

Return type:

int | None

static diameter_hops(topology: Topology) → int | None

Calculates the network diameter (longest shortest path) in hops.

The diameter is the maximum shortest path length between any pair of nodes, measured in number of hops (links traversed).

Note: This is the recommended method for computing diameter in hops. For distance-based measurement, use diameter_kms().

Parameters:

topology (topolib.topology.topology.Topology) – Instance of topolib.topology.topology.Topology.

Returns:

Network diameter in hops, or None if network is disconnected

Return type:

int | None

static diameter_kms(topology: Topology) → float | None

Calculates the network diameter (longest shortest path) in kilometers.

Uses the physical distance (length attribute) of links to compute the longest shortest path distance.

Parameters:

topology (topolib.topology.topology.Topology) – Instance of topolib.topology.topology.Topology.

Returns:

Network diameter in kilometers, or None if network is disconnected

Return type:

float | None

static edge_betweenness_centrality(topology: Topology) → Dict[tuple[int, int], float]

Calculates the edge betweenness centrality for each link.

Parameters:

topology (topolib.topology.topology.Topology) – Instance of topolib.topology.topology.Topology.

Returns:

Dictionary {(source_id, target_id): edge_betweenness}

Return type:

dict[tuple[int, int], float]

static edge_betweenness_stats(topology: Topology) → Dict[str, float]

Calculates statistics (min, mean, max) of edge betweenness centrality.

Parameters:

topology (topolib.topology.topology.Topology) – Instance of topolib.topology.topology.Topology.

Returns:

Dictionary with keys ‘min’, ‘mean’, ‘max’

Return type:

dict[str, float]

static eigenvector_centrality(topology: Topology) → Dict[int, float]

Calculates the eigenvector centrality for each node.

Parameters:

topology (topolib.topology.topology.Topology) – Instance of topolib.topology.topology.Topology.

Returns:

Dictionary {node_id: eigenvector_centrality}

Return type:

dict[int, float]

static global_efficiency(topology: Topology) → float

Calculates the global efficiency of the network. Formula: E_glob = 1/(n(n-1)) * sum(1/d(u,v)) for all u != v

Parameters:

topology (topolib.topology.topology.Topology) – Instance of topolib.topology.topology.Topology.

Returns:

Global efficiency

Return type:

float

static link_length_stats(topology: Topology) → Dict[str, float | None]

Calculates the minimum, maximum, and average link lengths.

Parameters:

topology (topolib.topology.topology.Topology) – Instance of topolib.topology.topology.Topology.

Returns:

Dictionary with keys ‘min’, ‘max’, ‘avg’.

Return type:

dict[str, float | None]

static network_density(topology: Topology) → float

Calculates the network density (ratio of actual edges to maximum possible edges). Formula: ND = 2m / (n(n-1)) where m is number of edges and n is number of nodes.

Parameters:

topology (topolib.topology.topology.Topology) – Instance of topolib.topology.topology.Topology.

Returns:

Network density

Return type:

float

static node_betweenness_stats(topology: Topology) → Dict[str, float]

Calculates statistics (min, mean, max) of node betweenness centrality.

Parameters:

topology (topolib.topology.topology.Topology) – Instance of topolib.topology.topology.Topology.

Returns:

Dictionary with keys ‘min’, ‘mean’, ‘max’

Return type:

dict[str, float]

static node_degree(topology: Topology) → Dict[int, int]

Calculates the degree of each node in the topology.

For bidirectional links (where both A->B and B->A exist), each node’s degree is incremented only once per connection.

Parameters:

topology (topolib.topology.topology.Topology) – Instance of topolib.topology.topology.Topology.

Returns:

Dictionary {node_id: degree}

Return type:

dict[int, int]

static spectral_radius(topology: Topology) → float

Calculates the spectral radius (largest absolute eigenvalue of adjacency matrix).

Parameters:

topology (topolib.topology.topology.Topology) – Instance of topolib.topology.topology.Topology.

Returns:

Spectral radius

Return type:

float

static weighted_spectral_distribution(topology: Topology) → float

Calculates the weighted spectral distribution of the normalized Laplacian. Formula: WSD(G) = sum((1-k) * N_f(lambda_L^D = k)) for k in K

Parameters:

topology (topolib.topology.topology.Topology) – Instance of topolib.topology.topology.Topology.

Returns:

Weighted spectral distribution

Return type:

float

topolib.analysis.traffic_matrix module

Traffic matrix generation module.

This module provides methods to generate traffic demand matrices using different models: - Gravitational model (population-based) - DC/IXP model (datacenter and internet exchange point-based) - Distribution probability model (resource-based traffic distribution)

class topolib.analysis.traffic_matrix.TrafficMatrix

Bases: object

Traffic matrix generator for network topologies.

Generates traffic demand matrices between nodes using different models. All matrices are returned as numpy arrays where matrix[i][j] represents traffic from node i to node j (in Gbps).

All methods are static and receive a Topology instance as parameter.

static gravitational(topology: Topology, rate: float = 0.015) → ndarray[tuple[Any, ...], dtype[float64]]

Generate traffic matrix using the gravitational model.

Traffic between nodes i and j is proportional to their populations: T(i,j) = K * Pop_i * Pop_j

Parameters:

• topology (Topology) – The network topology.

• rate (float) – Traffic rate per population unit (default: 0.015 Gbps per capita)

Returns:

Traffic matrix where matrix[i][j] is traffic from node i to node j (Gbps). Shape: (n_nodes, n_nodes)

Return type:

numpy.ndarray

static mpt(topology: Topology, alpha_1: float = 10.0, alpha_2: float = 7.5, omega: float = 100.0) → ndarray[tuple[Any, ...], dtype[float64]]

Generate traffic matrix using the Multi-Period Traffic (MPT) model.

Traffic depends on node degrees and the difference between DC and IXP resources: - If combined degree > 2*avg_degree: T(i,j) = alpha_1 * C(N,2) * delta_i * delta_j + omega - Otherwise: T(i,j) = alpha_2 * N * delta_i * delta_j + omega

where N = degree_i + degree_j, delta_i = |DC_i - IXP_i|

Parameters:

• topology (Topology) – The network topology.

• alpha_1 (float) – Scaling factor for high-degree node pairs (default: 10.0). Converts combinatorial values to Gbps.

• alpha_2 (float) – Scaling factor for low-degree node pairs (default: 7.5). Converts linear values to Gbps.

• omega (float) – Base traffic offset (default: 100.0 Gbps). Ensures minimum traffic even in absence of DCs or IXPs.

Returns:

Traffic matrix where matrix[i][j] is traffic from node i to node j (Gbps). Shape: (n_nodes, n_nodes)

Return type:

numpy.ndarray

static multiperiod(base_matrix: ndarray[tuple[Any, ...], dtype[float64]], num_periods: int = 10, base_growth_rate: float = 0.1, random_variation: float = 0.02, seed: int | None = None) → ndarray[tuple[Any, ...], dtype[float64]]

Generate multi-period traffic matrices with growth over time.

This method generates traffic matrices for multiple periods (e.g., years), applying a base growth rate plus random variation to each period.

Parameters:

• base_matrix (numpy.ndarray) – Initial traffic matrix (period 0) as a 2D numpy array. Should be generated using one of the traffic generation methods (gravitational, mpt, or ram).

• num_periods (int) – Number of periods to generate (default: 10).

• base_growth_rate (float) – Base yearly growth rate as decimal (default: 0.10 for 10%).

• random_variation (float) – Standard deviation for random growth variation (default: 0.02 for 2% std). Variation is sampled from a normal distribution N(0, random_variation).

• seed (int or None) – Random seed for reproducibility (default: None).

Returns:

3D array of shape (num_periods, n_nodes, n_nodes) where: - First dimension is the period index - matrix[p][i][j] is traffic from node i to node j in period p (Gbps)

Return type:

numpy.ndarray

Examples

>>> # First generate a base traffic matrix
>>> base_matrix = TrafficMatrix.gravitational(topology, rate=0.015)
>>>
>>> # Generate 10 periods with 10% base growth and 2% std variation
>>> matrices = TrafficMatrix.multiperiod(
...     base_matrix,
...     num_periods=10,
...     base_growth_rate=0.10,
...     random_variation=0.02,
...     seed=42
... )
>>> # Access period 5 matrix
>>> period_5_matrix = matrices[5]

>>> # Using MPT model as base
>>> base_matrix = TrafficMatrix.mpt(topology)
>>> matrices = TrafficMatrix.multiperiod(
...     base_matrix,
...     num_periods=5,
...     base_growth_rate=0.08,
...     random_variation=0.03
... )

Notes

The growth is compounded: each period multiplies the previous period’s traffic by (1 + growth_rate), where growth_rate = base_growth_rate + variation, and variation is sampled from a normal distribution N(0, random_variation).

static ram(topology: Topology, w_pop: float = 0.015, w_dc: float = 400.0, w_ixp: float = 2857.0, alpha: float = 1.0, beta: float = 1.0, gamma: float = 1.0) → ndarray[tuple[Any, ...], dtype[float64]]

Generate traffic matrix using the Region Aggregation Model (RAM).

Traffic from node i to j is distributed proportionally based on resource shares and leaving traffic: T(i,j) = traffic_leaving_i * (share_j / (1 - share_i))

Parameters:

• topology (Topology) – The network topology.

• w_pop (float) – Weight for population (Gbps per capita, default: 0.015)

• w_dc (float) – Weight for datacenter capacity (Gbps per DC, default: 400)

• w_ixp (float) – Weight for IXP capacity (Gbps per IXP, default: 2857)

• alpha (float) – Proportion of population data to use in the formula (default: 1.0). Controls what fraction of pop attribute is considered. Value of 1.0 uses all population data (equal importance with beta=1.0, gamma=1.0).

• beta (float) – Proportion of datacenter data to use in the formula (default: 1.0). Controls what fraction of dc attribute is considered. Value of 1.0 uses all datacenter data.

• gamma (float) – Proportion of IXP data to use in the formula (default: 1.0). Controls what fraction of ixp attribute is considered. Value of 1.0 uses all IXP data.

Returns:

Traffic matrix where matrix[i][j] is traffic from node i to node j (Gbps). Shape: (n_nodes, n_nodes)

Return type:

numpy.ndarray

Examples

>>> # Equal importance: use all attributes fully
>>> matrix = TrafficMatrix.ram(topology, alpha=1.0, beta=1.0, gamma=1.0)
>>> # Use 50% of each attribute
>>> matrix = TrafficMatrix.ram(topology, alpha=0.5, beta=0.5, gamma=0.5)
>>> # Emphasize IXP: use 30% pop/dc, 100% IXP
>>> matrix = TrafficMatrix.ram(topology, alpha=0.3, beta=0.3, gamma=1.0)

static to_csv(matrix: ndarray[tuple[Any, ...], dtype[float64]], topology: Topology, filename: str) → None

Export traffic matrix to CSV file.

Parameters:

• matrix (numpy.ndarray) – Traffic matrix as numpy array

• topology (Topology) – The topology (needed to get node IDs for labels)

• filename (str) – Output CSV filename

static to_json(matrix: ndarray[tuple[Any, ...], dtype[float64]], topology: Topology, filename: str) → None

Export traffic matrix to JSON file.

The JSON format is a list of traffic demands between node pairs, using node names and the ‘required’ field for traffic values.

Parameters:

• matrix (numpy.ndarray) – Traffic matrix as numpy array

• topology (Topology) – The topology (needed to get node information)

• filename (str) – Output JSON filename

Notes

The output JSON structure is a list of demands: [

{“src”: “Node_A”, “dst”: “Node_B”, “required”: 10}, {“src”: “Node_A”, “dst”: “Node_C”, “required”: 15}, …

] Only non-zero traffic demands are included.