Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / efficiency.py @ 5cef0f13

History | View | Annotate | Download (4.26 KB)

1
# efficiency.py - functions for computing node, edge, and graph efficiency
2
#
3
# Copyright 2011, 2012, 2013, 2014, 2015 NetworkX developers
4
#
5
# This file is part of NetworkX.
6
#
7
# NetworkX is distributed under a BSD license; see LICENSE.txt for more
8
# information.
9
"""Provides functions for computing the efficiency of nodes and graphs."""
10
from __future__ import division
11

    
12
from itertools import permutations
13

    
14
import networkx as nx
15
from networkx.exception import NetworkXNoPath
16
from ..utils import not_implemented_for
17

    
18
__all__ = ['efficiency', 'local_efficiency', 'global_efficiency']
19

    
20

    
21
@not_implemented_for('directed')
22
def efficiency(G, u, v):
23
    """Returns the efficiency of a pair of nodes in a graph.
24

25
    The *efficiency* of a pair of nodes is the multiplicative inverse of the
26
    shortest path distance between the nodes [1]_. Returns 0 if no path
27
    between nodes.
28

29
    Parameters
30
    ----------
31
    G : :class:`networkx.Graph`
32
        An undirected graph for which to compute the average local efficiency.
33
    u, v : node
34
        Nodes in the graph ``G``.
35

36
    Returns
37
    -------
38
    float
39
        Multiplicative inverse of the shortest path distance between the nodes.
40

41
    Notes
42
    -----
43
    Edge weights are ignored when computing the shortest path distances.
44

45
    See also
46
    --------
47
    local_efficiency
48
    global_efficiency
49

50
    References
51
    ----------
52
    .. [1] Latora, Vito, and Massimo Marchiori.
53
           "Efficient behavior of small-world networks."
54
           *Physical Review Letters* 87.19 (2001): 198701.
55
           <https://doi.org/10.1103/PhysRevLett.87.198701>
56

57
    """
58
    try:
59
        eff = 1 / nx.shortest_path_length(G, u, v)
60
    except NetworkXNoPath:
61
        eff = 0
62
    return eff
63

    
64

    
65
@not_implemented_for('directed')
66
def global_efficiency(G):
67
    """Returns the average global efficiency of the graph.
68

69
    The *efficiency* of a pair of nodes in a graph is the multiplicative
70
    inverse of the shortest path distance between the nodes. The *average
71
    global efficiency* of a graph is the average efficiency of all pairs of
72
    nodes [1]_.
73

74
    Parameters
75
    ----------
76
    G : :class:`networkx.Graph`
77
        An undirected graph for which to compute the average global efficiency.
78

79
    Returns
80
    -------
81
    float
82
        The average global efficiency of the graph.
83

84
    Notes
85
    -----
86
    Edge weights are ignored when computing the shortest path distances.
87

88
    See also
89
    --------
90
    local_efficiency
91

92
    References
93
    ----------
94
    .. [1] Latora, Vito, and Massimo Marchiori.
95
           "Efficient behavior of small-world networks."
96
           *Physical Review Letters* 87.19 (2001): 198701.
97
           <https://doi.org/10.1103/PhysRevLett.87.198701>
98

99
    """
100
    n = len(G)
101
    denom = n * (n - 1)
102
    if denom != 0:
103
        g_eff = sum(efficiency(G, u, v) for u, v in permutations(G, 2)) / denom
104
    else:
105
        g_eff = 0
106
    # TODO This can be made more efficient by computing all pairs shortest
107
    # path lengths in parallel.
108
    #
109
    # TODO This summation can be trivially parallelized.
110
    return g_eff
111

    
112

    
113
@not_implemented_for('directed')
114
def local_efficiency(G):
115
    """Returns the average local efficiency of the graph.
116

117
    The *efficiency* of a pair of nodes in a graph is the multiplicative
118
    inverse of the shortest path distance between the nodes. The *local
119
    efficiency* of a node in the graph is the average global efficiency of the
120
    subgraph induced by the neighbors of the node. The *average local
121
    efficiency* is the average of the local efficiencies of each node [1]_.
122

123
    Parameters
124
    ----------
125
    G : :class:`networkx.Graph`
126
        An undirected graph for which to compute the average local efficiency.
127

128
    Returns
129
    -------
130
    float
131
        The average local efficiency of the graph.
132

133
    Notes
134
    -----
135
    Edge weights are ignored when computing the shortest path distances.
136

137
    See also
138
    --------
139
    global_efficiency
140

141
    References
142
    ----------
143
    .. [1] Latora, Vito, and Massimo Marchiori.
144
           "Efficient behavior of small-world networks."
145
           *Physical Review Letters* 87.19 (2001): 198701.
146
           <https://doi.org/10.1103/PhysRevLett.87.198701>
147

148
    """
149
    # TODO This summation can be trivially parallelized.
150
    efficiency_list = (global_efficiency(G.subgraph(G[v])) for v in G)
151
    return sum(efficiency_list) / len(G)