ブランデスのアルゴリズム

ブランデスのアルゴリズム

各頂点の媒介中心性に基づいて、最小 (赤) から最大 (青) まで色分けされた無向グラフ。
クラス	中心性 ネットワーク理論
データ構造	連結グラフ
最悪の場合の パフォーマンス	${\displaystyle O(|V||E|)}$(加重なし) (加重あり) ${\displaystyle O(|V||E|+|V|^{2}\log |V|)}$
最悪の場合の 空間複雑度	${\displaystyle O(|V|+|E|)}$

ネットワーク理論において、ブランデスのアルゴリズムはグラフの頂点の媒介中心性を計算するアルゴリズムである。このアルゴリズムは2001年にウルリック・ブランデスによって初めて発表された。^{[1]媒介中心性は、}中心性の他の尺度とともに、ソーシャルネットワークやコンピュータネットワークなど、多くの現実世界のネットワークにおいて重要な尺度である。^{[2] [3] [4]}

ノードの中心性 にはいくつかの指標があり、その1つが媒介中心性である。^[5]連結グラフ内のノードの場合、媒介中心性は次のように定義される。^{[6] [7]}${\displaystyle v}$

${\displaystyle C_{B}(v)=\sum _{s\in V}\sum _{t\in V}{\frac {\sigma _{st}(v)}{\sigma _{st} }}}$

ここで、 はノード からノード までの最短経路の総数であり、は を通過するこれらの経路の数です。重み付けされていないグラフの場合、経路の長さは、経路に含まれるエッジの数であると考えられます。 ${\displaystyle \sigma_{st}}$${\displaystyle s}$${\displaystyle t}$${\displaystyle \sigma _{st}(v)}$${\displaystyle v}$

慣例により、の場合は常に となります。唯一のパスは空のパスだからです。また、の場合はまたは となります。最短パスはエンドポイント を通過しないためです。${\displaystyle \sigma_{st}=1}$${\displaystyle s=t}$${\displaystyle \sigma _{st}(v)=0}$${\displaystyle v}$${\displaystyle s}$${\displaystyle t}$

数量

${\displaystyle \delta _{st}(v)={\frac {\sigma _{st}(v)}{\sigma _{st}}}}$

はのペア依存性として知られ、を経由する最短経路の割合を表します。媒介中心性は、すべてのペアにおけるペア依存性の合計です。ペア依存性と同様に、特定の頂点 に関して の(単一の) 依存性を定義することも便利です。${\displaystyle st}$${\displaystyle v}$${\displaystyle s}$${\displaystyle t}$${\displaystyle v}$${\displaystyle v}$${\displaystyle s}$

${\displaystyle \delta _{s}(v)=\sum _{t\in V}\delta _{st}(v)}$、

これにより、簡潔な定式化が得られる。

${\displaystyle C_{B}(v)=\sum _{s\in V}\delta _{s}(v)}$。

Brandes のアルゴリズムは、グラフ内のすべてのノードの媒介中心性を計算します。すべての頂点に対して2 つの段階があります。 ${\displaystyle s}$

と各頂点の間の 最短経路の数は、幅優先探索を使って計算されます。幅優先探索は から始まり、からの各頂点の最短距離が記録され、グラフが離散的な層に分割されます。さらに、各頂点は、その頂点を指す前の層にある頂点の集合 を追跡します。集合構築記法で記述すると、次のように記述できます。${\displaystyle \sigma_{sv}}$${\displaystyle s}$${\displaystyle v}$${\displaystyle s}$${\displaystyle d(v)}$${\displaystyle s}$${\displaystyle v}$${\displaystyle p(v)}$

${\displaystyle p(v)=\{u\in V\mid (u,v)\in E\land d(u)+1=d(v)\}}$。

これは、次の簡単な反復式に役立ちます。${\displaystyle \sigma_{sv}}$

${\displaystyle \sigma _{sv}=\sum _{u\in p(v)}\sigma _{su}}$、

これは本質的に、 が深さ にある場合、への単一の辺によって延長された深さ にある任意の最短経路はへの最短経路になる、ということを述べています。 ${\displaystyle v}$${\displaystyle d(v)}$${\displaystyle d(v)-1}$${\displaystyle v}$${\displaystyle v}$

ブランデスは頂点依存性について次の再帰式を証明した: ^[1]

${\displaystyle \delta _{s}(u)=\sum _{v\mid u\in p(v)}{\frac {\sigma _{su}}{\sigma _{sv}}}\cdot (1+\デルタ _{s}(v))}$、

ここで、合計はより1 辺だけ離れたすべての頂点に対して行われます。この補題により、ペアの依存関係をすべて明示的に合計する必要がなくなります。この式を使用すると、深さ の頂点に対するの単一の依存関係は、深さ の層によって決定されます。さらに、合計の順序は無関係であるため、最も深い層からボトムアップのアプローチを開始できます。 ${\displaystyle v}$${\displaystyle s}$${\displaystyle u}$${\displaystyle s}$${\displaystyle u}$${\displaystyle d(u)}$${\displaystyle d(u)+1}$

