Make It or Break It: Manipulating Robustness in Large Networks（SDM'14）を読んだ

研究室の教授がこれは面白かった！って言ってたからSDM'14に出てた論文

Make It or Break It: Manipulating Robustness in Large Networks

を読んだ（論文はタイトルでググればPDFが出てきます）。

採択論文リストはここから。

概要

ネットワーク（インターネット、ソーシャルネットワークとか）がその機能を果たすには、ある程度強く繋がっていないといけない。

わかり易い例がインターネットのネットワークで、AS（Autonomous system）とかルーターをノード、それらの間の物理的な配線をエッジであらわすと、あるルータからあるルータへの通信は、このネットワーク上でそれらを表すノード同士が連結してないと届かない。

そういう意味で、ネットワーク上のルータが故障したり（ノードの削除）、配線が切れちゃったり（エッジの削除）してもできるだけ多くのノードが連結してる状態であってほしい。多くのノードが非連結の状態になってしまうと、そのネットワークはもはやその機能を果たさなくなってしまう。

この連結度合いみたいなのをネットワーク上でどう測るかっていう指標が、この論文で扱われているロバストネスになる。

ロバストネスが大きいネットワークはちょっとやそっとノードやエッジを削除しても、強く連結したままの状態を保つ（ちなみにもっともロバストネスが大きいネットワークは完全グラフ）。

ロバストネスの指標としてはいろいろなものが提案されているが、この論文ではそれらの中から最も「扱いやすい」ものを決定し、それを最大化もしくは最小化するようなエッジ、ノードの削除、追加方法を決定するアルゴリズムを提案している。

貢献

ネットワークのロバストネスを表す指標を比較し、最良のものを決定
ネットワークのロバストネスを最大化もしくは最小化するような操作（エッジ、ノードの除去、エッジの追加）を構成するアルゴリズムを提案

ロバストネスの指標

ロバストネスの指標は多く提案されているが、そのうちのどれも以下の性質の少なくとも一つを持ってしまう。

グラフにちょっと操作を加えただけで大きく変化してしまう
- 例えば最短経路の長さは少しエッジやノードを削除しただけで大幅に変わってしまうため、最短経路をベースにしたロバストネス指標も大幅な変化をしてしまう。
部分的にしかロバストネスを評価できない
計算が組み合わせ爆発を起こす
連結グラフに対してしか意味を成さない
- 例えばAlgebraic connectivity（ラプラシアンの第二固有値）はグラフが連結していないと常に０になる
操作に対して値が単調に変化しない
- ネットワークに対してエッジを追加すればロバストネスは直感的には大きくなってほしいが、多くの場合常にそうなるわけではない

Natural connectivityは上記の性質を一つも持たないため、一番いい！

Natural connectivityは以下で定義される（ $\lambda_j$ は隣接行列のj番目の固有値）。

$\bar{\lambda} = \ln{\left(\frac{1}{n}\sum_{j=1}^{n} e^{\lambda_j}\right)}$

簡単にいえば隣接行列の固有値の平均値。

これは、閉路の重み付き個数を表す。

なんでこれが閉路の個数を表すのかは論文に説明有り
短い閉路に大きな重み
直感的には任意の二つのノードが短く、多くのパスでつながっているほどネットワークのロバストネスは大きい
閉路に属すエッジを一つ削除しても、まだそれに属すノードは連結のまま

長所

非連結なグラフのロバストネスもうまく測れる
エッジやノードの追加削除に対して単調に増加減少する

問題定義（三つ）

MIOBI-BREAKEDGE
- グラフGと整数kが与えられたとき、natural connectivityを最も減少させるエッジの集合S（|S|=k）を出力
MIOBI-BREAKNODE
- グラフGと整数kが与えられたとき、natural connectivityを最も減少させるノードの集合S（|S|=k）を出力
MIOBI-MAKEEDGE
- グラフGと整数kが与えられたとき、natural connectivityを最も増加させるエッジの集合S（|S|=k）を出力

アルゴリズム

大体一緒だからMIOBI-BREAKEDGEを解くアルゴリズムだけ書く

隣接行列の固有値、固有ベクトルを上からt個計算
あるエッジeに対して、それを削除した時のnatural connectivityの差分を計算
- 差分の計算式がある
全てのエッジに対して２を計算し、最も減少するエッジを削除
１に戻るをk回繰り返す

ポイント

Netural connectivityの差分の計算式がある（厳密）
ただし、Natural connectivityを計算する時に上からt個の固有値しか使ってない（近似）
固有値、固有ベクトルの更新式がある（厳密）
固有値、固有ベクトルの更新には更新前の全ての固有値、固有ベクトルが必要になるが、アルゴリズムでは上からt個しかつかってない（近似）
貪欲法を使っている（貪欲法で厳密解は得られない）

実験

スタンフォードのSNAPのデータを使って実験
- ASデータとGnutellaのデータ
いろんなベースラインと比較したけど、提案手法が最も良かった
- ただし、二番目に良かった手法（次数最大の二つのノード間のエッジを削除）よりはほんの少し良いだけ
グラフのサイズ（エッジの数）に対してもちゃんとスケールした
- ほぼ線形

感想

ものすごく読みやすかった。無駄なことは書かずにエッセンスだけ抜き出して書いてるのがすごく伝わってきてよかった。まぁただ読みやすいのはいいんだけど、定理の証明が「テクニカルレポートに書かれてるからそれを読んでね」ってのは論文的にはどうなのっていうのはあった（よく見るから定番の方法なのかな）。アルゴリズムの説明でどこが近似でどこは厳密なのかがしっかりと書かれててよかった。普通に「この式で計算します」とか言われてもはいそうですかとしかならないけど、「この式で計算すれば厳密な値が求まります。定理はこれです。」と言われるとすごくわかりやすい。まぁ良い論文は大体そうなってるかな。