constant_potts_model

constant_potts_model(G, communities, weight, node_weight, resolution)

Computes the Constant Potts Model, which is a measure of quality of a partition. This is defined in [1] as

\[Q = \sum_{C \in P} E(C,C) - \gamma n_C^2\]

Where

E(C,C) is the sum of all edge weights within the community C, n_C is the sum of the weights of the nodes in C. gamma is the resolution parameter. See Notes below for more more detail on resolution parameter.

The Constant Potts Model is similar to modularity, but overcomes the so-called resolution limit problem when used in community detection algorithms like leiden and louvain.

The Constant Potts Model is used by default in the leiden community detection algorithm

Parameters:

GNetworkX Graph

communitieslist or iterable of sets of nodes

These node sets must represent a partition of G’s nodes.

weightstring or None, optional

The edge attribute that holds the numerical value used as a weight. If None or an edge does not have that attribute, then that edge has weight 1.

node_weightstring or None, optional

The node attribute that holds the numerical value used as a weight. If None or an edge does not have tha attribute, then the node is treated as having weight 1

resolutionfloat

For smaller resolution values, the constant_potts_model will be maximised by a partition consisting of larger communities; for larger resolution values constant_potts_model will be maximised for smaller communities.

Returns:

Qfloat

The Constant Potts Model value of the partition.

Notes

The interpretation of the resolution parameter gamma is explained as follows in page 3 of [1]:

[The Constant Potts Model] tries to maximize the number of internal edges while at the same time keeping relatively small communities.

[The resolution, gamma] balances these two imperatives. In fact, the parameter gamma acts as the inner and outer edge density threshold. That is, suppose there is a community [C] with [E(C, C)] edges and [n_C] nodes. Then it is better to split it into two communities r and s whenever

\[\frac{[E(r,s)]}{2 n_r n_s} < \gamma\]

where [E(r,s)] is the number [or weighted sum] of links between community r and s. This ratio is exactly the density of links between community r and s. So, the link density between communities should be lower than gamma, while the link density within communities should be higher than gamma.

References

[1] (1,2)

V.A. Traag, P. Van Dooren, Y. Nesterov “Narrow scope for resolution-limit-free community detection” <https://arxiv.org/abs/1104.3083>