Description

1 General Instructions
• There is no written part in this assignment, your entire grade will be based on your performance in the coding contest. A part of the grade is based on correctness (test cases passed) and the other on efficiency.
• The programming part of this assignment will be hosted on hackerrank
(https://www.hackerrank.com/) as a programming contest. To participate in this contest, please create a hackerrank account with your illinois.edu email id. The contest framework will allow you to verify the correctness of your submission based on a set of sample test cases. We will use additional test cases to grade your submission (hidden test cases will be significantly larger than the samples). Please check the course piazza page for the contest URL. You need to register in the contest to solve the programming question. Remember to use the hackerrank account associated with your Illinois email id.
• The questions are based on the following reference paper .
1
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 presentation and the SimRank wiki ).
• SimRank with the evidence metric : Use two different evidence metrics (Eqn 7.3,
7.4) to alter the similarity scores obtained with SimRank.
2