Quick Detection of High-degree Entities in Large Directed Networks
-
Konstantin Avrachenkov, Nelly Litvak, Liudmila Ostroumova Prokhorenkova, Eugenia Suyargulova
-
ICDM 2014
概要
問題
-
|V|より遥かに小さいAPI呼び出しで人気ユーザを知る
API
-
ユーザを一様ランダムに選ぶ
-
ユーザ1人の入次数
-
ユーザ1人の出辺
提案手法
-
S ← n1頂点をランダムに選ぶ
-
Sの出辺を計算
-
T ← Sから多く指されているtop-n2頂点
-
Tの入次数を計算
-
API呼出回数 = n1+n2
実験
-
n1+n2=1000回のAPI
-
評価指標
-
真のtop-kの内何割見つけられたか
-
n2個から漏れた最上位
-
Ground Truthは非公開…提案手法で50万呼出を採用
解析
-
第一段階で平均次数×n1頂点くらいしか選ばれないので,n2を馬鹿でかくしても意味ない
-
nの大きさと精度
準線形時間
2015/01/08
最終更新:2015年01月08日 17:38