Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/linalg/laplacianmatrix.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 """Laplacian matrix of graphs. | |
2 """ | |
3 import networkx as nx | |
4 from networkx.utils import not_implemented_for | |
5 | |
6 __all__ = [ | |
7 "laplacian_matrix", | |
8 "normalized_laplacian_matrix", | |
9 "directed_laplacian_matrix", | |
10 "directed_combinatorial_laplacian_matrix", | |
11 ] | |
12 | |
13 | |
14 @not_implemented_for("directed") | |
15 def laplacian_matrix(G, nodelist=None, weight="weight"): | |
16 """Returns the Laplacian matrix of G. | |
17 | |
18 The graph Laplacian is the matrix L = D - A, where | |
19 A is the adjacency matrix and D is the diagonal matrix of node degrees. | |
20 | |
21 Parameters | |
22 ---------- | |
23 G : graph | |
24 A NetworkX graph | |
25 | |
26 nodelist : list, optional | |
27 The rows and columns are ordered according to the nodes in nodelist. | |
28 If nodelist is None, then the ordering is produced by G.nodes(). | |
29 | |
30 weight : string or None, optional (default='weight') | |
31 The edge data key used to compute each value in the matrix. | |
32 If None, then each edge has weight 1. | |
33 | |
34 Returns | |
35 ------- | |
36 L : SciPy sparse matrix | |
37 The Laplacian matrix of G. | |
38 | |
39 Notes | |
40 ----- | |
41 For MultiGraph/MultiDiGraph, the edges weights are summed. | |
42 | |
43 See Also | |
44 -------- | |
45 to_numpy_array | |
46 normalized_laplacian_matrix | |
47 laplacian_spectrum | |
48 """ | |
49 import scipy.sparse | |
50 | |
51 if nodelist is None: | |
52 nodelist = list(G) | |
53 A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight, format="csr") | |
54 n, m = A.shape | |
55 diags = A.sum(axis=1) | |
56 D = scipy.sparse.spdiags(diags.flatten(), [0], m, n, format="csr") | |
57 return D - A | |
58 | |
59 | |
60 @not_implemented_for("directed") | |
61 def normalized_laplacian_matrix(G, nodelist=None, weight="weight"): | |
62 r"""Returns the normalized Laplacian matrix of G. | |
63 | |
64 The normalized graph Laplacian is the matrix | |
65 | |
66 .. math:: | |
67 | |
68 N = D^{-1/2} L D^{-1/2} | |
69 | |
70 where `L` is the graph Laplacian and `D` is the diagonal matrix of | |
71 node degrees. | |
72 | |
73 Parameters | |
74 ---------- | |
75 G : graph | |
76 A NetworkX graph | |
77 | |
78 nodelist : list, optional | |
79 The rows and columns are ordered according to the nodes in nodelist. | |
80 If nodelist is None, then the ordering is produced by G.nodes(). | |
81 | |
82 weight : string or None, optional (default='weight') | |
83 The edge data key used to compute each value in the matrix. | |
84 If None, then each edge has weight 1. | |
85 | |
86 Returns | |
87 ------- | |
88 N : Scipy sparse matrix | |
89 The normalized Laplacian matrix of G. | |
90 | |
91 Notes | |
92 ----- | |
93 For MultiGraph/MultiDiGraph, the edges weights are summed. | |
94 See to_numpy_array for other options. | |
95 | |
96 If the Graph contains selfloops, D is defined as diag(sum(A,1)), where A is | |
97 the adjacency matrix [2]_. | |
98 | |
99 See Also | |
100 -------- | |
101 laplacian_matrix | |
102 normalized_laplacian_spectrum | |
103 | |
104 References | |
105 ---------- | |
106 .. [1] Fan Chung-Graham, Spectral Graph Theory, | |
107 CBMS Regional Conference Series in Mathematics, Number 92, 1997. | |
108 .. [2] Steve Butler, Interlacing For Weighted Graphs Using The Normalized | |
109 Laplacian, Electronic Journal of Linear Algebra, Volume 16, pp. 90-98, | |
110 March 2007. | |
111 """ | |
112 import numpy as np | |
113 import scipy | |
114 import scipy.sparse | |
115 | |
116 if nodelist is None: | |
117 nodelist = list(G) | |
118 A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight, format="csr") | |
119 n, m = A.shape | |
120 diags = A.sum(axis=1).flatten() | |
121 D = scipy.sparse.spdiags(diags, [0], m, n, format="csr") | |
122 L = D - A | |
123 with scipy.errstate(divide="ignore"): | |
124 diags_sqrt = 1.0 / np.sqrt(diags) | |
125 diags_sqrt[np.isinf(diags_sqrt)] = 0 | |
126 DH = scipy.sparse.spdiags(diags_sqrt, [0], m, n, format="csr") | |
127 return DH.dot(L.dot(DH)) | |
128 | |
129 | |
130 ############################################################################### | |
131 # Code based on | |
132 # https://bitbucket.org/bedwards/networkx-community/src/370bd69fc02f/networkx/algorithms/community/ | |
133 | |
134 | |
135 @not_implemented_for("undirected") | |
136 @not_implemented_for("multigraph") | |
137 def directed_laplacian_matrix( | |
138 G, nodelist=None, weight="weight", walk_type=None, alpha=0.95 | |
139 ): | |
140 r"""Returns the directed Laplacian matrix of G. | |
141 | |
142 The graph directed Laplacian is the matrix | |
143 | |
144 .. math:: | |
145 | |
146 L = I - (\Phi^{1/2} P \Phi^{-1/2} + \Phi^{-1/2} P^T \Phi^{1/2} ) / 2 | |
147 | |
148 where `I` is the identity matrix, `P` is the transition matrix of the | |
149 graph, and `\Phi` a matrix with the Perron vector of `P` in the diagonal and | |
150 zeros elsewhere. | |
151 | |
152 Depending on the value of walk_type, `P` can be the transition matrix | |
153 induced by a random walk, a lazy random walk, or a random walk with | |
154 teleportation (PageRank). | |
155 | |
156 Parameters | |
157 ---------- | |
158 G : DiGraph | |
159 A NetworkX graph | |
160 | |
161 nodelist : list, optional | |
162 The rows and columns are ordered according to the nodes in nodelist. | |
163 If nodelist is None, then the ordering is produced by G.nodes(). | |
164 | |
165 weight : string or None, optional (default='weight') | |
166 The edge data key used to compute each value in the matrix. | |
167 If None, then each edge has weight 1. | |
168 | |
169 walk_type : string or None, optional (default=None) | |
170 If None, `P` is selected depending on the properties of the | |
171 graph. Otherwise is one of 'random', 'lazy', or 'pagerank' | |
172 | |
173 alpha : real | |
174 (1 - alpha) is the teleportation probability used with pagerank | |
175 | |
176 Returns | |
177 ------- | |
178 L : NumPy matrix | |
179 Normalized Laplacian of G. | |
180 | |
181 Notes | |
182 ----- | |
183 Only implemented for DiGraphs | |
184 | |
185 See Also | |
186 -------- | |
187 laplacian_matrix | |
188 | |
189 References | |
190 ---------- | |
191 .. [1] Fan Chung (2005). | |
192 Laplacians and the Cheeger inequality for directed graphs. | |
193 Annals of Combinatorics, 9(1), 2005 | |
194 """ | |
195 import numpy as np | |
196 from scipy.sparse import spdiags, linalg | |
197 | |
198 P = _transition_matrix( | |
199 G, nodelist=nodelist, weight=weight, walk_type=walk_type, alpha=alpha | |
200 ) | |
201 | |
202 n, m = P.shape | |
203 | |
204 evals, evecs = linalg.eigs(P.T, k=1) | |
205 v = evecs.flatten().real | |
206 p = v / v.sum() | |
207 sqrtp = np.sqrt(p) | |
208 Q = spdiags(sqrtp, [0], n, n) * P * spdiags(1.0 / sqrtp, [0], n, n) | |
209 I = np.identity(len(G)) | |
210 | |
211 return I - (Q + Q.T) / 2.0 | |
212 | |
213 | |
214 @not_implemented_for("undirected") | |
215 @not_implemented_for("multigraph") | |
216 def directed_combinatorial_laplacian_matrix( | |
217 G, nodelist=None, weight="weight", walk_type=None, alpha=0.95 | |
218 ): | |
219 r"""Return the directed combinatorial Laplacian matrix of G. | |
220 | |
221 The graph directed combinatorial Laplacian is the matrix | |
222 | |
223 .. math:: | |
224 | |
225 L = \Phi - (\Phi P + P^T \Phi) / 2 | |
226 | |
227 where `P` is the transition matrix of the graph and and `\Phi` a matrix | |
228 with the Perron vector of `P` in the diagonal and zeros elsewhere. | |
229 | |
230 Depending on the value of walk_type, `P` can be the transition matrix | |
231 induced by a random walk, a lazy random walk, or a random walk with | |
232 teleportation (PageRank). | |
233 | |
234 Parameters | |
235 ---------- | |
236 G : DiGraph | |
237 A NetworkX graph | |
238 | |
239 nodelist : list, optional | |
240 The rows and columns are ordered according to the nodes in nodelist. | |
241 If nodelist is None, then the ordering is produced by G.nodes(). | |
242 | |
243 weight : string or None, optional (default='weight') | |
244 The edge data key used to compute each value in the matrix. | |
245 If None, then each edge has weight 1. | |
246 | |
247 walk_type : string or None, optional (default=None) | |
248 If None, `P` is selected depending on the properties of the | |
249 graph. Otherwise is one of 'random', 'lazy', or 'pagerank' | |
250 | |
251 alpha : real | |
252 (1 - alpha) is the teleportation probability used with pagerank | |
253 | |
254 Returns | |
255 ------- | |
256 L : NumPy matrix | |
257 Combinatorial Laplacian of G. | |
258 | |
259 Notes | |
260 ----- | |
261 Only implemented for DiGraphs | |
262 | |
263 See Also | |
264 -------- | |
265 laplacian_matrix | |
266 | |
267 References | |
268 ---------- | |
269 .. [1] Fan Chung (2005). | |
270 Laplacians and the Cheeger inequality for directed graphs. | |
271 Annals of Combinatorics, 9(1), 2005 | |
272 """ | |
273 from scipy.sparse import spdiags, linalg | |
274 | |
275 P = _transition_matrix( | |
276 G, nodelist=nodelist, weight=weight, walk_type=walk_type, alpha=alpha | |
277 ) | |
278 | |
279 n, m = P.shape | |
280 | |
281 evals, evecs = linalg.eigs(P.T, k=1) | |
282 v = evecs.flatten().real | |
283 p = v / v.sum() | |
284 Phi = spdiags(p, [0], n, n) | |
285 | |
286 Phi = Phi.todense() | |
287 | |
288 return Phi - (Phi * P + P.T * Phi) / 2.0 | |
289 | |
290 | |
291 def _transition_matrix(G, nodelist=None, weight="weight", walk_type=None, alpha=0.95): | |
292 """Returns the transition matrix of G. | |
293 | |
294 This is a row stochastic giving the transition probabilities while | |
295 performing a random walk on the graph. Depending on the value of walk_type, | |
296 P can be the transition matrix induced by a random walk, a lazy random walk, | |
297 or a random walk with teleportation (PageRank). | |
298 | |
299 Parameters | |
300 ---------- | |
301 G : DiGraph | |
302 A NetworkX graph | |
303 | |
304 nodelist : list, optional | |
305 The rows and columns are ordered according to the nodes in nodelist. | |
306 If nodelist is None, then the ordering is produced by G.nodes(). | |
307 | |
308 weight : string or None, optional (default='weight') | |
309 The edge data key used to compute each value in the matrix. | |
310 If None, then each edge has weight 1. | |
311 | |
312 walk_type : string or None, optional (default=None) | |
313 If None, `P` is selected depending on the properties of the | |
314 graph. Otherwise is one of 'random', 'lazy', or 'pagerank' | |
315 | |
316 alpha : real | |
317 (1 - alpha) is the teleportation probability used with pagerank | |
318 | |
319 Returns | |
320 ------- | |
321 P : NumPy matrix | |
322 transition matrix of G. | |
323 | |
324 Raises | |
325 ------ | |
326 NetworkXError | |
327 If walk_type not specified or alpha not in valid range | |
328 """ | |
329 import numpy as np | |
330 from scipy.sparse import identity, spdiags | |
331 | |
332 if walk_type is None: | |
333 if nx.is_strongly_connected(G): | |
334 if nx.is_aperiodic(G): | |
335 walk_type = "random" | |
336 else: | |
337 walk_type = "lazy" | |
338 else: | |
339 walk_type = "pagerank" | |
340 | |
341 M = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight, dtype=float) | |
342 n, m = M.shape | |
343 if walk_type in ["random", "lazy"]: | |
344 DI = spdiags(1.0 / np.array(M.sum(axis=1).flat), [0], n, n) | |
345 if walk_type == "random": | |
346 P = DI * M | |
347 else: | |
348 I = identity(n) | |
349 P = (I + DI * M) / 2.0 | |
350 | |
351 elif walk_type == "pagerank": | |
352 if not (0 < alpha < 1): | |
353 raise nx.NetworkXError("alpha must be between 0 and 1") | |
354 # this is using a dense representation | |
355 M = M.todense() | |
356 # add constant to dangling nodes' row | |
357 dangling = np.where(M.sum(axis=1) == 0) | |
358 for d in dangling[0]: | |
359 M[d] = 1.0 / n | |
360 # normalize | |
361 M = M / M.sum(axis=1) | |
362 P = alpha * M + (1 - alpha) / n | |
363 else: | |
364 raise nx.NetworkXError("walk_type must be random, lazy, or pagerank") | |
365 | |
366 return P |