圖算法/尋找破壞圖形的最節點的兩個節點

Question

我試圖開發一種從圖形中刪除兩個節點時檢索破壞性度量的方法。到目前爲止，我正在執行一系列算法，比如多重度量的度量，度量，PageRank等。 顯而易見，它可以通過實際移除兩個節點然後分析結果圖（或圖的集合）來完成，但這是當兩個節點有O（N^2）個組合時也是耗時的。 任何幫助引導我在正確的方向，將不勝感激。

Answer 1

我想你要找的是KPP-Neg問題（關鍵球員問題）。

它是根據網絡依賴其關鍵參與者維持凝聚力的程度來定義的。這是一個「負面」問題，因爲它測量的是網絡內聚性的減少量，如果節點不存在，則會發生這種情況。

（與KPP-Pos問題相反，您需要尋找一組網絡節點，這些網絡節點可以快速分散信息，態度，行爲或商品）。

兩個KPP的問題是在The key player problem [Borgatti，2003; Identifying sets of key players in a network [Borgatti，2006]定義。另見「主要參與者」 - Yves Zenou的討論here。

自從發表這些論文以來，還提出了更多的方法。只是谷歌主要球員社交網絡。