Hadoop performing matrix vector multiplication several times

Question

I'm trying to implement Eigenvector centrality in Hadoop, where we have an iteration as follows (r is a vector and A is a matrix):

r_i+1 = A*r_i
r_i+1 = r_i+1/||r_i+1||

Where || denotes the norm of the vector. A is in a .txt file and r is a vector, initialised to [1 1 1 1 ...] with size n compatible with A. I believe that since I need r_i to compute r_(i+1) I cannot parallelise the loop, but I can parallelise the computation itself. I am not sure on how do that though. My initial idea would be to:

• Have the vector initialised as a global variable
• At the map stage, where j is an index on the components, compute r[j]*A[j,:] that is, the value at jth position of r times the row. This would result in a new row, with multiple values and all with the same key (j).
• At the reduce stage, add together all of the values of the key j for each key. This will be equivalent to the new vector r (before normalisation).
• Normalise the vector manually in the main function and redo the process.

However, I have a few problems with this idea: Using a global variable for the vector for instance, as first: I don't know whether this is reasonable or not from a performance standpoint, and second: I don't know how I would do to update the vector with the results from the reduce stage.

Another problem I see is I don't know how to run this repeatedly. I am doing an implementation in Java, so I have a Mapper class and a Reducer class, I call the jobs in the main function, but can I make it an iteration?

Answer 1

I believe that this provides a nice example that is appliacable to you as well.

Your map step can compute every element r_(t + 1)[i] = A[i, :] * r_(t) / ||r_(t)||, then just print it so the reducer can grab it.

Your reduce step can just grab the input, and assemble the final vector.