特征向量中心算法/伪代码

Question

我想知道是否有人可以指向某个特征向量中心伪代码或算法(用于社交网络分析)的方向.我已经在维基百科和谷歌搜索了一些信息,但我找不到任何关于广义算法或伪代码的描述.

谢谢!

Answer 1

图G中的顶点v的特征向量中心性似乎是G的邻接矩阵A的主要特征向量的第v个条目,其由该特征向量的条目的总和来缩放.

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

请注意,权力迭代需要做的唯一操作是将A重复乘以向量.这很容易做到; Av的第i个条目只是对应于顶点i所连接的顶点j的v的条目的总和.

功率迭代的收敛速度在最大特征值与绝对值为第二大的特征值之比是线性的.也就是说,如果最大特征值是λ- _最大和第二大的按绝对值特征值是λ- ₂,在你的特征值估计的误差得到由拉姆达减少系数_最大/|拉姆达₂ |.

中出现在实践中(社交网络的图形,例如)通常具有的λ有较大差距图表_最大值和λ ₂,所以幂迭代通常将收敛可接受快; 在几十次迭代中并且几乎与起点无关,您将得到一个在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.