Boost Graph Library：コミュニティ検出のためにBGLにきちんとしたアルゴリズムが組み込まれていますか？

Question

大規模な本番サーバーにBGLを使用している人はいますか？

• ネットワークはいくつのノードで構成されていますか？
• コミュニティの検出
• BGLにはコミュニティを検出するクールな方法がありますか？
• 2つのコミュニティが1つまたは2つのエッジでリンクされている場合がありますが、これらのエッジは信頼性が低く、消えてしまう可能性があります。エッジがまったくない場合もあります。

誰かがこの問題を解決する方法について簡単に話してもらえますか。 心を開いてインスピレーションを与えてください。

これまでのところ、2つのノードが（コミュニティ内の）島にある場合、うまく処理できました。 それほど高価ではありませんが、今では、別々の島にある2つのノードが互いに最も近いかどうかを調べる必要があります。信頼できない地理データを最小限にしか使用できません。

これを比main的に本土および島と比較し、社会的距離の文脈から除外する場合。どちらの土地が水域全体で最も近いかを調べたいと思います。

Answer 1

数百万のノードを持つグラフにBGLを使用しましたが、使用できるグラフのサイズは、実行しようとしているアルゴリズムによって異なります。ノード間の距離をすばやく計算できます。データに応じて最も適切な4つの最短パスアルゴリズムがあります（単一のポイントペア、すべてのポイントペア、スパースグラフとデンスグラフなど）。

コミュニティの検出に関しては、BGLに特別に組み込まれたアルゴリズムはありません（ただし、プロジェクトの終了時に貢献できる可能性があります）。コミュニティ検出アルゴリズムの構築に役立ついくつかのアルゴリズムがあります。 max-flow / min-cut アルゴリズム通常、コミュニティ検出で使用されます（2つのノード間で多くのフローが可能な場合、それらは同じコミュニティ内にある可能性が高く、あまりフローがない場合、最小カットはコミュニティ間の道路を表す可能性があります）。 を減らすために、グラフのノードを順序付けるための発見的方法もあります。帯域幅。 「コミュニティ」を構成するノードこのような順序で互いに近くなる可能性があります。

Answer 2

私が知る限り、BGLにはコミュニティ検出専用のアルゴリズムはありません。

「島」別切断されたサブグラフのことですか？

また、グラフには「距離」という概念がありません。

この「社会的距離」は、定義しなければならないものです。これが完了すると、作業の大部分が完了します。

リンク先のページには多数のメソッドがリストされていますが、それらのほとんどは「距離」メトリックのようなものを定義してから、定義をアルゴリズムにプラグインするだけです。

@ David Nehme

エッジの重みのないグラフは接続性に関するものであり、距離の概念はありません。ネットワークについて話したい場合は、距離について話すことができます。ただし、すべてのエッジに対して暗黙のエッジウェイト1を想定しない限り、エッジウェイトのないグラフには距離がありません。しかし、これはまさにグラフをネットワークに変えているだけです。

また、彼は2つの切断されたグラフ間の距離について話している。これをモデル化するには、エッジ距離とは別に、ノード間の距離に関する外部概念を導入する必要があります。