Random-walk domination in large graphs: problem definitions and fast solutions
-
Rong-Hua Li, Jeffrey Xu Yu, Xin Huang, Hong Cheng
-
CoRR
概要
-
2種類ランダムウォーク支配問題、というものを考えた
-
ソーシャルネットワーク上にアイテムを配置したり、色々なアプリケーションがある
-
どの頂点からも長さLのランダムウォークによるヒッティングタイムが短い
-
長さLのランダムウォークがターゲットノードに到達する確率が高い
-
DPベースの貪欲アルゴリズム
-
評価関数をサンプリングで近似
イントロ
-
オンラインソーシャルネット上にアイテムを設置
-
Flickr上では皆ランダムウォークするので、見てほしいものを上手く配置したい
-
広告の配置の最適化
-
P2Pネットワークの高速化
問題定義
-
前知識
-
G=(V, E): 有向グラフ
-
L: ランダムウォークの長さ
-
T_{uv}^L: 特定のuから始まる長さLのランダムウォークがもらえた時に、最初にvに到達するインデックス(無ければL)
-
h_{uv}^L: E[T_{uv}^L]
-
問題1
-
$$ \max nL - \sum_{u \in V \setminus S}h_{uS}^L $$
-
$$ s.t. |S| \leq k $$
-
nLは定数、後々の近似比の議論のため???
-
問題2
-
$$ \max E[\sum_{u \in V}X_{uS}^L] $$
-
$$ s.t. |S| \leq k $$
-
X_{uS}^Lはuから始まるランダムウォークがSに到達するインディケーター
-
これはinfluence maximizationとは違うんだああああああ!!!!!(力説)
アルゴリズム
-
問題1も問題2も目的関数はmonotoneかつsubmodular
-
汎用的なgreedy algorithmはO(kn)回目的関数を評価する
-
DPベース
-
u∈Sの時を基底として、再帰的に定義できる(超簡単)
-
計算量: O(nmL)
-
全体でO(kn^2mL)でオワコン
-
近似アルゴリズム
-
各uからランダムウォークをしてSに引っかかる時刻とかを求めて平均をとる
-
ちょっと速くなった
-
ちゃんと精度も議論している
-
計算量: O(nRL)
-
全体O(kn^2RL)
-
( ・´ω・`)
-
marginal gainの高速化
-
最初にランダムウォークをしておいて、marginal gainを簡単に計算する
-
SODAのテクニックと多分同じ
-
全体O(kRLn)
実験
-
DPと近似の比較
-
あんまり変わらなかった( ^ω^)
-
出てきた解についてだけなので、あり得る
-
0-originじゃなかった(´・ω・`)
-
実行時間
-
Fig.4 でDPベースが図をはみ出そうでワロタ
-
logスケールにしてくれ~
-
近似は速すぎて見えない
-
Rを変えるとだいたい線形
-
ヒューリスティクスとの比較
-
Degreeとかは悪い
-
実行時間はDegreeが20s…入力だけじゃん
まとめ
-
既にO(kRLn)なので、これより早くするのは…
-
kの部分も暗に早くしてそう、分からんが
-
influence max.と比べるとどうなるんだろう…。
CoRR random walk
2013-11-17 22:56:01 (Sun)
最終更新:2013年11月17日 22:56