Modularity of a Partition

Problem

Compute the modularity of a partition of an undirected graph into communities.

With m edges, community c contributes L_c / m - (d_c / (2m))^2, where L_c is the number of edges inside c and d_c is the sum of degrees of its nodes. Return the sum over communities. edges is a list of [u, v] pairs and community maps each node to a community id.

Hint

Modularity compares internal edge density against what a random graph would produce.

Test cases

case 1

in: [4,[[0,1],[2,3]],[0,0,1,1]]

expected: 0.5

case 2

in: [3,[[0,1],[1,2],[2,0]],[0,0,0]]

expected: 0

case 3

in: [4,[[0,1],[0,2],[0,3]],[0,1,2,3]]

expected: -0.3333333333333333

case 4

in: [4,[[0,1],[1,2],[2,3]],[0,0,1,1]]

expected: 0.16666666666666666

Starter codePython

def modularity(n, edges, community):
    # Your code here
    pass

4 test cases · run your code against them in the editor