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"""Laplacian matrix of graphs.
3All calculations here are done using the out-degree. For Laplacians using
4in-degree, use `G.reverse(copy=False)` instead of `G` and take the transpose.
6The `laplacian_matrix` function provides an unnormalized matrix,
7while `normalized_laplacian_matrix`, `directed_laplacian_matrix`,
8and `directed_combinatorial_laplacian_matrix` are all normalized.
9"""
11import networkx as nx
12from networkx.utils import not_implemented_for
14__all__ = [
15 "laplacian_matrix",
16 "normalized_laplacian_matrix",
17 "directed_laplacian_matrix",
18 "directed_combinatorial_laplacian_matrix",
19]
22@nx._dispatchable(edge_attrs="weight")
23def laplacian_matrix(G, nodelist=None, weight="weight"):
24 """Returns the Laplacian matrix of G.
26 The graph Laplacian is the matrix L = D - A, where
27 A is the adjacency matrix and D is the diagonal matrix of node degrees.
29 Parameters
30 ----------
31 G : graph
32 A NetworkX graph
34 nodelist : list, optional
35 The rows and columns are ordered according to the nodes in nodelist.
36 If nodelist is None, then the ordering is produced by G.nodes().
38 weight : string or None, optional (default='weight')
39 The edge data key used to compute each value in the matrix.
40 If None, then each edge has weight 1.
42 Returns
43 -------
44 L : SciPy sparse array
45 The Laplacian matrix of G.
47 Notes
48 -----
49 For MultiGraph, the edges weights are summed.
51 This returns an unnormalized matrix. For a normalized output,
52 use `normalized_laplacian_matrix`, `directed_laplacian_matrix`,
53 or `directed_combinatorial_laplacian_matrix`.
55 This calculation uses the out-degree of the graph `G`. To use the
56 in-degree for calculations instead, use `G.reverse(copy=False)` and
57 take the transpose.
59 See Also
60 --------
61 :func:`~networkx.convert_matrix.to_numpy_array`
62 normalized_laplacian_matrix
63 directed_laplacian_matrix
64 directed_combinatorial_laplacian_matrix
65 :func:`~networkx.linalg.spectrum.laplacian_spectrum`
67 Examples
68 --------
69 For graphs with multiple connected components, L is permutation-similar
70 to a block diagonal matrix where each block is the respective Laplacian
71 matrix for each component.
73 >>> G = nx.Graph([(1, 2), (2, 3), (4, 5)])
74 >>> print(nx.laplacian_matrix(G).toarray())
75 [[ 1 -1 0 0 0]
76 [-1 2 -1 0 0]
77 [ 0 -1 1 0 0]
78 [ 0 0 0 1 -1]
79 [ 0 0 0 -1 1]]
81 >>> edges = [
82 ... (1, 2),
83 ... (2, 1),
84 ... (2, 4),
85 ... (4, 3),
86 ... (3, 4),
87 ... ]
88 >>> DiG = nx.DiGraph(edges)
89 >>> print(nx.laplacian_matrix(DiG).toarray())
90 [[ 1 -1 0 0]
91 [-1 2 -1 0]
92 [ 0 0 1 -1]
93 [ 0 0 -1 1]]
95 Notice that node 4 is represented by the third column and row. This is because
96 by default the row/column order is the order of `G.nodes` (i.e. the node added
97 order -- in the edgelist, 4 first appears in (2, 4), before node 3 in edge (4, 3).)
98 To control the node order of the matrix, use the `nodelist` argument.
100 >>> print(nx.laplacian_matrix(DiG, nodelist=[1, 2, 3, 4]).toarray())
101 [[ 1 -1 0 0]
102 [-1 2 0 -1]
103 [ 0 0 1 -1]
104 [ 0 0 -1 1]]
106 This calculation uses the out-degree of the graph `G`. To use the
107 in-degree for calculations instead, use `G.reverse(copy=False)` and
108 take the transpose.
110 >>> print(nx.laplacian_matrix(DiG.reverse(copy=False)).toarray().T)
111 [[ 1 -1 0 0]
112 [-1 1 -1 0]
113 [ 0 0 2 -1]
114 [ 0 0 -1 1]]
116 References
117 ----------
118 .. [1] Langville, Amy N., and Carl D. Meyer. Google’s PageRank and Beyond:
119 The Science of Search Engine Rankings. Princeton University Press, 2006.
121 """
122 import scipy as sp
124 if nodelist is None:
125 nodelist = list(G)
126 A = nx.to_scipy_sparse_array(G, nodelist=nodelist, weight=weight, format="csr")
127 n, m = A.shape
128 D = sp.sparse.dia_array((A.sum(axis=1), 0), shape=(m, n)).tocsr()
129 return D - A
132@nx._dispatchable(edge_attrs="weight")
133def normalized_laplacian_matrix(G, nodelist=None, weight="weight"):
134 r"""Returns the normalized Laplacian matrix of G.
136 The normalized graph Laplacian is the matrix
138 .. math::
140 N = D^{-1/2} L D^{-1/2}
142 where `L` is the graph Laplacian and `D` is the diagonal matrix of
143 node degrees [1]_.
145 Parameters
146 ----------
147 G : graph
148 A NetworkX graph
150 nodelist : list, optional
151 The rows and columns are ordered according to the nodes in nodelist.
152 If nodelist is None, then the ordering is produced by G.nodes().
154 weight : string or None, optional (default='weight')
155 The edge data key used to compute each value in the matrix.
156 If None, then each edge has weight 1.
158 Returns
159 -------
160 N : SciPy sparse array
161 The normalized Laplacian matrix of G.
163 Notes
164 -----
165 For MultiGraph, the edges weights are summed.
166 See :func:`to_numpy_array` for other options.
168 If the Graph contains selfloops, D is defined as ``diag(sum(A, 1))``, where A is
169 the adjacency matrix [2]_.
171 This calculation uses the out-degree of the graph `G`. To use the
172 in-degree for calculations instead, use `G.reverse(copy=False)` and
173 take the transpose.
175 For an unnormalized output, use `laplacian_matrix`.
177 Examples
178 --------
180 >>> import numpy as np
181 >>> edges = [
182 ... (1, 2),
183 ... (2, 1),
184 ... (2, 4),
185 ... (4, 3),
186 ... (3, 4),
187 ... ]
188 >>> DiG = nx.DiGraph(edges)
189 >>> print(nx.normalized_laplacian_matrix(DiG).toarray())
190 [[ 1. -0.70710678 0. 0. ]
191 [-0.70710678 1. -0.70710678 0. ]
192 [ 0. 0. 1. -1. ]
193 [ 0. 0. -1. 1. ]]
195 Notice that node 4 is represented by the third column and row. This is because
196 by default the row/column order is the order of `G.nodes` (i.e. the node added
197 order -- in the edgelist, 4 first appears in (2, 4), before node 3 in edge (4, 3).)
198 To control the node order of the matrix, use the `nodelist` argument.
200 >>> print(nx.normalized_laplacian_matrix(DiG, nodelist=[1, 2, 3, 4]).toarray())
201 [[ 1. -0.70710678 0. 0. ]
202 [-0.70710678 1. 0. -0.70710678]
203 [ 0. 0. 1. -1. ]
204 [ 0. 0. -1. 1. ]]
205 >>> G = nx.Graph(edges)
206 >>> print(nx.normalized_laplacian_matrix(G).toarray())
207 [[ 1. -0.70710678 0. 0. ]
208 [-0.70710678 1. -0.5 0. ]
209 [ 0. -0.5 1. -0.70710678]
210 [ 0. 0. -0.70710678 1. ]]
212 See Also
213 --------
214 laplacian_matrix
215 normalized_laplacian_spectrum
216 directed_laplacian_matrix
217 directed_combinatorial_laplacian_matrix
219 References
220 ----------
221 .. [1] Fan Chung-Graham, Spectral Graph Theory,
222 CBMS Regional Conference Series in Mathematics, Number 92, 1997.
223 .. [2] Steve Butler, Interlacing For Weighted Graphs Using The Normalized
224 Laplacian, Electronic Journal of Linear Algebra, Volume 16, pp. 90-98,
225 March 2007.
226 .. [3] Langville, Amy N., and Carl D. Meyer. Google’s PageRank and Beyond:
227 The Science of Search Engine Rankings. Princeton University Press, 2006.
228 """
229 import numpy as np
230 import scipy as sp
232 if nodelist is None:
233 nodelist = list(G)
234 A = nx.to_scipy_sparse_array(G, nodelist=nodelist, weight=weight, format="csr")
235 n, _ = A.shape
236 diags = A.sum(axis=1)
237 D = sp.sparse.dia_array((diags, 0), shape=(n, n)).tocsr()
238 L = D - A
239 with np.errstate(divide="ignore"):
240 diags_sqrt = 1.0 / np.sqrt(diags)
241 diags_sqrt[np.isinf(diags_sqrt)] = 0
242 DH = sp.sparse.dia_array((diags_sqrt, 0), shape=(n, n)).tocsr()
243 return DH @ (L @ DH)
246###############################################################################
247# Code based on work from https://github.com/bjedwards
250@not_implemented_for("undirected")
251@not_implemented_for("multigraph")
252@nx._dispatchable(edge_attrs="weight")
253def directed_laplacian_matrix(
254 G, nodelist=None, weight="weight", walk_type=None, alpha=0.95
255):
256 r"""Returns the directed Laplacian matrix of G.
258 The graph directed Laplacian is the matrix
260 .. math::
262 L = I - \frac{1}{2} \left (\Phi^{1/2} P \Phi^{-1/2} + \Phi^{-1/2} P^T \Phi^{1/2} \right )
264 where `I` is the identity matrix, `P` is the transition matrix of the
265 graph, and `\Phi` a matrix with the Perron vector of `P` in the diagonal and
266 zeros elsewhere [1]_.
268 Depending on the value of walk_type, `P` can be the transition matrix
269 induced by a random walk, a lazy random walk, or a random walk with
270 teleportation (PageRank).
272 Parameters
273 ----------
274 G : DiGraph
275 A NetworkX graph
277 nodelist : list, optional
278 The rows and columns are ordered according to the nodes in nodelist.
279 If nodelist is None, then the ordering is produced by G.nodes().
281 weight : string or None, optional (default='weight')
282 The edge data key used to compute each value in the matrix.
283 If None, then each edge has weight 1.
285 walk_type : string or None, optional (default=None)
286 One of ``"random"``, ``"lazy"``, or ``"pagerank"``. If ``walk_type=None``
287 (the default), then a value is selected according to the properties of `G`:
288 - ``walk_type="random"`` if `G` is strongly connected and aperiodic
289 - ``walk_type="lazy"`` if `G` is strongly connected but not aperiodic
290 - ``walk_type="pagerank"`` for all other cases.
292 alpha : real
293 (1 - alpha) is the teleportation probability used with pagerank
295 Returns
296 -------
297 L : NumPy matrix
298 Normalized Laplacian of G.
300 Notes
301 -----
302 Only implemented for DiGraphs
304 The result is always a symmetric matrix.
306 This calculation uses the out-degree of the graph `G`. To use the
307 in-degree for calculations instead, use `G.reverse(copy=False)` and
308 take the transpose.
310 See Also
311 --------
312 laplacian_matrix
313 normalized_laplacian_matrix
314 directed_combinatorial_laplacian_matrix
316 References
317 ----------
318 .. [1] Fan Chung (2005).
319 Laplacians and the Cheeger inequality for directed graphs.
320 Annals of Combinatorics, 9(1), 2005
321 """
322 import numpy as np
323 import scipy as sp
325 # NOTE: P has type ndarray if walk_type=="pagerank", else csr_array
326 P = _transition_matrix(
327 G, nodelist=nodelist, weight=weight, walk_type=walk_type, alpha=alpha
328 )
330 n, m = P.shape
332 evals, evecs = sp.sparse.linalg.eigs(P.T, k=1)
333 v = evecs.flatten().real
334 p = v / v.sum()
335 # p>=0 by Perron-Frobenius Thm. Use abs() to fix roundoff across zero gh-6865
336 sqrtp = np.sqrt(np.abs(p))
337 Q = (
338 sp.sparse.dia_array((sqrtp, 0), shape=(n, n)).tocsr()
339 @ P
340 @ sp.sparse.dia_array((1.0 / sqrtp, 0), shape=(n, n)).tocsr()
341 )
342 # NOTE: This could be sparsified for the non-pagerank cases
343 I = np.identity(len(G))
345 return I - (Q + Q.T) / 2.0
348@not_implemented_for("undirected")
349@not_implemented_for("multigraph")
350@nx._dispatchable(edge_attrs="weight")
351def directed_combinatorial_laplacian_matrix(
352 G, nodelist=None, weight="weight", walk_type=None, alpha=0.95
353):
354 r"""Return the directed combinatorial Laplacian matrix of G.
356 The graph directed combinatorial Laplacian is the matrix
358 .. math::
360 L = \Phi - \frac{1}{2} \left (\Phi P + P^T \Phi \right)
362 where `P` is the transition matrix of the graph and `\Phi` a matrix
363 with the Perron vector of `P` in the diagonal and zeros elsewhere [1]_.
365 Depending on the value of walk_type, `P` can be the transition matrix
366 induced by a random walk, a lazy random walk, or a random walk with
367 teleportation (PageRank).
369 Parameters
370 ----------
371 G : DiGraph
372 A NetworkX graph
374 nodelist : list, optional
375 The rows and columns are ordered according to the nodes in nodelist.
376 If nodelist is None, then the ordering is produced by G.nodes().
378 weight : string or None, optional (default='weight')
379 The edge data key used to compute each value in the matrix.
380 If None, then each edge has weight 1.
382 walk_type : string or None, optional (default=None)
383 One of ``"random"``, ``"lazy"``, or ``"pagerank"``. If ``walk_type=None``
384 (the default), then a value is selected according to the properties of `G`:
385 - ``walk_type="random"`` if `G` is strongly connected and aperiodic
386 - ``walk_type="lazy"`` if `G` is strongly connected but not aperiodic
387 - ``walk_type="pagerank"`` for all other cases.
389 alpha : real
390 (1 - alpha) is the teleportation probability used with pagerank
392 Returns
393 -------
394 L : NumPy matrix
395 Combinatorial Laplacian of G.
397 Notes
398 -----
399 Only implemented for DiGraphs
401 The result is always a symmetric matrix.
403 This calculation uses the out-degree of the graph `G`. To use the
404 in-degree for calculations instead, use `G.reverse(copy=False)` and
405 take the transpose.
407 See Also
408 --------
409 laplacian_matrix
410 normalized_laplacian_matrix
411 directed_laplacian_matrix
413 References
414 ----------
415 .. [1] Fan Chung (2005).
416 Laplacians and the Cheeger inequality for directed graphs.
417 Annals of Combinatorics, 9(1), 2005
418 """
419 import scipy as sp
421 P = _transition_matrix(
422 G, nodelist=nodelist, weight=weight, walk_type=walk_type, alpha=alpha
423 )
425 n, m = P.shape
427 evals, evecs = sp.sparse.linalg.eigs(P.T, k=1)
428 v = evecs.flatten().real
429 p = v / v.sum()
430 # NOTE: could be improved by not densifying
431 Phi = sp.sparse.dia_array((p, 0), shape=(n, n)).toarray()
433 return Phi - (Phi @ P + P.T @ Phi) / 2.0
436def _transition_matrix(G, nodelist=None, weight="weight", walk_type=None, alpha=0.95):
437 """Returns the transition matrix of G.
439 This is a row stochastic giving the transition probabilities while
440 performing a random walk on the graph. Depending on the value of walk_type,
441 P can be the transition matrix induced by a random walk, a lazy random walk,
442 or a random walk with teleportation (PageRank).
444 Parameters
445 ----------
446 G : DiGraph
447 A NetworkX graph
449 nodelist : list, optional
450 The rows and columns are ordered according to the nodes in nodelist.
451 If nodelist is None, then the ordering is produced by G.nodes().
453 weight : string or None, optional (default='weight')
454 The edge data key used to compute each value in the matrix.
455 If None, then each edge has weight 1.
457 walk_type : string or None, optional (default=None)
458 One of ``"random"``, ``"lazy"``, or ``"pagerank"``. If ``walk_type=None``
459 (the default), then a value is selected according to the properties of `G`:
460 - ``walk_type="random"`` if `G` is strongly connected and aperiodic
461 - ``walk_type="lazy"`` if `G` is strongly connected but not aperiodic
462 - ``walk_type="pagerank"`` for all other cases.
464 alpha : real
465 (1 - alpha) is the teleportation probability used with pagerank
467 Returns
468 -------
469 P : numpy.ndarray
470 transition matrix of G.
472 Raises
473 ------
474 NetworkXError
475 If walk_type not specified or alpha not in valid range
476 """
477 import numpy as np
478 import scipy as sp
480 if walk_type is None:
481 if nx.is_strongly_connected(G):
482 if nx.is_aperiodic(G):
483 walk_type = "random"
484 else:
485 walk_type = "lazy"
486 else:
487 walk_type = "pagerank"
489 A = nx.to_scipy_sparse_array(G, nodelist=nodelist, weight=weight, dtype=float)
490 n, m = A.shape
491 if walk_type in ["random", "lazy"]:
492 DI = sp.sparse.dia_array((1.0 / A.sum(axis=1), 0), shape=(n, n)).tocsr()
493 if walk_type == "random":
494 P = DI @ A
495 else:
496 I = sp.sparse.eye_array(n, format="csr")
497 P = (I + DI @ A) / 2.0
499 elif walk_type == "pagerank":
500 if not (0 < alpha < 1):
501 raise nx.NetworkXError("alpha must be between 0 and 1")
502 # this is using a dense representation. NOTE: This should be sparsified!
503 A = A.toarray()
504 # add constant to dangling nodes' row
505 A[A.sum(axis=1) == 0, :] = 1 / n
506 # normalize
507 A = A / A.sum(axis=1)[np.newaxis, :].T
508 P = alpha * A + (1 - alpha) / n
509 else:
510 raise nx.NetworkXError("walk_type must be random, lazy, or pagerank")
512 return P