graph_tool.spectral.hashimoto

graph_tool.spectral.hashimoto(g, index=None, compact=False, operator=False, csr=True)

Return the Hashimoto (or non-backtracking) matrix of a graph.

Parameters:

gGraph

Graph to be used.

indexVertexPropertyMap (optional, default: None)

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

compactboolean (optional, default: False)

If True, a compact \(2|V|\times 2|V|\) version of the matrix is returned.

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:

Hcsr_matrix or HashimotoOperator or CompactHashimotoOperator

The (sparse) Hashimoto matrix.

Notes

The Hashimoto (a.k.a. non-backtracking) matrix [hashimoto] is defined as

\[\begin{split}h_{k\to l,i\to j} = \begin{cases} 1 & \text{if } (k,l) \in E, (i,j) \in E, l=i, k\ne j,\\ 0 & \text{otherwise}, \end{cases}\end{split}\]

where \(E\) is the edge set. It is therefore a \(2|E|\times 2|E|\) asymmetric square matrix (or \(|E|\times |E|\) for directed graphs), indexed over edge directions.

If the option compact=True is passed, the matrix returned has shape \(2|V|\times 2|V|\), where \(|V|\) is the number of vertices, and is given by

\[\begin{split}\boldsymbol h = \left(\begin{array}{c|c} \boldsymbol A & -\boldsymbol 1 \\ \hline \boldsymbol D-\boldsymbol 1 & \boldsymbol 0 \end{array}\right)\end{split}\]

where \(\boldsymbol A\) is the adjacency matrix, and \(\boldsymbol D\) is the diagonal matrix with the node degrees [krzakala_spectral].

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

[hashimoto]

Hashimoto, Ki-ichiro. “Zeta functions of finite graphs and representations of p-adic groups.” Automorphic forms and geometry of arithmetic varieties. 1989. 211-280. DOI: 10.1016/B978-0-12-330580-0.50015-X [sci-hub, @tor]

[krzakala_spectral]

Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zdeborová, and Pan Zhang, “Spectral redemption in clustering sparse networks”, PNAS 110 (52) 20935-20940, 2013. DOI: 10.1073/pnas.1312486110 [sci-hub, @tor], arXiv: 1306.5550

Examples

>>> g = gt.collection.data["football"]
>>> H = gt.hashimoto(g, operator=True)
>>> N = 2 * g.num_edges()
>>> ew1 = scipy.sparse.linalg.eigs(H, k=N//2, which="LR", return_eigenvectors=False)
>>> ew2 = scipy.sparse.linalg.eigs(H, k=N-N//2, which="SR", return_eigenvectors=False)
>>> ew = np.concatenate((ew1, ew2))

>>> figure(figsize=(8, 4))
<...>
>>> 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("hashimoto-spectrum.svg")

Hashimoto matrix spectrum for the network of American football teams.