グラフを最も混乱させる2つのノードを見つけるためのグラフアルゴリズム/アプローチ

Question

グラフから2つのノードを削除するときに、破壊の尺度を取得する方法を開発しようとしています。これまでは、中央、度、ページランクなどの複数の測定値のようなアルゴリズムのコレクションを実行しています。 実際には2つのノードを削除し、結果のグラフ（またはグラフの集合）を分析することによって行うことができます。 2つのノードの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」も参照してください。

これらの論文が発表されて以来、もっと多くのアプローチが提案されました。ただgoogle 主要プレーヤーソーシャルネットワーク。