Random Graph Generator

個人的メモ

(1 つ目のコードについて)
$G(n, p)$ は愚直にやると $\O (n^2)$ かかるが次にどの辺を取るかを幾何分布に従う乱数によって決めることができるので(次に取るのが $i$ 個先となる確率は $p(1-p)^{i-1}$ なので), 期待計算量 $\O (np)$ で求めることができる. また他によく見る random tree の構築は一様ランダムというわけではないので, 一様ランダムな木の生成として prufer code から復元する実装を載せている. ランダムグラフの理論でよく目にする Galton-Watson 過程に基づいて木を構築する方法もあるらしいがよく知らない. 他の関数については基本的に書くだけ.
(2 つ目のコードについて)
後半のアルゴリズムは次数列が与えられたときにそれを満たすような(連結な)グラフを一様ランダムで生成するアルゴリズムになっていてその中で出力されるグラフが連結である必要がある場合(こちらのほうが難しい)について説明する(以下の 2 つのステップからなる).
(I) 与えられた次数列を満たす単純連結なグラフを構築する(Havel-Hakimi アルゴリズム). これは線形時間で行うことができる. 次に (II) 連結なグラフの異なる $2$ 辺をランダムに選んで swap するという操作を繰り返す. を行う. (II) の操作によってグラフが非連結になる場合は invalid ととして自分自身に移るとする. このとき swap 操作を繰り返すことで与えられた次数列を満たす異なる $2$ つのグラフ間を移りあえることから既約であることが言え, また自分自身に移る遷移が存在することから非周期的であるのでこの(有限)マルコフ連鎖は極限分布を持ち, またその分布はよく知られた事実から一様分布となる. そのため swap 操作を十分な回数繰り返すことで一様ランダムなグラフが得られる(収束速度はグラフ依存. 正規化ラプラシアン行列の第二固有値による評価が有名).
ここで swap 操作を行った影響でグラフが非連結になる可能性があり, またそれを特定するのには複雑なアルゴリズムを使わないとすると $\O (m)$ 時間を要する. そのため元論文では window size $T$ を定め, $T$ 回 swap を繰り返した後に非連結なら $T$ 回の swap 操作をなしにして $T \ast= 0.923...$, 連結なら $T \ast= 1.131...$ と更新して操作を続けることにする. 定数は著者たちがヒューリスティックに決めたものである. 実際に動かしてみると結構速く動作する(TIME を適宜設定しその間回し続けるという実装にしている). ちなみに非連結を許すならただ回すだけでいい. (連結な)単純グラフが存在しない場合は assert を吐くようにしている.
(追記) FOCS 2019 で次数列が与えられた場合にグラフを uniformly at random に生成する高速な手法が発表されたみたい(参考).