1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
|
"""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"]
@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.
Examples
--------
>>> G = nx.Graph([(0, 1), (0, 2), (0, 3), (1, 2), (1, 3)])
>>> nx.efficiency(G, 2, 3) # this gives efficiency for node 2 and 3
0.5
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
@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.
Examples
--------
>>> G = nx.Graph([(0, 1), (0, 2), (0, 3), (1, 2), (1, 3)])
>>> round(nx.global_efficiency(G), 12)
0.916666666667
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
@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.
Examples
--------
>>> G = nx.Graph([(0, 1), (0, 2), (0, 3), (1, 2), (1, 3)])
>>> nx.local_efficiency(G)
0.9166666666666667
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)
|
