graph_tool.spectral - Spectral properties

Summary

adjacency	Return the adjacency matrix of the graph.
laplacian	Return the Laplacian (or Bethe Hessian if \(r > 1\)) matrix of the graph.
incidence	Return the incidence matrix of the graph.
transition	Return the transition matrix of the graph.
modularity_matrix	Return the modularity matrix of the graph.
hashimoto	Return the Hashimoto (or non-backtracking) matrix of a graph.
AdjacencyOperator	A scipy.sparse.linalg.LinearOperator representing the adjacency matrix of a graph.
LaplacianOperator	A scipy.sparse.linalg.LinearOperator representing the laplacian matrix of a graph.
IncidenceOperator	A scipy.sparse.linalg.LinearOperator representing the incidence matrix of a graph.
TransitionOperator	A scipy.sparse.linalg.LinearOperator representing the transition matrix of a graph.
HashimotoOperator	A scipy.sparse.linalg.LinearOperator representing the hashimoto matrix of a graph.
CompactHashimotoOperator	A scipy.sparse.linalg.LinearOperator representing the compact hashimoto matrix of a graph.

Contents

graph_tool.spectral.adjacency(g, weight=None, vindex=None, operator=False, csr=True)

Return the adjacency matrix of the graph.

Parameters

gGraph

Graph to be used.

weightEdgePropertyMap (optional, default: None)

Edge property map with the edge weights.

vindexVertexPropertyMap (optional, default: None)

Vertex property map specifying the row/column indexes. 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

Acsr_matrix or AdjacencyOperator

The (sparse) adjacency matrix.

Notes

For undirected graphs, the adjacency matrix is defined as

\[\begin{split}A_{ij} = \begin{cases} 1 & \text{if } (j, i) \in E, \\ 2 & \text{if } i = j \text{ and } (i, i) \in E, \\ 0 & \text{otherwise}, \end{cases}\end{split}\]

where \(E\) is the edge set.

For directed graphs, we have instead simply

\[\begin{split}A_{ij} = \begin{cases} 1 & \text{if } (j, i) \in E, \\ 0 & \text{otherwise}. \end{cases}\end{split}\]

In the case of weighted edges, the entry values are multiplied by the weight of the respective edge.

In the case of networks with parallel edges, the entries in the matrix become simply the edge multiplicities (or twice them for the diagonal, for undirected graphs).

Note

For directed graphs the definition above means that the entry \(A_{ij}\) 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

wikipedia-adjacency

http://en.wikipedia.org/wiki/Adjacency_matrix

Examples

