Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/linalg/laplacianmatrix.py: 23%
88 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""Laplacian matrix of graphs.
2"""
3import networkx as nx
4from networkx.utils import not_implemented_for
6__all__ = [
7 "laplacian_matrix",
8 "normalized_laplacian_matrix",
9 "total_spanning_tree_weight",
10 "directed_laplacian_matrix",
11 "directed_combinatorial_laplacian_matrix",
12]
15@not_implemented_for("directed")
16@nx._dispatch(edge_attrs="weight")
17def laplacian_matrix(G, nodelist=None, weight="weight"):
18 """Returns the Laplacian matrix of G.
20 The graph Laplacian is the matrix L = D - A, where
21 A is the adjacency matrix and D is the diagonal matrix of node degrees.
23 Parameters
24 ----------
25 G : graph
26 A NetworkX graph
28 nodelist : list, optional
29 The rows and columns are ordered according to the nodes in nodelist.
30 If nodelist is None, then the ordering is produced by G.nodes().
32 weight : string or None, optional (default='weight')
33 The edge data key used to compute each value in the matrix.
34 If None, then each edge has weight 1.
36 Returns
37 -------
38 L : SciPy sparse array
39 The Laplacian matrix of G.
41 Notes
42 -----
43 For MultiGraph, the edges weights are summed.
45 See Also
46 --------
47 :func:`~networkx.convert_matrix.to_numpy_array`
48 normalized_laplacian_matrix
49 :func:`~networkx.linalg.spectrum.laplacian_spectrum`
51 Examples
52 --------
53 For graphs with multiple connected components, L is permutation-similar
54 to a block diagonal matrix where each block is the respective Laplacian
55 matrix for each component.
57 >>> G = nx.Graph([(1, 2), (2, 3), (4, 5)])
58 >>> print(nx.laplacian_matrix(G).toarray())
59 [[ 1 -1 0 0 0]
60 [-1 2 -1 0 0]
61 [ 0 -1 1 0 0]
62 [ 0 0 0 1 -1]
63 [ 0 0 0 -1 1]]
65 """
66 import scipy as sp
68 if nodelist is None:
69 nodelist = list(G)
70 A = nx.to_scipy_sparse_array(G, nodelist=nodelist, weight=weight, format="csr")
71 n, m = A.shape
72 # TODO: rm csr_array wrapper when spdiags can produce arrays
73 D = sp.sparse.csr_array(sp.sparse.spdiags(A.sum(axis=1), 0, m, n, format="csr"))
74 return D - A
77@not_implemented_for("directed")
78@nx._dispatch(edge_attrs="weight")
79def normalized_laplacian_matrix(G, nodelist=None, weight="weight"):
80 r"""Returns the normalized Laplacian matrix of G.
82 The normalized graph Laplacian is the matrix
84 .. math::
86 N = D^{-1/2} L D^{-1/2}
88 where `L` is the graph Laplacian and `D` is the diagonal matrix of
89 node degrees [1]_.
91 Parameters
92 ----------
93 G : graph
94 A NetworkX graph
96 nodelist : list, optional
97 The rows and columns are ordered according to the nodes in nodelist.
98 If nodelist is None, then the ordering is produced by G.nodes().
100 weight : string or None, optional (default='weight')
101 The edge data key used to compute each value in the matrix.
102 If None, then each edge has weight 1.
104 Returns
105 -------
106 N : SciPy sparse array
107 The normalized Laplacian matrix of G.
109 Notes
110 -----
111 For MultiGraph, the edges weights are summed.
112 See :func:`to_numpy_array` for other options.
114 If the Graph contains selfloops, D is defined as ``diag(sum(A, 1))``, where A is
115 the adjacency matrix [2]_.
117 See Also
118 --------
119 laplacian_matrix
120 normalized_laplacian_spectrum
122 References
123 ----------
124 .. [1] Fan Chung-Graham, Spectral Graph Theory,
125 CBMS Regional Conference Series in Mathematics, Number 92, 1997.
126 .. [2] Steve Butler, Interlacing For Weighted Graphs Using The Normalized
127 Laplacian, Electronic Journal of Linear Algebra, Volume 16, pp. 90-98,
128 March 2007.
129 """
130 import numpy as np
131 import scipy as sp
133 if nodelist is None:
134 nodelist = list(G)
135 A = nx.to_scipy_sparse_array(G, nodelist=nodelist, weight=weight, format="csr")
136 n, m = A.shape
137 diags = A.sum(axis=1)
138 # TODO: rm csr_array wrapper when spdiags can produce arrays
139 D = sp.sparse.csr_array(sp.sparse.spdiags(diags, 0, m, n, format="csr"))
140 L = D - A
141 with np.errstate(divide="ignore"):
142 diags_sqrt = 1.0 / np.sqrt(diags)
143 diags_sqrt[np.isinf(diags_sqrt)] = 0
144 # TODO: rm csr_array wrapper when spdiags can produce arrays
145 DH = sp.sparse.csr_array(sp.sparse.spdiags(diags_sqrt, 0, m, n, format="csr"))
146 return DH @ (L @ DH)
149@nx._dispatch(edge_attrs="weight")
150def total_spanning_tree_weight(G, weight=None):
151 """
152 Returns the total weight of all spanning trees of `G`.
154 Kirchoff's Tree Matrix Theorem states that the determinant of any cofactor of the
155 Laplacian matrix of a graph is the number of spanning trees in the graph. For a
156 weighted Laplacian matrix, it is the sum across all spanning trees of the
157 multiplicative weight of each tree. That is, the weight of each tree is the
158 product of its edge weights.
160 Parameters
161 ----------
162 G : NetworkX Graph
163 The graph to use Kirchhoff's theorem on.
165 weight : string or None
166 The key for the edge attribute holding the edge weight. If `None`, then
167 each edge is assumed to have a weight of 1 and this function returns the
168 total number of spanning trees in `G`.
170 Returns
171 -------
172 float
173 The sum of the total multiplicative weights for all spanning trees in `G`
174 """
175 import numpy as np
177 G_laplacian = nx.laplacian_matrix(G, weight=weight).toarray()
178 # Determinant ignoring first row and column
179 return abs(np.linalg.det(G_laplacian[1:, 1:]))
182###############################################################################
183# Code based on work from https://github.com/bjedwards
186@not_implemented_for("undirected")
187@not_implemented_for("multigraph")
188@nx._dispatch(edge_attrs="weight")
189def directed_laplacian_matrix(
190 G, nodelist=None, weight="weight", walk_type=None, alpha=0.95
191):
192 r"""Returns the directed Laplacian matrix of G.
194 The graph directed Laplacian is the matrix
196 .. math::
198 L = I - (\Phi^{1/2} P \Phi^{-1/2} + \Phi^{-1/2} P^T \Phi^{1/2} ) / 2
200 where `I` is the identity matrix, `P` is the transition matrix of the
201 graph, and `\Phi` a matrix with the Perron vector of `P` in the diagonal and
202 zeros elsewhere [1]_.
204 Depending on the value of walk_type, `P` can be the transition matrix
205 induced by a random walk, a lazy random walk, or a random walk with
206 teleportation (PageRank).
208 Parameters
209 ----------
210 G : DiGraph
211 A NetworkX graph
213 nodelist : list, optional
214 The rows and columns are ordered according to the nodes in nodelist.
215 If nodelist is None, then the ordering is produced by G.nodes().
217 weight : string or None, optional (default='weight')
218 The edge data key used to compute each value in the matrix.
219 If None, then each edge has weight 1.
221 walk_type : string or None, optional (default=None)
222 If None, `P` is selected depending on the properties of the
223 graph. Otherwise is one of 'random', 'lazy', or 'pagerank'
225 alpha : real
226 (1 - alpha) is the teleportation probability used with pagerank
228 Returns
229 -------
230 L : NumPy matrix
231 Normalized Laplacian of G.
233 Notes
234 -----
235 Only implemented for DiGraphs
237 See Also
238 --------
239 laplacian_matrix
241 References
242 ----------
243 .. [1] Fan Chung (2005).
244 Laplacians and the Cheeger inequality for directed graphs.
245 Annals of Combinatorics, 9(1), 2005
246 """
247 import numpy as np
248 import scipy as sp
250 # NOTE: P has type ndarray if walk_type=="pagerank", else csr_array
251 P = _transition_matrix(
252 G, nodelist=nodelist, weight=weight, walk_type=walk_type, alpha=alpha
253 )
255 n, m = P.shape
257 evals, evecs = sp.sparse.linalg.eigs(P.T, k=1)
258 v = evecs.flatten().real
259 p = v / v.sum()
260 # p>=0 by Perron-Frobenius Thm. Use abs() to fix roundoff across zero gh-6865
261 sqrtp = np.sqrt(np.abs(p))
262 Q = (
263 # TODO: rm csr_array wrapper when spdiags creates arrays
264 sp.sparse.csr_array(sp.sparse.spdiags(sqrtp, 0, n, n))
265 @ P
266 # TODO: rm csr_array wrapper when spdiags creates arrays
267 @ sp.sparse.csr_array(sp.sparse.spdiags(1.0 / sqrtp, 0, n, n))
268 )
269 # NOTE: This could be sparsified for the non-pagerank cases
270 I = np.identity(len(G))
272 return I - (Q + Q.T) / 2.0
275@not_implemented_for("undirected")
276@not_implemented_for("multigraph")
277@nx._dispatch(edge_attrs="weight")
278def directed_combinatorial_laplacian_matrix(
279 G, nodelist=None, weight="weight", walk_type=None, alpha=0.95
280):
281 r"""Return the directed combinatorial Laplacian matrix of G.
283 The graph directed combinatorial Laplacian is the matrix
285 .. math::
287 L = \Phi - (\Phi P + P^T \Phi) / 2
289 where `P` is the transition matrix of the graph and `\Phi` a matrix
290 with the Perron vector of `P` in the diagonal and zeros elsewhere [1]_.
292 Depending on the value of walk_type, `P` can be the transition matrix
293 induced by a random walk, a lazy random walk, or a random walk with
294 teleportation (PageRank).
296 Parameters
297 ----------
298 G : DiGraph
299 A NetworkX graph
301 nodelist : list, optional
302 The rows and columns are ordered according to the nodes in nodelist.
303 If nodelist is None, then the ordering is produced by G.nodes().
305 weight : string or None, optional (default='weight')
306 The edge data key used to compute each value in the matrix.
307 If None, then each edge has weight 1.
309 walk_type : string or None, optional (default=None)
310 If None, `P` is selected depending on the properties of the
311 graph. Otherwise is one of 'random', 'lazy', or 'pagerank'
313 alpha : real
314 (1 - alpha) is the teleportation probability used with pagerank
316 Returns
317 -------
318 L : NumPy matrix
319 Combinatorial Laplacian of G.
321 Notes
322 -----
323 Only implemented for DiGraphs
325 See Also
326 --------
327 laplacian_matrix
329 References
330 ----------
331 .. [1] Fan Chung (2005).
332 Laplacians and the Cheeger inequality for directed graphs.
333 Annals of Combinatorics, 9(1), 2005
334 """
335 import scipy as sp
337 P = _transition_matrix(
338 G, nodelist=nodelist, weight=weight, walk_type=walk_type, alpha=alpha
339 )
341 n, m = P.shape
343 evals, evecs = sp.sparse.linalg.eigs(P.T, k=1)
344 v = evecs.flatten().real
345 p = v / v.sum()
346 # NOTE: could be improved by not densifying
347 # TODO: Rm csr_array wrapper when spdiags array creation becomes available
348 Phi = sp.sparse.csr_array(sp.sparse.spdiags(p, 0, n, n)).toarray()
350 return Phi - (Phi @ P + P.T @ Phi) / 2.0
353def _transition_matrix(G, nodelist=None, weight="weight", walk_type=None, alpha=0.95):
354 """Returns the transition matrix of G.
356 This is a row stochastic giving the transition probabilities while
357 performing a random walk on the graph. Depending on the value of walk_type,
358 P can be the transition matrix induced by a random walk, a lazy random walk,
359 or a random walk with teleportation (PageRank).
361 Parameters
362 ----------
363 G : DiGraph
364 A NetworkX graph
366 nodelist : list, optional
367 The rows and columns are ordered according to the nodes in nodelist.
368 If nodelist is None, then the ordering is produced by G.nodes().
370 weight : string or None, optional (default='weight')
371 The edge data key used to compute each value in the matrix.
372 If None, then each edge has weight 1.
374 walk_type : string or None, optional (default=None)
375 If None, `P` is selected depending on the properties of the
376 graph. Otherwise is one of 'random', 'lazy', or 'pagerank'
378 alpha : real
379 (1 - alpha) is the teleportation probability used with pagerank
381 Returns
382 -------
383 P : numpy.ndarray
384 transition matrix of G.
386 Raises
387 ------
388 NetworkXError
389 If walk_type not specified or alpha not in valid range
390 """
391 import numpy as np
392 import scipy as sp
394 if walk_type is None:
395 if nx.is_strongly_connected(G):
396 if nx.is_aperiodic(G):
397 walk_type = "random"
398 else:
399 walk_type = "lazy"
400 else:
401 walk_type = "pagerank"
403 A = nx.to_scipy_sparse_array(G, nodelist=nodelist, weight=weight, dtype=float)
404 n, m = A.shape
405 if walk_type in ["random", "lazy"]:
406 # TODO: Rm csr_array wrapper when spdiags array creation becomes available
407 DI = sp.sparse.csr_array(sp.sparse.spdiags(1.0 / A.sum(axis=1), 0, n, n))
408 if walk_type == "random":
409 P = DI @ A
410 else:
411 # TODO: Rm csr_array wrapper when identity array creation becomes available
412 I = sp.sparse.csr_array(sp.sparse.identity(n))
413 P = (I + DI @ A) / 2.0
415 elif walk_type == "pagerank":
416 if not (0 < alpha < 1):
417 raise nx.NetworkXError("alpha must be between 0 and 1")
418 # this is using a dense representation. NOTE: This should be sparsified!
419 A = A.toarray()
420 # add constant to dangling nodes' row
421 A[A.sum(axis=1) == 0, :] = 1 / n
422 # normalize
423 A = A / A.sum(axis=1)[np.newaxis, :].T
424 P = alpha * A + (1 - alpha) / n
425 else:
426 raise nx.NetworkXError("walk_type must be random, lazy, or pagerank")
428 return P