Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/centrality/current_flow_betweenness_subset.py @ 0:4f3585e2f14b draft default tip
"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 """Current-flow betweenness centrality measures for subsets of nodes.""" | |
2 import networkx as nx | |
3 from networkx.algorithms.centrality.flow_matrix import flow_matrix_row | |
4 from networkx.utils import not_implemented_for, reverse_cuthill_mckee_ordering | |
5 | |
6 __all__ = [ | |
7 "current_flow_betweenness_centrality_subset", | |
8 "edge_current_flow_betweenness_centrality_subset", | |
9 ] | |
10 | |
11 | |
12 @not_implemented_for("directed") | |
13 def current_flow_betweenness_centrality_subset( | |
14 G, sources, targets, normalized=True, weight=None, dtype=float, solver="lu" | |
15 ): | |
16 r"""Compute current-flow betweenness centrality for subsets of nodes. | |
17 | |
18 Current-flow betweenness centrality uses an electrical current | |
19 model for information spreading in contrast to betweenness | |
20 centrality which uses shortest paths. | |
21 | |
22 Current-flow betweenness centrality is also known as | |
23 random-walk betweenness centrality [2]_. | |
24 | |
25 Parameters | |
26 ---------- | |
27 G : graph | |
28 A NetworkX graph | |
29 | |
30 sources: list of nodes | |
31 Nodes to use as sources for current | |
32 | |
33 targets: list of nodes | |
34 Nodes to use as sinks for current | |
35 | |
36 normalized : bool, optional (default=True) | |
37 If True the betweenness values are normalized by b=b/(n-1)(n-2) where | |
38 n is the number of nodes in G. | |
39 | |
40 weight : string or None, optional (default=None) | |
41 Key for edge data used as the edge weight. | |
42 If None, then use 1 as each edge weight. | |
43 | |
44 dtype: data type (float) | |
45 Default data type for internal matrices. | |
46 Set to np.float32 for lower memory consumption. | |
47 | |
48 solver: string (default='lu') | |
49 Type of linear solver to use for computing the flow matrix. | |
50 Options are "full" (uses most memory), "lu" (recommended), and | |
51 "cg" (uses least memory). | |
52 | |
53 Returns | |
54 ------- | |
55 nodes : dictionary | |
56 Dictionary of nodes with betweenness centrality as the value. | |
57 | |
58 See Also | |
59 -------- | |
60 approximate_current_flow_betweenness_centrality | |
61 betweenness_centrality | |
62 edge_betweenness_centrality | |
63 edge_current_flow_betweenness_centrality | |
64 | |
65 Notes | |
66 ----- | |
67 Current-flow betweenness can be computed in $O(I(n-1)+mn \log n)$ | |
68 time [1]_, where $I(n-1)$ is the time needed to compute the | |
69 inverse Laplacian. For a full matrix this is $O(n^3)$ but using | |
70 sparse methods you can achieve $O(nm{\sqrt k})$ where $k$ is the | |
71 Laplacian matrix condition number. | |
72 | |
73 The space required is $O(nw)$ where $w$ is the width of the sparse | |
74 Laplacian matrix. Worse case is $w=n$ for $O(n^2)$. | |
75 | |
76 If the edges have a 'weight' attribute they will be used as | |
77 weights in this algorithm. Unspecified weights are set to 1. | |
78 | |
79 References | |
80 ---------- | |
81 .. [1] Centrality Measures Based on Current Flow. | |
82 Ulrik Brandes and Daniel Fleischer, | |
83 Proc. 22nd Symp. Theoretical Aspects of Computer Science (STACS '05). | |
84 LNCS 3404, pp. 533-544. Springer-Verlag, 2005. | |
85 http://algo.uni-konstanz.de/publications/bf-cmbcf-05.pdf | |
86 | |
87 .. [2] A measure of betweenness centrality based on random walks, | |
88 M. E. J. Newman, Social Networks 27, 39-54 (2005). | |
89 """ | |
90 from networkx.utils import reverse_cuthill_mckee_ordering | |
91 | |
92 try: | |
93 import numpy as np | |
94 except ImportError as e: | |
95 raise ImportError( | |
96 "current_flow_betweenness_centrality requires NumPy ", "http://numpy.org/" | |
97 ) from e | |
98 if not nx.is_connected(G): | |
99 raise nx.NetworkXError("Graph not connected.") | |
100 n = G.number_of_nodes() | |
101 ordering = list(reverse_cuthill_mckee_ordering(G)) | |
102 # make a copy with integer labels according to rcm ordering | |
103 # this could be done without a copy if we really wanted to | |
104 mapping = dict(zip(ordering, range(n))) | |
105 H = nx.relabel_nodes(G, mapping) | |
106 betweenness = dict.fromkeys(H, 0.0) # b[v]=0 for v in H | |
107 for row, (s, t) in flow_matrix_row(H, weight=weight, dtype=dtype, solver=solver): | |
108 for ss in sources: | |
109 i = mapping[ss] | |
110 for tt in targets: | |
111 j = mapping[tt] | |
112 betweenness[s] += 0.5 * np.abs(row[i] - row[j]) | |
113 betweenness[t] += 0.5 * np.abs(row[i] - row[j]) | |
114 if normalized: | |
115 nb = (n - 1.0) * (n - 2.0) # normalization factor | |
116 else: | |
117 nb = 2.0 | |
118 for v in H: | |
119 betweenness[v] = betweenness[v] / nb + 1.0 / (2 - n) | |
120 return {ordering[k]: v for k, v in betweenness.items()} | |
121 | |
122 | |
123 @not_implemented_for("directed") | |
124 def edge_current_flow_betweenness_centrality_subset( | |
125 G, sources, targets, normalized=True, weight=None, dtype=float, solver="lu" | |
126 ): | |
127 r"""Compute current-flow betweenness centrality for edges using subsets | |
128 of nodes. | |
129 | |
130 Current-flow betweenness centrality uses an electrical current | |
131 model for information spreading in contrast to betweenness | |
132 centrality which uses shortest paths. | |
133 | |
134 Current-flow betweenness centrality is also known as | |
135 random-walk betweenness centrality [2]_. | |
136 | |
137 Parameters | |
138 ---------- | |
139 G : graph | |
140 A NetworkX graph | |
141 | |
142 sources: list of nodes | |
143 Nodes to use as sources for current | |
144 | |
145 targets: list of nodes | |
146 Nodes to use as sinks for current | |
147 | |
148 normalized : bool, optional (default=True) | |
149 If True the betweenness values are normalized by b=b/(n-1)(n-2) where | |
150 n is the number of nodes in G. | |
151 | |
152 weight : string or None, optional (default=None) | |
153 Key for edge data used as the edge weight. | |
154 If None, then use 1 as each edge weight. | |
155 | |
156 dtype: data type (float) | |
157 Default data type for internal matrices. | |
158 Set to np.float32 for lower memory consumption. | |
159 | |
160 solver: string (default='lu') | |
161 Type of linear solver to use for computing the flow matrix. | |
162 Options are "full" (uses most memory), "lu" (recommended), and | |
163 "cg" (uses least memory). | |
164 | |
165 Returns | |
166 ------- | |
167 nodes : dict | |
168 Dictionary of edge tuples with betweenness centrality as the value. | |
169 | |
170 See Also | |
171 -------- | |
172 betweenness_centrality | |
173 edge_betweenness_centrality | |
174 current_flow_betweenness_centrality | |
175 | |
176 Notes | |
177 ----- | |
178 Current-flow betweenness can be computed in $O(I(n-1)+mn \log n)$ | |
179 time [1]_, where $I(n-1)$ is the time needed to compute the | |
180 inverse Laplacian. For a full matrix this is $O(n^3)$ but using | |
181 sparse methods you can achieve $O(nm{\sqrt k})$ where $k$ is the | |
182 Laplacian matrix condition number. | |
183 | |
184 The space required is $O(nw)$ where $w$ is the width of the sparse | |
185 Laplacian matrix. Worse case is $w=n$ for $O(n^2)$. | |
186 | |
187 If the edges have a 'weight' attribute they will be used as | |
188 weights in this algorithm. Unspecified weights are set to 1. | |
189 | |
190 References | |
191 ---------- | |
192 .. [1] Centrality Measures Based on Current Flow. | |
193 Ulrik Brandes and Daniel Fleischer, | |
194 Proc. 22nd Symp. Theoretical Aspects of Computer Science (STACS '05). | |
195 LNCS 3404, pp. 533-544. Springer-Verlag, 2005. | |
196 http://algo.uni-konstanz.de/publications/bf-cmbcf-05.pdf | |
197 | |
198 .. [2] A measure of betweenness centrality based on random walks, | |
199 M. E. J. Newman, Social Networks 27, 39-54 (2005). | |
200 """ | |
201 try: | |
202 import numpy as np | |
203 except ImportError as e: | |
204 raise ImportError( | |
205 "current_flow_betweenness_centrality requires NumPy " "http://numpy.org/" | |
206 ) from e | |
207 if not nx.is_connected(G): | |
208 raise nx.NetworkXError("Graph not connected.") | |
209 n = G.number_of_nodes() | |
210 ordering = list(reverse_cuthill_mckee_ordering(G)) | |
211 # make a copy with integer labels according to rcm ordering | |
212 # this could be done without a copy if we really wanted to | |
213 mapping = dict(zip(ordering, range(n))) | |
214 H = nx.relabel_nodes(G, mapping) | |
215 edges = (tuple(sorted((u, v))) for u, v in H.edges()) | |
216 betweenness = dict.fromkeys(edges, 0.0) | |
217 if normalized: | |
218 nb = (n - 1.0) * (n - 2.0) # normalization factor | |
219 else: | |
220 nb = 2.0 | |
221 for row, (e) in flow_matrix_row(H, weight=weight, dtype=dtype, solver=solver): | |
222 for ss in sources: | |
223 i = mapping[ss] | |
224 for tt in targets: | |
225 j = mapping[tt] | |
226 betweenness[e] += 0.5 * np.abs(row[i] - row[j]) | |
227 betweenness[e] /= nb | |
228 return {(ordering[s], ordering[t]): v for (s, t), v in betweenness.items()} |