Normalized Mutual Information Partitions

Problem

Compare two partitions of the same nodes with normalized mutual information.

Compute NMI = I(A; B) / sqrt(H(A) * H(B)) using natural logarithms, where H is Shannon entropy of the label distribution and I is the mutual information. Return 0.0 when either partition has zero entropy. a and b are label lists of equal length.

Hint

NMI is invariant to relabeling of the communities, unlike node accuracy.

Test cases

case 1

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

expected: 1

case 2

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

expected: 0

case 3

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

expected: 0.6666666666666667

case 4

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

expected: 0.579380164285695

case 5

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

expected: 0

Starter codePython

import math
def normalized_mutual_information(a, b):
    # Your code here
    pass

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