グラフデータを対象とした重み付きReservoir Sampling

概要

論文の詳細を見る
近年、ソーシャルメディアや SNS の爆発的な普及に伴い、データ解析の対象は従来の単純な表構造データから、人・物・場所といった多様な情報のつながりを表現可能なグラフ構造へとシフトしつつある。グラフの様々な特徴量を得るためにサンプリング手法が重要である。これまでのグラフサンプリング手法では、ランダムウォークがよく用いられ、グラフ構造を探索しながらサンプルを抽出する。しかし、ランダムウォークは、一部の次数の高いノードに偏り、一様なサンプルを抽出することができない問題点がある。本研究では、我々は重み付き Reservoir Sampling アルゴリズム RWW を提案し、高次数ノードへの偏りを解消できるだけではなく、グラフ探索範囲の拡大やグラフの進化に対応できるサンプル抽出を実現する。シミュレーション実験では、評価対象のグラフをランダムグラフとして生成し、提案手法によってサンプルを抽出する。抽出した結果の次数分布を中心に、理想なサンプル結果と比べ、類似度を評価した。
2013-11-19