bfs : Breath First Search

幅優先探索（Breadth-First Search: BFS）は、探索元の頂点を始点とする探索順序である。BFSは次の深さに移る前に、現在の深さ（ソース頂点からの距離）にあるすべての頂点を走査する。BFSは非常に基本的なものであるため、他のグラフアルゴリズムでは暗黙のうちに使われていることが多い。我々は、グラフ500[14]のように、探索中に親頂点を追跡することで、BFSをカーネル化する。どの到達頂点に対しても、複数の親頂点が存在する可能性がある。なぜなら、到達頂点よりも深さが1小さい隣接頂点がその親頂点になる可能性があるからである。複数の合法的な親頂点があると、与えられたソース頂点からのBFSの正しい解が複数存在することになる。このため、あるソース頂点から始まるBFSの正しい解を、以下を満たす親配列と定義する：
- parent[source] = source
- vがソースから到達不可能な場合、parent[v] = -1
- vが到達可能でparent[v] = uの場合，uからvへの辺が存在する．
- もしvが到達可能でparent[v] = uなら、depth[v] = depth[u] + 1である。
BFSの使い方によっては、到達可能性や深さだけを追跡するものもあるが、我々は、親を追跡することを選択する。その代わりに到達可能性を追跡することにした場合、到達可能性は各頂点に対してブール値を返すだけなので、探索が幅優先の方法で実行されたことを検証する方法はない。しかし、深さを追跡するBFSの実装は、親を追跡するBFSのより困難なアプリケーションでは不可能な最適化を実行することができる[23]。

SSSP: Single-Source Shortest Paths

単一始点最短経路（Single-Source Shortest Paths: SSSP）は、与えられた始点から他の到達可能な頂点までの最短経路の距離を計算する。2つの頂点間の距離は、2つの頂点を結ぶパスに沿った辺の重みの最小和である。親頂点はBFSが既に提供しているので、我々は求めない。解は距離であり、最短経路そのものではないからである。

2つの頂点間に複数の最短経路があっても、すべての最短経路の距離は同じである。我々のベンチマーク・グラフは全て正の辺の重みを持つ。SSSPの正しい解を、以下のようなソース頂点からの距離配列と定義する：

distance[source] = 0
vがソースから到達不可能な場合、distance[v] = ∞ (または既知のセンチネル値)
vがソースから到達可能な場合、ソースからvへの結合重みdistance[v]のパスが存在する。
vがソースから到達可能な場合、ソースからvまでdistance[v]よりも小さい結合重みのパスは存在しない。

Page Rank (PR)

PageRank (PR)は、グラフ内のすべての頂点のPageRankスコアを計算する。減衰係数d(0.85)を持つ頂点vのスコア( $PR$ )は次のようになる：

$PR(v) = \dfrac{1-d}{|V|} + d\sum_{u\in N-(v)}\dfrac{PR(u)}{|N+(u)|}$

PRについては、1回の追加反復ですべての頂点のPageRankスコアの合計が $10^{-4}$ より小さく変化するような頂点のPageRankスコアが必要である。より正式には、ベンチマーク・カーネルがスコア $PR_k$ を返し、古典的な実装が $PR_k$ から1回の反復で $PR_{k+1}$ を生成する場合、解が公差に従うなら正しい：

[tex: \sum{v\in V} PR{k}(v)-PR_{k+1}(v) <10^{-4} ]

必要な公差の選択は、スコアの収束性と実行時間のトレードオフである。

スコアがほとんど収束し、ほとんどのグラフで妥当な反復回数(5～20回)になるので、実用的に $10^{-4}$ を選択する。この許容範囲は、累積順序の違いによる多少の数値ノイズを暗黙のうちに許容するものでもある。この許容範囲を満たし、グラフの変更や前処理の最適化が試行時間に含まれる限り、より高度な実装も許容する。

Connected Components (CC)

連結成分(CC)は、すべての頂点をその連結成分によってラベル付けし、各連結成分にはそれぞれ固有のラベルが割り当てられる。グラフが有向グラフの場合、必要なのは弱連結成分しか必要としないので、2つの頂点が同じ連結成分にある場合、グラフの辺を無向性と解釈すれば、2つの頂点間にパスがあるのと同じことになる。次数ゼロの（切断された）頂点は、それぞれ独自のラベルを得るべきである。正しさを定義するには、次の等価関係が必要である：

uとvの間に無向パスが存在する場合に限り、頂点uとvは同じ成分ラベルを持つ。

Betweenness Centrality (BC)

BC(Betweenness Centrality)は、頂点の部分集合からの最短パスのみを計算することで、グラフ内のすべての頂点のbetweenness Centralityスコアを近似する。頂点vのbetweenness centralityは、その頂点を通る最短パスの割合と定義される。 [tex: \sigma{st}] を頂点 $s$ と $t$ 間の最短パスの数、 [tex: \sigma{st}(v)] を $v$ を通る最短パスの数とすると、vのbetweenness centrality scoreは次のようになる：

[tex: BC(v)=\sum{s,t\in V,s\ne v\ne t } \dfrac{\sigma{st}(v)}{\sigma_{st}}]

近似のために、BCスコアは4つの異なるソースからの最短パスを考慮して計算されるべきである。これらの中心性スコアは1に正規化されるべきである。ほとんどの実装がBrandesアルゴリズム[7]を利用し、4つのBFS探索を実行することを期待するが、Brandesアルゴリズムの利用は必須ではない。BC実装は、すべての入力グラフを重みなしとして扱うべきである。

正しさについては、同じソース頂点を用いた代替アルゴリズムの単純で正しい実装からの出力と比較することを推奨する。この場合、累積は異なる順序で起こり得るので、検証者は多少の数値ノイズを許容する必要があるかもしれない。

Triangle Counting (TC)

三角形カウント（TC）は、グラフ中の三角形の総数を計算する。三角形とは、互いに直接接続された3つの頂点(サイズ3の閥)と定義する。三角形は並べ替えに対して不変であるため、同じ3つの頂点がどのような順序で並べられたとしても、1つの三角形として数えられるべきである。さらに、三角形の定義では辺の方向を無視するので、入力グラフは無向グラフと解釈できる。TCの場合、解は一意なので、結果を比較するのは些細なことである。残念ながら、三角形の総数を実際に計算せずに検証する簡単な方法はない。

検証のためには、ベンチマーク実装の結果と別の実装の結果を比較することを推奨する。

msyksphinz.hatenablog.com