Relationship Classification in Large Scale Online Social Networks and Its Impact on Information Propagation

INFOCOM'11．

• relationship classification
• impact: information influence

Network Model and Problems

Network Model

graph G. E -> link category L

property: transitivity, community structure

depeer insight: transitivity, 関係のカテゴリもそうなのではないか．カテゴリが違うと，確率はとても低い．

Problem

グラフが与えられる．一部の辺にはラベルがわかっている．ラベルのついていない辺にラベルをつける．

Algorithm

• アイディア
  • 頂点 v から頂点 u への辺のラベルと，v と同じクラスタの頂点 w と u の関係は同じカテゴリ
  • 違うクラスタへの辺は違う関係

t-affect

頂点集合 U からの t-affect function．各頂点 v について，頂点集合 U からスタートして t 回ランダムに動く間に 1 度でも到達する確率．

RCA

• ある頂点に注目する
• 同じラベルでつながってる頂点集合がある．
• その集合からのt-affect functionを計算する．
• それを各ラベルについてやって，各辺について argmax とってラベルをつける．

Information Propagation

w(v), c(v): weight, cost of user v. コストの和が B 以下で重み最大化．

independent cascade model [KDD'03].

Experiments

• 30% にラベルがついていれば 70% の精度で推定ができる
• そしてそれを使えば influence maximization の結果も向上