Mercurial > repos > shellac > guppy_basecaller

comparison env/lib/python3.7/site-packages/networkx/linalg/laplacianmatrix.py @ 0:26e78fe6e8c4 draft

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