2

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!

4

2 回答 2

9

图 G 中顶点 v 的特征向量中心性似乎是 G 的邻接矩阵 A 的主要特征向量的第 v 个条目，按该特征向量的条目之和缩放。

幂迭代，从任何严格的正向量开始，将趋向于 A 的主要特征向量。

请注意，幂迭代需要做的唯一操作是重复地将 A 乘以一个向量。这很容易做到；Av 的第 i 个条目只是与顶点 i 连接的顶点 j 对应的 v 的条目的总和。

幂次迭代的收敛速度与最大特征值与绝对值第二大的特征值之比呈线性关系。也就是说，如果最大特征值是 lambda max并且第二大绝对值特征值是 lambda 2，则特征值估计中的误差会减少 lambda max / |lambda 2 | 的因子。

实践中出现的图（例如社交网络图）通常在 lambda max和 lambda 2之间有很大的差距，因此幂迭代通常会以可接受的速度快速收敛；在几十次迭代中，几乎不管起点如何，您都会得到一个在 10 -9范围内的特征值估计。

所以，考虑到这个理论，这里有一些伪代码：

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.
于 2013-01-22T02:06:54.040 回答
0

我只知道一点点。这是我在课堂上学到的伪代码。

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
于 2018-07-16T17:00:01.067 回答