KIWAM_KEN_DIARY

ざっくりメモ：Correcting for Missing Data in Information Cascades(WSDM11)

論文

http://cs.stanford.edu/people/jure/pubs/cascades-wsdm11.pdf

情報拡散に関する研究

ネットワークがあるとき，そのネットワークを通じて情報が拡散する．(a)の図は，情報が流れる可能性のあるネットワーク(Twitterのフォロー関係とは逆向きになる)

f:id:A_Koide0519:20121213174247p:plain

(b),(c)は観測された情報拡散系列．

この時，分析内容次第で(b)か(c)か決定する．

Twitterのリツイートデータなどを単純に収集すると(c)のようなDAG構造になる．ただ，研究していると親が一意に決まった方が都合がいいことが多いので(b)のようなTree構造として扱うことが（個人的には）多い．

一方で，たいていの場合に拡散系列はCompleteな状態で観測されることはない．

なので，欠損した拡散系列からCompleteな拡散系列の代表的な特徴量を推定することを考える．今回はk-treeモデルを提案し，実データと人工データで評価する．結果として，90%欠損しててもCompleteな拡散系列の特徴量を推定できることが分かった．

○目的

完全な情報拡散系列 $C$ の特徴量集合 $\bf X$ を欠損データから推定すること．

流れとしては

欠損拡散系列 $C'$ の特徴量 $\bf X'$ と，欠損状態のk-treeモデルで推定した特徴量 $\bf X'_M$ が出来るだけ一致するようなk-treeのパラメータを決定
このパラメータに基づいて，完全k-treeモデルの特徴量 $\bf X_M$ を算出
$\bf X_M$ は完全拡散系列 $C$ の特徴量 $\bf X$ と一致するはずなので，これにより完全拡散系列の特徴量を推定する

○k-treeモデル

f:id:A_Koide0519:20121213184500p:plain

完全k-treeの場合， $\Gamma(b,h,k)$

欠損k-treeの場合， $\Gamma(p,b,h,k)$

treeの拡散系列を対象にする場合は $k=1$ ，それ以外は $k>1$

これらのパラメータとk-treeモデルによって理論的に求められる特徴量 $\bf X$

ノード数X1
エッジ数X2
ぼっちノード数X3
連結成分数X4
リーフノード以外の出次数X5
平均ノード次数X6

定義と証明が詳細に記されている．今回は省略．

○モデルの推定

・まずは， $p$ (元データからどのくらい欠損しているか)を得る．

$k=1$ のときはpが容易に求まるが，そうでない場合は親ノードがわかればpがどんな値でも問題ないようにする．

・pが決まったら次に $b,h,k$ を求める．

パラメータの良さは， $\bf X'$ と， $\bf X'_M$ の二乗誤差を最小にするものを選択．

また，先述のようにpが不明の場合に備えて，欠損拡散系列を $0<\alpha\leq1$ の範囲で再サンプリングして，各 $\alpha$ での二乗誤差を最小にするパラメータを選択する

○評価

人工ネットワーク（Erdos-Renyiモデル）＋人工拡散データ（SIモデル）

TwitterフォローNW(7000万ノード，20億リンク(!!))＋人工データ(SIモデル)

TwitterフォローNW＋URLの付与されたRetweet

BlogNW＋引用？カスケード

100ノード以上がかかわった拡散系列を250個用意(Twitter)．

100ノード以上がかかわった拡散系列を100個用意(Blog)．

○k-treeモデルの頑健性

実験ではサンプルの欠損は考慮せず $C=C',\sigma=1.0$ ， $\alpha$ の値を0.1刻みで変化させて評価

$\alpha$ の変化に応じた推定結果．TwitterNWの人工データとRetweetデータのX2-X4の実データの結果と推定結果を示す．どれも上手くフィットしている．Retweetのコンポーネント数は微妙かも．

○拡散系列の特徴量推定精度

サンプルの欠損 $\sigma$ を0.1刻みで変化させたときの完全拡散系列の特徴量の推定誤差を調査．完全拡散系列の特徴量として

ノード数
エッジ数
リーフノード以外のノード数
拡散系列の幅

単純な $C'$ から得られる特徴量 $x'(\sigma)$ と， $C'$ からk-treeによる推定をした $x_M$ の推定誤差を比較

多くの場合で $\sigma=0.9$ までは $x_M$ が勝つが， $\sigma>0.9$ になると， $C' \approx C$ となるので $x'(\sigma)$ のほうがよくなる．

○パラメータ推定の頑健性

拡散系列にガウシアンでノイズ入れて推定させてもエラーは小さい．

最後の方はちょっと疲れた．

Lescovecのチームはとにかく徹底的に評価しているので，見習いたい．

どんな拡散系列をつかったのか気になる．100ノード以上のカスケードって，極端な話，数百程度のカスケードしか見てない可能性もあるし，そうだとすると巨大なネットワークを使ってごまかしているかも…と思われかねないような．

参考文献，論文内のfigure引用先

Correcting for Missing Data in Information Cascades(WSDM11)