Mercurial > repos > shellac > sam_consensus_v3

comparison env/lib/python3.9/site-packages/networkx/algorithms/efficiency_measures.py @ 0:4f3585e2f14b draft default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author shellac
date Mon, 22 Mar 2021 18:12:50 +0000
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:4f3585e2f14b
1 """Provides functions for computing the efficiency of nodes and graphs."""
2
3 import networkx as nx
4 from networkx.exception import NetworkXNoPath
5 from ..utils import not_implemented_for
6
7 __all__ = ["efficiency", "local_efficiency", "global_efficiency"]
8
9
10 @not_implemented_for("directed")
11 def efficiency(G, u, v):
12 """Returns the efficiency of a pair of nodes in a graph.
13
14 The *efficiency* of a pair of nodes is the multiplicative inverse of the
15 shortest path distance between the nodes [1]_. Returns 0 if no path
16 between nodes.
17
18 Parameters
19 ----------
20 G : :class:`networkx.Graph`
21 An undirected graph for which to compute the average local efficiency.
22 u, v : node
23 Nodes in the graph ``G``.
24
25 Returns
26 -------
27 float
28 Multiplicative inverse of the shortest path distance between the nodes.
29
30 Notes
31 -----
32 Edge weights are ignored when computing the shortest path distances.
33
34 See also
35 --------
36 local_efficiency
37 global_efficiency
38
39 References
40 ----------
41 .. [1] Latora, Vito, and Massimo Marchiori.
42 "Efficient behavior of small-world networks."
43 *Physical Review Letters* 87.19 (2001): 198701.
44 <https://doi.org/10.1103/PhysRevLett.87.198701>
45
46 """
47 try:
48 eff = 1 / nx.shortest_path_length(G, u, v)
49 except NetworkXNoPath:
50 eff = 0
51 return eff
52
53
54 @not_implemented_for("directed")
55 def global_efficiency(G):
56 """Returns the average global efficiency of the graph.
57
58 The *efficiency* of a pair of nodes in a graph is the multiplicative
59 inverse of the shortest path distance between the nodes. The *average
60 global efficiency* of a graph is the average efficiency of all pairs of
61 nodes [1]_.
62
63 Parameters
64 ----------
65 G : :class:`networkx.Graph`
66 An undirected graph for which to compute the average global efficiency.
67
68 Returns
69 -------
70 float
71 The average global efficiency of the graph.
72
73 Notes
74 -----
75 Edge weights are ignored when computing the shortest path distances.
76
77 See also
78 --------
79 local_efficiency
80
81 References
82 ----------
83 .. [1] Latora, Vito, and Massimo Marchiori.
84 "Efficient behavior of small-world networks."
85 *Physical Review Letters* 87.19 (2001): 198701.
86 <https://doi.org/10.1103/PhysRevLett.87.198701>
87
88 """
89 n = len(G)
90 denom = n * (n - 1)
91 if denom != 0:
92 lengths = nx.all_pairs_shortest_path_length(G)
93 g_eff = 0
94 for source, targets in lengths:
95 for target, distance in targets.items():
96 if distance > 0:
97 g_eff += 1 / distance
98 g_eff /= denom
99 # g_eff = sum(1 / d for s, tgts in lengths
100 # for t, d in tgts.items() if d > 0) / denom
101 else:
102 g_eff = 0
103 # TODO This can be made more efficient by computing all pairs shortest
104 # path lengths in parallel.
105 return g_eff
106
107
108 @not_implemented_for("directed")
109 def local_efficiency(G):
110 """Returns the average local efficiency of the graph.
111
112 The *efficiency* of a pair of nodes in a graph is the multiplicative
113 inverse of the shortest path distance between the nodes. The *local
114 efficiency* of a node in the graph is the average global efficiency of the
115 subgraph induced by the neighbors of the node. The *average local
116 efficiency* is the average of the local efficiencies of each node [1]_.
117
118 Parameters
119 ----------
120 G : :class:`networkx.Graph`
121 An undirected graph for which to compute the average local efficiency.
122
123 Returns
124 -------
125 float
126 The average local efficiency of the graph.
127
128 Notes
129 -----
130 Edge weights are ignored when computing the shortest path distances.
131
132 See also
133 --------
134 global_efficiency
135
136 References
137 ----------
138 .. [1] Latora, Vito, and Massimo Marchiori.
139 "Efficient behavior of small-world networks."
140 *Physical Review Letters* 87.19 (2001): 198701.
141 <https://doi.org/10.1103/PhysRevLett.87.198701>
142
143 """
144 # TODO This summation can be trivially parallelized.
145 efficiency_list = (global_efficiency(G.subgraph(G[v])) for v in G)
146 return sum(efficiency_list) / len(G)