Revision a7c5c0e2
fiddle/heuristicbetweennesscentrality/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/quynhnguyenms/fiddle/heuristicbetweennesscentrality') 

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