graphs.graph_centrality¶

Graph Centrality Algorithms for Determining Central and Median Nodes in a Graph.

This module provides functions to compute the central and median nodes in a weighted graph based on graph-theoretical centrality measures. The central node minimizes the maximum shortest-path distance to all other reachable nodes (eccentricity), while the median node maximizes the sum of the reciprocals of the shortest-path distances to all other reachable nodes (harmonic closeness centrality).

Problem Description: Given a weighted graph G = (V, E), where V is the set of vertices, and E is the set of edges with positive weights representing distances between nodes, determine:

Central Node: The node with minimal eccentricity. The eccentricity of a node v is defined as the greatest distance between v and any other node reachable from v.
Median Node: The node with maximal harmonic closeness centrality. The harmonic closeness centrality of a node v is the sum of the reciprocals of the shortest-path distances from v to all other reachable nodes.

Algorithms Implemented: - Floyd-Warshall Algorithm for All-Pairs Shortest Paths. - Calculation of Eccentricity and Harmonic Closeness Centrality.

Algorithm Descriptions:

Floyd-Warshall Algorithm (Pseudo-code):¶

for k from 1 to N:

for i from 1 to N:

for j from 1 to N:

if distance[i][j] > distance[i][k] + distance[k][j]:: distance[i][j] = distance[i][k] + distance[k][j]

Central and Median Node Calculation:¶

For each node i:

Eccentricity[i] = maximum distance from node i to any other reachable node.
Closeness[i] = sum of reciprocals of distances from node i to all reachable nodes.

Select:

Central Node: node with minimal eccentricity.
Median Node: node with maximal closeness.

References: - https://en.wikipedia.org/wiki/Centrality - Floyd-Warshall Algorithm: https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm - Closeness Centrality: https://en.wikipedia.org/wiki/Closeness_centrality

Example Application: These algorithms can be applied to real-world problems, such as determining the optimal location for facilities (e.g., emergency response centers) to minimize response times within a network. By identifying the central or median nodes, organizations can make informed decisions on resource placement to improve efficiency and accessibility.

Functions¶

