PageRank
- Uses the PageRank algorithm described in the Google Pregel paper
- Introduces partitioning and collective communication
- Lets the user submit his/her own TextFile to calculate the sites' Pagerank!
Implementation
For detailed questions in terms of implementation have a look at my blog. It describes the algorithm and focuses on the main ideas showing implementation things.
http://codingwiththomas.blogspot.com/2011/04/pagerank-with-apache-hama.html
Usage
hama/bin/hama jar ../hama-0.x.0-examples.jar page <damping factor> <epsilon error> <optional: output path> <optional: input path>
Change "x" to the version you are using!
The output path should never be the root path! It is default on "pagerank/out".
The default parameters are:
0.85 0.001
As you can see 0.85 is the damping factor, that is the probability which a user will "randomly" jump to other sides. See the Random Surfer Model.
0.001 is the convergence error, the error will always be measured after an iteration. It tells how much the pagerank of all sites has changed. If you are setting this to a lower factor, it will take more iterations.
Submit your own Web-graph
You can transform your graph as a adjacency list to fit into the input which Hama is going to parse and calculate the Pagerank.
The file that Hama can successfully parse is a TextFile that has the following layout:
Site1\tSite2\tSite3 Site2\tSite3 Site3
This piece of text will adjacent Site1 to Site2 and Site3, Site2 to Site3 and Site3 is a dangling node. As you can see a site is always on the leftmost side (we call it the key-site), and the outlinks are seperated by tabs (\t) as the following elements.
Make sure that every site's outlink can somewhere be found in the file as a key-site. Otherwise it will result in weird NullPointerExceptions.
A call could look like this:
0.85 0.001 pagerank/out pagerank/in
Make sure that if you provide an in-path, you're setting an outpath, too!
Output
The output is a double value that is between zero and 1.0. Where 1.0 is a very "famous" site.
All pages' rank should sum up to 1.0, otherwise the algorithm is broken.
Sample Adjacencylist File
You can download an adjacencylist Textfile containing 2,442,507 vertices and 32,282,149 edges, including a random web graph based on the URLs of dmoz.org (http://rdf.dmoz.org/). It is arround 680mb large and can be downloaded here:
You can run it with
hama/bin/hama jar ../hama-0.x.0-examples.jar page 0.85 0.001 pagerank/output PATH_TO_YOUR_TXT_FILE
Obviously you have to replace "PATH_TO_YOUR_TXT_FILE" to the path where your downloaded file lies.
Have fun! If you are facing problems, feel free to ask questions on the official mailing list.