Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

# Source code for networkx.algorithms.efficiency

# efficiency.py - functions for computing node, edge, and graph efficiency
#
# Copyright 2011, 2012, 2013, 2014, 2015 NetworkX developers
#
# This file is part of NetworkX.
#
# 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.

--------
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.

--------
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.

--------
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)