Modularity Delta on Community Merge

Problem

Compute the modularity change caused by merging two communities.

With m edges, merging A and B changes modularity by e_AB / m - (d_A * d_B) / (2 * m^2), where e_AB counts edges between the communities and d_A, d_B sum degrees inside each. edges is a list of [u, v] pairs and community maps nodes to community ids. Return the float delta, or 0.0 when m is zero or a equals b.

Hint

Internal edges reward the merge while the degree product penalizes it.

Test cases

case 1

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

expected: 0.2222222222222222

case 2

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

expected: -0.5

case 3

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

expected: 0.2222222222222222

case 4

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

expected: 0

case 5

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

expected: 0

Starter codePython

def modularity_delta_merge(n, edges, community, a, b):
    # Your code here
    pass

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