Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/efficiency_measures.py: 41%
32 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""Provides functions for computing the efficiency of nodes and graphs."""
3import networkx as nx
4from networkx.exception import NetworkXNoPath
6from ..utils import not_implemented_for
8__all__ = ["efficiency", "local_efficiency", "global_efficiency"]
11@not_implemented_for("directed")
12@nx._dispatch
13def efficiency(G, u, v):
14 """Returns the efficiency of a pair of nodes in a graph.
16 The *efficiency* of a pair of nodes is the multiplicative inverse of the
17 shortest path distance between the nodes [1]_. Returns 0 if no path
18 between nodes.
20 Parameters
21 ----------
22 G : :class:`networkx.Graph`
23 An undirected graph for which to compute the average local efficiency.
24 u, v : node
25 Nodes in the graph ``G``.
27 Returns
28 -------
29 float
30 Multiplicative inverse of the shortest path distance between the nodes.
32 Examples
33 --------
34 >>> G = nx.Graph([(0, 1), (0, 2), (0, 3), (1, 2), (1, 3)])
35 >>> nx.efficiency(G, 2, 3) # this gives efficiency for node 2 and 3
36 0.5
38 Notes
39 -----
40 Edge weights are ignored when computing the shortest path distances.
42 See also
43 --------
44 local_efficiency
45 global_efficiency
47 References
48 ----------
49 .. [1] Latora, Vito, and Massimo Marchiori.
50 "Efficient behavior of small-world networks."
51 *Physical Review Letters* 87.19 (2001): 198701.
52 <https://doi.org/10.1103/PhysRevLett.87.198701>
54 """
55 try:
56 eff = 1 / nx.shortest_path_length(G, u, v)
57 except NetworkXNoPath:
58 eff = 0
59 return eff
62@not_implemented_for("directed")
63@nx._dispatch
64def global_efficiency(G):
65 """Returns the average global efficiency of the graph.
67 The *efficiency* of a pair of nodes in a graph is the multiplicative
68 inverse of the shortest path distance between the nodes. The *average
69 global efficiency* of a graph is the average efficiency of all pairs of
70 nodes [1]_.
72 Parameters
73 ----------
74 G : :class:`networkx.Graph`
75 An undirected graph for which to compute the average global efficiency.
77 Returns
78 -------
79 float
80 The average global efficiency of the graph.
82 Examples
83 --------
84 >>> G = nx.Graph([(0, 1), (0, 2), (0, 3), (1, 2), (1, 3)])
85 >>> round(nx.global_efficiency(G), 12)
86 0.916666666667
88 Notes
89 -----
90 Edge weights are ignored when computing the shortest path distances.
92 See also
93 --------
94 local_efficiency
96 References
97 ----------
98 .. [1] Latora, Vito, and Massimo Marchiori.
99 "Efficient behavior of small-world networks."
100 *Physical Review Letters* 87.19 (2001): 198701.
101 <https://doi.org/10.1103/PhysRevLett.87.198701>
103 """
104 n = len(G)
105 denom = n * (n - 1)
106 if denom != 0:
107 lengths = nx.all_pairs_shortest_path_length(G)
108 g_eff = 0
109 for source, targets in lengths:
110 for target, distance in targets.items():
111 if distance > 0:
112 g_eff += 1 / distance
113 g_eff /= denom
114 # g_eff = sum(1 / d for s, tgts in lengths
115 # for t, d in tgts.items() if d > 0) / denom
116 else:
117 g_eff = 0
118 # TODO This can be made more efficient by computing all pairs shortest
119 # path lengths in parallel.
120 return g_eff
123@not_implemented_for("directed")
124@nx._dispatch
125def local_efficiency(G):
126 """Returns the average local efficiency of the graph.
128 The *efficiency* of a pair of nodes in a graph is the multiplicative
129 inverse of the shortest path distance between the nodes. The *local
130 efficiency* of a node in the graph is the average global efficiency of the
131 subgraph induced by the neighbors of the node. The *average local
132 efficiency* is the average of the local efficiencies of each node [1]_.
134 Parameters
135 ----------
136 G : :class:`networkx.Graph`
137 An undirected graph for which to compute the average local efficiency.
139 Returns
140 -------
141 float
142 The average local efficiency of the graph.
144 Examples
145 --------
146 >>> G = nx.Graph([(0, 1), (0, 2), (0, 3), (1, 2), (1, 3)])
147 >>> nx.local_efficiency(G)
148 0.9166666666666667
150 Notes
151 -----
152 Edge weights are ignored when computing the shortest path distances.
154 See also
155 --------
156 global_efficiency
158 References
159 ----------
160 .. [1] Latora, Vito, and Massimo Marchiori.
161 "Efficient behavior of small-world networks."
162 *Physical Review Letters* 87.19 (2001): 198701.
163 <https://doi.org/10.1103/PhysRevLett.87.198701>
165 """
166 # TODO This summation can be trivially parallelized.
167 efficiency_list = (global_efficiency(G.subgraph(G[v])) for v in G)
168 return sum(efficiency_list) / len(G)