graph_tool.spectral.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:
gGraph

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.

weightEdgePropertyMap (optional, default: None)

Edge property map with the edge weights.

rdouble (optional, default: 1.)

Regularization parameter. If \(r > 1\), and norm is False, then this corresponds to the Bethe Hessian. (This parameter has an effect only for norm == False.)

vindexVertexPropertyMap (optional, default: None)

Vertex property map specifying the row/column indices. If not provided, the internal vertex index is used.

operatorbool (optional, default: False)

If True, a scipy.sparse.linalg.LinearOperator subclass is returned, instead of a sparse matrix.

csrbool (optional, default: True)

If True, and operator is False, a scipy.sparse.csr_matrix sparse matrix is returned, otherwise a scipy.sparse.coo_matrix is returned instead.

Returns:
Lcsr_matrix or LaplacianOperator

The (sparse) Laplacian matrix.

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}\) if deg=="out" or \(\Gamma(v_i)=\sum_j A_{ij}w_{ij}\) if deg=="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.

Note

For many linear algebra computations it is more efficient to pass operator=True. This makes this function return a scipy.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 module scipy.sparse.linalg. This avoids copying the whole graph as a sparse matrix, and performs the multiplication operations in parallel (if enabled during compilation).

References

[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")
../_images/laplacian-spectrum.svg

Laplacian matrix spectrum for the political blogs network.#

>>> 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")
../_images/norm-laplacian-spectrum.svg

Normalized Laplacian matrix spectrum for the political blogs network.#