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) $$
-
N_d(v)
-
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: 内容による類似性
-
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