狠狠撸

Ｔｈe Bursty Dynamics of the
Twitter Information Network
D1 臼井翔平
第一回とりらぼ輪読会 2014/5/31
Seth Myers Jure Leskovec
Stanford University

Abstruct
? Tweet,Retweet burstがネットワーク構造を
変える事がある
?このネットワーク構造の変化はどんなものか
?ネットワークの変化を起こすバーストはどんなも
のか
? Retweetが引き起こすネットワーク構造変化
をモデル化

Background
? ネットワークのダイナミクスは理解されていな
い
?リンクの生成と削除
? 2つのダイナミクスに着目
?情報共有のダイナミクス
?ネットワークの進化

目的
? 情報共有がネットワーク構造の変化をもたら
すか
? ネットワーク上での情報拡散の理解
?burstの分析

Present work
? Information causes bursts in network
evolution
? Bursts of edge creations and deletions
? Modeling and predicting bursts

Twitterのダイナミクス
? Followリンクの追加と削除
? 2011年11月のfollowerネットワークを収集
?13,100,000ノード
?1,700,000,000リンク
? 112,300,000リンクの追加(7%)
? 39,200,000リンクの削除(2.3%)

Twitterのダイナミクス
? 9%のリンクが変化している
? 3リンク追加される毎に1リンク削除
高いダイナミクス
成長するだけのネットワークではない

Twitterの情報共有
? 1,200,000,000ツイート
? 116,300,000リツイート
? TweetとRetweetがfollowerネットワークに影
響を与える？

入次数との関係
入次数との関係がある

Retweetとnew Follow
? 入次数1000から2000のノード
Retweetが多い程new 蹿辞濒濒辞飞别谤が多い

Tweet数とfollowの削除
? 入次数1000から2000のノード
tweetが多すぎるとfollowが減る

ユーザアクティビティとfollow
? 入次数が多いノードに関して関係あり？
?Retweetとfollow
?Tweetとunfollow
? 本当に関係があるかはわからない
?時系列でみてみる

時系列での比較
? ユーザA(??? = 266,842)
Retweetが増加した後followが増加

? ユーザA(??? = 218,045)
Retweetが増加してもfollowは増加しない

? ユーザA(??? = 112,988)
Retweetがなくてもfollowは増減

? Retweetが増加した後にfollowが増加する事
がある
? Retweetが増加した後常にfollowが増加する
わけではない
? Retweetがなくてもfollowの増減はある
どんなRetweetがfollowは増加につながる？
変化後のネットワークの構造は？

ノードのego-network
? あるノードをfollowしているノードのネットワー
ク
? Follow(Unfollow)バーストの前後でego-
networkが変化する？

Tweet similarity
? 2ノード間のtweet similarityをTF-IDFで定義
? ????? = ?? ? ???
???：単語の出現頻度
????：逆文書頻度

Follower Tweet Similarity
? Tweet元ノードとfollowerのtweet similarity
Tweet-unfollow retweet-follow

Follower Tweet Coherence
? Tweet元ノードのfollower間のtweet similarity

ノード間類似度
? Follow, unfollow burst発生後
?Retweet及びtweet元とfollowユーザの類似度が
増加
?Followユーザ間の類似度も増加
Ego-network全体の類似度が増加

Weakly connected components
? Ego-networkのコンポーネントの比

Edge density
? Ego-networkのリンク密度

ネットワークの性質
? Follow, unfollow burst発生後
? コンポーネント数の増加
?新しいコミュニティからの参入が予想される
? リンク密度の増加
?Followerがお互いにfollowし合う
?これが類似度の上昇になっている

Follow burstを引き起こすtweet
? どのような場合にfollow burstが起きる？
? トークン：10回以上使われた単語
? 全てのトークンがretweet burstに含まれるが
，全てがfollow burstを引き起こしてない
? あるトークン????がfollow burstを引き起こす
確率

事例
? “Occupy Wall Street”
movement
?収入不平等に対する活動
? 少なくとも16個のトークンが
活動に関わっている

事例
? “officer”を含むtweetはかなり
followバーストをおこしやすい
? Followバーストを起こしやすい
tokenが存在する

Followバーストのモデリング
? Retweet burstの元tweetからfollow burstが
起きるかどうかを予測する
? 2-hop neighborhoodだけを考える
?Followの追加先の平均パス長は2.036

followバーストのアイディア
? より興味の近いノードを発見する事で起きる
?Follow burst後に類似度が上がる
? 普段retweetしないノードがretweetすると発
生
?普段目に届かない

Tweet similarityのモデル化
? いくつかのユーザのtweet similarityの分布
おおむね正規分布

Tweet similarityのモデル化
? ???：iのfollowerの類似度の平均と比べたjの
類似度
? ? ?, ? ：iとjの類似度

Follow確率
? ??,? = ? ? ?????? ? ???)
≡ ? ? exp ? ? ???
= ? ? exp
?
??
? ?? ? ?, ? ? ??
= ? ?
exp(?? ? ?, ? )
exp(??)
?
? ?
= ? ?
?(?, ?)
exp(??)
?
? ?

Cと?の最適化
? 実データとフィッティング

Follow burstの確率
? 新規followの期待値： ?∈?2(?) ??,?
? Follow burstはそれまで知らなかったノードを
retweetによって知る
?? ??(?, [?, ? + ??))：区間[?, ? + ??)の間にfollowし
ている誰かがiのtweetをretweetしたノード集合

実験
? Retweetバーストデータ：400,000
?内21%がfollowバースト
? followバースト確率を使ってランク付け
? 笔谤别肠颈蝉颈辞苍-谤别肠补濒濒曲线の础鲍颁で评価

結果
既存手法より優れている

まとめ
? Retweetとfollowの関係を分析
?retweetバーストが起こると，followバーストが起
こる事がある
? Followバースト後のネットワークの特性を分
析
?Followバースト後にはユーザの類似度が増加
? Followバーストのモデル化
?Retweetからfollowバーストの発生を高精度で推
定

意見
? Follow burstを起こしやすいtokenがある
?うん???
?どういうtokenがburstしやすいっていうのは言え
るんだろうか???ってか言ってどうするんだろう??
? このモデルは一体何につかうんだろうか???
?Retweetに対して広がった結果を使ってるから予
測は無理
?シミュレーションとかに使うってことなのかなぁ．．

狠狠撸

The bursty dynamics of the twitter information network

More Related Content

The bursty dynamics of the twitter information network