hashimoto#

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

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].

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

[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")

../_images/hashimoto-spectrum.svg — Hashimoto matrix spectrum for the network of American football teams.#

hashimoto

Contents

hashimoto#