laplacian

Contents

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.

LinearOperator vs. sparse matrices

For many linear algebra computations it is more efficient to pass operator=True to this function. In this case, it will 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) — 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

[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.#

Contents