graph_tool.spectral - Spectral properties

Summary

adjacency	Return the adjacency matrix of the graph.
laplacian	Return the Laplacian matrix of the graph.
incidence	Return the incidence matrix of the graph.

Contents

graph_tool.spectral.adjacency(g, weight=None, index=None)

Return the adjacency matrix of the graph.

Parameters :

g : Graph

Graph to be used.

weight : PropertyMap (optional, default: True)

Edge property map with the edge weights.

index : PropertyMap (optional, default: None)

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

Returns :

a : csr_matrix

The (sparse) adjacency matrix.

Notes

The adjacency matrix is defined as

\[\begin{split}a_{i,j} = \begin{cases} 1 & \text{if } v_i \text{ is adjacent to } v_j, \\ 2 & \text{if } i = j, \text{ the graph is undirected and there is a self-loop incident in } v_i, \\ 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.

References

[wikipedia-adjacency]

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

Examples

>>> g = gt.collection.data["polblogs"]
>>> A = gt.adjacency(g)
>>> ew, ev = scipy.linalg.eig(A.todense())

>>> figure(figsize=(8, 2))
<...>
>>> scatter(real(ew), imag(ew), c=abs(ew))
<...>
>>> xlabel(r"$\operatorname{Re}(\lambda)$")
<...>
>>> ylabel(r"$\operatorname{Im}(\lambda)$")
<...>
>>> tight_layout()
>>> savefig("adjacency-spectrum.pdf")

Adjacency matrix spectrum for the political blog network.

graph_tool.spectral.laplacian(g, deg='total', normalized=False, weight=None, index=None)

Return the Laplacian matrix of the graph.

Parameters :

g : Graph

Graph to be used.

deg : str (optional, default: “total”)

Degree to be used, in case of a directed graph.

normalized : bool (optional, default: False)

Whether to compute the normalized Laplacian.

weight : PropertyMap (optional, default: True)

Edge property map with the edge weights.

index : PropertyMap (optional, default: None)

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

Returns :

l : csr_matrix

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 } v_i \text{ is adjacent to } v_j \\ 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\). 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 } v_i \text{ is adjacent to } v_j \\ 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_{ij}w_{ij}\) if deg=="out" or \(\Gamma(v_i)=\sum_j A_{ji}w_{ji}\) deg=="in".

References

[wikipedia-laplacian]

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

Examples

>>> g = gt.collection.data["polblogs"]
>>> L = gt.laplacian(g)
>>> ew, ev = scipy.linalg.eig(L.todense())

>>> figure(figsize=(8, 2))
<...>
>>> scatter(real(ew), imag(ew), c=abs(ew))
<...>
>>> xlabel(r"$\operatorname{Re}(\lambda)$")
<...>
>>> ylabel(r"$\operatorname{Im}(\lambda)$")
<...>
>>> tight_layout()
>>> savefig("laplacian-spectrum.pdf")

Laplacian matrix spectrum for the political blog network.

>>> L = gt.laplacian(g, normalized=True)
>>> ew, ev = scipy.linalg.eig(L.todense())

>>> figure(figsize=(8, 2))
<...>
>>> scatter(real(ew), imag(ew), c=abs(ew))
<...>
>>> xlabel(r"$\operatorname{Re}(\lambda)$")
<...>
>>> ylabel(r"$\operatorname{Im}(\lambda)$")
<...>
>>> tight_layout()
>>> savefig("norm-laplacian-spectrum.pdf")

Normalized Laplacian matrix spectrum for the political blog network.

graph_tool.spectral.incidence(g, vindex=None, eindex=None)

Return the incidence matrix of the graph.

Parameters :

g : Graph

Graph to be used.

vindex : PropertyMap (optional, default: None)

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

eindex : PropertyMap (optional, default: None)

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

Returns :

a : csr_matrix

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}\]

References

[wikipedia-incidence]

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

Examples

>>> g = gt.random_graph(100, lambda: (2,2))
>>> m = gt.incidence(g)
>>> print(m.todense())
[[-1. -1.  0. ...,  0.  0.  0.]
 [ 0.  0.  0. ...,  0.  0.  0.]
 [ 0.  0.  0. ...,  0.  0.  0.]
 ..., 
 [ 0.  0. -1. ...,  0.  0.  0.]
 [ 0.  0.  0. ...,  0.  0.  0.]
 [ 0.  0.  0. ...,  1.  0.  0.]]