Reciprocity in Social Networks with Capacity Constraints - todo314 @ ウィキ

Reciprocity in Social Networks with Capacity Constraints

• Bo Jiang, Zhi-Li Zhang, Don Towsley
• KDD 2015

概要

• 相互性（双方向辺の割合）が知りたい
• 双方向辺数最大化問題
  • NP-hard
    • 3-pathを調整するヒューリスティクス
  • 上限とか考える
• 実験的考察
  • 実際のネットワークのいくつかは上限に凄く近い
  • ヒューリスティクスが意外と良い

動機付け

• スウェーデンのWikipedia
  • 相互性 21% …これは大きいか？
  • ランダムグラフ 0% …よく分からん
  • （次数制限の下の）上限 28% …21%は凄そう
  • 逆に 90% …21%は対して凄くない
• 何か同時入出次数列が大事な因子らしい
  • 実際フォロー・フォロワー数とか表すし，P2Pでも…
  • 基礎的ということで

問題定義等

• そもそも次数列からグラフが作れるのか？
• Erdős-Gallai（無向グラフ）
  • 次数列が降順∧和が偶数とする
  • graphic（グラフが作れる）な必要十分条件
  • $$ \sum_{1 \leq i \leq k} d_i \leq k(k-1) + \sum_{k+1 \leq i \leq n} \min\{d_i, k\} $$
• Fulkerson-Chen-Anstee（有向グラフ）
  • 出次数列が降順∧入次数和＝出次数和とする
  • $$ \sum_{1 \leq i \leq k} d_i^+ \leq \sum_{1 \leq i \leq k}\min\{ d_i^-, k-1\} + \sum_{k+1 \leq i \leq n} \min\{d_i^-, k\} $$
• 最大相互性問題
  • $$ \rho(G) = $$ 双方向な（有効）辺数
  • $$ r(G) = \rho(G)/|G| $$
  • maximize $\rho(G)$
  • subject to $$ G \in \mathcal{G}(\mathbf{d}^+, \mathbf{d}^-) $$

色々解析

• β=Σmax{入次数(v), 出次数(v)} が上限
  • ザッツ当たり前
• β=最適値 <= $$ {\bf d}^+ \wedge {\bf d}^- $$と$$ {\bf d}^+ \vee {\bf d}^- $$がgraphic
  • 必要条件ではない（すぐわかるが例を沢山示してる）
• "最適値=上限?"はNP-complete
  • 証明は呼んでない
• 最適化問題はNP-hard

最適グラフの性質

• 作ったグラフに3-path (v0, v1, v2, v3)があるとする
• 3ケースについて，相互性を増加できる「辺の張り直し」が出来る (Fig. 5)
• 逆に最適解は↑な3-pathを持たない
• ヒューリスティクス: そういう3-pathがある限り張り直す
  • 最適ではないが良さそう（らすい
• 他の複雑なパターンについても述べてるけど略．

実験

データセット

• OSN，生物学，通信，共購入(co-purchasing)，Web，Wikipedia，ソフトウェア呼出，P2P

実際の相互性 vs. 上限

• 相互性と上限／辺数（共に[0,1]）をプロット
• P2Pはほぼ相互性が0
• 呼出も低い
  • この辺はそりゃそうだ
• 社会・Wikipediaは高い
  • 上限に結構マッチ
• （相互性）／（上限／辺数）をジャンル毎にBOXでプロットして見る
  • 生物学，ソフトウェア，P2Pが全体的に低い
  • Wiki-Vote，Stackoverflow，スペインWikipediaが例外的に低い

3-pathヒューリスティクス

• 何か大体上限に一致する
• あの簡単な上限に近いグラフを作れるということ
• 3種類の3-pathが相互性低下の原因（？）

まとめ

• △じゃなくて＝
• この問題は近似アルゴリズムを与えるだけとかそういうんじゃ，
• データマイニングじゃ発見ないし，データベースでも意味ないしで評価されん
• 分類？とかには使えないのかな？

KDD 相互性

2015/08/24