Community Label Propagation Iteration

Problem

Run synchronous label propagation to convergence on an undirected graph.

Each node starts with its own index as its label. In every round each node adopts the most frequent label among its neighbors (ties go to the smallest label), isolated nodes keep their label, and all nodes update at once. Repeat until labels stop changing or 100 rounds pass, and return the final labels. edges is a list of [u, v] pairs.

Hint

Synchronous updates can oscillate; the round cap keeps the procedure deterministic.

Test cases

case 1

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

expected: [0,0,0,2,2,2]

case 2

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

expected: [0,1,0,1]

case 3

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

expected: [0,1,1,1]

case 4

in: [3,[]]

expected: [0,1,2]

case 5

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

expected: [0,0,0,0]

Starter codePython

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

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