-
Notifications
You must be signed in to change notification settings - Fork 3
/
graph_generators.py
186 lines (147 loc) · 5.84 KB
/
graph_generators.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
import networkx as nx
import numpy as np
import time, copy
from collections import Counter
def generate_initial_graph(n,k,W):
#Graph at time zero
Goriginal=nx.Graph()
for i in range(1,n+1):
Goriginal.add_node(i,group=np.random.choice(range(1,k+1),1),majority=1) #fixing groups
for j in range(1,n+1):
for i in range(1,j):
if np.random.rand() <= W[Goriginal.node[i]['group']-1,Goriginal.node[j]['group']-1]:
Goriginal.add_edge(i,j)
return Goriginal
def generate_minorities(Gcurrent,Gprevious,k,minority_pct_ub,t):
# print('\n\ncurrent time',t)
current_community_sizes = np.zeros(k)
for i in Gcurrent.nodes():
if Gcurrent.node[i]['majority'] == 1:
current_community_sizes[Gcurrent.node[i]['group']-1] += 1
# print('current_community_sizes',current_community_sizes)
minority_counter = np.zeros(k)
nodes = np.random.permutation(Gcurrent.nodes())
for i in nodes:
# print('t',t-1,'i',i,'maj:',Gprevious.node[i]['majority'],'grp:',Gprevious.node[i]['group'][0])
if (Gprevious.node[i]['majority']== 1) and (np.random.rand() < np.random.rand()*minority_pct_ub):
Gprevious.node[i]['majority'] = 0
temp_old_group = Gcurrent.node[i]['group'][0]
# print(temp_old_group,type(temp_old_group))
Gcurrent.node[i]['group'] = np.random.choice(list(range(1,temp_old_group))+list(range(temp_old_group+1,k+1)), 1)
minority_counter[temp_old_group-1] += 1
# print('node ', i, ' changed community from ',temp_old_group,' to ',Gcurrent.node[i]['group'][0],' at time ',t)
if Gprevious.node[i]['majority'] == 0:
Gcurrent.node[i]['majority'] = 0 #if it is a minority, keep it a minority
# print('node ', i, ' has minority status at time ',t-1)
if np.max(minority_counter) >= minority_pct_ub*np.min(current_community_sizes):
break
return Gcurrent,Gprevious
def generate_graph_sequence(params):
'''
Graph at 0 is the single original graph
Graphs at times t-1,...,total_time are the evolved ones
'''
dynamic = params['dynamic']
xi = params['xitrue']
Mu = params['Mutrue']
W = params['Wtrue']
n = params['n']
k = params['k']
total_time = params['total_time']
log_start_time = params['start_time']
flag_adversarial= params['spectral_adversarial']
minority_pct_ub = params['minority_pct_ub']
with_majority_dynamics = params['with_majority_dynamics']
#Create the first graph
st = log_start_time
# print("\tGenerating GT sequence for the", dynamic, "dynamic")
Goriginal = generate_initial_graph(n,k,W)
Wold = copy.deepcopy(W)
#Create the subsequent total_time number of graphs indexed from 1 to total_time
GT = [Goriginal]
for t in range(1,total_time+1): #t = 1,2,...,T
# print('\t\tGraph at snapshot', t, ' time', time.time() - st)
if flag_adversarial is True:
W = 1-W #Adversarial
Gcurrent = nx.Graph()
for node in GT[t-1].nodes(data=True):
Gcurrent.add_node(node[0],group=node[1]['group'],majority=node[1]['majority'])
if dynamic=='bernoulli':
for i in Gcurrent.nodes():
for j in Gcurrent.nodes():
if i < j:
if (i, j) in GT[t - 1].edges():
if np.random.rand() > Mu[Gcurrent.node[i]['group'] - 1, Gcurrent.node[j]['group'] - 1]:
Gcurrent.add_edge(i, j)
else:
if np.random.rand() <= (W[Gcurrent.node[i]['group'] - 1, Gcurrent.node[j]['group'] - 1])*(Mu[Gcurrent.node[i]['group'] - 1, Gcurrent.node[j]['group'] - 1]):
Gcurrent.add_edge(i, j)
elif dynamic=='lazy':
if with_majority_dynamics is True:
Gcurrent,GT[t-1] = generate_minorities(Gcurrent,GT[t-1],k,minority_pct_ub,t)
for i in Gcurrent.nodes():
for j in Gcurrent.nodes():
if i < j:
if np.random.rand() <= xi:
if (i,j) in GT[t-1].edges():
Gcurrent.add_edge(i,j)
else:
if np.random.rand() <= W[Gcurrent.node[i]['group']-1,Gcurrent.node[j]['group']-1]:
Gcurrent.add_edge(i,j)
else:
raise NotImplementedError
GT.append(Gcurrent)
if flag_adversarial is False:
print('\tTime taken for ',dynamic, 'graph sequence generation:', time.time() - st)
else:
print('\tTime taken for ADVERSARIAL ',dynamic, ' dynamic graph sequence generation:', time.time() - st)
return GT
def add_noise(GT,noise_type='random',noise_level=None):
if noise_level is None:
noise_level = 0.8
GTnoisy = []
if noise_type=='random':
for G in GT:
Gnew = G.copy()
for e in G.edges():
if np.random.rand() <= noise_level:
Gnew.remove_edge(*e)
GTnoisy.append(Gnew)
else:
GTnoisy = GT #TBD
return GTnoisy
def graph_stats_fixed_group(params,GT):
nodecounts = []
edgecounts = []
for G in GT:
nodecounts.append(len(G.nodes()))
edgecounts.append(len(G.edges()))
gtrue = {x[0]:x[1]['group'][0] for x in GT[0].nodes(data=True)} #only works for fixed group
community_sizes = Counter([gtrue[i] for i in gtrue])
return {'gtrue':gtrue, 'nodecounts': nodecounts, 'edgecounts': edgecounts, 'community_sizes': community_sizes}
if __name__=='__main__':
np.random.seed(1000)
params = {}
params['n'] = 100 # size of the graph
params['Mutrue'] = np.array([[.4,.6],[.6,.4]])# [bernoulli]
params['Wtrue'] = np.array([[.4,.2],[.2,.4]])
params['k'] = params['Wtrue'].shape[0] # number of communities
params['xitrue'] = .2 # [lazy]
params['start_time'] = time.time()
params['spectral_adversarial'] = False
params['total_time'] = 4 # power of 2, number of additional graph snapshots
params['minority_pct_ub'] = 0.49
params['with_majority_dynamics'] = False
# params['dynamic'] = 'bernoulli'
# GT = generate_graph_sequence(params)
# params['spectral_adversarial'] = True
# GT = generate_graph_sequence(params)
# params['dynamic'] = 'lazy'
# GT = generate_graph_sequence(params)
# params['spectral_adversarial'] = False
# GT = generate_graph_sequence(params)
params['with_majority_dynamics'] = True
params['dynamic'] = 'lazy'
GT = generate_graph_sequence(params)
# params['spectral_adversarial'] = False
# GT = generate_graph_sequence(params)