エレガントなSciPy ―Pythonによる科学技術計算

226

付録　演習の解答

A.15

　解答：ぶら下がりノードの処理法

以下は「

6.4.1

　演習：ぶら下がりノードの処理法」の解答です。

確率行列を持つには、遷移行列のすべての列の総和が

1

である必要があります。この条件は、

ある生物種が他のどの種にも食べられない場合には、満たされません。この場合、その生物種に対

応する列の要素は、すべてゼロになります。しかし、そのような列のすべてを

1/n

で置き換える

操作は、高コストとなります。

肝心なのは、変換行列と現在の確率ベクトルの乗算に、どの列も同じ量だけ寄与することに気付

くことです。つまり、これらの列を足すと、反復の乗算の結果に

1

つの値が加えられるのです。

どんな値かというと、

1/n

に、ぶら下がりノードに対応する

r

の要素を掛けたものです。このこと

は、ぶら下がりノードに対応する位置の要素の値が

1/n

で、それ以外の要素はゼロであるベクト

ルと、現在の反復のベクトル

r

の内積として表されます。

def power2(Trans, damping=0.85, max_iter=10**5):

n = Trans.shape[0]

dangling = (1/n) * np.ravel(Trans.sum(axis=0) == 0)

r0 = np.full(n, 1/n)

r = r0

for _ in range(max_iter):

rnext = (damping * (Trans @ r + dangling @ r) +

(1 - damping) / n) ...