2

重み付けされていないグラフのすべてのノードのBetwennessCentralityを計算するプログラムを作成しています。そのためには、ASSSP（All Single Source Shortest Paths）を見つける必要があります。プログラムを作成しているうちに、最終的には結びつきがあることに気づきました（ソースから宛先までの距離は同じですが、パスは異なります）。これは私をこの質問に導きました。これらの関係をどのように解決する必要がありますか？ランダムなタイブレーカーを使用する場合、Betweenness Centralityの各出力は、同じ入力に対してわずかに異なる可能性があります。小さな模範的なグラフを作成しましょう。

   A
  / \
B    C
  \ /
   D

ここで、AノードがASSSPを検索するソースであるとしましょう。2つのパス（A->B->DとA->C->D）が存在し、それらのボットは同じ長さであり、両方とも最短のものであることがはっきりとわかります。今、私はどれを選ぶべきですか、そしてどのような条件で？

ランダムタイブレーカー（問題）

最初に見つかったようなランダムなタイブレーカーを使用すると、最短パスとしてマークされます（プログラムは配布されるため、このソリューションはランダムに機能します）。次に、ノードBとCで値が異なるため、BetweennessCentralityに問題が発生します。どのパスが最短としてマークされたかによって異なります。

誰かがこの問題を解決する方法を知っていますか、それとも私は何かが足りないだけですか？

4

3 に答える 3

1

中間中心性を適切に計算するには、グラフ内のすべての最短経路を考慮する必要があります。2つのノードAとBの間にk個の最短経路がある場合、各最短経路は、パスが通過するノードの合計中間スコアに1/k貢献します。一般に、ネットワーク内のすべての最短パスを実際に見つけて（そして保存して）、中間中心性を計算するべきではありません。より効率的なアルゴリズムについては、次の論文を参照してください。

中間中心性のためのより高速なアルゴリズム

于 2012-07-11T18:20:51.273 に答える
0

はい、SSSP、または単一ソース最短経路は、コンピュータサイエンスで非常に一般的な問題です。標準的な方法の1つは、最初に遭遇したパスが、同じ距離にある他のパスよりも短いことです。

たとえば、あなたの例では、A->B->D以前A->C->Dに処理したアルゴリズムA->B->Dで、が最短経路になります。

それでも不明な点がある場合は、ダイクストラのアルゴリズムがあなたの求めているものだと思います。

于 2012-07-11T16:08:11.473 に答える
0

お気づきの問題が原因で、Betweenness Centralityは、ソースとターゲットの間の1つのパスだけを調べることによって実際に計算されるのではなく、最短パスの数を数えることによって計算されます。これには、適切な最短経路アルゴリズムを変更する必要があります。たとえば、Floyd–WarshallアルゴリズムやJohnsonのアルゴリズムなどです。

于 2012-07-11T17:47:49.523 に答える