>>> g = gt.collection.data["polblogs"]
>>> A = gt.adjacency(g, operator=True)
>>> N = g.num_vertices()
>>> ew1 = scipy.sparse.linalg.eigs(A, k=N//2, which="LR", return_eigenvectors=False)
>>> ew2 = scipy.sparse.linalg.eigs(A, 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("adjacency-spectrum.svg")

Adjacency matrix spectrum for the political blogs network.

class graph_tool.spectral.AdjacencyOperator(*args, **kwargs)

A scipy.sparse.linalg.LinearOperator representing the adjacency matrix of a graph. See adjacency() for details.

graph_tool.spectral.laplacian(g, deg='out', norm=False, weight=None, r=1, vindex=None, operator=False, csr=True)

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

wikipedia-laplacian

http://en.wikipedia.org/wiki/Laplacian_matrix

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

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

Normalized Laplacian matrix spectrum for the political blogs network.

class graph_tool.spectral.LaplacianOperator(*args, **kwargs)

A scipy.sparse.linalg.LinearOperator representing the laplacian matrix of a graph. See laplacian() for details.

graph_tool.spectral.incidence(g, vindex=None, eindex=None, operator=False, csr=True)

Return the incidence matrix of the graph.

Parameters

gGraph

Graph to be used.

vindexVertexPropertyMap (optional, default: None)

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

eindexEdgePropertyMap (optional, default: None)

Edge property map specifying the column indexes. If not provided, the internal edge 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

acsr_matrix or IncidenceOperator

The (sparse) incidence matrix.

Notes

For undirected graphs, the incidence matrix is defined as

\[\begin{split}b_{i,j} = \begin{cases} 1 & \text{if vertex } v_i \text{and edge } e_j \text{ are incident}, \\ 0 & \text{otherwise} \end{cases}\end{split}\]

For directed graphs, the definition is

\[\begin{split}b_{i,j} = \begin{cases} 1 & \text{if edge } e_j \text{ enters vertex } v_i, \\ -1 & \text{if edge } e_j \text{ leaves vertex } v_i, \\ 0 & \text{otherwise} \end{cases}\end{split}\]

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

wikipedia-incidence

http://en.wikipedia.org/wiki/Incidence_matrix

Examples

>>> g = gt.collection.data["polblogs"]
>>> B = gt.incidence(g, operator=True)
>>> N = g.num_vertices()
>>> s1 = scipy.sparse.linalg.svds(B, k=N//2, which="LM", return_singular_vectors=False)
>>> s2 = scipy.sparse.linalg.svds(B, k=N-N//2, which="SM", return_singular_vectors=False)
>>> s = np.concatenate((s1, s2))
>>> s.sort()

>>> figure(figsize=(8, 2))
<...>
>>> plot(s, "s")
[...]
>>> xlabel(r"$i$")
Text(...)
>>> ylabel(r"$\lambda_i$")
Text(...)
>>> tight_layout()
>>> savefig("polblogs-indidence-svd.svg")

Incidence singular values for the political blogs network.

class graph_tool.spectral.IncidenceOperator(*args, **kwargs)

A scipy.sparse.linalg.LinearOperator representing the incidence matrix of a graph. See incidence() for details.

graph_tool.spectral.transition(g, weight=None, vindex=None, operator=False, csr=True)

Return the transition matrix of the graph.

Parameters

gGraph

Graph to be used.

weightEdgePropertyMap (optional, default: None)

Edge property map with the edge weights.

vindexVertexPropertyMap (optional, default: None)

Vertex property map specifying the row/column indexes. 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

Tcsr_matrix or TransitionOperator

The (sparse) transition matrix.

Notes

The transition matrix is defined as

\[T_{ij} = \frac{A_{ij}}{k_j}\]

where \(k_i = \sum_j A_{ji}\), and \(A_{ij}\) is the adjacency matrix.

In the case of weighted edges, the values of the adjacency matrix are multiplied by the edge weights.

Note

For directed graphs the definition above means that the entry \(T_{ij}\) 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

wikipedia-transition

https://en.wikipedia.org/wiki/Stochastic_matrix

Examples

>>> g = gt.collection.data["polblogs"]
>>> T = gt.transition(g, operator=True)
>>> N = g.num_vertices()
>>> ew1 = scipy.sparse.linalg.eigs(T, k=N//2, which="LR", return_eigenvectors=False)
>>> ew2 = scipy.sparse.linalg.eigs(T, 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("transition-spectrum.svg")

Transition matrix spectrum for the political blogs network.

class graph_tool.spectral.TransitionOperator(*args, **kwargs)

A scipy.sparse.linalg.LinearOperator representing the transition matrix of a graph. See transition() for details.

graph_tool.spectral.modularity_matrix(g, weight=None, vindex=None)

Return the modularity matrix of the graph.

Parameters

gGraph

Graph to be used.

weightEdgePropertyMap (optional, default: None)

Edge property map with the edge weights.

indexVertexPropertyMap (optional, default: None)

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

Returns

BLinearOperator

The (sparse) modularity matrix, represented as a LinearOperator.

Notes

The modularity matrix is defined as

\[B_{ij} = A_{ij} - \frac{k^+_i k^-_j}{2E}\]

where \(k^+_i = \sum_j A_{ji}\), \(k^-_i = \sum_j A_{ij}\), \(2E=\sum_{ij}A_{ij}\) and \(A_{ij}\) is the adjacency matrix.

In the case of weighted edges, the values of the adjacency matrix are multiplied by the edge weights.

References

newman-modularity

M. E. J. Newman, M. Girvan, “Finding and evaluating community structure in networks”, Phys. Rev. E 69, 026113 (2004). DOI: 10.1103/PhysRevE.69.026113 [sci-hub, @tor]

Examples

>>> g = gt.collection.data["polblogs"]
>>> B = gt.modularity_matrix(g)
>>> N = g.num_vertices()
>>> ew1 = scipy.sparse.linalg.eigs(B, k=N//2, which="LR", return_eigenvectors=False)
>>> ew2 = scipy.sparse.linalg.eigs(B, 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(...)
>>> autoscale()
>>> tight_layout()
>>> savefig("modularity-spectrum.svg")

Modularity matrix spectrum for the political blogs network.

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

class graph_tool.spectral.HashimotoOperator(*args, **kwargs)

A scipy.sparse.linalg.LinearOperator representing the hashimoto matrix of a graph. See hashimoto() for details.

class graph_tool.spectral.CompactHashimotoOperator(*args, **kwargs)

A scipy.sparse.linalg.LinearOperator representing the compact hashimoto matrix of a graph. See hashimoto() for details.