directed_combinatorial_laplacian_matrix#
- directed_combinatorial_laplacian_matrix(G, nodelist=None, weight='weight', walk_type=None, alpha=0.95)[source]#
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 andPhi
a matrix with the Perron vector ofP
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"
. Ifwalk_type=None
(the default), then a value is selected according to the properties ofG
: -walk_type="random"
ifG
is strongly connected and aperiodic -walk_type="lazy"
ifG
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.
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, useG.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