大規模な実稼働サーバーに BGL を使用している人はいますか?
誰かがこの問題を解決する方法について簡単に話すことができますか. 私の心を開いて、私にインスピレーションを与えてください。
これまでのところ、2 つのノードが 1 つの島 (コミュニティ内) にあるかどうかを最も安価な方法で解決することができましたが、別の島にあるどの 2 つのノードが互いに最も近いかを判断する必要があります。信頼できない地理データは最小限しか使用できません。
それを比喩的に本土と島と比較し、社会的距離の文脈から外すと. 私は、水域を横切って最も接近している 2 つの土地を特定したいと考えています。
何百万ものノードを持つグラフに BGL を使用しましたが、使用できるグラフのサイズは、実行しようとしているアルゴリズムによって異なります。ノード間の距離をすばやく計算できます。データに応じて最も適用可能な 4 つの最短経路アルゴリズムがあります: (点の単一のペア、点のすべてのペア、疎グラフと密グラフ、...)。
コミュニティの検出に関しては、特に BGL に組み込まれているアルゴリズムはありません (ただし、プロジェクトが終了したら貢献できるかもしれません)。コミュニティ検出アルゴリズムの構築に役立つアルゴリズムがいくつかあります。max-flow/min-cutアルゴリズムは通常、コミュニティの検出に使用されます( 2 つのノード間で多くのフローが可能である場合、それらは同じコミュニティにある可能性が高く、あまりフローがない場合、最小-cut はコミュニティ間の道路を表す可能性が高い)。グラフのノードを並べ替えて帯域幅を削減するためのヒューリスティックもあります。「コミュニティ」を構成するノードは、このような順序で互いに近接している可能性があります。
私の知る限り、BGL にはコミュニティ検出専用のアルゴリズムはありません。
「島」とは、切断されたサブグラフを意味しますか?
また、グラフには「距離」という概念がありません。
この「社会的距離」は、あなたが定義しなければならないものです。ここまでできれば、作業の大部分は完了です。
リンク先のページには多数の方法がリストされていますが、それらのほとんどでは、「距離」メトリックのようなものを定義し、定義をアルゴリズムにプラグインするだけで済みます。
@デビッド・ネーメ
エッジ ウェイトのないグラフは、接続性のみを考慮したものであり、距離の概念はありません。ネットワークについて話したい場合は、距離について話すことができます。ただし、エッジの重みを持たないグラフには、すべてのエッジの暗黙のエッジの重みを 1 と仮定しない限り、距離はありません。しかし、これは実際にはグラフをネットワークに変えているだけです。
また、彼は 2 つの切断されたグラフ間の距離についても話しています。これをモデル化するには、エッジ距離とは別に、ノード間の距離の外部概念を導入する必要があります。