完整和加權網絡中的社區檢測

Question

我確實有一個完整的網絡圖，每個頂點都相互連接，它們只在不同的權重形式上有所不同。一個示例網絡將是：一個貿易網絡，其中每個國家都以某種方式相互連接，並且僅以不同的交易量形式存在差異。

現在的問題是我如何能夠以這種形式的網絡執行社區檢測。通常的嫌疑人（算法）只能在未加權或不完整的網絡中執行。主要問題是測地線無處不在。

兩個選項走進了我的腦海：

1. 剪切網絡成小塊，通過一定的「重量閾值水平」
2. 或者使用聚類算法把整個網絡切斷他們成塊模型。但我認爲「測地術語不會有差異」這個問題仍將存在。

Answer 1

提出了幾種方法。

在Fast unfolding of communities in large networks（Blondel等人，2008）中提出了一種簡單而有效的方法。它支持加權網絡。摘要摘要如下：

我們提出一種簡單的方法來提取大型網絡的社區結構。我們的方法是基於模塊化 優化的啓發式方法。它被證明在計算時間方面優於所有其他已知社區的檢測方法。此外，通過所謂的 模塊化測量，所檢測社區的質量 非常好。

從紙張報價：

我們現在介紹一下我們的算法，發現大型網絡的高度模塊化分區 在很短的時間，並且展現一個完整的 層次社會結構的網絡，從而給 訪問不同的社區檢測解決方案。

所以它應該適用於完整的圖形，但你應該更好地檢查它。

C++實現可用here（現在維護here）。

您的其他想法 - 使用權重閾值 - 可能被證明是一個很好的預處理步驟，特別是對於不會分割完整圖的算法。我相信最好將它設置爲權重的某個百分位數（例如中位數）。