読者です 読者をやめる 読者になる 読者になる

よんだ:Event-based Social Networks: Linking the Online and Offline Social Worlds(KDD2012)

http://lsnaworkshop.netii.net/ebsn/ebsn.pdf

 

あらまし

MeetupやPlancastのようなイベントベースの新たに出現したオンラインソーシャルサービスは,高い評判を受け,急激に成長してきた.これらのサービスから,新たなソーシャルネットワーク~イベントベースソーシャルネットワーク(EBSN)を観測した.EBSNはそのほかの利便性のあるソーシャルネットワークのようなオンラインのソーシャルな相互作用だけでなく,オフラインの活動内から得た様々なオフラインのソーシャルな相互作用を含んでいる.Meetupから収集したデータを分析することで,ESBNの特性を確認し,"重い裾を持つ次数分布"や”ソーシャルな相互作用の強い局所性”のような唯一で興味深い特徴を確認する.

つづいて,2つの挑戦的な問題「コミュニティの検出と情報の流れ」から,EBSNの異種の性質(オンラインとオフラインの両方のソーシャルな相互作用の共存)を実験する.我々は,EBSNから検出されるコミュニティは,その他のソーシャルネットワーク(例えば位置ベースのソーシャルネットワーク)よりもより結合力があることを発見した.情報の流れの問題では,イベント推薦問題を研究する.様々な情報拡散のパターンを分析することで,オンラインとオフラインの相互作用を考慮したコミュニティベースの拡散モデルが,最も予測力を提供することを示す.

本稿はEBSNをスケールに分析し,新たな種類のソーシャルネットワークの将来的な分析の道を開くための最初の研究である.本分析のデータは,http://www.largenetwork.org/ebsnからダウンロードできる.

 

EBSNの例

f:id:A_Koide0519:20120706224659p:plain

 

 オンラインでつながっている人動詞のオフラインの交流を促進するサービスっぽい.

 

ネットワークとしてはheterogeneous network

f:id:A_Koide0519:20120708032056p:plain

を考える

f:id:A_Koide0519:20120708032333p:plain・・・オンラインネットワーク

f:id:A_Koide0519:20120708032347p:plain・・・オフラインネットワーク

 

データセット

EBSN…Meetupのデータを使用

LBSN…Gowallaのデータを利用(位置情報をシェアするサービス?)

 

f:id:A_Koide0519:20120707210122p:plain

 

グラフGのリンクに重みをつける

オンラインの場合,任意のユーザu_i,u_jの,グループg_kへの所属の被り度により0 \leq w_{i,j}^{on} \leq 1で重み付け.

f:id:A_Koide0519:20120707210916p:plain

 

オフラインの場合,同じソーシャルイベントe_kに参加していればいるほどry

f:id:A_Koide0519:20120707211453p:plain

 

・データセットの特性

ソーシャルイベントのタイミングは平日で午後2時,午後8時にピーク.休日は朝11時にもピークが来て,全体的にイベント数が多い.場所はやはり都市を中心に行われている.

 

イベント数の分布とソーシャルグループの参加人数の分布では,ほぼPower-lawに従う.やや裾が重い分布(極めて大きいものがちらほら存在する)になる.

 

ネットワーク的な特徴.

比較ネットワーク

1.EBSNのオンラインネットワーク

2.EBSNのオフラインネットワーク

3.EBSNの結合ネットワーク

4.LBSNネットワーク

 

1.と2.を比較すると,1.の方が密なネットワーク.さらにEBSNとLBSNを比較するとEBSNは密なネットワーク.

 

※今回は無向グラフにしてある

 

ネットワークの次数分布をみると,EBSNはどのネットワークでもPower-law分布よりも裾が重い.これは,後に出てくる巨大なイベントとグループの存在が関係しているらしい.また,オンラインネットワークとオフラインネットワークの次数には正の相関がある(0.368)

 

さらに,EBSNの参加イベントの局所性とLBSNのフォローユーザ間の局所性を調査.

どちらのサービスでも局所性が高い傾向にある.特に.EBSNの80%以上のユーザが10マイル以内のソーシャルイベントに関心を持っている。また,EBSN間ではオフラインの方が局所性が高い.

 

・EBSNのコミュニティ構造

Kernel k-means(http://www.cs.utexas.edu/users/inderjit/public_papers/kdd_spectral_kernelkmeans.pdf

を利用(要勉強)

A:ネットワークの隣接行列

グラフ分割の目的関数として有名なNormalized cut(http://www.cs.berkeley.edu/~malik/papers/SM-ncut.pdf)

f:id:A_Koide0519:20120708021556p:plain

f:id:A_Koide0519:20120708021819p:plain f:id:A_Koide0519:20120708021829p:plain

このへんいろいろ書いてあるのでできたら後日.

 

これを拡張

f:id:A_Koide0519:20120708022249p:plain

 

ベースライン1

Linear Combination

f:id:A_Koide0519:20120708022348p:plain

 

ベースライン2

Generalized SVD

f:id:A_Koide0519:20120708022422p:plain

 

※この辺写しただけ

 

評価

Davies-Bouldin index

 

結果

EBSNはLBSNよりも結合力がある.さらにオンラインとオフラインでは,オンラインの方が結合力がある。

 

・EBSNの情報の流れ

3つのパターン

f:id:A_Koide0519:20120708023441p:plain

 

特に,小規模の局所的コミュニティは急速に内部に情報が伝わると考えられる.

なので,それを考慮した拡散モデルを定義

※式省略.時間があれば細かく

 

評価

Seedユーザとして素早い反応をするTopKユーザを選定.このユーザにイベント情報を与えたときに,イベント情報に対して”Yes”と反応したユーザ数をTopKユーザによってカバーされるユーザで割った値をrecallとして利用.

 

ベースラインとしてランダムウォークモデルとCollaborative Filtering を利用.

ランダムウォーク:パラメータ \betaを用意し,情報の発信源に情報の流れを戻す確率とする.0のときは,通常のランダムウォークモデル

Collaborative Filtering:過去のイベントへの参加,グループの所属の集合の一致度をJaccard係数で測定.高いほど情報を伝えやすい

 

提案手法がよくなる.Kが少ない時はオフラインの方が性能がよいが,Kの数を増やしていくと急激に性能が良くなる

 

後半の方はもはや眠くて何書いているのかわからないので,時間見つけて後半部分は読み直したい.