`find_central_and_median_node`(→ tuple[tuple[int, ...)	Determine the central and median nodes based on shortest-path distances.
`find_central_node`(→ tuple[int, float])	Identify the node with minimal eccentricity among reachable nodes.
`find_median_node`(→ tuple[int, float])	Identify the node with maximal closeness among reachable nodes.
`floyd_warshall_algorithm`(→ numpy.ndarray)	Compute all-pairs shortest paths using the Floyd-Warshall algorithm.
`get_reachable_distances`(→ numpy.ndarray)	Filter reachable distances, excluding infinite values (unreachable nodes).
`initialize_distance_matrix`(→ numpy.ndarray)	Initialize the distance matrix and validate edge weights.
`test_cyclic_graph`(→ None)	Test a cyclic graph where there is a cycle between nodes.
`test_directed_acyclic_graph`(→ None)	Test a directed acyclic graph (DAG).
`test_disconnected_graph`(→ None)	Test a disconnected graph with nodes that cannot reach each other.
`test_fully_connected_graph`(→ None)	Test a fully connected graph.
`test_graph_with_negative_weight`(→ None)	Test a graph with negative weight, which should raise a ValueError.
`test_graph_with_zero_weight`(→ None)	Test a graph with zero weight, which should raise a ValueError.
`test_large_fully_connected_graph`(→ None)	Test a larger fully connected graph with random weights.
`test_single_node`(→ None)	Test a graph with a single node.
`test_sparse_graph`(→ None)	Test a larger sparse graph.
`test_two_nodes_positive_weight`(→ None)	Test a graph with two nodes connected by a positive weight.

Module Contents¶

graphs.graph_centrality.find_central_and_median_node(distance_matrix: numpy.ndarray) → tuple[tuple[int, float], tuple[int, float]]¶

Determine the central and median nodes based on shortest-path distances.

For each node, calculates its eccentricity and harmonic closeness centrality, considering only reachable nodes. Then, identifies the central node (minimal eccentricity) and median node (maximal closeness).

Args:

distance_matrix: A numpy.ndarray representing shortest-path distances: between all pairs of nodes.

Returns:

A tuple containing:

central_node: A tuple (node index, eccentricity) for the node with minimal eccentricity.
median_node: A tuple (node index, closeness) for the node with maximal harmonic closeness centrality.

graphs.graph_centrality.find_central_node(eccentricities: list[tuple[int, float]]) → tuple[int, float]¶

Identify the node with minimal eccentricity among reachable nodes.

Args:: eccentricities: List of tuples (node index, eccentricity).
Returns:: The node with minimal eccentricity and its value. Returns (-1, inf) if no valid nodes are found.

graphs.graph_centrality.find_median_node(closenesses: list[tuple[int, float]]) → tuple[int, float]¶

Identify the node with maximal closeness among reachable nodes.

Args:: closenesses: List of tuples (node index, closeness centrality).
Returns:: The node with maximal closeness and its value. Returns (-1, inf) if no valid nodes are found.

graphs.graph_centrality.floyd_warshall_algorithm(graph: dict[int, list[tuple[int, float]]]) → numpy.ndarray¶

Compute all-pairs shortest paths using the Floyd-Warshall algorithm.

Floyd-Warshall Complexity:¶

Time Complexity: O(N^3), where N is the number of nodes. Space Complexity: O(N^2), for storing the distance matrix.

Args:: graph: The graph represented as an adjacency list.
Returns:: The distance matrix with the shortest paths between all pairs of nodes.

graphs.graph_centrality.get_reachable_distances(distances: numpy.ndarray) → numpy.ndarray¶

Filter reachable distances, excluding infinite values (unreachable nodes).

Args:: distances: Array of shortest-path distances from a specific node.
Returns:: An array of distances to reachable nodes only (finite values).

graphs.graph_centrality.initialize_distance_matrix(graph: dict[int, list[tuple[int, float]]], number_of_nodes: int) → numpy.ndarray¶

Initialize the distance matrix and validate edge weights.

Args:: graph: The graph represented as an adjacency list. number_of_nodes: The total number of nodes in the graph.
Returns:: A numpy.ndarray representing the initialized distance matrix.
Raises:: ValueError: If any edge has a non-positive weight.

graphs.graph_centrality.test_cyclic_graph() → None¶

Test a cyclic graph where there is a cycle between nodes.

>>> graph = {
...     0: [(1, 1.0)],
...     1: [(2, 1.0)],
...     2: [(0, 1.0)]
... }
>>> distance_matrix = floyd_warshall_algorithm(graph)
>>> central_node, median_node = find_central_and_median_node(distance_matrix)
>>> central_node
(0, 2.0)
>>> median_node
(0, 1.5)

graphs.graph_centrality.test_directed_acyclic_graph() → None¶

Test a directed acyclic graph (DAG).

>>> graph = {
...     0: [(1, 1.0), (2, 2.0)],
...     1: [(3, 3.0)],
...     2: [(3, 1.0)],
...     3: []
... }
>>> distance_matrix = floyd_warshall_algorithm(graph)
>>> central_node, median_node = find_central_and_median_node(distance_matrix)
>>> central_node
(2, 1.0)
>>> median_node
(0, 1.8333333333333333)

graphs.graph_centrality.test_disconnected_graph() → None¶

Test a disconnected graph with nodes that cannot reach each other.

>>> graph = {
...     0: [],
...     1: [],
...     2: []
... }
>>> distance_matrix = floyd_warshall_algorithm(graph)
>>> central_node, median_node = find_central_and_median_node(distance_matrix)
>>> central_node
(-1, inf)
>>> median_node
(-1, inf)

graphs.graph_centrality.test_fully_connected_graph() → None¶

Test a fully connected graph.

>>> graph = {
...     0: [(1, 1.0), (2, 1.0)],
...     1: [(0, 1.0), (2, 1.0)],
...     2: [(0, 1.0), (1, 1.0)],
... }
>>> distance_matrix = floyd_warshall_algorithm(graph)
>>> central_node, median_node = find_central_and_median_node(distance_matrix)
>>> central_node
(0, 1.0)
>>> median_node
(0, 2.0)

graphs.graph_centrality.test_graph_with_negative_weight() → None¶

Test a graph with negative weight, which should raise a ValueError.

>>> graph = {0: [(1, -2.0)], 1: []}
>>> floyd_warshall_algorithm(graph)
Traceback (most recent call last):
...
ValueError: Edge weight must be positive. Found -2.0 between nodes 0 and 1.

graphs.graph_centrality.test_graph_with_zero_weight() → None¶

Test a graph with zero weight, which should raise a ValueError.

>>> graph = {0: [(1, 0.0)], 1: []}
>>> floyd_warshall_algorithm(graph)
Traceback (most recent call last):
...
ValueError: Edge weight must be positive. Found 0.0 between nodes 0 and 1.

graphs.graph_centrality.test_large_fully_connected_graph() → None¶

Test a larger fully connected graph with random weights.

>>> import random
>>> random.seed(42)
>>> number_of_nodes = 10
>>> graph = {i: [(j, random.uniform(1, 10)) for j in
...          range(number_of_nodes) if i != j]
...          for i in range(number_of_nodes)}
>>> distance_matrix = floyd_warshall_algorithm(graph)
>>> central_node, median_node = find_central_and_median_node(distance_matrix)
>>> central_node[0] is not None  # Ensure it found a central node
True
>>> median_node[0] is not None  # Ensure it found a median node
True

graphs.graph_centrality.test_single_node() → None¶

Test a graph with a single node.

>>> graph = {0: []}
>>> distance_matrix = floyd_warshall_algorithm(graph)
>>> central_node, median_node = find_central_and_median_node(distance_matrix)
>>> central_node
(0, 0.0)
>>> median_node
(0, 0.0)

graphs.graph_centrality.test_sparse_graph() → None¶

Test a larger sparse graph.

>>> graph = {
...     0: [(1, 2.0)],
...     1: [(2, 3.0)],
...     2: [(3, 4.0)],
...     3: [(4, 5.0)],
...     4: []
... }
>>> distance_matrix = floyd_warshall_algorithm(graph)
>>> central_node, median_node = find_central_and_median_node(distance_matrix)
>>> central_node
(3, 5.0)
>>> median_node
(0, 0.8825396825396825)

graphs.graph_centrality.test_two_nodes_positive_weight() → None¶

Test a graph with two nodes connected by a positive weight.

>>> graph = {0: [(1, 5.0)], 1: [(0, 5.0)]}
>>> distance_matrix = floyd_warshall_algorithm(graph)
>>> central_node, median_node = find_central_and_median_node(distance_matrix)
>>> central_node
(0, 5.0)
>>> median_node
(0, 0.2)

graphs.graph_centrality¶

Floyd-Warshall Algorithm (Pseudo-code):¶

Central and Median Node Calculation:¶

Functions¶

Module Contents¶

Floyd-Warshall Complexity:¶

thealgorithms-python

Navigation

Related Topics