normalized_laplacian_matrix#

normalized_laplacian_matrix(G, nodelist=None, weight='weight')[source]#

Returns the normalized Laplacian matrix of G.

The normalized graph Laplacian is the matrix

\[N = D^{-1/2} L D^{-1/2}\]

where L is the graph Laplacian and D is the diagonal matrix of node degrees [1].

Parameters:

Ggraph: A NetworkX graph
nodelistlist, optional: The rows and columns are ordered according to the nodes in nodelist. If nodelist is None, then the ordering is produced by G.nodes().
weightstring or None, optional (default=’weight’): The edge data key used to compute each value in the matrix. If None, then each edge has weight 1.

Returns:

NSciPy sparse array: The normalized Laplacian matrix of G.

See also

laplacian_matrix
normalized_laplacian_spectrum
directed_laplacian_matrix
directed_combinatorial_laplacian_matrix

Notes

For MultiGraph, the edges weights are summed. See to_numpy_array() for other options.

If the Graph contains selfloops, D is defined as diag(sum(A, 1)), where A is the adjacency matrix [2].

This calculation uses the out-degree of the graph G. To use the in-degree for calculations instead, use G.reverse(copy=False) and take the transpose.

For an unnormalized output, use laplacian_matrix.

References

[1]

Fan Chung-Graham, Spectral Graph Theory, CBMS Regional Conference Series in Mathematics, Number 92, 1997.

[2]

Steve Butler, Interlacing For Weighted Graphs Using The Normalized Laplacian, Electronic Journal of Linear Algebra, Volume 16, pp. 90-98, March 2007.

[3]

Langville, Amy N., and Carl D. Meyer. Google’s PageRank and Beyond: The Science of Search Engine Rankings. Princeton University Press, 2006.

Examples

>>> import numpy as np
>>> edges = [
...     (1, 2),
...     (2, 1),
...     (2, 4),
...     (4, 3),
...     (3, 4),
... ]
>>> DiG = nx.DiGraph(edges)
>>> print(nx.normalized_laplacian_matrix(DiG).toarray())
[[ 1.         -0.70710678  0.          0.        ]
 [-0.70710678  1.         -0.70710678  0.        ]
 [ 0.          0.          1.         -1.        ]
 [ 0.          0.         -1.          1.        ]]

Notice that node 4 is represented by the third column and row. This is because by default the row/column order is the order of G.nodes (i.e. the node added order – in the edgelist, 4 first appears in (2, 4), before node 3 in edge (4, 3).) To control the node order of the matrix, use the nodelist argument.

>>> print(nx.normalized_laplacian_matrix(DiG, nodelist=[1, 2, 3, 4]).toarray())
[[ 1.         -0.70710678  0.          0.        ]
 [-0.70710678  1.          0.         -0.70710678]
 [ 0.          0.          1.         -1.        ]
 [ 0.          0.         -1.          1.        ]]
>>> G = nx.Graph(edges)
>>> print(nx.normalized_laplacian_matrix(G).toarray())
[[ 1.         -0.70710678  0.          0.        ]
 [-0.70710678  1.         -0.5         0.        ]
 [ 0.         -0.5         1.         -0.70710678]
 [ 0.          0.         -0.70710678  1.        ]]
----

Additional backends implement this function

graphblas : OpenMP-enabled sparse linear algebra backend.