Compact routing in power-law graphs

Wei Chen, Christian Sommer, Shang-Hua Teng, and Yajun Wang. 2009. Compact routing in power-law graphs. In Proceedings of the 23rd international conference on Distributed computing (DISC'09), Idit Keidar (Ed.). Springer-Verlag, Berlin, Heidelberg, 379-391.

実際にはTALGに出しているらしき原稿の方を読んだ． こっちだと数式がレンダリングされます http://iwi.tc/wiki/index.php?%E8%AB%96%E6%96%87%2F%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96%E7%B3%BB%2FA%20Compact%20Routing%20Scheme%20and%20Approximate%20Distance%20Oracle%20for%20Power-law%20Graphs

Preliminaries [#j422360e]

  • モデル fixed degree random graph (FDRG)
    • 重みの期待値列 $\vec{w}$ が与えられているとする (expected degree sequence)
      • ただし任意の $i$ で $w_i^2 < \sum_j w_j$ とする
    • $ P[\{v_i, v_{i'}\} \in E]=w_i w_{i'} \rho $, $ \rho = 1 / \sum_j w_j $
  • モデル random power-law graph $RPLG(n, \tau)$
    • $w_j = \left( \frac{n}j \right)^{1/(\tau-1)}$
    • $ P[\{v_i, v_{i'}\} \in E]= \min\{ w_i w_{i'} \rho, 1 \} $
  • RPLG を採用する理由
    • 辺が独立であるため，理論的に扱いやすい．
    • assortativity: 多分ホモフィリー性のこと．高い次数は高い次数とくっつく．
      • これはsocial networks ではそうだ．対義語: disortativity, technological and biological networks. （今回の応用的にはまずいんじゃｗ）
      • 高い次数の点は，以下の2通り
      1. "core" に居る
      2. 少なくとも1つの近傍は "core" にいる．
      • $ s(G) := \sum_{\{u, v\} \in E} deg(u) \cdot deg(v) $ が，"hub-like core" をどれだけ持っているかを表す指標である [Li 2005, Definition 4.1]

The Adapted Compact Routing Scheme [#ib8672be]

定義

  • コア
    • $core_{\gamma'}(\vec{w}) := \{ v_i : w_i > n^{\gamma'} \} $
    • $core_{\gamma'}(G) := \{ v_i : deg_G(v_i) > n^{\gamma'} / 4 \} $
  • landmark = $core_{\gamma'}(G)$
  • l(u) := u's closest landmark
  • local targets of $u$ := $B_G(u)$
    • $B_G(u) := \{ v \in V : d(u, v) < d(u, l(u)) \}$ (ball relative to the core)

基本戦略

  • 各ノードは，以下への最短路へのポートを覚えている
    • all landmarks
    • all local targets
  • ゴール v がそこに入ってなければ，l(v) に送る．
  • labeled scheme
    • 各ノード u がゴール v の l(v) を知らないといけない
    • l(v) から v への最短路の間の w では，$v \not\in B_G(w)$ かも．
      • なので，l(v) だけじゃなくて，l(v) から v への最短路をエンコードしておく．

Analysis of the Compact Routing Scheme [#w878a8b3]

概要

  • stretch は簡単（power-law関係なし）
  • スペースを頑張って証明する
    • core のサイズ
    • ball のサイズ
      • 実際には，core と ball のサイズの最善のトレードオフを実現するパラメータを $\gamma$ など実は選んでいたのであった
    • "アドレス" のサイズ
Stretch [#s7ed892f]

power-law 関係なかった．

Random Power-Law Graphs and their Cores and Balls [#uf6e1284]

RPLG の新しい性質を何本か証明している

定義

  • $ Vol(S) := \sum_{v_i \in S} w_i$
  • $ vol(S) := \sum_{v_i \in S} deg_G(v_i) $

Lemma 5.2

  • $RPLG(n, \tau)$ にて $ n < Vol(G) \leq \frac{\tau-1}{\tau-2}n $
    • まぁそりゃそうだわ

Lemma 5.5

  • $RPLG(n, \tau), w_i \geq 32 \ln n$. $P[w_i/4 \leq D_i \leq 3w_i] > 1 - 2 / n^4$
    • つまり，次数は非常に高い確率で $w_i$ の周り
    • 証明ながし

Lemma 5.6

  • $RPLG(n, \tau), Vol(S) \geq 192 \ln n$. $P[Vol(S) / 8 \leq vol(S) \leq 4Vol(S)] \geq 1 - 2/n^3$

Corollary 5.7

  • $vol(G)/2 \leq \frac{4(\tau - 1)}{\tau - 2}n$ with probability at least $1 - 1/n^2$

Lemma 5.8

  • $Vol(S) \cdot Vol(T) > c \cdot Vol(G)$ なら
  • $P[d(S, T) > 1] = \prod_{v_i \in S, v_j\in T} \max\{ 0, 1 - w_iw_j / Vol(G) \} \leq e^{-Vol(S) \cdot Vol(T) / Vol(G)} \leq e^{-c}$
Core Size [#t24b2c8c]
  • $\delta' = \frac{1-\gamma}{\tau-1}$． （多分前にも定義している）
  • $|core_{\gamma'}(\vec{w})| = \lceil n^\gamma \rceil - 1$

Lemma 5.9

  • w.h.p. $core(\vec{w}) \subseteq core(G)$
    • つまり，Gのほうのしきい値をいじったおかげで，Gからとっても元のcoreを全部とれてる可能性が超高い
    • 証明はLemma5.5から

Lemma 5.10

  • w.h.p. $ |core(G)| = \Theta(n^\gamma)$
Ball Sizes [#je8bf0a3]
  • $\beta = $ほげほげ（定数）．w.h.p.
    • $|B_G(u)| = O(n^\beta)$
    • $|E(B_G(u))| = O(n^\beta \log n). $ （頂点集合内部の辺）

References [#r39f22ad]

  • [Aiello et al. 2000] AIELLO, W., CHUNG, F. R. K., AND LU, L. L. 2000. A random graph model for massive graphs. In 32nd ACM Symposium on Theory of Computing (STOC). 171–180.
    • FDRG の定義，解析
  • [Chung and Lu 2002] The average distances in random graphs with given expected degrees. Internet Mathematics 1, 91–114. See also PNAS 99, pp. 15879–15882.
    • FDRG の定義，解析
  • [Chung and Lu 2006] Complex Graphs and Networks. American Mathematical Society
    • FDRG の定理？
  • [Li et al. 2005] LI, L., ALDERSON, D., DOYLE, J. C., AND WILLINGER, W. 2005. Towards a theory of scale-free graphs: Definition, properties, and implications. Internet Mathematics 2, 4, 431–523.
    • core っぽさ指数

感想 [#r7aa2e52]

全体 [#dc9090b6]

長いがシンプル，そして応用性は低い，と思った

  • これは，批判しているわけではない（証明は簡単ではないし，こういうの初めてやってマジでスゲェと思う）
  • 長い：証明が長い，しかもそれらは割とテクくて簡単ではない
  • シンプル：アルゴリズムが簡単
  • シンプル：証明も方針自体は簡単
    • 主に core と ball のサイズをバウンドした
  • 応用性は低い：このアルゴリズム以外も同じフレームワーク（core と ball）で証明できるとはとても思えない

なぜか？

  • やっぱり本質的にこういうことをやるのは難しいモノである？
    • ランダムグラフとか数学のやべぇ人専用の恐るべきジャンルって感じあるからな
  • 道具が足りていないだけ？
    • core, ball のサイズみたいなのを，モデルの性質だと思えば，今回も主にモデルの性質を証明したのだ
    • そういう意味では，モデルに対してそういう定理が揃っていればこの論文は超簡単に証明できたかもしれない
    • そういう状態になっていれば，もっと難しいアルゴリズムとその証明にも挑戦出来る状態になるか？
細かいところ [#dbc285f3]
  • power-law＋ホモフィリー性で core-fringe 的な性質が出るんだな
    • fringe の高いクラスター係数が重要かと思っていたが．
  • とりあえず core-fringe 系の性質の議論をしている論文をもっと他にも探して，できれば自分らの手法の理論解析につなげる