Eigenvector Centrality Algorithm/Pseudocode
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!
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 lambdamax and the second-largest-by-absolute-value eigenvalue is lambda2, the error in your eigenvalue estimate gets reduced by a factor of lambdamax / |lambda2|.
Graphs that arise in practice (social network graphs, for instance) typically have a wide gap between lambdamax and lambda2, 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.
上一篇: 网格中的自由网络
下一篇: 特征向量中心性算法/伪代码