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
|
import networkx as nx
import numpy as np
import collections
import timeout
#from itertools import izip
from sklearn.preprocessing import normalize
class InfluenceGraph(nx.DiGraph):
"""
networkX graph with mat and logmat attributes
"""
def __init__(self, max_proba=None, min_proba=None, *args, **kwargs):
self.max_proba = max_proba
self.min_proba = min_proba
super(InfluenceGraph, self).__init__(*args, **kwargs)
def erdos_init(self, n, p):
G = nx.erdos_renyi_graph(n, p, directed=True)
self.add_edges_from(G.edges())
def connected_watts_strogatz(self, n, k, p):
"""
n : number of nodes
k : number of nearest neighbor
p : proba of rewiring edge
"""
G = nx.connected_watts_strogatz_graph(n, k, p)
self.add_edges_from(G.edges())
self.add_edges_from([(node_2, node_1) for node_1, node_2 in G.edges()])
def powerlaw_cluster(self, n, m, p, seed=139):
"""
n : number of nodes
m : number of random edges to add for each node
p : proba of adding triangle for each random edge
seed : random number generator
"""
G = nx.powerlaw_cluster_graph(n, m, p, seed)
self.add_edges_from(G.edges())
self.add_edges_from([(node_2, node_1) for node_1, node_2 in G.edges()])
def import_from_file(self, file_name):
"""
Takes a file from the Stanford collection of networks
"""
with open(file_name, 'r') as f:
for edge in f:
if "#" not in edge:
u, v = [int(node) for node in edge.split()]
self.add_edge(u, v)
@property
def mat(self):
if not hasattr(self, '_mat'):
self._mat = self.max_proba * np.random.rand(len(self), len(self)
) * np.asarray(nx.adjacency_matrix(self).todense().T)
return self._mat
@property
def logmat(self):
if not hasattr(self, '_logmat'):
self._logmat = np.log(1 - self.mat)
return self._logmat
class Cascade(list):
"""
Cascade object: list with attributes
"""
def __init__(self, *args, **kwargs):
super(Cascade, self).__init__(*args, **kwargs)
def infection_time(self, node):
"""
Returns lists of infections times for node i in cascade
"""
infected_times = []
for t, infected_set in enumerate(self):
if infected_set[node]:
infected_times.append(t)
if not infected_times:
infected_times.append(None)
return infected_times
def candidate_infectors(self, node):
"""
Returns Counter of nodes infected just before node i was
"""
candidate_infectors = collections.Counter()
for t in self.infection_time(node):
if t: # avoid cases where t=0 or t is None
candidate_infectors.update(np.where(self[t-1])[0])
return candidate_infectors
@timeout.timeout(5)
def icc_cascade(G, p_init):
"""
Returns boolean vectors for one cascade
True means node was active at that time step
p_init: proba that node in seed set
"""
susceptible = np.ones(G.number_of_nodes(), dtype=bool)
active = np.random.rand(G.number_of_nodes()) < p_init
susceptible = susceptible & np.logical_not(active)
cascade = Cascade()
while active.any():
cascade.append(active)
active = np.exp(np.dot(G.logmat, active)) \
< np.random.rand(G.number_of_nodes())
active = active & susceptible
susceptible = susceptible & np.logical_not(active)
if not cascade:
return icc_cascade(G, p_init)
return cascade
def generate_cascades(G, p_init, n_cascades):
"""
returns list of cascades
"""""
return [icc_cascade(G,p_init) for i in range(n_cascades)]
def icc_matrixvector_for_node(cascades, node):
"""
for the ICC model:
Returns M, w in matrix form where rows of M are i = t + k.T
Excludes all (t,k) after node infection time; w = 1_{infected}
"""
#TODO: you need to remove the variable corresponding to the node
#you are solving for!!!!
if node is None:
return np.vstack(cascades), None
else:
w = []
M = []
for cascade in cascades:
t_i = cascade.infection_time(node)[0]
if t_i != 0:
indicator = np.zeros(len(cascade[:t_i]))
if t_i:
indicator[-1] = 1
w.append(indicator)
M.append(np.array(cascade[:t_i]))
if not M:
print("Node {} was never infected at t != 0".format(node))
M = np.vstack(M)
w = np.hstack(w)
return M, w
def normalize_matrix(M):
"""
returns M with normalized (L_1 norm) columns
"""
return normalize(M.astype("float32"), axis=0, norm="l2")
def add_edges_from_proba_vector(G, p_node, node, floor_cstt):
"""
Takes proba vector, node and adds edges to G by flooring very small
probabilities
Also updates G's mat matrix
"""
floor_parent = np.nonzero(p_node*(p_node > floor_cstt))
for parent in floor_parent[0]:
G.add_edge(parent, node)
#TODO: update G's mat matrix
return G
def test():
"""
unit test
"""
G = InfluenceGraph(max_proba = .3)
G.erdos_init(n = 10, p = 1)
import time
t0 = time.time()
A = generate_cascades(G, .1, 2)
M, w = icc_matrixvector_for_node(A, 0)
t1 = time.time()
print(t1 - t0)
if __name__ == "__main__":
test()
|
