Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/centrality/current_flow_betweenness.py: 17%
83 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""Current-flow betweenness centrality measures."""
2import networkx as nx
3from networkx.algorithms.centrality.flow_matrix import (
4 CGInverseLaplacian,
5 FullInverseLaplacian,
6 SuperLUInverseLaplacian,
7 flow_matrix_row,
8)
9from networkx.utils import (
10 not_implemented_for,
11 py_random_state,
12 reverse_cuthill_mckee_ordering,
13)
15__all__ = [
16 "current_flow_betweenness_centrality",
17 "approximate_current_flow_betweenness_centrality",
18 "edge_current_flow_betweenness_centrality",
19]
22@not_implemented_for("directed")
23@py_random_state(7)
24@nx._dispatch(edge_attrs="weight")
25def approximate_current_flow_betweenness_centrality(
26 G,
27 normalized=True,
28 weight=None,
29 dtype=float,
30 solver="full",
31 epsilon=0.5,
32 kmax=10000,
33 seed=None,
34):
35 r"""Compute the approximate current-flow betweenness centrality for nodes.
37 Approximates the current-flow betweenness centrality within absolute
38 error of epsilon with high probability [1]_.
41 Parameters
42 ----------
43 G : graph
44 A NetworkX graph
46 normalized : bool, optional (default=True)
47 If True the betweenness values are normalized by 2/[(n-1)(n-2)] where
48 n is the number of nodes in G.
50 weight : string or None, optional (default=None)
51 Key for edge data used as the edge weight.
52 If None, then use 1 as each edge weight.
53 The weight reflects the capacity or the strength of the
54 edge.
56 dtype : data type (float)
57 Default data type for internal matrices.
58 Set to np.float32 for lower memory consumption.
60 solver : string (default='full')
61 Type of linear solver to use for computing the flow matrix.
62 Options are "full" (uses most memory), "lu" (recommended), and
63 "cg" (uses least memory).
65 epsilon: float
66 Absolute error tolerance.
68 kmax: int
69 Maximum number of sample node pairs to use for approximation.
71 seed : integer, random_state, or None (default)
72 Indicator of random number generation state.
73 See :ref:`Randomness<randomness>`.
75 Returns
76 -------
77 nodes : dictionary
78 Dictionary of nodes with betweenness centrality as the value.
80 See Also
81 --------
82 current_flow_betweenness_centrality
84 Notes
85 -----
86 The running time is $O((1/\epsilon^2)m{\sqrt k} \log n)$
87 and the space required is $O(m)$ for $n$ nodes and $m$ edges.
89 If the edges have a 'weight' attribute they will be used as
90 weights in this algorithm. Unspecified weights are set to 1.
92 References
93 ----------
94 .. [1] Ulrik Brandes and Daniel Fleischer:
95 Centrality Measures Based on Current Flow.
96 Proc. 22nd Symp. Theoretical Aspects of Computer Science (STACS '05).
97 LNCS 3404, pp. 533-544. Springer-Verlag, 2005.
98 https://doi.org/10.1007/978-3-540-31856-9_44
99 """
100 import numpy as np
102 if not nx.is_connected(G):
103 raise nx.NetworkXError("Graph not connected.")
104 solvername = {
105 "full": FullInverseLaplacian,
106 "lu": SuperLUInverseLaplacian,
107 "cg": CGInverseLaplacian,
108 }
109 n = G.number_of_nodes()
110 ordering = list(reverse_cuthill_mckee_ordering(G))
111 # make a copy with integer labels according to rcm ordering
112 # this could be done without a copy if we really wanted to
113 H = nx.relabel_nodes(G, dict(zip(ordering, range(n))))
114 L = nx.laplacian_matrix(H, nodelist=range(n), weight=weight).asformat("csc")
115 L = L.astype(dtype)
116 C = solvername[solver](L, dtype=dtype) # initialize solver
117 betweenness = dict.fromkeys(H, 0.0)
118 nb = (n - 1.0) * (n - 2.0) # normalization factor
119 cstar = n * (n - 1) / nb
120 l = 1 # parameter in approximation, adjustable
121 k = l * int(np.ceil((cstar / epsilon) ** 2 * np.log(n)))
122 if k > kmax:
123 msg = f"Number random pairs k>kmax ({k}>{kmax}) "
124 raise nx.NetworkXError(msg, "Increase kmax or epsilon")
125 cstar2k = cstar / (2 * k)
126 for _ in range(k):
127 s, t = pair = seed.sample(range(n), 2)
128 b = np.zeros(n, dtype=dtype)
129 b[s] = 1
130 b[t] = -1
131 p = C.solve(b)
132 for v in H:
133 if v in pair:
134 continue
135 for nbr in H[v]:
136 w = H[v][nbr].get(weight, 1.0)
137 betweenness[v] += w * np.abs(p[v] - p[nbr]) * cstar2k
138 if normalized:
139 factor = 1.0
140 else:
141 factor = nb / 2.0
142 # remap to original node names and "unnormalize" if required
143 return {ordering[k]: v * factor for k, v in betweenness.items()}
146@not_implemented_for("directed")
147@nx._dispatch(edge_attrs="weight")
148def current_flow_betweenness_centrality(
149 G, normalized=True, weight=None, dtype=float, solver="full"
150):
151 r"""Compute current-flow betweenness centrality for nodes.
153 Current-flow betweenness centrality uses an electrical current
154 model for information spreading in contrast to betweenness
155 centrality which uses shortest paths.
157 Current-flow betweenness centrality is also known as
158 random-walk betweenness centrality [2]_.
160 Parameters
161 ----------
162 G : graph
163 A NetworkX graph
165 normalized : bool, optional (default=True)
166 If True the betweenness values are normalized by 2/[(n-1)(n-2)] where
167 n is the number of nodes in G.
169 weight : string or None, optional (default=None)
170 Key for edge data used as the edge weight.
171 If None, then use 1 as each edge weight.
172 The weight reflects the capacity or the strength of the
173 edge.
175 dtype : data type (float)
176 Default data type for internal matrices.
177 Set to np.float32 for lower memory consumption.
179 solver : string (default='full')
180 Type of linear solver to use for computing the flow matrix.
181 Options are "full" (uses most memory), "lu" (recommended), and
182 "cg" (uses least memory).
184 Returns
185 -------
186 nodes : dictionary
187 Dictionary of nodes with betweenness centrality as the value.
189 See Also
190 --------
191 approximate_current_flow_betweenness_centrality
192 betweenness_centrality
193 edge_betweenness_centrality
194 edge_current_flow_betweenness_centrality
196 Notes
197 -----
198 Current-flow betweenness can be computed in $O(I(n-1)+mn \log n)$
199 time [1]_, where $I(n-1)$ is the time needed to compute the
200 inverse Laplacian. For a full matrix this is $O(n^3)$ but using
201 sparse methods you can achieve $O(nm{\sqrt k})$ where $k$ is the
202 Laplacian matrix condition number.
204 The space required is $O(nw)$ where $w$ is the width of the sparse
205 Laplacian matrix. Worse case is $w=n$ for $O(n^2)$.
207 If the edges have a 'weight' attribute they will be used as
208 weights in this algorithm. Unspecified weights are set to 1.
210 References
211 ----------
212 .. [1] Centrality Measures Based on Current Flow.
213 Ulrik Brandes and Daniel Fleischer,
214 Proc. 22nd Symp. Theoretical Aspects of Computer Science (STACS '05).
215 LNCS 3404, pp. 533-544. Springer-Verlag, 2005.
216 https://doi.org/10.1007/978-3-540-31856-9_44
218 .. [2] A measure of betweenness centrality based on random walks,
219 M. E. J. Newman, Social Networks 27, 39-54 (2005).
220 """
221 if not nx.is_connected(G):
222 raise nx.NetworkXError("Graph not connected.")
223 n = G.number_of_nodes()
224 ordering = list(reverse_cuthill_mckee_ordering(G))
225 # make a copy with integer labels according to rcm ordering
226 # this could be done without a copy if we really wanted to
227 H = nx.relabel_nodes(G, dict(zip(ordering, range(n))))
228 betweenness = dict.fromkeys(H, 0.0) # b[v]=0 for v in H
229 for row, (s, t) in flow_matrix_row(H, weight=weight, dtype=dtype, solver=solver):
230 pos = dict(zip(row.argsort()[::-1], range(n)))
231 for i in range(n):
232 betweenness[s] += (i - pos[i]) * row[i]
233 betweenness[t] += (n - i - 1 - pos[i]) * row[i]
234 if normalized:
235 nb = (n - 1.0) * (n - 2.0) # normalization factor
236 else:
237 nb = 2.0
238 for v in H:
239 betweenness[v] = float((betweenness[v] - v) * 2.0 / nb)
240 return {ordering[k]: v for k, v in betweenness.items()}
243@not_implemented_for("directed")
244@nx._dispatch(edge_attrs="weight")
245def edge_current_flow_betweenness_centrality(
246 G, normalized=True, weight=None, dtype=float, solver="full"
247):
248 r"""Compute current-flow betweenness centrality for edges.
250 Current-flow betweenness centrality uses an electrical current
251 model for information spreading in contrast to betweenness
252 centrality which uses shortest paths.
254 Current-flow betweenness centrality is also known as
255 random-walk betweenness centrality [2]_.
257 Parameters
258 ----------
259 G : graph
260 A NetworkX graph
262 normalized : bool, optional (default=True)
263 If True the betweenness values are normalized by 2/[(n-1)(n-2)] where
264 n is the number of nodes in G.
266 weight : string or None, optional (default=None)
267 Key for edge data used as the edge weight.
268 If None, then use 1 as each edge weight.
269 The weight reflects the capacity or the strength of the
270 edge.
272 dtype : data type (default=float)
273 Default data type for internal matrices.
274 Set to np.float32 for lower memory consumption.
276 solver : string (default='full')
277 Type of linear solver to use for computing the flow matrix.
278 Options are "full" (uses most memory), "lu" (recommended), and
279 "cg" (uses least memory).
281 Returns
282 -------
283 nodes : dictionary
284 Dictionary of edge tuples with betweenness centrality as the value.
286 Raises
287 ------
288 NetworkXError
289 The algorithm does not support DiGraphs.
290 If the input graph is an instance of DiGraph class, NetworkXError
291 is raised.
293 See Also
294 --------
295 betweenness_centrality
296 edge_betweenness_centrality
297 current_flow_betweenness_centrality
299 Notes
300 -----
301 Current-flow betweenness can be computed in $O(I(n-1)+mn \log n)$
302 time [1]_, where $I(n-1)$ is the time needed to compute the
303 inverse Laplacian. For a full matrix this is $O(n^3)$ but using
304 sparse methods you can achieve $O(nm{\sqrt k})$ where $k$ is the
305 Laplacian matrix condition number.
307 The space required is $O(nw)$ where $w$ is the width of the sparse
308 Laplacian matrix. Worse case is $w=n$ for $O(n^2)$.
310 If the edges have a 'weight' attribute they will be used as
311 weights in this algorithm. Unspecified weights are set to 1.
313 References
314 ----------
315 .. [1] Centrality Measures Based on Current Flow.
316 Ulrik Brandes and Daniel Fleischer,
317 Proc. 22nd Symp. Theoretical Aspects of Computer Science (STACS '05).
318 LNCS 3404, pp. 533-544. Springer-Verlag, 2005.
319 https://doi.org/10.1007/978-3-540-31856-9_44
321 .. [2] A measure of betweenness centrality based on random walks,
322 M. E. J. Newman, Social Networks 27, 39-54 (2005).
323 """
324 if not nx.is_connected(G):
325 raise nx.NetworkXError("Graph not connected.")
326 n = G.number_of_nodes()
327 ordering = list(reverse_cuthill_mckee_ordering(G))
328 # make a copy with integer labels according to rcm ordering
329 # this could be done without a copy if we really wanted to
330 H = nx.relabel_nodes(G, dict(zip(ordering, range(n))))
331 edges = (tuple(sorted((u, v))) for u, v in H.edges())
332 betweenness = dict.fromkeys(edges, 0.0)
333 if normalized:
334 nb = (n - 1.0) * (n - 2.0) # normalization factor
335 else:
336 nb = 2.0
337 for row, (e) in flow_matrix_row(H, weight=weight, dtype=dtype, solver=solver):
338 pos = dict(zip(row.argsort()[::-1], range(1, n + 1)))
339 for i in range(n):
340 betweenness[e] += (i + 1 - pos[i]) * row[i]
341 betweenness[e] += (n - i - pos[i]) * row[i]
342 betweenness[e] /= nb
343 return {(ordering[s], ordering[t]): v for (s, t), v in betweenness.items()}