Label Propagation One Step

Problem

Perform one synchronous step of label propagation on an undirected graph.

Each node adopts the most frequent label among its neighbors; ties are broken by the smallest label, and isolated nodes keep their own label. Return the new label list. labels is the initial list and edges is a list of [u, v] pairs.

Hint

All nodes update simultaneously from the labels of the previous round.

Test cases

case 1

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

expected: [1,0,1]

case 2

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

expected: [1,0,0,0]

case 3

in: [[5,7],[[0,1]]]

expected: [7,5]

case 4

in: [[3],[]]

expected: [3]

case 5

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

expected: [1,0,0]

Starter codePython

def label_propagation(labels, edges):
    # Your code here
    pass

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