VLDB'16 論文採択：媒介中心性の動的更新
国際学会 VLDB 2016 に論文が採択されました．VLDB (International Conference on Very Large Data Bases) は SIGMOD と並ぶデータベース分野の最も有名な学会です．学会は来年 9 月にインドのニューデリーです．
今回の論文は "Fully Dynamic Betweenness Centrality Maintenance on Massive Networks" というタイトルで，東大今井研の林くん（主著者），NII の吉田さんとの共著です．我々は DEIM 2015 にて「動的なネットワークにおける媒介中心性の高速計算手法」というタイトルの発表をしており，優秀論文賞を頂くことができました．今回の論文はその論文の続きに相当しますが，いくつかのアイディアの追加により更に大幅に性能が向上しています．
媒介中心性とは？
中心性 (centrality) とは，グラフ上の頂点の重要さを測定する指標のことです．媒介中心性 (betweenness centrality) は最も人気のある中心性の 1 つで，ネットワーク解析を扱う書籍には必ず取り上げられており，実際の解析を行う方々からお話を伺っても，よく話に上がります．コミュニティ検出アルゴリズムの定番である Girvan-Newman アルゴリズムも媒介中心性に基いています．
媒介中心性は，全頂点対の最短経路が通る割合として定義されます（より詳しくは Wikipedia などをご覧下さい）．感覚的には，物や情報が「どのぐらいその頂点を通過したいか」で重要度を表す，という気持ちだと思います．実際に実データに適用した際の結果は確かになかなか興味深くて，例えば人間関係のグラフでは，単に友人が多いといよりも，多数のコミュニティに所属するような人物が浮き上がってきます．
媒介中心性に対するアルゴリズム
媒介中心性の厳密な値の計算は，Brandes のアルゴリズムにより O(頂点数 * 枝数) 時間で行うことができ，計算量の意味では，これ以上高速なアルゴリズムは知られていません．（ちなみに，Brandes のアルゴリズムは巧妙な動的計画法に基づく面白いアルゴリズムなので是非調べてみて下さい．）
Brandes のアルゴリズムは，残念ながら，百万頂点を軽く超える現在の大規模なグラフに適用することは困難な計算量を持っています．そこで，大規模グラフでも媒介中心性を使えるようにするため，近年，推定値を高速に計算するアルゴリズムがとても良く研究されてきています．
本論文：動的ネットワークにおける媒介中心性の更新
本論文で扱うのは，動的なグラフにおいて，各頂点の媒介中心性の推定値を更新し続けるという問題です．それを実現する一番単純な方法は，グラフが更新されるたびに，既存の手法で 1 から計算し直す方法ですが，毎回とても時間がかかってしまいます．そこで，グラフに対して付加的なデータ構造を管理しておくことにより，瞬時に媒介中心性の推定値を更新する，というのが本論文で扱うアプローチです．
基本的な考え方としては，グラフの頂点対を幾つかサンプリングし，それらの間の最短経路の DAG による表現を管理します．我々はこれを Hypergraph Sketch と呼んでいます．頂点の追加・削除の際には，一定確率で，偏らせた確率分布を用いてサンプリングを再度行うことにより，サンプルを保ちます．辺の追加・削除の際には，各最短路 DAG を必要に応じて更新します．ただし，最短路 DAG の更新は，それだけを持っている状態では効率的に行うのは難しいです．そこで，両側幅優先探索の途中状態をデータ構造化した Two-Ball Index というデータ構造を別途保っておくことにより，更新が必要な箇所を高速に特定できるようにします．しかし，このデータ構造を用いても，到達不能な頂点対が一定数存在する場合には，とても大きな範囲を無駄に探索することになり性能が著しく低下してしまいます．そこで，大まかに到達可能性を判定できるデータ構造も新たに導入し，それらを組み合わせることにより無駄な探索を抑えています（我々はこれを Special-Purpose Reachability Index と呼んでいます）．
我々の実験では，これらのパーツを組み合わせたデータ構造は数十億辺からなるソーシャルグラフやウェブグラフにおいても十分高速に自身のデータ構造と媒介中心性の推定値を更新できました（ただし，性能は要求する精度によります）．
感想など
今回作ったデータ構造は，自分の最短経路への愛情をちょっと発揮できた気がして気に入ってます．上述の 3 つのデータ構造は，3 つとも最短路木や最短路 DAG 及びその一部分（＋それぞれの付加情報）になってます．最短経路の塊みたいなデータ構造です．
