読者です 読者をやめる 読者になる 読者になる

02. Basic Network Properties and the Random Graph Model

  • Observation, Models, Algorithms の表:おもろい
  • 基本的な定義

Erdos-Renyi Random Graph Model

  • $ G_{n,p} $ := n 頂点,全枝確率 p で存在
  • 次数分布:二項分布になる.
  • クラスタ係数
    • ペアの間には確率 p で枝がある.従って C = p.
    • p = $\frac\overline{k}N$ なので,次数が定数のとき,N が大きくなるほど小さくなってしまう.

余談:configuration model.各頂点の次数を完全に指定.余っている spoke をランダムに繋げる.

直径
  • 定義.グラフ G が expansion $\alpha$ を持つとは.
    • 任意の頂点集合 S に対して,$ e(S, \overline{S}) \geq \alpha \min(|S|, |V \setminus S|) $
    • ロバストネス
  • 3-regular random graph.定数の expansion $\alpha$ を持つ.
  • 3-regular random graph の直径は $O((\log n) / \alpha)$.
    • 両側 BFS を考えれば良い