中規模のグラフ(570ノード、69127辺、密度:g42形式の0.42)を持ち、Nより大きい(例えば5)すべてのクリークを列挙したいと思います。最も効率的な方法は何ですか?私は一般的な言語やソフトウェアパッケージでライブラリを探しています。中規模グラフのクリーク列挙
答えて
SNAP network analysis libraryを使用できます。これは、Tomita et al。 2006アルゴリズム。他のすべての理論的に高速のアルゴリズムは、Tomitaらよりも著しく遅いことが示されている。実際には、少なくとも疎なグラフの場合(Eppstein et al。2010)。
もしそのアルゴリズムが大きなグラフのためにあまりにも多くのメモリを必要とするならば、Eppsteinらの線形空間アルゴリズムを試すことができます。 2010/2011
富田(富田)E。全ての最大クリークを生成するための最悪の場合の計算量および計算実験。理論コンピュータ科学、2006,363,28-42。DOI:10.1016/j.tcs.2006.06.015
Eppstein、D .; Löffler、M. & Strash、D. Cheong、O.最適に近い時間にスパースグラフのすべての最大クリークをリストアップする。 ISAAC '10:Proc。第21回アルゴリズムと計算に関する国際シンポジウム、Springer Berlin/Heidelberg、2010、6506、403-414 DOI:10.1007/978-3-642-17517-6_36
Eppstein、D. & Strash、D.大きなスパースの実世界グラフのすべての最大クリークをリストアップします。 SEA'11:Proc。第10回実験アルゴリズムに関する国際シンポジウム、Springer Berlin/Heidelberg、2011、6630、364-375 DOI:10.1007/978-3-642-20662-7_31
その目的を達成できるSNAPの機能はどれですか? 'cliques.h'の' GetMaxClique'関数はノードベクトル内に一つのクリークしか出力しません。すべてのクリークを出力できるのはどの機能ですか? – user3813057
- 1. 中規模大規模プロジェクトの構造
- 2. 列挙グラフ
- 3. 適切な大規模な列挙型デザイン
- 4. 列挙型の中の列挙型
- 5. 中規模の配列の相互相関
- 6. セグメンテーションフォールト、大規模配列
- 7. LINQと正規列挙
- 8. 大規模なperlの配列のスローダウン
- 9. DTOの列挙型命名規則
- 10. 中規模の関数を効率的に並列に適用する方法
- 11. 大規模なPHP配列ページ設定
- 12. 大規模なネットワーク反復 - 並列性?
- 13. 最大、最大クリーク
- 14. エンタープライズ規模のDDD?
- 15. omniauth-twitterでTwitterから中規模または大規模のプロフィール画像を取得する
- 16. 実行中の多数の(!)小規模クエリの影響
- 17. 中小規模のプロジェクトのためのFlaskフレームワーク
- 18. config.rbとpagesの中規模変数の可視性
- 19. 小中規模のWebサイトのPHP簡単キャッシングテクニック
- 20. 中規模のAndroidアプリケーションの構築が非常に遅い
- 21. Sybase:大規模データベースから小規模データベースへのダンプ/ロード
- 22. 中規模のMVCアプリケーションを設計する方法
- 23. 小規模コレクションの中で最も速い並べ替え
- 24. 大規模なSVGレンダリング中のDOM操作
- 25. node.jsは中規模/大規模なビジネスWebアプリケーションに対応していますか?
- 26. Odoo大規模デプロイ
- 27. 大規模算術
- 28. 大規模マルチテナントプログラマブルCMS?
- 29. 小規模なスルーリクエストデータストレージ
- 30. Snap.svg規模とSVG
ブーストグラフライブラリで検索してください。 –