GraphLab Label Propagation

def degree_count_fn (src, edge, dst):
        """
        http://graphlab.com/products/create/docs/generated/graphlab.SGraph.triple_apply.html
        """
        src['degree'] += 1
        dst['degree'] += 1
        return (src, edge, dst)


# In[15]:

#from collections import Counter
#from random import choice

def top_labels(labels):
    from collections import Counter
    c = Counter(labels)
    best = max(c.values())
    top = [label for label, count in c.iteritems()
           if count == best]
    return top

def propagate_labels(src, edge, dst):
    from random import choice, random

    def handle(src, dst):

        # aliases
        src_degree = src["degree"]
        src_neighbor_labels = src["neighbor_labels"]
        dst_label = dst["label"]
        src_neighbor_labels.append(dst_label)

        top_labels_in_src_neighbors = top_labels(src_neighbor_labels)

        if len(src_neighbor_labels) == src_degree:
            if src["stage"] == 1:
                src["label"] = choice(top_labels_in_src_neighbors)
            elif src["stage"] == 2:
                src["done"] = int(src["label"] in top_labels_in_src_neighbors)# and len(top_labels_in_src_neighbors) == 1)

    if random() < 0.5:
        handle(src, dst)
        handle(dst, src)
    else:
        handle(dst, src)
        handle(src, dst)

    return src, edge, dst

import graphlab.aggregate as agg

STAGE_PROPAGATE = 1
STAGE_IS_DONE = 2

def label_graph(g, max_iterations=10000):
    g.vertices['label'] = g.vertices['__id']
    g.vertices['done'] = 0

    #for iteration in xrange(iterations):
    #    print "#", iteration
    for i in xrange(max_iterations):
        g.vertices['neighbor_labels'] = g.vertices.apply(lambda _:[])
        g.vertices['stage'] = STAGE_PROPAGATE
        g =  g.triple_apply(propagate_labels, ['label', 'neighbor_labels'])

        g.vertices['neighbor_labels'] = g.vertices.apply(lambda _:[])
        g.vertices['stage'] = STAGE_IS_DONE
        g =  g.triple_apply(propagate_labels, ['neighbor_labels', 'done'])

        done_count = g.vertices.groupby(key_columns='done', operations={'count': agg.COUNT()})
        if 0 not in done_count["done"]:
            break

    del g.vertices['neighbor_labels']
    del g.vertices['stage']
    del g.vertices['done']
    return g


# In[15]:

sgraph.vertices["degree"] = 0
sgraph_with_degrees = sgraph.triple_apply(degree_count_fn, mutated_fields=['degree'])
labelled_g = label_graph(sgraph_with_degrees)