グラフの中で最も影響度が大きい2つのノードの組み合わせを見つけたいという最適化問題を解決しようとしています。私はこれを基底中心（BC）に基づいていきたいとします。より賢明なアプローチは、1つのノード（おそらくBCが高いノード）を選択し、その結果のネットワークのBCを計算し、BCの値が最も高いノードを削除することです。私の目標は、元のグラフから取り除かれたときにノードの最高得点の組み合わせのリストを生成することです。私はランダムなノードを選ぶ簡略化された方法を実装しました。もしスコアが以前のものよりも高い場合、2つのノードのうちの1つが次の組み合わせで再利用されます。私は、このアプローチがコードがローカルの最適な組み合わせに「詰まる」のであれば十分であるかどうかはわかりません。 正しい方向に私を操縦するためのあらゆる指針が評価されます。グラフ内のノードの最高得点ペアを見つけます。
悪用できるグラフや機能のプロパティがない限り、最大値が見つかるようにすべてのペアをチェックする必要があります。
いくつかの近似性中心性計算アルゴリズムが提案されている。
あなたの一般的な方法は良好であり、サンプリング [Riondato、Kornaropoulos] 2015 herehereを通して媒介中心の高速近似で使用されるものと幾分類似しています。
引用：
を「大規模ネットワークでの正確な計算は非常に高価であることから、 我々は間隔度 推定のための2つの効率的な乱択アルゴリズムを提示するアルゴリズムは、最短 パスのランダムサンプリングに基づいており、確率的保証を提供しています。 近似[...]第1のアルゴリズムは、すべての頂点（または辺）の奥行きを推定します。すべての近似値は、実数値からの加算係数ε∈（0,1）内にあり、少なくとも1-δであり、第2のアルゴリズムは、最高の頂点（またはエッジ）に焦点を当て、トゥイーンネスを計算し、それらの中間値を乗法因子ε内に推定し、確率は少なくとも1 - δである。これは、トップK頂点（またはエッジ）についてのそのような近似を計算することができる最初のアルゴリズムである。 「両方のアルゴリズムの
時間複雑度は、O（| E | + | V |ログイン| V | R *（））である。Rは（精度を決定する）、サンプルサイズで、
その第2のアルゴリズムは、ユースケースのために非常に適切である（K = 2）：
「これはトップKの頂点（またはエッジ） このような近似を計算することができる最初のアルゴリズムである。」
あなたが一番高いペアを持っていることを確認するには、それらをすべてテストしてください。あなたのデータが非常に寛容でない限り、これはおそらくあなたのアルゴリズムがスタックしていることを示すでしょう、あなたが示唆するように - 獣の性質。 –
ええ、問題は大きなサイズのグラフで、N *（N-1）/ 2個のユニークな組み合わせのようなもので、おそらく実行する必要があるため、中心性アルゴリズムN *（N-1）回実行する必要があるということです組み合わせごとに2回。だから私は、これらの組み合わせのほんの一部しか計算されない最適化の代替策であると考えていました。 – user1171426