graph_tool.spectral
- Spectral properties¶
Summary¶
Return the adjacency matrix of the graph. |
|
Return the Laplacian (or Bethe Hessian if \(r > 1\)) matrix of the graph. |
|
Return the incidence matrix of the graph. |
|
Return the transition matrix of the graph. |
|
Return the modularity matrix of the graph. |
|
Return the Hashimoto (or non-backtracking) matrix of a graph. |
|
A |
|
A |
|
A |
|
A |
|
A |
|
A |
Contents¶
- graph_tool.spectral.adjacency(g, weight=None, vindex=None, operator=False, csr=True)[source]¶
Return the adjacency matrix of the graph.
- Parameters
- g
Graph
Graph to be used.
- weight
EdgePropertyMap
(optional, default:None
) Edge property map with the edge weights.
- vindex
VertexPropertyMap
(optional, default:None
) Vertex property map specifying the row/column indexes. If not provided, the internal vertex index is used.
- operator
bool
(optional, default:False
) If
True
, ascipy.sparse.linalg.LinearOperator
subclass is returned, instead of a sparse matrix.- csr
bool
(optional, default:True
) If
True
, andoperator
isFalse
, ascipy.sparse.csr_matrix
sparse matrix is returned, otherwise ascipy.sparse.coo_matrix
is returned instead.
- g
- Returns
- A
csr_matrix
orAdjacencyOperator
The (sparse) adjacency matrix.
- A
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 ascipy.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 modulescipy.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
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)[source]¶
A
scipy.sparse.linalg.LinearOperator
representing the adjacency matrix of a graph. Seeadjacency()
for details.
- 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
- g
Graph
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.
- weight
EdgePropertyMap
(optional, default:None
) Edge property map with the edge weights.
- r
double
(optional, default:1.
) Regularization parameter. If \(r > 1\), and
norm
isFalse
, then this corresponds to the Bethe Hessian. (This parameter has an effect only fornorm == False
.)- vindex
VertexPropertyMap
(optional, default:None
) Vertex property map specifying the row/column indexes. If not provided, the internal vertex index is used.
- operator
bool
(optional, default:False
) If
True
, ascipy.sparse.linalg.LinearOperator
subclass is returned, instead of a sparse matrix.- csr
bool
(optional, default:True
) If
True
, andoperator
isFalse
, ascipy.sparse.csr_matrix
sparse matrix is returned, otherwise ascipy.sparse.coo_matrix
is returned instead.
- g
- Returns
- L
csr_matrix
orLaplacianOperator
The (sparse) Laplacian matrix.
- L
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}\) ifdeg=="out"
or \(\Gamma(v_i)=\sum_j A_{ij}w_{ij}\) ifdeg=="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 ascipy.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 modulescipy.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
- 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)[source]¶
A
scipy.sparse.linalg.LinearOperator
representing the laplacian matrix of a graph. Seelaplacian()
for details.
- graph_tool.spectral.incidence(g, vindex=None, eindex=None, operator=False, csr=True)[source]¶
Return the incidence matrix of the graph.
- Parameters
- g
Graph
Graph to be used.
- vindex
VertexPropertyMap
(optional, default:None
) Vertex property map specifying the row indexes. If not provided, the internal vertex index is used.
- eindex
EdgePropertyMap
(optional, default:None
) Edge property map specifying the column indexes. If not provided, the internal edge index is used.
- operator
bool
(optional, default:False
) If
True
, ascipy.sparse.linalg.LinearOperator
subclass is returned, instead of a sparse matrix.- csr
bool
(optional, default:True
) If
True
, andoperator
isFalse
, ascipy.sparse.csr_matrix
sparse matrix is returned, otherwise ascipy.sparse.coo_matrix
is returned instead.
- g
- Returns
- a
csr_matrix
orIncidenceOperator
The (sparse) incidence matrix.
- a
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 ascipy.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 modulescipy.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
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)[source]¶
A
scipy.sparse.linalg.LinearOperator
representing the incidence matrix of a graph. Seeincidence()
for details.
- graph_tool.spectral.transition(g, weight=None, vindex=None, operator=False, csr=True)[source]¶
Return the transition matrix of the graph.
- Parameters
- g
Graph
Graph to be used.
- weight
EdgePropertyMap
(optional, default:None
) Edge property map with the edge weights.
- vindex
VertexPropertyMap
(optional, default:None
) Vertex property map specifying the row/column indexes. If not provided, the internal vertex index is used.
- operator
bool
(optional, default:False
) If
True
, ascipy.sparse.linalg.LinearOperator
subclass is returned, instead of a sparse matrix.- csr
bool
(optional, default:True
) If
True
, andoperator
isFalse
, ascipy.sparse.csr_matrix
sparse matrix is returned, otherwise ascipy.sparse.coo_matrix
is returned instead.
- g
- Returns
- T
csr_matrix
orTransitionOperator
The (sparse) transition matrix.
- T
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 ascipy.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 modulescipy.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
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)[source]¶
A
scipy.sparse.linalg.LinearOperator
representing the transition matrix of a graph. Seetransition()
for details.
- graph_tool.spectral.modularity_matrix(g, weight=None, vindex=None)[source]¶
Return the modularity matrix of the graph.
- Parameters
- g
Graph
Graph to be used.
- weight
EdgePropertyMap
(optional, default:None
) Edge property map with the edge weights.
- index
VertexPropertyMap
(optional, default:None
) Vertex property map specifying the row/column indexes. If not provided, the internal vertex index is used.
- g
- Returns
- B
LinearOperator
The (sparse) modularity matrix, represented as a
LinearOperator
.
- B
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)[source]¶
Return the Hashimoto (or non-backtracking) matrix of a graph.
- Parameters
- g
Graph
Graph to be used.
- index
VertexPropertyMap
(optional, default:None
) Edge property map specifying the row/column indexes. If not provided, the internal edge index is used.
- compact
boolean
(optional, default:False
) If
True
, a compact \(2|V|\times 2|V|\) version of the matrix is returned.- operator
bool
(optional, default:False
) If
True
, ascipy.sparse.linalg.LinearOperator
subclass is returned, instead of a sparse matrix.- csr
bool
(optional, default:True
) If
True
, andoperator
isFalse
, ascipy.sparse.csr_matrix
sparse matrix is returned, otherwise ascipy.sparse.coo_matrix
is returned instead.
- g
- Returns
- H
csr_matrix
orHashimotoOperator
orCompactHashimotoOperator
The (sparse) Hashimoto matrix.
- H
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 ascipy.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 modulescipy.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)[source]¶
A
scipy.sparse.linalg.LinearOperator
representing the hashimoto matrix of a graph. Seehashimoto()
for details.
- class graph_tool.spectral.CompactHashimotoOperator(*args, **kwargs)[source]¶
A
scipy.sparse.linalg.LinearOperator
representing the compact hashimoto matrix of a graph. Seehashimoto()
for details.