Spanning edge centrality: large-scale computation and applications (WWW '15)

Charalampos Mavroforakis, Richard Garcia-Lebron, Ioannis Koutis and Evimaria Terzi.

概要

Spanning edge centralityは各辺を含んでいる全域木の割合がどのくらいであるかによって定まる辺の重要度の指標。 Spanning edge centralityは実際のネットワークにおける辺の重要度をうまく捉えているようであるにも関わらずあまり関心を集めて来なかった。これはSpanning edge centralityの計算に非常に多くの時間を要していたためだと思われる。この論文では既存の理論的成果をうまく組み合わせることによってほぼ線形時間の乱択近似アルゴリズムを提案する。さらに実際のネットワークにおける実験によってSpanning edge centralityがノイズに対して強い耐性をもち、情報拡散における重要度を良く捉えていることを示す。

アルゴリズム

辺e={u, v}のspanning edge centralityがu-v間のeffective resistanceと等しいことを利用し各辺のspanning edge centralityを線形方程式で記述する。これを解くとspanning edge centralityが求まるのだが厳密にやるとラプラシアン行列の擬似逆行列を求める必要があり頂点数の二乗よりおそくなってまずい。提案手法では、以下のような道具を用いて計算を高速化している。

effective resistanceが各頂点に対応する単位行列をBL^-1 (Bは接続行列)で射影したベクトル同士の距離で表せることに着目。
BL^-1 e_uはm要素からなるベクトルなので、Jonson-inenstrausの補題を使って長さlog(n)のランダムベクトルを用いて低次元のベクトルに射影して距離の計算を高速化。
L^-1を用いてベクトルを射影する必要が出てくるのだが高速なSDDソルバを使えばほぼ線形時間でできる。

実験

辺を何％か増やしたり減らしたりして実験している。数％程度の変化ではspanning edge centralityは対して変化しない。一方betweenness centralityはめちゃくちゃ変わる。また、各centralityの高い辺集合を削除したときにICモデルによる情報拡散を見るとspanning edge centralityの高い辺を削除すると情報拡散が大きく減るということがわかる。betweenness centralityの場合は一番高い奴らよりもそこそこ高い辺を抜いた方が情報拡散が減る。