JSAI参加してないメモ4

JSAIはこれでラストにしよう

現実の多重有向ネットワークがもつような特性を表現できる成長モデルの構築を目指す。
Twitterのお気に入りやRTを人の嗜好ネットワークと考えると、同じ人がつぶやくツイートを何度もお気にいりしたりRTしたりすることはよくある．

モデルとしては、BAモデル（次数優先）を多重NWに拡張した多重BAと、CNNモデル（友達の友達は友達！）を多重に拡張した多重CNN．

多重BAの場合は新ノード＋リンクを追加するか新リンクのみを追加するかの確率 $\alpha$ と、新リンク追加が選択されたときに多重リンクにするか否かの確率 $\beta$ が用意されている．

多重CNNの場合は、 $\alpha$ はBAと同じで、、新リンク追加が選択されたときに多重リンクにするか、潜在リンクの顕在化を選択するかを確率 $\gamma$ で決定する．

実ネットワークとして、Twitterのお気にいる関係NW、Twitterのリツイートネットワークを用意．
評価として、個々のノードを情報源とした情報拡散を行い、その期待影響度が実ネットワークと近い結果となるかで評価．なお、情報拡散モデル上での多重リンクの扱いは、単純にリンクの本数だけコイン投げをするチャンスが増えることに相当する．

結果として、多重CNNが実ネットワークに最も近いような結果を出した．また、ICモデルはある程度の次数になると期待影響度が手詰まりになる．

- - - - -

以前は期待影響度ではなくて、いろんなネットワーク指標で評価していたけど、結構難しかったのかな…
個人的に気になるのは、リンクを張る時の向きをランダムに決定していることろ．向きの決定は実際のネットワークを表現するときに重要になりそうな気がするけどなぁ…ネットワーク系はやっぱりおもしろい

Twitter上の情報拡散系列からの変化点検出

情報拡散系列における拡散スピードの変化点検出．
情報の拡散遅れは指数分布に従っていると仮定．

従来法は、変化点数 $J$ が事前に与えられたときに、尤度が最大になるような変化点集合と遅れパラメータを推定する．
貪欲法を利用して、変化点を一つづつ埋め込んでいく．

提案法は、さらに局所改善を導入．従来法で一通り求めた後に $J-1$ 個の変化点は固定してその中で尤度が最大になる変化点を見つける．これを書く変化点に行い、変化点のずれがなくなったところで終了．

従来法は拡散系列のノード数と変化点数の積がオーダーになる．提案法もそこまで処理時間に差はない．
ここまでが前論文までの話

今回は、事前に変化点を与えなくても妥当な変化点数を自動で求めてくれるように、尤度比検定を導入する．
変化点が $J+1$ の際の尤度と $J$ の時の尤度の減算により求められる統計量が自由度2の $\chi^2$ 分布に漸近することを利用し、適当な有意水準 $\alpha$ を設けてその限界値を統計量が下回ったらアルゴリズムをしゅうりょうするようにする．

実験では、人口データで拡散系列を作って、従来法に尤度比検定を入れたものと、提案法に尤度比検定を入れたもので、変化点数の推定正解率と、時間遅れパラメータの誤差で評価．

変化点数は提案法の方が非常にうまく推定できている．時間遅れパラメータの誤差は、従来法がうまくいくこともあるが、これは従来法が時間遅れパラメータの誤差を変化点数を増やすことで補おうとしていることが要因らしい．

実際のTwitterのリツイートに提案法を適用すると、一見一度のバーストが起きているだけの拡散に見えても、実際には30くらいの変化点があって、そのバースト内でも細かい変化がある．

- - - - -

実験から評価、実データへの適用まで大変読みやすかった．実データの場合、時間遅れパラメータの増減に寄与していそうなユーザが検出できるとさらにありがたみが増しそう．まとめにも書いてある、MDLやAICなどのモデル選択で変わるところはあるのだろうか．

ソーシャルネットワーク上での影響を最大化するターゲットノード

