ScienceClass_Algorithm/simrank.py at master · ArkTicketTech/ScienceClass_Algorithm · GitHub

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
maxs = 0
maxq = (0,0)
st_neighbors = {}
qs_neighbors = {}
st_list = set()
qs_list = set()
st_sim = {}
qs_sim = {}
new_qs_sim = {}
new_st_sim = {}


def initialize():

		global maxs
		global maxq
		global st_neighbors
		global qs_neighbors
		file = open("sample.txt")
		while 1:
			line = file.readline()
			if not line:
				break

			temp = line.split("\t")

			for i,each in enumerate(temp):
					temp[i] = int(temp[i])

			if(not st_neighbors.has_key(temp[0])):
				st_neighbors[temp[0]] = []
			st_sim[(temp[0],temp[0])] = 1

			if(not qs_neighbors.has_key((temp[1],temp[2]))):
				qs_neighbors[(temp[1],temp[2])] = []
			qs_sim[((temp[1],temp[2]),(temp[1],temp[2]))] = 1

			st_neighbors[temp[0]] = st_neighbors[temp[0]] + [(temp[1],temp[2])]
			qs_neighbors[(temp[1],temp[2])] = qs_neighbors[(temp[1],temp[2])] + [temp[0]]

			st_list.add(temp[0])
			qs_list.add((temp[1],temp[2]))

			if(maxs<int(temp[0])): maxs = int(temp[0])
			if(maxq<(int(temp[1]),int(temp[2]))): maxq = (int(temp[1]),int(temp[2]))


def simqueryStudent(s1,s2,Converge):
		if s1 == s2 : return 1;
		tmp = Converge / (len(st_neighbors[s1]) * len(st_neighbors[s2]))

		# print tmp
		# print st_neighbors[s1]
		# print st_neighbors[s2]

		# if(not st_neighbors.has_key(s1) or not st_neighbors.has_key(s2)):
		# 	return 0

		simsum = 0
		for nb1 in st_neighbors[s1]:
				for nb2 in st_neighbors[s2]:
					if qs_sim.has_key((nb1,nb2)):
						simsum = simsum + qs_sim[(nb1,nb2)]


		return tmp * simsum

def simqueryQStep(q1,q2,Converge):
		if q1 == q2 : return 1;
		tmp = Converge / (len(qs_neighbors[q1]) * len(qs_neighbors[q2]))
		simsum = 0

		# print tmp
		# print qs_neighbors[q1]
		# print qs_neighbors[q2]

		# if(not qs_neighbors.has_key(q1) or not qs_neighbors.has_key(q2)):
		# 	return 0

		for nb1 in qs_neighbors[q1]:
				for nb2 in qs_neighbors[q2]:
					if st_sim.has_key((nb1,nb2)):
						simsum = simsum + st_sim[(nb1,nb2)]

		return tmp * simsum

def simrank(C=0.6, times=100):

		global qs_sim
		global st_sim

		for q1 in qs_list:
			for q2 in qs_list:
				if(q1 == q2):
					new_qs_sim[(q1,q2)] = 1
				else:
					new_qs_sim[(q1,q2)] = simqueryQStep(q1,q2,C)

		for s1 in st_list:
			for s2 in st_list:
				if(s1 == s2):
					new_st_sim[(s1,s2)] = 1
				else:
					new_st_sim[(s1,s2)] = simqueryStudent(s1,s2,C)

		# print new_st_sim
		# print new_qs_sim

		qs_sim = new_qs_sim
		st_sim = new_st_sim


# def simqueryQStep():


def main():
	initialize()

	# print qs_neighbors

	# print qs_sim
	# print simqueryStudent(1,2,0.8)
	# print simqueryQStep((1,3),(4,1),0.8)


	# print st_list
	# print qs_list

	simrank()

	print qs_sim
	print st_sim

	# print st_neighbors[1]

	# print len(st_neighbors['1'])
	# print len(qs_neighbors[('4','1')])
	# print maxs
	# print maxq

main()