JOI 2018/2019 春合宿 講義2「大規模グラフアルゴリズム入門」
(個人用のメモです)
大規模グラフとは
プログラミングコンテストでも頻出
世の中もグラフだらけ
ソーシャルネットワーク(Twitter, Facebook など)
人が頂点,友達関係が辺
道路網
交差点同士を結ぶ道路
Web リンク
Web ページを頂点,リンクを辺とみれる
グラフの応用例 経路探索
道路網はグラフとみれる
経路探索は最短路問題に近い
フォロー推奨
ソーシャルネットワークもグラフ構造を持つ
頂点がユーザー,辺がフォロー関係
このグラフ構造から,ユーザーの近さが推定できる
Web 検索
頂点がページ,辺がリンク
Google の PageRank(Web ページの重要性を判断する方法)
大規模ゆえの困難さ
近接中心性の場合
グラフ上の頂点がどれぐらい重要か
ある頂点から他の全ちょうてんの距離の和の逆数であらわす
u を固定すれば BFS で O(m)
全て求めるのは O(nm)
現実では?
LiveJournal(ソーシャルネットワーク)では n = 4847571, m = 68993773
Facebook では n = 13.9 億,m = 4000 億
アルゴリズムの改善
無理っぽいことが知られている
そんなアルゴリズムがあると充足可能性問題に関する強指数時間仮説を否定することになる
現実的なアプローチ
厳密解をあきらめてそれに近い,近そうな値で代用する
グラフの性質を生かし,枝刈りなどで高速化
大規模グラフの性質
m << n^2
各人が 10 億人と知り合いなんかあり得ない
直径が小さいことが多い
数人巡ればほとんどの人に廻れる
ソーシャルネットワークに顕著
中心性
グラフ上で重要な頂点を見つけたい
Web 検索,店舗の出店計画(コンビニなど)
各頂点がどれぐらい重要かを数値的に評価する指標
近接中心性,調和中心性,媒介中心性,PageRank,Katz 中心性など
近接中心性
平均的に他の頂点まで近いと重要ぽい
ランダムサンプリング
Q. 100000 個の数の平均値を推定してください
A. ランダムに何個か選んで平均値を取る
これで得られる平均値の期待値は真の平均値に等しい(不偏推定量)
選ぶ個数を増やすと,真の平均値に近い値を得やすくなる
S(u) := u とほかの頂点との距離の和
近接中心性と大小が反転するだけ
少数の v から S(u) を推定
v_1, v_2, ... , v_k をランダムに選び,それぞれを計算
ランダムサンプリングの限界
以上には慣れた点があると分散が大きくなる
2014 年:枢軸法 ランダムに選んだ中で最も近い点での S をそのまま使用
2017 年:枢軸誘導推定 [Murai] ランダムサンプリングと枢軸法を組み合わせた応用
枢軸法との違い
ランダムサンプリングで枢軸法を修正
実際の S と枢軸法での S の差をサンプリングで修正
なぜうまくいくか
三角不等式より,各頂点との差が u と近い頂点との距離に抑えられる
近い頂点が u に近ければ S の分散も必ず小さい
近接中心性が大きいもの k 個の頂点を厳密に求めたい
ヒューリスティックなアプローチ
枝刈り
各頂点 u に対し,S(u) の下界を管理
S が小さい順に頂点を見ていく
どうやって下界を計算するか
ある頂点から BFS をする
距離 i の頂点数を n とすると,距離 i の頂点に対する S の下界は Σj (n * |i - j|)
O(n + m + r^2)(r は直径)
実は r^2 はいらない
2頂点を起点にして考えても OK
Neighborhood-based
まず木で考える
s から距離 k の頂点数を求める
一般のグラフ
大きく求まってしまう
媒介中心性
s - t 間の最短炉のうち,v を通る最短路の数の s, t についての和
グラフ上の辺に沿った通信を考える
多くの最短路に現れる頂点は多くの通信を媒介していて重要と言える
v が s - t 最短路上にあれば,(s - v の最短路の数)*(v - t の最短路の数)で求まる
実は O(nm) で出来る
Brandes のアルゴリズム
s を固定したときの和を全ての v に対して O(m) で求める
s - v - t という最短路が v の前に通る頂点 u の場合は t によらず s - u 最短路の数が比例する
まず s からの最短路 DAG を求める
s から遠い頂点からその頂点を t としたときの寄与の和を求める
Page らによって 90 年代に提案
ちょうてんの重要性の指標だが,ある頂点から見た相対的な重要性の評価も可能
α : dumping factor 0.85 ぐらい
π : 初期確率分布
頂点 v の PageRank PR(v) は n 個の連立方程式になっていて,解くのに O(n^3) かかる.
起点 u をランダムに選ぶ
確率 1 - α で今の頂点に止まり,α でその頂点から出ている辺を 1 つランダムに選んで移動する
PR(v) は v で停止する確率に等しい
l 回の移動後に停止せず v にいる確率を確率 DP で求める
l を十分大きくすればちょうど l 回目に止まる確率は真の PR(v) に近づく
O(ml) で PR(v) を近似可能
Personalized PageRank (PPR)
π(s) = 1, π(それ以外の頂点) = 0 とすれば s から見た相対的な重要度を評価できる
s からランダムウォークを始めて t で止まる確率が PPR(s, t)
なので, s から大量にランダムウォークをすれば近似できる
Push アルゴリズム
さっきの DP では 0 あるいは小さな値が多発し,効率がよくない
ここでは,パスの長さを全体で一気に 1 増やすのではなく,少しずつ増やしていく
BiPPR
モンテカルロ法と Backward Push を組み合わせる
乱択データ構造 HyperLogLog
集合中の異なる要素数を推定
集合要素数推定
Q. 各頂点に対しそこから距離 l 以下の頂点はいくつか
l - 1 の距離である頂点に足せばよいか?→ 不正解
数を足し上げるだけではだめだが,代わりに和集合を考えると正しい
和集合・要素数を高速に計算できるデータ構造が欲しい
長さ m(2のべき乗)の - inf で初期化された配列からなる
集合の各要素 v に対して 0 から m - 1 の値を取る乱数 j(v),確率 2^(-i) で値 i を取る乱数 r(v) を定めておく
M_j(v) ← max(M_j(v), r(v)) で追加できる
各頂点に HyperLogLog を持たせると出来る