c# - ランダム隣接リストジェネレータ

Question

私は現在、最終年度のプロジェクトのグラフで最大クリークを見つけるためのアプリケーションの開発に取り組んでいます。私はほとんどのプロジェクトを完了し、アプリケーションのテストを開始したばかりです。

アプリケーションは現在、隣接リストを入力として使用していますが、誰かが隣接リストのランダムジェネレーターを知っているかどうか疑問に思っていたので、アプリケーションをテストできますか？

どうもありがとう

Answer 1

隣接リストではなく隣接行列の観点からグラフを考えると、この問題に対処するのははるかに簡単です。頂点のあるグラフは、行列でm表すことができます。各エッジは、存在しない場合は0、存在する場合は1です。mm

有向グラフの場合はすべての要素が必要ですが、無向グラフの場合は上三角行列が必要です。

隣接行列を取得したら、それを隣接リストに簡単に変換できます。

Answer 2

ランダムグラフモデルによって異なります。最も単純なモデルはErdős–Rényiモデルで、ノードの数と任意のペア間のリンクの確率を指定します。これは簡単に生成できますが、実際の世界で観察されるほとんどのネットワークとはまったく類似していないため、結果のグラフはあまり面白くありません。実世界のネットワークには通常、べき乗則の次数分布とより高いクラスタリング係数があります。これに対処するために興味があるかもしれない他のいくつかの標準モデルがあります（Watts-StrogatzまたはBarabási-Albert）。また、このペーパーで説明されているLFRモデルを使用しました。このモデルには、ここで入手可能なソースコードがあります。