The math equation of one page j for PageRank is:

rPagej=cPagei IPagejrPageiOPagei+1-cn

where rPagej represents the PageRank value of Pagej, IPagej represents the set of pages pointing into Pagej, OPagei represents the number of outlinks from Pagei,c0,1 represents the decay factor, and n represents the number of web pages in the web graph. The decay factor is usually set to 0.85, i.e., c=0.85.

If we write out the equations for all the nodes, we have a system of linear equations. __________________________ method is usually used to solve the system of linear equations. The time complexity is O(_________________), where represents the number of iterations, and m represents the number of edges in the graph.

To design the MapReduce algorithm for implementing the power iteration method for computing PageRank, we need to first figure out the Mapper and Reducer.

Let us use Oi to represent the set of __________________ from Pagei and Ij to represent the set of ______________________ pointing into Pagej.

Each mapper will read one line of the adjacency list file. That means each mapper knows all the outlinks of a node.

Mapper:

Input	PageRank value rit-1 of node i Outlinks Oi of node i (one row of the adjacency matrix)
Output	For each node jOi, output < __________________ , ___________________ >

Each mapper processes a single node i. Each mapper knows the outlinks of node i. For each out neighbor node jOi, the mapper will output a key-value pair, where the key is the index of node j, and the value is the value rit-11|Oi| .

Reducer:

Input	<_________________ , ____________________________> , where node iIj
Output	< _________________, ____________________________ >, where rjt=____________________________+____________________

Each reducer processes a single node j. During the shuffle processes, all the key-value pairs with the same ________________ will be sent to the same___________________. Therefore, each reducer knows the _____________________ of node j. For each in-neighbor node iIj, the reducer knows the value rit-11|Oi|. The reducer will sum these values together. The reducer will then calculates the value of the PageRank equation rjt=ciIjrit-11|Oi| +1-cn. The reducer will output a key-value pair, where the key is the index of node ___________________, and the value is the value rjt=ciIjrit-11|Oi| +1-cn .

Since the mapper needs to read two files, therefore we use the __________________________ technique to read the PageRank value file, and use the InputFileFormat to read one line in the adjacency list file.

The MapReduce program will repeat this process many times in order to calculate the final PageRank values. After each iteration, the intermediate PageRank values will written into the _______________________. At the beginning of each iteration, the program will read the intermediate PageRank values from the______________________.

Can we use combiner in the program? ______________.

If so, can we use the code of reducer as the combiner? ______________.

If not, please describe the idea of combiner.

Combiner:

Input	<__________________ , a list of __________________> , where node iIj
Output	< ___________________, value_________________________ >, where ________________________=iIj____________________

Do we need to change the code of reducer if we use this combiner? __________________.