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
|
package edu.brown.cs.student.term.hub;
import edu.brown.cs.student.term.DatabaseQuerier;
import edu.brown.cs.student.term.repl.commands.SetupCommand;
import java.time.Instant;
import java.util.*;
public class HubSearch {
LinkMapper mapper;
Map<Holder, Set<Holder>> followerToLeaderMap = new HashMap<>();
public HubSearch(LinkMapper mapper){
this.mapper = mapper;
}
public Map<Holder, Double> runHubSearch(Instant start, Instant end){
followerToLeaderMap = mapper.makeFollowerLinks(start, end);
int numHolders = followerToLeaderMap.size();
List<Holder> holders = new ArrayList<>(followerToLeaderMap.keySet());
double[] weights = new double[numHolders];
double[] rank = new double[numHolders];
double[] rankPrime = new double[numHolders];
System.err.println(numHolders + "\t" + getDigits(numHolders));
Arrays.fill(rankPrime, 1.0 / numHolders);
double thresh = Math.pow(.1, getDigits(numHolders));
while(!withinDistance(rank, rankPrime, thresh)){
rank = Arrays.copyOf(rankPrime, rankPrime.length);
//calculating hub rank for ith holder
for(int i = 0; i < numHolders; i++){
rankPrime[i] = 0;
//iterating through all holders to calculate hub rank
for(int j = 0; j < numHolders; j++){
double weightIJ = getWeight(holders.get(i), holders.get(j), numHolders);
rankPrime[i] += (weightIJ * rank[j]);
}
}
}
//potentially should change this to be a map from holder id => double?
Map<Holder, Double> hubRankMap = new HashMap<>();
for(int i = 0; i < rankPrime.length; i++){
hubRankMap.put(holders.get(i), rankPrime[i]);
}
return hubRankMap;
}
private double getWeight(Holder leader, Holder follower, int numHolders){
//dampening factor
double damp = 0.15;
/*
In Hub Search
we have the leader and follower if follower links to (follows) leader,
then we want to add some weight from follower to leader,
but should that weight be diluted by the number of people
who followed leader or the number of people who follower followed
--- probably the second option ;( */
Set<Holder> peopleFollowed = followerToLeaderMap.get(follower);
int numberFollowed = peopleFollowed.size();
if(peopleFollowed.contains(leader)){
//constructs the leader to follower links as we go for use later on
leader.addFollower(new Holder(follower.getId(), follower.getName()));
return ((damp / numHolders) + (1 - damp) * (1.0 / numberFollowed));
} else if(numberFollowed == 0){
return ((damp / numHolders) + (1 - damp) * (1.0 / numHolders));
} else {
return (damp / numHolders);
}
}
private boolean withinDistance(double[] r, double[] rPrime, double threshold){
double sum = 0.0;
for(int i = 0; i < r.length; i++){
sum += Math.pow((r[i] - rPrime[i]), 2);
}
System.err.println(sum + "\t" + !(sum <= 0.0000001));
return sum <= 0.001*threshold;
}
private int getDigits(int numFollowers) {
int count = 1;
int temp = numFollowers;
while(temp >= 10) {
count++;
temp /= 10;
System.out.println(temp);
}
return count;
}
}
|
