directed_laplacian_matrix(G, nodelist=None, weight='weight', walk_type=None, alpha=0.95)[source]#

Returns the directed Laplacian matrix of G.

The graph directed Laplacian is the matrix

\[L = I - \frac{1}{2} \left (\Phi^{1/2} P \Phi^{-1/2} + \Phi^{-1/2} P^T \Phi^{1/2} \right )\]

where I is the identity matrix, P is the transition matrix of the graph, and Phi a matrix with the Perron vector of P in the diagonal and zeros elsewhere [1].

Depending on the value of walk_type, P can be the transition matrix induced by a random walk, a lazy random walk, or a random walk with teleportation (PageRank).


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.

walk_typestring or None, optional (default=None)

One of "random", "lazy", or "pagerank". If walk_type=None (the default), then a value is selected according to the properties of G: - walk_type="random" if G is strongly connected and aperiodic - walk_type="lazy" if G is strongly connected but not aperiodic - walk_type="pagerank" for all other cases.


(1 - alpha) is the teleportation probability used with pagerank

LNumPy matrix

Normalized Laplacian of G.


Only implemented for DiGraphs

The result is always a symmetric matrix.

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.



Fan Chung (2005). Laplacians and the Cheeger inequality for directed graphs. Annals of Combinatorics, 9(1), 2005