の他のすべての頂点への の依存性は、時間内に計算できることがわかります。幅優先探索中、頂点が訪問される順序はスタック データ構造に記録されます。次に、バックプロパゲーション ステップで、 からの距離によって降順に自然にソートされた頂点が繰り返しポップオフされます。 ${\displaystyle s}$${\displaystyle u}$${\displaystyle O(|E|)}$${\displaystyle s}$

ポップされた各ノードについて、その前のノードを反復処理します。つまり、への寄与が追加されます。${\displaystyle v}$${\displaystyle u\in p(v)}$${\displaystyle v}$${\displaystyle \delta _{s}(u)}$

${\displaystyle {\frac {\sigma _{su}}{\sigma _{sv}}}\cdot (1+\delta _{s}(v))}$。

重要なのは、幅優先探索の性質上、各層は依存関係を完全に伝播してから、より低い深さの層に移動することです。伝播が に戻ると、すべての頂点にが含まれるようになります。これらは に簡単に追加できます。${\displaystyle s}$${\displaystyle v}$${\displaystyle \delta _{s}(v)}$${\displaystyle C_{B}(v)}$

${\displaystyle C_{B}(v)=\sum _{s\in V}\delta _{s}(v)}$。

単一ソース最短経路とバックプロパゲーションの反復後、それぞれにの媒介中心性が含まれます。 ${\displaystyle |V|}$${\displaystyle C_{B}(v)}$${\displaystyle v}$

次の疑似コードは重み付けされていない有向グラフ上のブランデスのアルゴリズムを示しています。^[8]

アルゴリズムBrandes( Graph )は、
    Graph.Vertices内の各 u に対して
        CB[ u ] ← 0を実行します。  

     Graph.Vertices内の各sに対して、  Graph.Vertices内の各vに対して、 
            δ[ v ] ← 0 を実行します // s の v への単一依存関係  
            
            prev[ v ] ← 空のリスト // BFS中のvの直前の要素
            σ[ v ] ← 0 // sからvへの最短経路の数（sは暗黙的）
            dist[ v ] ← null              // 最初はパスは不明です。
        σ[ s ] ← 1 // 開始頂点を除く
        dist[ s ] ← 0

        Q ← sのみを含むキュー    // 幅優先探索
        S ← 空のスタック // 頂点が訪問された順序を記録する

        //単一ソースの最短経路

         Qが空でない間にu ← Q .dequeue()
             S .push( u )を実行します。
            

             Graph.Neighbours [ u ]の各v に対して、 dist[ v ] = nullの場合、 
                    dist[ v ] ← dist[ u ] + 1
                     Q .enqueue( v )
                を実行し、 dist[ v ] = dist[ u ] + 1の場合、 
                    σ[ v ] ← σ[ v ] + σ[ u ]を実行します。 
                 
                    前[ v ].append( u )

        //依存関係の逆伝播

         Sが空でない間、v ← S .pop()を実行します。
            

             prev[ v ]の各u に対して
                δ[ u ] ← δ[ u ] + σ[ u ] / σ[ v ] * (1 + δ[ v ])を実行します。

                 u ≠ s の場合CB 
                    [ v ] ← CB[ v ] + δ[ v ] // 無向グラフの場合は半分になる

    CBを
返す

アルゴリズムの実行時間は、頂点の数と辺の数で表されます。 ${\displaystyle |V|}$${\displaystyle |E|}$

各頂点 に対して、時間のかかる幅優先探索を実行します。グラフは連結されており、辺の数は少なくとも であるため、コンポーネントは項 を包含します。 ${\displaystyle s}$${\displaystyle O(|V|+|E|)}$${\displaystyle |E|}$${\displaystyle |V|}$${\displaystyle |V|-1}$

バックプロパゲーションの段階では、すべての頂点がスタックから取り出され、その前の頂点が反復処理されます。ただし、前の頂点の各エントリはグラフ内のエッジに対応するため、この段階も によって制限されます。 ${\displaystyle O(|E|)}$

したがって、アルゴリズム全体の実行時間は となり、従来のアルゴリズムで達成された時間制限よりも改善されています。^[1]さらに、ブランデスのアルゴリズムは、通常スペースを必要とする単純なアルゴリズムの空間計算量を改善しています。ブランデスのアルゴリズムは、各頂点のデータとともに最大で先行データのみを保存するため、余分な空間計算量は${\displaystyle O(|V||E|)}$${\displaystyle O(|V|^{3})}$${\displaystyle O(|V|^{2})}$${\displaystyle |E|}$${\displaystyle O(|V|+|E|)}$

このアルゴリズムは、幅優先探索の代わりにダイクストラ法を使うことで重み付きグラフに一般化できる。無向グラフを操作する場合、各パスの逆の対応を二重にカウントすることを避けるために、媒介中心性を2で割ることがある。また、最大長さのパスの媒介性、辺の媒介性、負荷の媒介性、応力の媒介性など、さまざまな中心性の尺度を計算するバリアントも存在する。^[8]${\displaystyle k}$