CommunityDetectionCodes/Prensentation/algorithms/dynamics/label_propagation_yche.py at master · RapidsAtHKUST/CommunityDetectionCodes · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
import networkx as nx
import random

if __name__ == '__main__':
    g = nx.read_edgelist('example_edge_list.txt', nodetype=int)


    def get_rand_element(l):
        if l:
            return l[random.randint(0, len(l) - 1)]
        else:
            return None


    def reverse_dict(original_dict):
        reversed_dict = {}
        for key, val in original_dict.iteritems():
            if val not in reversed_dict:
                reversed_dict[val] = []
            reversed_dict[val].append(key)
        return reversed_dict


    def print_result(graph, label_name):
        print dict(zip(graph.nodes(),
                       map(lambda node: graph.node[node][label_name], graph.nodes())))
        # print ' '.join(map(lambda node: str(node) + ':' + str(graph.node[node][label_name]), graph.nodes()))


    def sync_label_propagation():
        iter_num = 5
        for node in nx.nodes(g):
            g.node[node]['prev'] = node
            g.node[node]['next'] = None

        for i in xrange(iter_num):
            for node in nx.nodes(g):
                label_count_dict = {}

                for neighbor in nx.neighbors(g, node):
                    if g.node[neighbor]['prev'] not in label_count_dict:
                        label_count_dict[g.node[neighbor]['prev']] = 0
                    label_count_dict[g.node[neighbor]['prev']] += 1

                label_list_dict = reverse_dict(label_count_dict)
                tie_list = label_list_dict[max(list(label_list_dict))]
                # print label_count_dict
                # print tie_list
                g.node[node]['next'] = get_rand_element(tie_list)

            for node in nx.nodes(g):
                g.node[node]['prev'] = g.node[node]['next']

            print_result(g, 'prev')


    def async_label_propagation():
        iter_num = 1
        for node in nx.nodes(g):
            g.node[node]['label'] = node
        for i in xrange(iter_num):
            for node in nx.nodes(g):
                label_count_dict = {}

                for neighbor in nx.neighbors(g, node):
                    if g.node[neighbor]['label'] not in label_count_dict:
                        label_count_dict[g.node[neighbor]['label']] = 0
                    label_count_dict[g.node[neighbor]['label']] += 1

                label_list_dict = reverse_dict(label_count_dict)
                tie_list = label_list_dict[max(list(label_list_dict))]
                # print label_count_dict
                # print tie_list
                g.node[node]['label'] = get_rand_element(tie_list)
                print_result(g, 'label')

            print_result(g, 'label')


    sync_label_propagation()
    # async_label_propagation()