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 を考えれば良い