Revision a7c5c0e2

View differences:

fiddle/heuristic-betweenness-centrality/centrality_structurally_equivalent.py
1
# Implement the section III in Puzis 2012 paper
2
# Heuristic Betweenness Centrality - Unifying Structurally Equivalent Vertices
3
# Dec 9, 2015
4

  
5
import os
6
import pprint
7
import networkx as nx
8
import betweenness_centrality as centrality
9
import utility
10
from pdb import set_trace as debugger
11

  
12
MAIN_CODE_DIR = os.environ.get('MAIN_CODE_DIR', '/home/quynh/Thesis/quynhnguyen-ms/fiddle/heuristic-betweenness-centrality')
13

  
14

  
15
class CommunicationImportance():
16
    def __init__(self, QG, G):
17
        self.QG = QG
18
        self.G = G
19

  
20
        # Generate empty communication importance matrix
21
        l = len(self.QG)
22
        self.h = [[0 for i in range(l)] for i in range(l)]
23

  
24
        self.compute_paths_between_structurally_equivalent_vertices()
25
        self.compute_paths_between_different_equivalence_classes()
26
        self.compute_paths_between_different_equivalence_classes()
27

  
28
        pp = pprint.PrettyPrinter(indent=4)
29
        pp.pprint(self.h)
30

  
31

  
32
    def get_by_index(self, index_1, index_2):
33
        return self.h[index_1][index_2]
34

  
35
    def update_by_index(self, index_1, index_2, new_value):
36
        self.h[index_1][index_2] = new_value
37

  
38
    def compute_paths_between_structurally_equivalent_vertices(self):
39
        """
40
        Calculates the Eq.4 in [Puzis 2012]
41
        """
42
        for index, node in enumerate(self.QG):
43
            vertex = list(node)[0]
44
            lhs = 2 * self.QG.get_1st_addend(vertex)
45
            rhs = 2 * self.QG.get_2nd_addend(vertex)
46

  
47
            print '%s \t %f \t %f' % (node, lhs, rhs)
48
            communication = lhs + rhs
49

  
50
            self.update_by_index(index, index, communication)
51

  
52
    def compute_paths_between_different_equivalence_classes(self):
53
        """
54
        Calculates the Eq.5 in [Puzis 2012]
55

  
56
        Interclass communication importance
57
        """
58
        l = len(self.QG)
59
        if l <= 1:
60
            return
61

  
62
        for i in range(l - 1):
63
            for j in range(1, l):
64
                if i == j:
65
                    continue
66
                lhs = self.QG.number_of_original_vertices_by_index(i)
67
                rhs = self.QG.number_of_original_vertices_by_index(j)
68

  
69
                communication = lhs * rhs
70

  
71
                self.update_by_index(i, j, communication)
72
                self.update_by_index(j, i, communication)
73

  
74

  
75

  
76
class QuotientGraph(nx.Graph):
77
    """
78
    node, nodes: are used to refer to the contracted nodes in the Quotient Graph
79

  
80
    vertex, vertices: are used to refer to the original vertices/nodes in the Graph.
81
    """
82
    def __init__(self, QG, G = None):
83
        super(QuotientGraph, self).__init__(QG)
84
        self.G = G
85

  
86

  
87
    def index_by_vertex(self, vertex):
88
        """
89
        Returns the index of the nodes in the quotient graph (QG),
90
        when given the original vertex from the original graph G.
91
        """
92
        for index, node in enumerate(self.nodes()):
93
            if vertex in node:
94
                return index
95

  
96
        # TODO: should I raised "Contracted node not found"
97
        return -1
98

  
99
    def get_node(self, index):
100
        if index < self.number_of_nodes() and index >= 0:
101
            return self.nodes()[index]
102
        else:
103
            raise nx.NetworkXError
104

  
105
    def get_node_by_vertex(self, vertex):
106
        return self.get_node(self.index_by_vertex(vertex))
107

  
108
    def number_of_original_vertices(self, node):
109
        """
110
        Returns the number of vertices in the original graph G, when given the
111
        contracted node.
112

  
113
        node: a contracted node from QG.
114
        """
115
        return len(node)
116

  
117
    def number_of_original_vertices_by_index(self, index):
118
        """
119
        Returns the number of nodes/vertices in the original graph G that
120
        was contracted in the QG.
121
        """
122
        node = self.get_node(index)
123
        return self.number_of_original_vertices(node)
124

  
125
    def neighbors_by_vertex(self, vertex):
126
        """
127
        Returns the neighbors in the QG when given the original vertex from the G.
128
        """
129
        node = self.get_node_by_vertex(vertex)
130
        return self.neighbors(node)
131

  
132
    def number_of_original_neighbors_by_vertex(self, vertex):
133
        """
134
        Returns the total number of v's neighbors in the original graph G.
135
        """
136
        neighbors = self.neighbors_by_vertex(vertex)
137
        nn = 0
138
        for neighbor in neighbors:
139
            nn += self.number_of_original_vertices(neighbor)
140
        return nn
141

  
142
    def number_of_original_neighbors_by_node(self, node):
143
        """
144
        Returns the total number of node's neighbors in the original graph G.
145
        """
146
        neighbors = self.neighbors(node)
147
        nn = 0
148
        for neighbor in neighbors:
149
            nn += self.number_of_original_vertices(neighbor)
150
        return nn
151

  
152
    def get_1st_addend(self, vertex):
153
        node = self.get_node_by_vertex(vertex)
154
        size_node = self.number_of_original_vertices(node)
155
        return size_node * (size_node - 1)
156

  
157
    def get_2nd_addend(self, vertex):
158
        """
159
        Returns the result for 2nd addend in Eq. 4 [Puzis 2012]
160
        """
161
        neighbors = self.neighbors_by_vertex(vertex)
162
        total = 0
163
        node = self.get_node_by_vertex(vertex)
164
        for neighbor in neighbors:
165
            size_node = self.number_of_original_vertices(node)
166
            size_neighbor = self.number_of_original_vertices(neighbor)
167

  
168
            total += size_node * size_neighbor * (size_neighbor - 1) * 1.0 / (
169
                self.number_of_original_neighbors_by_vertex(vertex))
170

  
171
        return total
172

  
173
if __name__ == '__main__':
174
    filepath = MAIN_CODE_DIR + '/input/simple.edges'
175
    file_suffix = 'edge_list'
176

  
177
    # Brandes betweenness centrality
178
    # utility.brandes_betweenness_centrality(filepath, file_suffix)
179

  
180
    # Heuristic betweenness centrality
181
    G = nx.read_weighted_edgelist(filepath)
182
    same_neighbors = lambda u, v: (u not in G[v] and v not in G[u]
183
                                and G[u] == G[v])
184

  
185
    QG = QuotientGraph(nx.quotient_graph(G, same_neighbors))
186

  
187
    CI = CommunicationImportance(QG, G)

Also available in: Unified diff