Random-walk domination in large graphs: problem definitions and fast solutions

Random-walk domination in large graphs: problem definitions and fast solutions

  • Rong-Hua Li, Jeffrey Xu Yu, Xin Huang, Hong Cheng
  • CoRR
    • 多分KDDに出した?

概要

  • 2種類ランダムウォーク支配問題、というものを考えた
  • ソーシャルネットワーク上にアイテムを配置したり、色々なアプリケーションがある
  1. どの頂点からも長さLのランダムウォークによるヒッティングタイムが短い
  2. 長さLのランダムウォークがターゲットノードに到達する確率が高い
  • DPベースの貪欲アルゴリズム
    • ちょっと遅い
  • 評価関数をサンプリングで近似
    • グラフサイズの線形時間で動く

イントロ

  • 応用を力説(イントロの1/2位?)
  1. オンラインソーシャルネット上にアイテムを設置
    • Flickr上では皆ランダムウォークするので、見てほしいものを上手く配置したい
  2. 広告の配置の最適化
  3. 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)

タグ:

CoRR random walk
最終更新:2013年11月17日 22:56