laplacian#
- graph_tool.spectral.laplacian(g, deg='out', norm=False, weight=None, r=1, vindex=None, operator=False, csr=True)[source]#
Return the Laplacian (or Bethe Hessian if \(r > 1\)) matrix of the graph.
- Parameters:
- g
Graph
Graph to be used.
- degstr (optional, default: “total”)
Degree to be used, in case of a directed graph.
- normbool (optional, default: False)
Whether to compute the normalized Laplacian.
- weight
EdgePropertyMap
(optional, default:None
) Edge property map with the edge weights.
- r
double
(optional, default:1.
) Regularization parameter. If \(r > 1\), and
norm
isFalse
, then this corresponds to the Bethe Hessian. (This parameter has an effect only fornorm == False
.)- vindex
VertexPropertyMap
(optional, default:None
) Vertex property map specifying the row/column indices. If not provided, the internal vertex index is used.
- operator
bool
(optional, default:False
) If
True
, ascipy.sparse.linalg.LinearOperator
subclass is returned, instead of a sparse matrix.- csr
bool
(optional, default:True
) If
True
, andoperator
isFalse
, ascipy.sparse.csr_matrix
sparse matrix is returned, otherwise ascipy.sparse.coo_matrix
is returned instead.
- g
- Returns:
- L
csr_matrix
orLaplacianOperator
The (sparse) Laplacian matrix.
- L
Notes
The weighted Laplacian matrix is defined as
\[\begin{split}\ell_{ij} = \begin{cases} \Gamma(v_i) & \text{if } i = j \\ -w_{ij} & \text{if } i \neq j \text{ and } (j, i) \in E \\ 0 & \text{otherwise}. \end{cases}\end{split}\]Where \(\Gamma(v_i)=\sum_j A_{ij}w_{ij}\) is sum of the weights of the edges incident on vertex \(v_i\).
In case of \(r > 1\), the matrix returned is the Bethe Hessian [bethe-hessian]:
\[\begin{split}\ell_{ij} = \begin{cases} \Gamma(v_i) + (r^2 - 1) & \text{if } i = j \\ -r w_{ij} & \text{if } i \neq j \text{ and } (j, i) \in E \\ 0 & \text{otherwise}. \end{cases}\end{split}\]The normalized version is
\[\begin{split}\ell_{ij} = \begin{cases} 1 & \text{ if } i = j \text{ and } \Gamma(v_i) \neq 0 \\ -\frac{w_{ij}}{\sqrt{\Gamma(v_i)\Gamma(v_j)}} & \text{ if } i \neq j \text{ and } (j, i) \in E \\ 0 & \text{otherwise}. \end{cases}\end{split}\]In the case of unweighted edges, it is assumed \(w_{ij} = 1\).
For directed graphs, it is assumed \(\Gamma(v_i)=\sum_j A_{ij}w_{ij} + \sum_j A_{ji}w_{ji}\) if
deg=="total"
, \(\Gamma(v_i)=\sum_j A_{ji}w_{ji}\) ifdeg=="out"
or \(\Gamma(v_i)=\sum_j A_{ij}w_{ij}\) ifdeg=="in"
.Note
For directed graphs the definition above means that the entry \(\ell_{i,j}\) corresponds to the directed edge \(j\to i\). Although this is a typical definition in network and graph theory literature, many also use the transpose of this matrix.
LinearOperator
vs. sparse matricesFor many linear algebra computations it is more efficient to pass
operator=True
to this function. In this case, it will return ascipy.sparse.linalg.LinearOperator
subclass, which implements matrix-vector and matrix-matrix multiplication, and is sufficient for the sparse linear algebra operations available in the scipy modulescipy.sparse.linalg
. This avoids copying the whole graph as a sparse matrix, and performs the multiplication operations in parallel (if enabled during compilation) — see note below.Parallel implementation.
If enabled during compilation, this algorithm will run in parallel using OpenMP. See the parallel algorithms section for information about how to control several aspects of parallelization.
(The above is only applicable if
operator == True
, and when the object returned is used to perform matrix-vector or matrix-matrix multiplications.)References
[wikipedia-laplacian][bethe-hessian]Saade, Alaa, Florent Krzakala, and Lenka Zdeborová. “Spectral clustering of graphs with the bethe hessian.” Advances in Neural Information Processing Systems 27 (2014): 406-414, arXiv: 1406.1880, https://proceedings.neurips.cc/paper/2014/hash/63923f49e5241343aa7acb6a06a751e7-Abstract.html
Examples
>>> g = gt.collection.data["polblogs"] >>> L = gt.laplacian(g, operator=True) >>> N = g.num_vertices() >>> ew1 = scipy.sparse.linalg.eigs(L, k=N//2, which="LR", return_eigenvectors=False) >>> ew2 = scipy.sparse.linalg.eigs(L, k=N-N//2, which="SR", return_eigenvectors=False) >>> ew = np.concatenate((ew1, ew2))
>>> figure(figsize=(8, 2)) <...> >>> scatter(real(ew), imag(ew), c=sqrt(abs(ew)), linewidths=0, alpha=0.6) <...> >>> xlabel(r"$\operatorname{Re}(\lambda)$") Text(...) >>> ylabel(r"$\operatorname{Im}(\lambda)$") Text(...) >>> tight_layout() >>> savefig("laplacian-spectrum.svg")
>>> L = gt.laplacian(g, norm=True, operator=True) >>> ew1 = scipy.sparse.linalg.eigs(L, k=N//2, which="LR", return_eigenvectors=False) >>> ew2 = scipy.sparse.linalg.eigs(L, k=N-N//2, which="SR", return_eigenvectors=False) >>> ew = np.concatenate((ew1, ew2))
>>> figure(figsize=(8, 2)) <...> >>> scatter(real(ew), imag(ew), c=sqrt(abs(ew)), linewidths=0, alpha=0.6) <...> >>> xlabel(r"$\operatorname{Re}(\lambda)$") Text(...) >>> ylabel(r"$\operatorname{Im}(\lambda)$") Text(...) >>> tight_layout() >>> savefig("norm-laplacian-spectrum.svg")