modularity_matrix

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