2018年02月01日

「10M頂点のランダムグラフ生成が1日以上待っても終わらないから実験出来ない．しない．」とか言われたので，Directed scale-free graphs の論文を読んで C++ で実装して投げつけた．10M 頂点/20M辺 のランダムグラフだと書き出しに時間食って 2分くらいかかるけど．

だがしかし，眠い頭でクソ真面目にヒストグラム（度数＋実数バイアス）に従った乱択をやる為に prefix sums をセグメント木で管理してO(n log n) で動くプログラムを書いたのだけど，よくよく考えてみたら directed scale-free graphs のモデルって度数分布に従った乱択（＝辺の一様乱択）か（頂点の）一様乱択かを単純に混ぜただけの分布なので辺リスト持ってたら毎回の乱択が O(1) になってトータル O(n) で終わるじゃん，とかいうことに寝て起きてから気づいた．

眠いとダメだね．

閑話休題．

NetworkX の directed scale-free graphs の実装はヒストグラムからの乱択に毎回 O(n) かけてるので激遅そう．無効グラフの BA モデルの方は各頂点 O(1) で乱択する実装なので大丈夫そう．