Quick Detection of High-degree Entities in Large Directed Networks

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人の出辺
    • ホントは1回当たり5000本

提案手法

  • 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