Starting from:
$34.99
Assignment 3: Query-Centric PageRank
Assignment 3: Query-Centric PageRank
PageRank is one of the most well known algorithms in information retrieval. Based on Wikipedia definition, PageRank works by counting the number and quality of links to a page to determine a rough estimate of how important the website is. The underlying assumption is that more important websites are likely to receive more links from other websites. In this assignment, we will investigate a different PageRank algorithm, personalized PageRank, a.k.a. query-centric PageRank, to address user information need when rank the documents or objects. We employ an important domain – Scholarly Search, for this assignment. Task 1: Rank the authors in scholarly database As Google Scholar shows, scholarly search can search and rank the publications based on user queries. For publication search, author ranking can be important (which can be used as a kind of paper prior). For this task, we will use PageRank to calculate the author importance. In the graph we provided, each node is an author, and each edge is a citation, i.e., 𝐴"→𝐴$. When an author accumulate more citations, this author can be more important, and his/her paper can be more important. We, then, will use PageRank to calculate the author importance given a graph. 𝜋𝑣"’(=𝑑 𝑃𝑣𝑢 𝑑𝑖𝑛𝑣 𝑢=1 𝜋𝑖𝑢 +1−𝑑 𝑁 The PageRank theory holds that an imaginary surfer who is randomly clicking on links will eventually stop clicking. The probability, at any step, that the person will continue is a damping factor d. Various studies have tested different damping factors (d), but it is generally assumed that the damping factor will be set around 0.85. The damping factor is subtracted from 1 (and in some variations of the algorithm, the result is divided by the number of documents (N) in the collection) and this term is then added to the product of the damping factor and the sum of the incoming PageRank scores. In this project, each node, e.g., v and u, is an author, and each edge translation probability is calculated by 𝑃𝑣𝑢, which can be used to characterize the probability that author u cite author v in the scholarly database (or to say the chance that author u vote author v is important). For implementation, you can use java JUNG package (http://jung.sourceforge.net/doc/api/index.html) and the PageRank algorithm is hosted in a java class: edu.uci.ics.jung.algorithms.scoring.PageRank<V,E For this task, you will need to submit the java code via: AuthorRank.java And, please list the top 10 ranked authors here:
Task 2: Rank the authors given a query While author ranking in the first task can be potentially important for scholarly search, one additional problem still exists – which author is more important in a domain? Or, given a query, which author(s) can be more important than others? In order to address this problem, we will need to use a different algorithm – PageRank with prior: 𝜋𝑣"’(=1−𝛽𝑏 𝑃𝑣𝑢 𝑑𝑖𝑛𝑣 𝑢=1 𝜋𝑖𝑢 +𝛽𝑏𝑝𝑝𝑟𝑖𝑜𝑟(𝑣) Unlike PageRank, for this formula a number of nodes can be used as the “seeds” on the graph, and they are more important to the target user given an information need (e.g., a query). In above formula, it is characterized as the prior probability 𝑝𝑝𝑟𝑖𝑜𝑟(𝑣). If the node v is not a seed, the prior can be 0. So, for this PageRank function, the importance of the node can be decided by two different components, 1. The random walk probability from node u to v 𝑃𝑣𝑢 :;<= ?( 𝜋𝑖𝑢, and 2. The prior probability 𝑝𝑝𝑟𝑖𝑜𝑟(𝑣). Note that, when a node is not directly or indirectly linked to the seed nodes, this node importance can be 0 or very low (even though this node has a large number of incoming edges). This is significantly different from PageRank. Then, the next question will be how to generate node prior 𝑝𝑝𝑟𝑖𝑜𝑟(𝑣). For this task, we will use Lucene. First, you will need to download the Lucene index we generated. Each Lucene document is a scholarly paper, which has four different fields: Paper ID, Paper Content (text), Author ID (mapping to the node ID on the graph) and Author Name. When user input a query, we will: 1. Send the query to the Lucene index (paper content field) and find the top ranked 300 publications via BM25 algorithm. 2. For each top ranked publication, we will extract the ranking score, and add the ranking score to the target author prior probability. For instance, if an author published 3 papers in the top 300 publication list and the ranking scores are 0.1, 0.05, and 0.05, the author prior can be 0.1+0.05+0.05 = 0.2 3. Then, we need to normalize the author prior. Because, in step 2, the author prior is not probability yet. You can use: 𝑝𝑝𝑟𝑖𝑜𝑟𝑣=𝑝𝑝𝑟𝑖𝑜𝑟(𝑣) 𝑝𝑝𝑟𝑖𝑜𝑟(𝑢) 4. Next, we will rank the authors with the priors generated in step 3. The PageRank with prior algorithm can be found in edu.uci.ics.jung.algorithms.scoring.PageRankWithPriors<V,E For this task, you will need to submit the java code via: AuthorRankwithQuery.java Please list the top 10 ranked authors given query “Data Mining” here: Please list the top 10 ranked authors given query “Information Retrieval” here:
PageRank is one of the most well known algorithms in information retrieval. Based on Wikipedia definition, PageRank works by counting the number and quality of links to a page to determine a rough estimate of how important the website is. The underlying assumption is that more important websites are likely to receive more links from other websites. In this assignment, we will investigate a different PageRank algorithm, personalized PageRank, a.k.a. query-centric PageRank, to address user information need when rank the documents or objects. We employ an important domain – Scholarly Search, for this assignment. Task 1: Rank the authors in scholarly database As Google Scholar shows, scholarly search can search and rank the publications based on user queries. For publication search, author ranking can be important (which can be used as a kind of paper prior). For this task, we will use PageRank to calculate the author importance. In the graph we provided, each node is an author, and each edge is a citation, i.e., 𝐴"→𝐴$. When an author accumulate more citations, this author can be more important, and his/her paper can be more important. We, then, will use PageRank to calculate the author importance given a graph. 𝜋𝑣"’(=𝑑 𝑃𝑣𝑢 𝑑𝑖𝑛𝑣 𝑢=1 𝜋𝑖𝑢 +1−𝑑 𝑁 The PageRank theory holds that an imaginary surfer who is randomly clicking on links will eventually stop clicking. The probability, at any step, that the person will continue is a damping factor d. Various studies have tested different damping factors (d), but it is generally assumed that the damping factor will be set around 0.85. The damping factor is subtracted from 1 (and in some variations of the algorithm, the result is divided by the number of documents (N) in the collection) and this term is then added to the product of the damping factor and the sum of the incoming PageRank scores. In this project, each node, e.g., v and u, is an author, and each edge translation probability is calculated by 𝑃𝑣𝑢, which can be used to characterize the probability that author u cite author v in the scholarly database (or to say the chance that author u vote author v is important). For implementation, you can use java JUNG package (http://jung.sourceforge.net/doc/api/index.html) and the PageRank algorithm is hosted in a java class: edu.uci.ics.jung.algorithms.scoring.PageRank<V,E For this task, you will need to submit the java code via: AuthorRank.java And, please list the top 10 ranked authors here:
Task 2: Rank the authors given a query While author ranking in the first task can be potentially important for scholarly search, one additional problem still exists – which author is more important in a domain? Or, given a query, which author(s) can be more important than others? In order to address this problem, we will need to use a different algorithm – PageRank with prior: 𝜋𝑣"’(=1−𝛽𝑏 𝑃𝑣𝑢 𝑑𝑖𝑛𝑣 𝑢=1 𝜋𝑖𝑢 +𝛽𝑏𝑝𝑝𝑟𝑖𝑜𝑟(𝑣) Unlike PageRank, for this formula a number of nodes can be used as the “seeds” on the graph, and they are more important to the target user given an information need (e.g., a query). In above formula, it is characterized as the prior probability 𝑝𝑝𝑟𝑖𝑜𝑟(𝑣). If the node v is not a seed, the prior can be 0. So, for this PageRank function, the importance of the node can be decided by two different components, 1. The random walk probability from node u to v 𝑃𝑣𝑢 :;<= ?( 𝜋𝑖𝑢, and 2. The prior probability 𝑝𝑝𝑟𝑖𝑜𝑟(𝑣). Note that, when a node is not directly or indirectly linked to the seed nodes, this node importance can be 0 or very low (even though this node has a large number of incoming edges). This is significantly different from PageRank. Then, the next question will be how to generate node prior 𝑝𝑝𝑟𝑖𝑜𝑟(𝑣). For this task, we will use Lucene. First, you will need to download the Lucene index we generated. Each Lucene document is a scholarly paper, which has four different fields: Paper ID, Paper Content (text), Author ID (mapping to the node ID on the graph) and Author Name. When user input a query, we will: 1. Send the query to the Lucene index (paper content field) and find the top ranked 300 publications via BM25 algorithm. 2. For each top ranked publication, we will extract the ranking score, and add the ranking score to the target author prior probability. For instance, if an author published 3 papers in the top 300 publication list and the ranking scores are 0.1, 0.05, and 0.05, the author prior can be 0.1+0.05+0.05 = 0.2 3. Then, we need to normalize the author prior. Because, in step 2, the author prior is not probability yet. You can use: 𝑝𝑝𝑟𝑖𝑜𝑟𝑣=𝑝𝑝𝑟𝑖𝑜𝑟(𝑣) 𝑝𝑝𝑟𝑖𝑜𝑟(𝑢) 4. Next, we will rank the authors with the priors generated in step 3. The PageRank with prior algorithm can be found in edu.uci.ics.jung.algorithms.scoring.PageRankWithPriors<V,E For this task, you will need to submit the java code via: AuthorRankwithQuery.java Please list the top 10 ranked authors given query “Data Mining” here: Please list the top 10 ranked authors given query “Information Retrieval” here:
1 file (61.1MB)
