Louvain Modularity Gain Lite

Problem

Compute the modularity gain of moving a node into each neighboring community, as in the local phase of Louvain.

For community c, gain = k_in / m - (total_degree_c * degree_node) / (2 * m^2), where k_in counts edges from the node to c and total_degree_c sums degrees in c. Consider only communities different from the node's own that contain a neighbor. Return [best_community, best_gain] (largest gain, ties by smallest community), or [-1, 0.0] when none exist. edges is a list of [u, v] pairs.

Hint

Positive gain means the node is more tightly connected to that community than chance predicts.

Test cases

case 1

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

expected: [0,0.5]

case 2

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

expected: [-1,0]

case 3

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

expected: [1,-0.07142857142857142]

case 4

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

expected: [-1,0]

case 5

in: [3,[],[0,0,0],0]

expected: [-1,0]

Starter codePython

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

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