« 国際会議WWW2010論文感想その8 (SNS,プライバシー,機械学習,UI) | トップページ | 第153回データベースシステム研究発表会 »

国際会議WWW2010論文感想 その9(社会ネットワーク,エッジ重み推定)

Rongjing Xiang, Jennifer Neville, Monica Rogati: Modeling Relationship Strength in Online Social Networks, Proc. WWW2010, 2010.
ソーシャルネットワーク,社会ネットワーク,エッジ重み推定
http://portal.acm.org/citation.cfm?id=1772790

ソーシャルネットワークにおいて,プロフィールの類似性と,ユーザ間のインタラクション情報に基づき,エッジの重み(関係性の強さ)を推定している.重みは連続値で推定される.推定のために教師なし学習モデルを提案している.具体的には,つながりの強さを表す潜在変数モデルを考案し,変数推定のために座標上昇最適化法(coordinate ascent optimization procedure)を提案している.

本論文では,提案手法は数式で示されており,それの言語的表現は難しいため,このまとめでも論文中の式を参照しながら要約する.根本的な考えとしては,つながりが強いほど,より多くのインタラクションを発生させるというものである.図1に示されるように,ユーザiとユーザj間の関係は,プロフィールx_iとプロフィールx_jが,潜在変数Z_ijに影響し,潜在変数(モデル)Z_ijがユーザi,j間のインタラクションy1_ij, y2_ij, ..., ym_ijを発生させる.mはインタラクションの個数である.

xが与えられたときにZが導き出され,その結果yが導き出される確率は式(1)のように表される.潜在モデルZが与えられたときに発生するインタラクションの起こる確率(P(Z|X))とxが与えられたときに潜在モデルZが導き出される確率(P(Y|Z))の積で与えられる.P(Y|Z)は,ユーザプロフィールx_i, x_j間の類似度に重みを付けたものを引数としたガウス分布の確率密度関数で表される.インタラクションymは,バイナリ変数である.

さらに図2に示されるように,各インタラクションtに補助変数ベクトルatを導入している.これは,元々投稿回数が多いユーザ(インタラクションが投稿したか否かであれば)は,出力yも大きくなるような工夫である.zとatが与えられたときのytの確率をモデル化するためにロジスティック関数を用いている(式(3))
.ここで,重みθはatへの重みであるが,これを学習で推定する(学習は,w, θ, Zを同時に推定するものである).(7)式により,ユーザi, j間のつながりの強さを表す.Dは歯科位置が決まっており,これを最大化するw, θを求める.

推定では,結合尤度(P(y, z, w, θ |x))を最大化するパラメータw, θ, zを座標上昇最適化法にて行う.座標上昇最適化法は,収束するまで,パラメータw, θ, zを更新する.更新は,Newton-Raphson法を用いる.各更新パラメータの偏微分を求め,それぞれが零になる点が推定されるパラメータである.

評価実験では,まずLinkedInを対象にしている.LinkedInのユーザ100人をシードノードとしてランダムに選び,2リンク以内の全ての近傍を抽出した.その中のペアを対象に実験している.プロフィールは表2にあるように,iとjが同じ学校に通っていたかどうかなどである.インタラクションは,iとjがコネクションを張っているか否かや,iがjのために推薦を行ったかどうかなどである.推定は,同じ仕事をしているか否か,同じ職能領域で働いているか否か,同じ地域に住んでいるか否かを,6つの簡単な推定手法と比較している.また,第三者がユーザiとjのプロフィールを両方とも見たか否かを評価基準として,6つの簡単な推定手法と比較している.その結果,提案手法が最も良いことを示している.

また,実験は,他のソーシャルネットワークとしてFacebookも対象として,Purdue大学の学生5人をシードノードとして実験をし,良い結果を示している.

(総評)
ユーザプロファイルとインタラクションを利用して,ソーシャルネットワークのエッジの重みを推定するというアイディアには新規性があると思われる.また,ユーザ間の社会的つながりの強さに関連する潜在変数を仮定し,プロファイル間の重みと,上記潜在変数,ユーザ間のインタラクションの関係をモデル化するという手法にも新規性があると考えられる.インタラクションに対する補助変数ベクトルも工夫の一つであるが,これがどれだけ寄与しているのかは明らかではない.評価もLinkedInとFacebookの二種類を用いてる点も評価できる.

|

« 国際会議WWW2010論文感想その8 (SNS,プライバシー,機械学習,UI) | トップページ | 第153回データベースシステム研究発表会 »

Web研究」カテゴリの記事