-
Notifications
You must be signed in to change notification settings - Fork 1
/
partition_original.py
231 lines (190 loc) · 8.99 KB
/
partition_original.py
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
'''
Created on Aug 30, 2013
@author: Emrah Cem{emrah.cem@utdallas.edu}
'''
import argparse
import os
import shutil
import errno
import subprocess
import networkx as nx
import random
import time
import math
from sampling.sampling_algorithms import *
import analytics
import networkx as nx
from collections import Counter
from math import *
import matplotlib.pyplot as plt
import numpy as np
import DivergenceMetrics2 as dm
import community
__all__=['add_path_to_graph','add_node_to_graph','add_edge_to_graph','generate_edge']
def drop_zeros(a_list):
return [i for i in a_list if i>0]
def log_binning(counter_dict,bin_count=35):
max_x = log10(max(counter_dict.keys()))
max_y = log10(max(counter_dict.values()))
max_base = max([max_x,max_y])
min_x = log10(min(drop_zeros(counter_dict.keys())))
bins = np.logspace(min_x,max_base,num=bin_count)
# Based off of: http://stackoverflow.com/questions/6163334/binning-data-in-python-with-scipy-numpy
bin_means_y = (np.histogram(counter_dict.keys(),bins,weights=counter_dict.values())[0] / np.histogram(counter_dict.keys(),bins)[0])
bin_means_x = (np.histogram(counter_dict.keys(),bins,weights=counter_dict.keys())[0] / np.histogram(counter_dict.keys(),bins)[0])
return bin_means_x,bin_means_y
def handleArgs():
"""Handle command-line input arguments."""
parser = argparse.ArgumentParser(description="Sample graphs.")
parser.add_argument("-n", "--nodes", type=int, required=True, help="the number of nodes", dest="N")
parser.add_argument("-s", "--start", default=1, type=int, help="the file number at which to start, inclusive", dest="start")
parser.add_argument("-e", "--end", default=10, type=int, help="the file number at which to end, inclusive", dest="end")
parser.add_argument("-o", "--output", default="generated_benches/", help="the output path, defaults to 'generated_benches/'", dest="out_directory_stem")
parser.add_argument("-percentages", "--sample_percentage", nargs="+", default=[0.1, 0.3, 0.5, 0.7], help="Sample percentage of the whole graph", dest="percentages")
parser.add_argument("-sac","--sampling_condition", default="", help="choose the sampling algorithm", dest="sampling_condition")
global args
args = parser.parse_args()
def generate_edge(G, with_replacement):
if with_replacement:
while True:
yield random.choice(G.edges())
else:
edge_list=random.sample(G.edges(),G.number_of_edges())#this will shuffle edges
for e in edge_list:
yield e
def add_path_to_graph(G,path):
if len(path)==1:
add_node_to_graph(G,path[0])
else:
G.add_path(path)
for n in path:
G.node[n]['times_selected']=G.node[n].get('times_selected',0)+1
u=path[0]
for v in path[1:]:
G.edge[u][v]['times_selected']=G.edge[u][v].get('times_selected',0)+1
u=v
G.graph['number_of_nodes_repeated']=G.graph.get('number_of_nodes_repeated',0)+len(path)
G.graph['number_of_edges_repeated']=G.graph.get('number_of_edges_repeated',0)+len(path)-1
def add_node_to_graph(G,n):
G.add_node(n)
G.node[n]['times_selected']=G.node[n].get('times_selected',0)+1
G.graph['number_of_nodes_repeated']=G.graph.get('number_of_nodes_repeated',0)+1
def add_edge_to_graph(G,e, add_nodes=True):
G.add_edge(*e)
G.edge[e[0]][e[1]]['times_selected']=G.edge[e[0]][e[1]].get('times_selected',0)+1
if add_nodes:
add_node_to_graph(G, e[0])
add_node_to_graph(G, e[1])
G.graph['number_of_edges_repeated']=G.graph.get('number_of_edges_repeated',0)+1
def createPathIfNeeded(path):
"""Credits to user 'Heikki Toivonen' on SO: http://stackoverflow.com/questions/273192/check-if-a-directory-exists-and-create-it-if-necessary"""
try:
os.makedirs(path)
except OSError as error:
if error.errno != errno.EEXIST:
raise
def maximum_connected_components(H):
"""creat maximum_connected_components"""
while True:
connectedComponents = nx.number_connected_components(H)
print "Num components: "+str(connectedComponents)
if connectedComponents > 1:
print "Taking the highest sub graph"
nbef = len(H.nodes())
print "Nodes before - "+str(len(H.nodes()))
highestCompNodes = 0
for comp in nx.connected_component_subgraphs(H):
compNodes = len(comp.nodes())
if compNodes > highestCompNodes:
highestCompNodes = compNodes
H = comp
print "Nodes after - "+str(len(H.nodes()))
naft = len(H.nodes())
if naft > int(nbef/connectedComponents):
return H
break
else:
print "try again"
#G_ = nx.convert_node_labels_to_integers(G, first_label=start)
continue
else:
return H
break
def removeDuplicateEdges(filename, separator, assume_one_max = False):
"""Given a network file separated by separator, removes edges such that the final network file_name
contains no two edges that connect the same pair of nodes.
Assumes node ids and cluster ids are integers.
If assume_one_max, the function will assume that there are at most two
edges in the original file connecting the same pair of nodes."""
read_file = filename
os.remove("temporary_function_execution.dat")
write_file = "temporary_function_execution.dat"
# assert not os.path.isfile(write_file)
with open(read_file, 'r') as read_f:
with open(write_file, 'wb') as write_f:
redundant_edges = {}
empty_set = set()
for line in read_f:
source, destination = line.split(separator)
source = int(source)
destination = int(destination.rstrip()) # remove newline character and trailing spaces
if not destination in redundant_edges.get(source, empty_set):
write_f.write(str(source) + separator + str(destination) + '\n')
redundant_edges[destination] = redundant_edges.get(destination, empty_set)
redundant_edges[destination].add(source)
empty_set = set() # reverse mutation due to previous line
elif assume_one_max:
redundant_edges[source].remove(destination)
#shutil.move(read_file, read_file + 'a')
shutil.move(write_file, read_file)
def sampleCommunities(sample, clustering_file, write_file, separator):
"""Given a network file separated by separator, removes edges such that the final network file_name
contains no two edges that connect the same pair of nodes.
Assumes node ids and cluster ids are integers.
If assume_one_max, the function will assume that there are at most two
edges in the original file connecting the same pair of nodes."""
sample_nodes=set(sample.nodes())
read_file = clustering_file
#write_file ="sample_"+read_file
#assert not os.path.isfile(write_file)
with open(read_file, 'r') as read_f:
with open(write_file, 'wb') as write_f:
for line in read_f:
node_id, cluster_id = line[:-1].split(separator)
node_id = int(node_id)
if node_id in sample_nodes:
write_f.write(str(node_id) + separator + str(cluster_id) + '\n')
#shutil.move(write_file, read_file)
#if __name__ == "__main__":
# handleArgs()
# createPathIfNeeded(args.out_directory_stem)
# for i in xrange(args.start, args.end + 1):
# Does seed file need to be handled here?
###zjp add sampling stragegy
# sample=induced_random_vertex_sampler(G, sample_size, with_replacement=False)
# fh=open(args.out_directory_stem + 'network_sample_v' + str(i) + '.dat','wb')
# nx.write_edgelist(sample, fh)
# G=nx.read_edgelist(args.out_directory_stem + 'network_v' + str(i) + '.dat', nodetype=int)
# shutil.move(args.bench_directory_stem + flag_file_name, args.out_directory_stem + "flags.dat")
if __name__ == "__main__":
total_snapshots = 10
k = 0
tcomms = [];
while (k < total_snapshots):
edgefile = './original_snapshot/output-prefix.t0000'+ str(k) + '.graph'
fp_edgefile = open(edgefile, 'rb')
sample_=nx.read_edgelist(fp_edgefile, nodetype=int)
fp_edgefile.close()
#partition sample
sample=maximum_connected_components(sample_)
part = community.best_partition(nx.Graph(sample))
for node in part.keys():
line = str(k) + ' ' + str(node) + ' ' + str(part[node]) + '\n'
tcomms.append(line)
k = k + 1
tcommsfile = './tcomms/original_output-prefix.tcomms'
fp_tcommsfile = open(tcommsfile, 'w+')
for line in tcomms:
fp_tcommsfile.write(line)
fp_tcommsfile.close()
print tcommsfile + "completed"