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