# efficiency.py - functions for computing node, edge, and graph efficiency
#
# Copyright 2011, 2012, 2013, 2014, 2015 NetworkX developers
#
# This file is part of NetworkX.
#
# NetworkX is distributed under a BSD license; see LICENSE.txt for more
# information.
"""Provides functions for computing the efficiency of nodes and graphs."""
from __future__ import division
from itertools import permutations
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:
g_eff = sum(efficiency(G, u, v) for u, v in permutations(G, 2)) / denom
else:
g_eff = 0
# TODO This can be made more efficient by computing all pairs shortest
# path lengths in parallel.
#
# TODO This summation can be trivially parallelized.
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)