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

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 """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()}