Triadic Measures on Graphs: The Power of Wedge Sampling - todo314 @ ウィキ

Triadic Measures on Graphs: The Power of Wedge Sampling

• C. Seshadhri, Ali Pinar, Tamara G. Kolda
• SDM 2013

概要

• クラスタ係数、次数毎のとか、色々を統一的なフレームワークでもとめる
• wedgeを適当な重みでサンプリングしてtriangleを数えるだけ
• サンプルサイズがグラフのサイズに依存しないところがポイント
• シンプルにboundが出る

提案手法

サンプリングの方法

• 基本的にはwedgeをとってきて、それがtriangleを構成するか？を判定する

global clustering coefficient

• choose(deg(v), 2)に比例する確率でvをとってくる
• vの近傍2頂点u,wをランダムにとってくる
• (u,v,w)は一様ランダムにサンプリングされる
• k = O(ε^{-2}logδ)サンプルで(ε,δ)を保証
  • Hoeffdingからほぼ直接

local clustering coefficient

• vを一様ランダムにサンプリング
• u,wをランダムにとってくる
• まぁ、期待値が一致するのは自明感
• サンプル数も同じ

degree-wise clustering coeffcients and triangle estimates

• degree-wiseは↑のまんま
• T_d: 次数dの頂点の三角形の個数
• 次数dの頂点をサンプリングして、近傍2つまでは同じ
• wedgeがopenか、wedgeの内いくつ次数dか、で4パターン場合分けしてカウント
• これはちょっとだけ巧妙かもしれない

まとめ

• 簡単過ぎワロタ…
• 誰でも思いつきそうだがどういうことなのだろう…

SDM clustering coefficient triangle

2014-01-24 23:41:15 (Fri)