directed_combinatorial_laplacian_matrix

directed_combinatorial_laplacian_matrix(G, nodelist=None, weight='weight', walk_type=None, alpha=0.95)

Return the directed combinatorial Laplacian matrix of G.

The graph directed combinatorial Laplacian is the matrix

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

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

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.

alphareal

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

Returns:

LNumPy matrix

Combinatorial Laplacian of G.

See also

laplacian_matrix

normalized_laplacian_matrix

directed_laplacian_matrix

Notes

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.

References

[1]

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