在圖中查找得分最高的一對節點。

我試圖解決一個優化問題，我想在圖中找到兩個節點的影響/重要性最高的組合。比方說，我想根據中介中心（卑詩省）。我想更明智的做法是選擇一個節點（也許一個具有高BC），然後計算生成的網絡的BC，然後刪除具有BC最高值的節點。我的目標是生成從原始圖形中刪除的最高得分節點組合的列表。我已經實現了一個簡化的方法來挑選出隨機節點，如果分數高於前一個分數，那麼這兩個節點中的一個將在下一個組合中重用。我不確定這種方法是否足夠好，如果代碼會在本地最優組合中「卡住」。任何指引我指引正確的方向將不勝感激。在圖中查找得分最高的一對節點。

來源

2017-06-26 user1171426

爲了確定你有最高的一對，測試他們。除非您的數據非常寬容，否則這可能會顯示您的算法卡住了，正如您所建議的 - 獸的性質。 –

是的，問題是與一個大尺寸圖是我然後需要運行一箇中心性算法N *（N-1）次，因爲它像N *（N-1）/ 2獨特的組合，也許我需要運行它每個組合兩次。所以我很希望這是一個優化的替代方案，只有這些組合的一小部分被計算出來。 – user1171426

除非您可以利用的圖形和/或功能的屬性，否則必須檢查所有對以確保找到最大值。

來源

2017-06-26 13:06:39

已經提出了幾種近似中介中心度計算算法。

你的通用方法是很好的，這是有點類似於通過採樣 [Riondato，Kornaropoulos] 2015年here here在中介中心的快速近似時使用的一個。

引用：

「自從在大型網絡精確計算是非常昂貴的，我們提出了介估計兩臺高效隨機化算法的算法是基於隨機採樣的最短路徑並提供概率保證第一個算法估計所有頂點（或邊）的中間性：所有近似值都在實數值附加因子ε∈（0,1）內，其概率爲最少1 - δ。第二種算法側重於最高的前K頂點（或邊）並且將它們的中間值估計到乘法因子ε內，概率至少爲1-δ。這是第一種可以計算頂K頂點（或邊）的近似算法。「

用於兩種算法的時間複雜度是O（R *（| E | + | V |登錄| V |）），其中r爲樣本大小（它決定了精度）

。他們的第二個算法是對你的使用情況很有關係（K = 2）：

「這是一個可以計算這種近似頂部-K頂點（或邊緣）的第一算法」。

來源

2017-07-08 05:31:40

在圖中查找得分最高的一對節點。

回答

相關問題