Boost圖庫：有沒有內置BGL社區檢測一個整潔的算法？

Question

人在那裏使用BGL大型生產服務器？

• 多少節點沒有網絡組成的呢？
• 你如何處理community detection
• BGL有沒有很酷的方式來檢測社區？
• 有時兩個社區可能一起通過一個或兩個邊鏈接，但這些邊緣是不可靠的，可以消失。有時根本沒有邊緣。

可能有人對如何解決這一問題上作簡短髮言。 請打開我的腦海，激勵我。

到目前爲止，我已經成功地制定出如果兩個節點是在一個小島上（在社區）的，以免昂貴的方式 ，但現在我需要找出其中的不同海島兩個節點彼此最接近。我們只能最小限度地使用不可靠的地理數據。

如果我們形象地把它比作一個大陸和島嶼，並把它拿出來的社會距離上下文。我想弄清楚哪兩塊土地在一個水體中最接近。

Answer 1

我已經將BGL用於具有數百萬個節點的圖形，但是您可以使用的圖形大小取決於您嘗試運行的算法。您可以快速計算節點之間的距離。根據您的數據，有4種最短路徑算法是最適用的：（單對點，對於所有點對，稀疏和密集圖，...）。

至於社區檢測，沒有任何專門針對BGL的算法（但也許您在完成項目時可以貢獻一個算法）。有幾種算法可能有助於構建社區檢測算法。max-flow/min-cut算法通常用於社區檢測（如果兩個節點之間可能存在大量流量，那麼它們可能位於同一個社區中，如果沒有多少流量，則最小切割可能代表社區之間的道路）。還有一些啓發式命令來排列圖的節點以減少bandwidth。構成「社區」的節點可能在這樣的排序中彼此接近。

Answer 2

據我所知BGL沒有任何算法專門爲社區發現。

通過「孤島」你的意思是斷開的子？

此外，圖形不具有「距離」的任何概念。

這種「社會距離」是，你將不得不定義的東西。一旦你完成了大部分工作就完成了。

有你鏈接到頁面上列出的多種方法，其中大多數的只需要你定義有點像「距離」的度量，然後把你定義成算法。

@大衛Nehme

圖表沒有邊緣的權重只有大約連通，他們沒有距離的概念。如果你想談論一個網絡，那麼你可以談論距離。但是沒有邊權重的圖沒有任何距離，除非你想假設所有邊的隱含邊權重爲1。但這只是將圖形變成網絡。

而且，他是在談論兩個不圖之間的距離。爲了對此進行建模，必須引入節點間距離的外部概念，與邊緣距離分開。