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
|
import networkx as nx
import numpy as np
def icc_cascade(G, p_init):
"""
input: graph with prob as edge attr
returns: 2D boolean matrix with indep. casc.
where 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 - active
cascade = []
while sum(active) and sum(susceptible):
cascade.append(active)
tmp = np.zeros(G.number_of_nodes(), dtype=bool)
for node in np.where(active)[0]:
for edge in G.edges(node, data=True):
tmp[edge[1]] += np.random.rand() < edge[2]["weight"] \
and susceptible[edge[1]]
active = tmp
susceptible = susceptible - active
cascade.append(active)
return cascade
def icc_cascade_2(G, p_init):
"""
input: graph with prob as edge attr
returns: 2D boolean matrix with indep. casc.
where 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 - active
cascade = []
while active.any() and susceptible.any():
cascade.append(active)
active = np.exp(np.dot(G.logmat, active)) \
< np.random.rand(G.number_of_nodes())
active = active & susceptible
susceptible = susceptible - active
return cascade
def test():
"""
unit test
"""
G = nx.erdos_renyi_graph(1000, 1, directed=True)
G.logmat = np.zeros((G.number_of_nodes(), G.number_of_nodes()))
for edge in G.edges(data=True):
edge[2]['weight'] = .3*np.random.rand()
G.logmat[edge[0],edge[1]] = np.log(1 - edge[2]["weight"])
import time
t0 = time.time()
print len(icc_cascade(G, p_init=.1))
t1 = time.time()
print t1 - t0
print len(icc_cascade_2(G, p_init=.1))
print time.time() - t1
if __name__ == "__main__":
test()
|
