Eigenvector Centrality Algorithm/Pseudocode

Question

I was wondering if anybody could point me in the direction of some eigenvector centrality pseudocode, or an algorithm (for social network analysis). I've already bounced around Wikipedia and Googled for some information, but I can't find any description of a generalized algorithm or pseudocode.

Thanks!

Answer 1

The eigenvector centrality of a vertex v in a graph G just seems to be the v'th entry of the dominant eigenvector of G's adjacency matrix A scaled by the sum of the entries of that eigenvector.

The power iteration, starting from any strictly-positive vector, will tend to the dominant eigenvector of A.

Notice that the only operation that power iteration needs to do is multiply A by a vector repeatedly. This is easy to do; the i'th entry of Av is just the sum of the entries of v corresponding to vertices j to which vertex i is connected.

The rate of convergence of power iteration is linear in the ratio of the largest eigenvalue to the eigenvalue whose absolute value is second largest. That is, if the largest eigenvalue is lambda_max and the second-largest-by-absolute-value eigenvalue is lambda₂, the error in your eigenvalue estimate gets reduced by a factor of lambda_max / |lambda₂|.

Graphs that arise in practice (social network graphs, for instance) typically have a wide gap between lambda_max and lambda₂, so power iteration will typically converge acceptably fast; within a few dozen iterations and almost irrespective of the starting point, you will have an eigenvalue estimate that's within 10^-9.

So, with that theory in mind, here's some pseudocode:

Let v = [1, 1, 1, 1, ... 1].
Repeat 100 times {
  Let w = [0, 0, 0, 0, ... 0].
  For each person i in the social network
    For each friend j of i
      Set w[j] = w[j] + v[i].
  Set v = w.
}
Let S be the sum of the entries of v.
Divide each entry of v by S.

Answer 2

I only know a little about it. This is the pseudo code I learned in the class.

input: a diagonalizable matrix A
   output: a scalar number h, which is the greatest(in absolute value) eigenvalue of A, and a nonzero vector v, the corresponding eigenvector of h, such that Av=hv
    begin
        initialization: initialize a vector b0, which may be an approximation to the dominant eigenvector or a random vector, and let k=0
         while k is smaller than the maximum iteration
            calculate bk+1 = A*bk/(|A*bk|)
            set k=k+1
end