読んでみた:Magnet Community Identification on Social Networks

http://www.cs.uic.edu/~yzhao/research/papers/rt145-wang.pdf

 

あらまし

ソーシャルコミュニティは,似たような興味を持つ人々を互いにつなぎ,ソーシャルネットワークアプリケーションで重要な役割を果たす.これらのコミュニティの例として,Fecebook上で同じ物を好む,Twitterで共通の対象をフォローする,LinkedInで似たようなグループの一員になる人々などがある.コミュニティ間のいくつかは,人々を引きつけている.引き合うコミュニティとは,同様の話題のほかのコミュニティより,人々の興味や注目をしっかりとひきつける各々のコミュニティである.ソーシャルネットワーク内での,爆発的な数の自己形成したコミュニティに伴い,ユーザに対する引き合うコミュニティの確認は重要な要求である.これは,ひきつけるコミュニティを突き止めるだけでなく,ユーザの出会いの改善や関与の増加の役に立つこともまた可能にする.例えば,ログインの頻度やユーザが生成するコンテンツの質などが上がられる.本稿では,マグネットコミュニティを確認する問題の学習を始める.最初に,注目の流れ・質・持続性のようなマグネットコミュニティの特性を観測する.次に,2次の制約プログラミングを基盤として,グラフランキング式のコミュニティの特徴検出の組み合わせにより,これらの特性を定式化する.詳細には,コミュニティをスーパーノードとして扱い,これらのスーパーノード間の相互関係としてリンクを張る.それにより,コミュニティネットワークが定義される.我々は,コミュニティの人を引き付ける特徴を異質の資源から検出する.例えば,コミュニティの無類の特徴や,そのほかのコミュニティに依存する特徴である.グラフランキングモデルはこれらの特徴により定式化される.さらに,モデルを規則化するため,コミュニティのマグネット特性を反映した制約を定義する.現実のソーシャルネットワークデータで,我々の枠組みの有効性を示す.

 

企業間の人材の流れをコミュニティ感のつながりとして例に上げている

f:id:A_Koide0519:20120726184453p:plain

エッジの数字は人材の流れの比.例えばYahoo!とFacebookの10.5:1は,FacebookからYahoo!へ1人の人材が流れるのに対して,Yahoo!からFacebookへ10.5にん人材が流れるという意味.

 

この図で言うと,Facebookはどこの会社の社員からも魅力的であるので,Magnet communityである.Yahoo!はContribution community

 

こういったMagnet communityは業界のトレンドの発見に役立つ.また,コミュニティのレコメンデーションや決定因子としても利用できる.

 

目的は,コミュニティ集合が与えられた時に,Magnet communityを検出すること.

 

グラフのランキング手法として有名なPagerankを利用すると,従業員数の多い企業に引っ張られてこれらの企業が上位にランキングしてしまう.正規化Pagerankを利用すると,たかだか100人の従業員しかいない企業ばかりが上位にランキングされてしまう.

この結果は,ユーザによる”理想の雇い主”ランキングと全く一致しない.こういったランキングはユーザの注目度を反映していると考えられる.

 

新たにMagnet communityをランキングできる手法を提案

 

・分析手法

グラフGが与えられた時,同じコミュニティに属する各ノードを統合したコミュニティグラフを構築する.

 

f:id:A_Koide0519:20120726191259p:plain

求めたいもの:各コミュニティのアトラクティブ値M=(m_1,...,m_k)

 

コミュニティグラフG_cから,ノードFeatuerF_v(各コミュニティで算出されるStandalone feature)とエッジFeatureF_e(遷移行列とユーザのコミュニティ間の移動を表現するベクトルを利用したFeature)を算出.

 

真のアトラクティブ値と推定値のノルムを最小化することが最終的な目的.

f:id:A_Koide0519:20120726193509p:plain

 

推定値の算出は,ノードFeatureとエッジFeatureの混合比を利用

f:id:A_Koide0519:20120726193734p:plain

f:id:A_Koide0519:20120726193746p:plain

 

ここからいろいろな制約条件を追加していく.

結構大変なのでカット.

 

・評価

Linkedinを利用し,各企業の人材の流れを収集.今回は,IT企業と金融企業を対象

 

事前調査として,業種内のIndustryの成長度を調査.

 

f:id:A_Koide0519:20120726194335p:plain

 

比較するランキング

提案手法:MIM

ベースライン:Pagerank

ユーザランキング1:Ideal Employer

ユーザランキング2:Admired Company

 

・分析結果(ケーススタディ)

IT企業

f:id:A_Koide0519:20120726200023p:plain

 

提案手法(2列目)では,上位にインターネット関連の企業が並び,ユーザ評価とも一致している.Pagerankでは,企業の大きさや従業員数の多さで順位が確定している.また,提案手法では,スタートアップの企業(Facebook,Linkedin)も上位にランキングされている.

また,最初の図で示したように,Yahoo!はContribution企業であるので,その他のインターネット関連の企業より順位が低い.

 

金融企業

f:id:A_Koide0519:20120726200057p:plain

 

Pagerankではやはり企業の大きさが効いている.提案手法では,J.P.MorganやGoldmanなどの関連の強い企業が上位.さらに,CB RichardやJones Langなどの成長力の高い産業が上位に入っている.

また,金融の場合は,スタートアップよりも,資本金や顧客の関連によってアトラクティブ値に影響を与える.

 

また,定量的な評価として,DCG(discounted cumukative gain)とweighted pairwise distanceを利用して,ベースラインや提案手法がユーザランキングとどれくらい一致するのか調査.

 

結果

提案手法のほうが,どちらも圧倒的にユーザランキングと一致する.

 

手法の頑健性

定数パラメータ \alphaの変化で値に変化が出るか(本当はもう一つ定数があるが,割愛)

パラメータを変化させても,それほど結果に大きな差は出ない(0.1~0.9の間で)