2

誰かが私を何らかの固有ベクトル中心性擬似コード、またはアルゴリズム（ソーシャルネットワーク分析用）の方向に向けることができるかどうか疑問に思いました。私はすでにウィキペディアとグーグルでいくつかの情報を探し回っていますが、一般化されたアルゴリズムや擬似コードの説明が見つかりません。

ありがとう！

4

2 に答える 2

9

グラフGの頂点vの固有ベクトル中心性は、Gの隣接行列Aの支配的な固有ベクトルのv番目のエントリであるように見えます。その固有ベクトルのエントリの合計によってスケーリングされます。

厳密に正のベクトルから始まるべき乗法は、Aの支配的な固有ベクトルになる傾向があります。

べき乗法が実行する必要がある唯一の操作は、Aにベクトルを繰り返し乗算することであることに注意してください。これは簡単です。Avのi番目のエントリは、頂点iが接続されている頂点jに対応するvのエントリの合計です。

べき乗法の収束率は、絶対値が2番目に大きい固有値に対する最大の固有値の比率で線形です。つまり、最大の固有値がlambda maxであり、絶対値で2番目に大きい固有値がlambda 2の場合、固有値推定の誤差はlambda max / | lambda2|の係数で減少します。

実際に発生するグラフ（たとえば、ソーシャルネットワークグラフ）は、通常、ラムダ最大値とラムダ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 に答える