modularity

Contents

modularity#

graph_tool.inference.modularity(g, b, gamma=1.0, weight=None)[source]#

Calculate Newman’s (generalized) modularity of a network partition.

Parameters:
gGraph

Graph to be used.

bVertexPropertyMap

Vertex property map with the community partition.

gammafloat (optional, default: 1.)

Resolution parameter.

weightEdgePropertyMap (optional, default: None)

Edge property map with the optional edge weights.

Returns:
Qfloat

Newman’s modularity.

Notes

Given a specific graph partition specified by prop, Newman’s modularity [newman-modularity-2006] is defined as:

\[Q = \frac{1}{2E} \sum_r e_{rr}- \frac{e_r^2}{2E}\]

where \(e_{rs}\) is the number of edges which fall between vertices in communities s and r, or twice that number if \(r = s\), and \(e_r = \sum_s e_{rs}\).

If weights are provided, the matrix \(e_{rs}\) corresponds to the sum of edge weights instead of number of edges, and the value of \(E\) becomes the total sum of edge weights.

References

[newman-modularity-2006]

M. E. J. Newman, “Modularity and community structure in networks”, Proc. Natl. Acad. Sci. USA 103, 8577-8582 (2006), DOI: 10.1073/pnas.0601602103 [sci-hub, @tor], arXiv: physics/0602124

Examples

>>> g = gt.collection.data["football"]
>>> gt.modularity(g, g.vp.value_tsevans)
0.5744393497...