You can use some kind of clustering technique (eg MapReduce), but with this small size of data, you absolutely don't need to use clustering.
With this size of data, you should be able to do it all in memory. Assuming a naive approach:
- 15 mb - Scores from the previous iteration (4,000,000 32 bit floats)
- 15 mb - Scores from the next iteration (4,000,000 32 bit floats)
- 190 mb - Web Graph, assuming a naive graph structure of {num outlinks, outlink 1, outlink 2, ... outlink n} made of 32 bit ints, the graph would fit in 45,000,000 * 32 bits + 4,000,000 * 32 bits,
About 250 mb. The naive approach would look something like this:
N <- size of graph
c <- dampening factor
source_scores[N] <- array of floats, initalised to 1 / N.
dest_scores[N] <- array of floats
repeat until convergence {
for all n up to N { dest_scores[n] = 0 }
for all source,dest links {
dest_scores[dest] += source_scores[source] / num_outlinks of source
}
for all n up to N {
dest_scores[n] = c * dest_scores[n] + (1 - c)/N
}
copy dest_scores to source_scores
}
"But I also have this other graph that WONT fit in memory!"
For in-memory pagerank computation on any size graph, check out this paper. It describes a multi-pass (per single pagerank iteration) technique that allows you to complete pagerank in memory, assuming stream access to the graph and scores from previous iterations.
It requires that you hold the current scores in memory. With 4,000,000 nodes, and assuming 32 bit floats, you're looking at about 15 megabytes of data, plus any array overhead. Your 48 gig server will be fine for this (and it will also be fine for the naive approach, see below).
You'll want a nice small representation of the graph that allows you to read it in in a stream. Since you're using Java, check out the WebGraph compression framework. It is described in detail in this paper. For a graph of 118,000,000 nodes and 1,000,000,000 links they quote a compression of 3.08 bits per link, which is amazing.
Note that there's also a C++ implementation of the WebGraph compression framework also available at that link, but it is MUCH SLOWER, mostly because it's a word for word port of the Java code, rather than a C++ implementation of the compression algorithm.
Using this approach, I had Java code for pagerank that achieved convergence in just under an hour on a single 2007-era desktop with 2 gig of ram, over an 80,000,000 node web graph. The C++ code for the same ran in about two hours (due to the speed differences in the compression implementation).
Let me know if you need any help.