"""Provides functions for computing the efficiency of nodes and graphs."""
import networkx as nx
from networkx.exception import NetworkXNoPath
from ..utils import not_implemented_for
__all__ = ["efficiency", "local_efficiency", "global_efficiency"]
[docs]@not_implemented_for("directed")
def efficiency(G, u, v):
"""Returns the efficiency of a pair of nodes in a graph.
The *efficiency* of a pair of nodes is the multiplicative inverse of the
shortest path distance between the nodes [1]_. Returns 0 if no path
between nodes.
Parameters
----------
G : :class:`networkx.Graph`
An undirected graph for which to compute the average local efficiency.
u, v : node
Nodes in the graph ``G``.
Returns
-------
float
Multiplicative inverse of the shortest path distance between the nodes.
Notes
-----
Edge weights are ignored when computing the shortest path distances.
See also
--------
local_efficiency
global_efficiency
References
----------
.. [1] Latora, Vito, and Massimo Marchiori.
"Efficient behavior of small-world networks."
*Physical Review Letters* 87.19 (2001): 198701.
<https://doi.org/10.1103/PhysRevLett.87.198701>
"""
try:
eff = 1 / nx.shortest_path_length(G, u, v)
except NetworkXNoPath:
eff = 0
return eff
[docs]@not_implemented_for("directed")
def global_efficiency(G):
"""Returns the average global efficiency of the graph.
The *efficiency* of a pair of nodes in a graph is the multiplicative
inverse of the shortest path distance between the nodes. The *average
global efficiency* of a graph is the average efficiency of all pairs of
nodes [1]_.
Parameters
----------
G : :class:`networkx.Graph`
An undirected graph for which to compute the average global efficiency.
Returns
-------
float
The average global efficiency of the graph.
Notes
-----
Edge weights are ignored when computing the shortest path distances.
See also
--------
local_efficiency
References
----------
.. [1] Latora, Vito, and Massimo Marchiori.
"Efficient behavior of small-world networks."
*Physical Review Letters* 87.19 (2001): 198701.
<https://doi.org/10.1103/PhysRevLett.87.198701>
"""
n = len(G)
denom = n * (n - 1)
if denom != 0:
lengths = nx.all_pairs_shortest_path_length(G)
g_eff = 0
for source, targets in lengths:
for target, distance in targets.items():
if distance > 0:
g_eff += 1 / distance
g_eff /= denom
# g_eff = sum(1 / d for s, tgts in lengths
# for t, d in tgts.items() if d > 0) / denom
else:
g_eff = 0
# TODO This can be made more efficient by computing all pairs shortest
# path lengths in parallel.
return g_eff
[docs]@not_implemented_for("directed")
def local_efficiency(G):
"""Returns the average local efficiency of the graph.
The *efficiency* of a pair of nodes in a graph is the multiplicative
inverse of the shortest path distance between the nodes. The *local
efficiency* of a node in the graph is the average global efficiency of the
subgraph induced by the neighbors of the node. The *average local
efficiency* is the average of the local efficiencies of each node [1]_.
Parameters
----------
G : :class:`networkx.Graph`
An undirected graph for which to compute the average local efficiency.
Returns
-------
float
The average local efficiency of the graph.
Notes
-----
Edge weights are ignored when computing the shortest path distances.
See also
--------
global_efficiency
References
----------
.. [1] Latora, Vito, and Massimo Marchiori.
"Efficient behavior of small-world networks."
*Physical Review Letters* 87.19 (2001): 198701.
<https://doi.org/10.1103/PhysRevLett.87.198701>
"""
# TODO This summation can be trivially parallelized.
efficiency_list = (global_efficiency(G.subgraph(G[v])) for v in G)
return sum(efficiency_list) / len(G)