-
Notifications
You must be signed in to change notification settings - Fork 0
/
mainFunc.py
159 lines (117 loc) · 5.14 KB
/
mainFunc.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
import snap
import TSSImplementation as tss
import random
import math
import copy
def set_static_threshold(graph, hash_table, value):
for v in graph.Nodes():
hash_table[v.GetId()] = value
return hash_table
def set_degree_based_threshold(graph, hash_table, proportion):
for v in graph.Nodes():
hash_table[v.GetId()] = math.ceil(proportion * v.GetOutDeg()) # e.g. 1/2 * node's degree
return hash_table
def set_edge_probability(graph, hash_table):
random.seed(123)
for edge in graph.Edges():
tupla = edge.GetId()
key = str(tupla[0]) + "-" + str(tupla[1])
hash_table[key] = random.random()
return hash_table
def deferred_decision(graph, probability_hash_table):
for edge in graph.Edges():
number_generated = random.random()
tupla = edge.GetId()
key = str(tupla[0]) + "-" + str(tupla[1])
#print("generated: " + str(number_generated) + " - compared to " + str(probability_hash_table[key]))
if number_generated < probability_hash_table[key]: # If random number generated is less than edge activation probability
#print("deleted edge (" + str(tupla[0]) + ", " + str(tupla[1]) + ")")
graph.DelEdge(tupla[0], tupla[1])
return graph
def exe_static_threshold():
# Load Graph
# noinspection PyUnresolvedReferences
graph = snap.LoadEdgeListStr(snap.TUNGraph, "dataset/twitch/ENGB/musae_ENGB_edges.csv", 0, 1)
# Get the degree of each node by storing them into an hash-table
# noinspection PyUnresolvedReferences
'''
degrees = graph.GetDegSeqV()
for i in range(0, degrees.Len()):
print("Node %s has degree %s" % (i, degrees[i]))
'''
# Set the threshold for each node statically
for i in range(1, 11):
# Creates an hash-table used to store the threshold for each node.
# noinspection PyUnresolvedReferences
t = snap.TIntH()
threshold = i
set_static_threshold(graph, t, threshold)
s = tss.tss(snap.ConvertGraph(type(graph), graph), t)
print("t = " + str(threshold) + " - seed set size = " + str(len(s)))
'''
print("Nodi nel seed set: \n")
for node_id in s:
print(str(node_id) + " ")
'''
def exe_proportional_threshold():
# Load Graph
# noinspection PyUnresolvedReferences
graph = snap.LoadEdgeListStr(snap.TUNGraph, "dataset/twitch/ENGB/musae_ENGB_edges.csv", 0, 1)
for i in range(10, 1, -1): # From 10 to 2
# Set the threshold for each node based on its degree
t = snap.TIntH()
proportion = 1/i
set_degree_based_threshold(graph, t, proportion)
s = tss.tss(snap.ConvertGraph(type(graph), graph), t)
print("proportion = " + str(proportion) + " - seed set size = " + str(len(s)))
def exe_probability_static_threshold():
# Load Graph
# noinspection PyUnresolvedReferences
graph = snap.LoadEdgeListStr(snap.TUNGraph, "dataset/twitch/ENGB/musae_ENGB_edges.csv", 0, 1)
for i in range(1, 11):
# Probability based deferred decision
t = dict() # Dictionary with an integer as key and an integer as value
probability = dict() # Dictionary with a string as key and a float as value
set_edge_probability(graph, probability)
threshold = i
set_static_threshold(graph, t, threshold)
mean = 0
for j in range(1, 11):
t_temp = copy.deepcopy(t)
new_graph = deferred_decision(snap.ConvertGraph(type(graph), graph), probability)
s = tss.tss(new_graph, t)
seed_set_size = len(s)
mean = mean + seed_set_size
mean = mean / 10
print("t = " + str(threshold) + " - mean seed set size = " + str(mean))
def exe_probability_proportional_threshold():
# Load Graph
# noinspection PyUnresolvedReferences
graph = snap.LoadEdgeListStr(snap.TUNGraph, "dataset/twitch/ENGB/musae_ENGB_edges.csv", 0, 1)
for i in range(10, 1, -1): # From 10 to 2
# Set the threshold for each node based on its degree
t = dict() # Dictionary with an integer as key and an integer as value
probability = dict() # Dictionary with a string as key and a float as value
set_edge_probability(graph, probability)
proportion = 1/i
set_degree_based_threshold(graph, t, proportion)
mean = 0
for j in range(1, 11):
t_temp = copy.deepcopy(t)
new_graph = deferred_decision(snap.ConvertGraph(type(graph), graph), probability)
s = tss.tss(new_graph, t_temp)
seed_set_size = len(s)
mean = mean + seed_set_size
mean = mean / 10
print("proportion = " + str(proportion) + " - mean seed set size = " + str(mean))
def test():
graph = snap.LoadEdgeListStr(snap.TUNGraph, "dataset/twitch/test/test.csv", 0, 1)
degrees = graph.GetDegSeqV()
for i in range(0, degrees.Len()):
print("Node %s has degree %s" % (i, degrees[i]))
if __name__ == "__main__":
#exe_static_threshold()
exe_proportional_threshold()
#exe_probability_static_threshold()
#exe_probability_proportional_threshold()
# test()