directed_laplacian_matrix#

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 - (\Phi^{1/2} P \Phi^{-1/2} + \Phi^{-1/2} P^T \Phi^{1/2} ) / 2\]

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).

Parameters:
GDiGraph

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)

If None, P is selected depending on the properties of the graph. Otherwise is one of ‘random’, ‘lazy’, or ‘pagerank’

alphareal

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

Returns:
LNumPy matrix

Normalized Laplacian of G.

See also

laplacian_matrix

Notes

Only implemented for DiGraphs

References

[1]

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