FRAUDAR: Bounding Graph Fraud in the Face of Camouflage - todo314 @ ウィキ

FRAUDAR: Bounding Graph Fraud in the Face of Camouflage

• Bryan Hooi, Hyun Ah Song, Alex Beutel, Neil Shah, Kijung Shin, Christos Faloutsos
• KDD 2016

概要

• ベストペーパー
• イカサマな関係を検出
  • Amazonのサクラレビュー
  • Twitterのフォロワーを買って強そうに見せる
• 貢献
  • 疑わしさの評価関数
  • 評価関数のほぼ線形時間の1/2-近似アルゴリズム

定式化

• モデル: ユーザ-オブジェクトの二部グラフ
  • 怪しい連中は集まる。
  • しかし、普通の連中にも繋がりカモフラージュする。
• camouflage-resistant := サクラが無関係(普通の連中への)辺を追加しても変わらない
• 提案疑わしさ指標
  • 重み付き辺密度
  • 辺uvの重み = 1/log(入次数(v)+定数)
    • 入次数(v)が超デカイ: そもそも大人気
    • log: 逆数は極端らしい
• 最密部分グラフとってきまーす！

実験

• 人工
  • 2000+2000頂点に200+200のサクラ＋不正商品追加
  • サクラ一割って多すぎじゃね？
• 実データ
  • Twitter 42M頂点、1.5B辺
  • 良かった

まとめ

• 手法は物凄く単純
  • 密部分グラフが熱い
• 実際に効果があったのが良いのかな

KDD 不正検知 密部分グラフ

2016/12/01