Modularity Compare Two Partitions

Problem

Compare the modularity of two partitions of the same undirected graph.

Compute Q = sum over communities of L_c / m - (d_c / (2m))^2, where L_c is the number of internal edges and d_c the total degree. Return [Qa, Qb, better] where better is 0 when Qa is at least Qb and 1 otherwise. edges is a list of [u, v] pairs.

Hint

Higher modularity means communities capture more edges than chance would predict.

Test cases

case 1

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

expected: [0.5,-0.5,0]

case 2

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

expected: [0.16666666666666663,-0.2777777777777778,0]

case 3

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

expected: [0,-0.2222222222222222,0]

Starter codePython

def best_partition(n, edges, part_a, part_b):
    # Your code here
    pass

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