Description
2 Programming Question (20 points)
The reference paper first describes conventional SimRank, a method for computing object
similarities in domains with object-object links. Specifically we will be considering Bipartite Simrank with 2 types of objects, users and textual advertisements. Unlike the HITS
algorithm, SimRank computes the most similar entities to a given entity (where the entities
could belong to either type). This enables advertisers to push the most relevant content to a
given user, depending on his/her history and the global click graph obtained from all other
users (which is the bipartite graph we are working with).
• Implement SimRank : Your first task is to implement conventional SimRank (Eqns
4.1 and 4.2 in the reference paper). You are required to use Partial Sum Sharing in
your implementation (refer to this presentation2 and the SimRank wiki3
).
• SimRank with the evidence metric : Use two different evidence metrics (Eqn 7.3,
7.4) to alter the similarity scores obtained with SimRank.
• Weighted SimRank : The previous 2 parts only required using the link structure
between the two types of objects. Now you will use the link weights as well, and
compute Weighted Simrank (which works well when the edges have weights assigned
to them quanitfying how similar a pair of objects are, rather than just a binary label).
Refer to Section 8 in the reference paper for this part.
2http://www.doc.ic.ac.uk/ wyu1/ppt/oral/icde13.pdf
3https://en.wikipedia.org/wiki/SimRank
2