Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""Current-flow betweenness centrality measures for subsets of nodes."""
3import networkx as nx
4from networkx.algorithms.centrality.flow_matrix import flow_matrix_row
5from networkx.utils import not_implemented_for, reverse_cuthill_mckee_ordering
7__all__ = [
8 "current_flow_betweenness_centrality_subset",
9 "edge_current_flow_betweenness_centrality_subset",
10]
13@not_implemented_for("directed")
14@nx._dispatchable(edge_attrs="weight")
15def current_flow_betweenness_centrality_subset(
16 G, sources, targets, normalized=True, weight=None, dtype=float, solver="lu"
17):
18 r"""Compute current-flow betweenness centrality for subsets of nodes.
20 Current-flow betweenness centrality uses an electrical current
21 model for information spreading in contrast to betweenness
22 centrality which uses shortest paths.
24 Current-flow betweenness centrality is also known as
25 random-walk betweenness centrality [2]_.
27 Parameters
28 ----------
29 G : graph
30 A NetworkX graph
32 sources: list of nodes
33 Nodes to use as sources for current
35 targets: list of nodes
36 Nodes to use as sinks for current
38 normalized : bool, optional (default=True)
39 If True the betweenness values are normalized by b=b/(n-1)(n-2) where
40 n is the number of nodes in G.
42 weight : string or None, optional (default=None)
43 Key for edge data used as the edge weight.
44 If None, then use 1 as each edge weight.
45 The weight reflects the capacity or the strength of the
46 edge.
48 dtype: data type (float)
49 Default data type for internal matrices.
50 Set to np.float32 for lower memory consumption.
52 solver: string (default='lu')
53 Type of linear solver to use for computing the flow matrix.
54 Options are "full" (uses most memory), "lu" (recommended), and
55 "cg" (uses least memory).
57 Returns
58 -------
59 nodes : dictionary
60 Dictionary of nodes with betweenness centrality as the value.
62 See Also
63 --------
64 approximate_current_flow_betweenness_centrality
65 betweenness_centrality
66 edge_betweenness_centrality
67 edge_current_flow_betweenness_centrality
69 Notes
70 -----
71 Current-flow betweenness can be computed in $O(I(n-1)+mn \log n)$
72 time [1]_, where $I(n-1)$ is the time needed to compute the
73 inverse Laplacian. For a full matrix this is $O(n^3)$ but using
74 sparse methods you can achieve $O(nm{\sqrt k})$ where $k$ is the
75 Laplacian matrix condition number.
77 The space required is $O(nw)$ where $w$ is the width of the sparse
78 Laplacian matrix. Worse case is $w=n$ for $O(n^2)$.
80 If the edges have a 'weight' attribute they will be used as
81 weights in this algorithm. Unspecified weights are set to 1.
83 References
84 ----------
85 .. [1] Centrality Measures Based on Current Flow.
86 Ulrik Brandes and Daniel Fleischer,
87 Proc. 22nd Symp. Theoretical Aspects of Computer Science (STACS '05).
88 LNCS 3404, pp. 533-544. Springer-Verlag, 2005.
89 https://doi.org/10.1007/978-3-540-31856-9_44
91 .. [2] A measure of betweenness centrality based on random walks,
92 M. E. J. Newman, Social Networks 27, 39-54 (2005).
93 """
94 import numpy as np
96 from networkx.utils import reverse_cuthill_mckee_ordering
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[n]=0 for n 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 * abs(row.item(i) - row.item(j))
113 betweenness[t] += 0.5 * abs(row.item(i) - row.item(j))
114 if normalized:
115 nb = (N - 1.0) * (N - 2.0) # normalization factor
116 else:
117 nb = 2.0
118 for node in H:
119 betweenness[node] = betweenness[node] / nb + 1.0 / (2 - N)
120 return {ordering[node]: value for node, value in betweenness.items()}
123@not_implemented_for("directed")
124@nx._dispatchable(edge_attrs="weight")
125def edge_current_flow_betweenness_centrality_subset(
126 G, sources, targets, normalized=True, weight=None, dtype=float, solver="lu"
127):
128 r"""Compute current-flow betweenness centrality for edges using subsets
129 of nodes.
131 Current-flow betweenness centrality uses an electrical current
132 model for information spreading in contrast to betweenness
133 centrality which uses shortest paths.
135 Current-flow betweenness centrality is also known as
136 random-walk betweenness centrality [2]_.
138 Parameters
139 ----------
140 G : graph
141 A NetworkX graph
143 sources: list of nodes
144 Nodes to use as sources for current
146 targets: list of nodes
147 Nodes to use as sinks for current
149 normalized : bool, optional (default=True)
150 If True the betweenness values are normalized by b=b/(n-1)(n-2) where
151 n is the number of nodes in G.
153 weight : string or None, optional (default=None)
154 Key for edge data used as the edge weight.
155 If None, then use 1 as each edge weight.
156 The weight reflects the capacity or the strength of the
157 edge.
159 dtype: data type (float)
160 Default data type for internal matrices.
161 Set to np.float32 for lower memory consumption.
163 solver: string (default='lu')
164 Type of linear solver to use for computing the flow matrix.
165 Options are "full" (uses most memory), "lu" (recommended), and
166 "cg" (uses least memory).
168 Returns
169 -------
170 nodes : dict
171 Dictionary of edge tuples with betweenness centrality as the value.
173 See Also
174 --------
175 betweenness_centrality
176 edge_betweenness_centrality
177 current_flow_betweenness_centrality
179 Notes
180 -----
181 Current-flow betweenness can be computed in $O(I(n-1)+mn \log n)$
182 time [1]_, where $I(n-1)$ is the time needed to compute the
183 inverse Laplacian. For a full matrix this is $O(n^3)$ but using
184 sparse methods you can achieve $O(nm{\sqrt k})$ where $k$ is the
185 Laplacian matrix condition number.
187 The space required is $O(nw)$ where $w$ is the width of the sparse
188 Laplacian matrix. Worse case is $w=n$ for $O(n^2)$.
190 If the edges have a 'weight' attribute they will be used as
191 weights in this algorithm. Unspecified weights are set to 1.
193 References
194 ----------
195 .. [1] Centrality Measures Based on Current Flow.
196 Ulrik Brandes and Daniel Fleischer,
197 Proc. 22nd Symp. Theoretical Aspects of Computer Science (STACS '05).
198 LNCS 3404, pp. 533-544. Springer-Verlag, 2005.
199 https://doi.org/10.1007/978-3-540-31856-9_44
201 .. [2] A measure of betweenness centrality based on random walks,
202 M. E. J. Newman, Social Networks 27, 39-54 (2005).
203 """
204 import numpy as np
206 if not nx.is_connected(G):
207 raise nx.NetworkXError("Graph not connected.")
208 N = G.number_of_nodes()
209 ordering = list(reverse_cuthill_mckee_ordering(G))
210 # make a copy with integer labels according to rcm ordering
211 # this could be done without a copy if we really wanted to
212 mapping = dict(zip(ordering, range(N)))
213 H = nx.relabel_nodes(G, mapping)
214 edges = (tuple(sorted((u, v))) for u, v in H.edges())
215 betweenness = dict.fromkeys(edges, 0.0)
216 if normalized:
217 nb = (N - 1.0) * (N - 2.0) # normalization factor
218 else:
219 nb = 2.0
220 for row, (e) in flow_matrix_row(H, weight=weight, dtype=dtype, solver=solver):
221 for ss in sources:
222 i = mapping[ss]
223 for tt in targets:
224 j = mapping[tt]
225 betweenness[e] += 0.5 * abs(row.item(i) - row.item(j))
226 betweenness[e] /= nb
227 return {(ordering[s], ordering[t]): value for (s, t), value in betweenness.items()}