ネットワーク上での期待影響度を最大にするような情報源集合を正確に効率よく求める問題（影響最大化問題）．

これまでの影響最大化問題は、情報源集合が決まった時、そのノードは確実にアクティブであるという仮定があった．しかし、実際にはその人に情報を与えても確実に情報を伝えてくれるとは限らない．

従来の影響最大化問題．アカマルが初期ノード集合．このノードは確実にアクティブ
f:id:A_Koide0519:20130609140519p:plain

今回は、初期集合に情報を伝えるところから始まるように問題を拡張する．この過程の上で、最も情報を伝えてくれそうなターゲット集合を求める．（ターゲット選択問題）

グラフを拡張し、新規ノードがターゲットに情報を伝えようとすることを考える．

f:id:A_Koide0519:20130609140845p:plain

何が変わるかというと、新規ユーザの情報によってターゲット集合全てがアクティブになるならば、これまでの問題とまったく変わらない．そうでない場合、アクティブになれなかったユーザはネットワーク内の他のユーザから改めて情報を仕入れなければならない．すなわち、伝える力はあっても収集能力のないユーザは二度と情報を受け取れない可能性がある．Twitterでいうならば誰もフォローしていないけど、たくさんフォローされているユーザがそれに当たる．

この問題において、適切なユーザを選べるように従来の式を拡張．

実験として、4つの実ネットワークを利用．
書く手法で選ばれたノード集合をターゲットとして情報拡散シミュレーションをしたときの期待影響度で評価．
比較として、従来の影響最大化問題における情報源集合、出次数の高いユーザ上位集合、ランダム法で比較．

結果として、ターゲット問題に拡張した提案手法が最も期待影響度を高くする．
また、選択されたノード集合は、提案手法とそのほかの手法で大きく異なる．ネットワークによっては全く一致しないものもあった．

- - - - -

新たな視点での影響度最大化問題ということで、とても興味深かった．Twitterなんかでも、有名人に”このツイート拡散してください！”みたいなことあるし、それに近いのかぁとも思った．その場合はネットワークを拡張するわけではないけど・・・それにしても新しいアイデアがどんどんでてきてるな

読む分野が偏りすぎている感はある。ちゃんと勉強したら機械学習とか自然言語処理の論文も読みたいですね．

追記（というか追加）

「デマの壁」仮説の検証

ソーシャルメディア上での情報伝達を阻害する「壁」の存在を検証する．
ソーシャルメディア上の人のつながりは”６次の隔たり”とも言われるように、簡単にネットワーク上の全ての人が全ての情報を得られそうな感じがするが、実際にはそんなことはない．デマ情報に関しても、自分のところに届く前に壁に食いとめられていたり、訂正情報だけが送られてくることもある．

このような壁の存在を解析するために、震災前後のTwitterの@messageで構成させるネットワークの近接中心性（自分以外のユーザとの距離の近さを表す）分布の変化をみる．一般的に、この分布が正規分布に従うことが分かっており、今回のTwitterネットワークも定常状態では確かに正規分布にほぼ従っている．一方、震災直後のネットワークをみると、近接中心性の高い部分にスパイクがいくつか見られる．

さらに、このような現象はどういう状況で表れるのかをWSモデルとBAモデルから分析．すると、BAモデルでは今回の震災直後に見られたスパイクが観測された．このスパイクは、ハブノードにだけ接続されたノードだった。したがって、このスパイクは、リツイート等で情報を伝搬した軌跡であると考えられる．

- - - - -

情報の壁というのは確かにあると思う．ただ、それはデマだけでなく定常時にもにも存在していそうな感があるので、今回の震災時のスパイク現象がデマの壁とどうからんでいるのか今後の展開が気になる．この壁が、人為的に行われているものなのか、単純に情報の鮮度が落ちて止まっただけなのか、クラスタ構造みたいなものがあって、その中で情報が飽和して終わったのか、色々な仮説が考えられそう．

見当違いだったら申し訳ないけど…