Scalable Similarity Estimation in Social Networks: Closeness, Node Labels, ...

Scalable Similarity Estimation in Social Networks: Closeness, Node Labels, and Random Edge Lengths

  • Edith Cohen, Daniel Delling, Fabian Fuchs, Andrew V. Goldberg, Moises Goldszmidt, Renato F. Werneck
  • COSN 2013

背景

  • 直径が小さいグラフで最短路を求める意味はあるのか?
  • そこを考えよう!

概要

  • 最短路ベースの頂点間関連性
  • RWR, SimRank, Resistance dsitance, …
  • この論文
    • 色々提案して、その計算、既存の関連性との比較
    • 神か

ADS

  • π_vu
    • Dijkstra rank
    • vにとってuは何番目に近い?
  • $$ \Phi_{<u}(v) $$
    • vにとってuより近い頂点の集合
  • N_d(v)
    • vから距離d以下の頂点集合
  • All-Distance Sketch (ADS)
    • $$ \mbox{ADS}(v) := \{ (u, d_{uv}) | r(u) < k_r^{\mbox{th}}(\Phi_{<u}(v)) \} $$
  • rで頂点に[0,1]の乱数を割当
  • $$ k_r^{\mbox{th}} $$: rで並べてk番目に小さいやつ
  • ADS(v)って何?
    • vを決めて
    • 距離が小さい順に見ていく
    • 今のところのk番目よりr値が小さかったら集合につっこむ
  • 大体近いのだけど、遠いのも入れておく
  • サイズの期待値: O(klog n)
  • 計算: O(|E|klog n)
  • あとは2-hop
  • boundを出せてるよ!
    • 実際は距離小さいので微妙…

Closeness similarity

  • 距離を使って関連性を作りたい!!
  • 一個目S_{α,β}
    • d(u,i)とd(v,i)のmaxの合計みたいな感じ
  • 二個目J_{α,β}
    • max{d(u,i), d(v,i)}/min{d(u,i), d(v,i)}の合計みたいな感じ
  • α、βはある性質を満たす関数
  • 距離は実際の距離とDijkstra rankの2パターン
    • この使い分けも議論(神か
  • いくつかの指標の一般化に対応している
  • ADSで推定する
    • これも保証有り

Randomized edge length

  • REL distance
    • 辺の重みを指数分布で設定
    • 距離の期待値 = REL
    • 実際にはMoonte-Carlo法
  • 関連性をちゃんと反映されている
    • ロバスト性が測れるから
  • ADSを適用

実験

  • データセット
    • ちょっと大きめ
    • ラベルサイズ小さなあ
  • ground truth: 内容による類似性
    • TF-IDFとか…
  • Query Distributionを考えよう!
    • Uniform
    • Hops: 各距離を一様に
    • Semantic: 類似性の大きさが一様に
  • 比較手法
    • Adamic-Adar, hops, distance, RWR
  • ADSは爆速な割には、他のに追随している

COSN shortest distance similarity

2013-12-12 17:28:41 (Thu)

最終更新:2013年12月12日 17:28