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 の結果も向上