« 第19回WI2研究会ノート | トップページ | 国際会議WWW2010論文感想その3 (Youtubeコメント分析,評判情報分析) »

国際会議WWW2010論文感想その2 (ソーシャルネットワーク,情報信頼性)

Jure Leskovec, Daniel Huttenlocher, Jon Kleinberg: Predicting positive and negative links in online social networks, Proc. of WWW'10, 2010.
複雑ネットワーク,ソーシャルネットワーク,情報信頼性,極性判定

ソーシャルネットワークにおいて,エッジのpositive/negativeを判定する論文である.データセットは,Epinions, Slashdot, Wikipediaの3種類を独自にクローリングして用意している.ソーシャルネットワークにおいて,局所的なリンク情報を特徴量として,機械学習(ロジスティック回帰)により,ノードu→v間のエッジの極性(positive/negative)を判定している.
特徴量としては,(a) uの出次数やvの入次数(positive/negativeごと),共通の友人数,(b) 媒介人を介した時のその方向やpositive/negativeの値を用いている.

まず実験では,(a)と(b)の予測精度を比較している.共通の友人数が閾値より多いノードのみ対象にした場合と,全ノードを対象とした場合で,場合分けしており,前者では(b)の影響の方が強いが,後者では(a)の影響の方が強い.それらを組み合わせた場合は,最も良くなっている.

また,社会心理学理論との対応付けを行っている.その理論とは具体的には,バランス理論とステータス理論である.バランス理論とは「友人の敵は私の敵」のような,2ステップ先のノードと自分との関係を表したものである.ステータス理論は,自分から見て相手をpositiveに評価していれば,相手から自分はnegativeに評価するというものである.すなわち,社会全体に絶対的な人間への評価基準がある場合に有効に働くような理論である.
これらは,上記の特徴量に反映されているが,それがモデルにおける係数として,正なのか負なのかで判定しており,概ね社会心理学理論に対応付けられることを示している.

また,あるデータセットで学習したモデルが他のデータセットで有効に働くかどうかも見ている.EpinionとSlashdot間は,モデルが共通化できそうなことを示している.

また,バランス理論とステータス理論から,エッジ判定のヒューリスティックを人手で作成し,それを学習モデルと比較している.ヒューリスティックは,バランス法では(u,v)を含む三角関係において,バランス理論が成り立つ数が多い方を採用している.ステータス法では,positiveな入次数,(-)negativeな入次数,(-)positiveな出次数,(+)negativeな入次数を足し合わせている.これらと比較した結果,学習モデルの方が良いことを示している.

全体のネットワーク構造の定理と一致するかも見ている.定理1では,互いにpositiveに評価し合うノードが全体に存在するかどうかを見ている.定理2では,ネットワーク全体において全てのノードが1位からn位まで並べることができるかどうかを見ている.定理1のためには,ノードをランダムに2つにグループ化し,互いのノードを交換し合い,目的関数が最大になるようにしている.定理2のためには,ノードをランダムに並べて,その順序を入れ替え,目的関数が最大になるようにしている.目的関数は,Newmanのモジュール性のようなもので,クラスタ内ではpositive評価値のエッジが多く,異なるクラスタ間ではnegative評価値のエッジが多いということを用いている(バランス理論).ステータス理論は,順序間でpositveiのエッジの向き,negativeのエッジの向きが一方方向であるかどうかを見ている.
これをオリジナルのネットワークと,ランダムに改変したネットワークで差があるかどうかを見ている.結果として,バランス理論はネットワーク全体では成立していないことを示している.ステータス理論は,ある程度成立していることを示している.

最後に,positiveな情報だけを使った場合と,negativeな情報も使った場合も示している.学習したモデルの精度は,negativeな情報も使った場合の方が良いことを示している.

総合評価
エッジに方向とpositive/negativeの値がついている社会ネットワークに対して,ローカルな特徴に基づく極性の判定について,非常に多くの調査を行っている.この点は高く評価できるものである.

|

« 第19回WI2研究会ノート | トップページ | 国際会議WWW2010論文感想その3 (Youtubeコメント分析,評判情報分析) »

Web研究」カテゴリの記事