图算法/寻找破坏图形的最节点的两个节点

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。

自从发表这些论文以来，还提出了更多的方法。只是谷歌主要球员社交网络。