DEIM Forum 2015 E3-4

動的なネットワークにおける媒介中心性の高速計算手法
林

孝紀†

秋葉

拓哉†

吉田

悠一††

† 東京大学大学院情報理工学系研究科コンピュータ科学専攻 〒 113-8654 東京都文京区本郷 7-3-1†† 国立情報学研究所 〒 101–8430 東京都千代田区一ツ橋 2-1-2
E-mail: †{thayashi,t.akiba}@is.s.u-tokyo.ac.jp, ††yyoshida@nii.ac.jp
あらまし

媒介中心性はグラフ上での各頂点の重要さを表し、ソーシャルネットワークの解析などにおいて最も基本的な指標の 1 つである。大規模なグラフにおける媒介中心性の厳密な計算は多大な時間を要するため、多くの近似手法が提案されてきた。特に、ランダムサンプリングに基づくアルゴリズムにより、グラフのサイズに対してほぼ線形の計算時間で高精度な近似値を得られることが知られている。一方、現実のネットワークは時間経過とともに絶えず変化しており、これらのネットワークの特性を解析する上で動的なグラフにおける媒介中心性の計算を効率良く行う
ことは非常に有用である。しかし、既存の近似アルゴリズムのほとんどは静的なグラフに対するものであり、ネット
ワークが変化するたびに最初から媒介中心性の計算をやり直すことは現実的ではない。また、動的なグラフに対する近似手法は少なく、大規模なグラフで動作するアルゴリズムは辺の挿入のみを扱うものしか知られていない。本論文では、動的なグラフにおける辺の挿入と削除の両方に対して、媒介中心性の近似値を効率よく更新していくためのデー
タ構造とアルゴリズムを提案する。実験によって提案手法が高いスケーラビリティを実現することを示した。
キーワード

グラフ, ソーシャルネットワーク, グラフマイニング, 媒介中心性, 動的ネットワーク

1. は じ め にソーシャルネットワーク・ウェブグラフなどの解析において、各頂点の重要度や影響力を定量化することは重要なタスクであクリメンタルな更新を行うためのデータ構造の保持に頂点数の 2 乗に比例する空間を必要とするため、大規模なネットワー
クにおいて十分なスケーラビリティを実現することはできていない。

る。Freeman [6] によって定義された媒介中心性は、頂点の影

Bergamini ら [3] は動的なネットワークにおいて、媒介中心

響力をその頂点が各 2 点間の最短路のうちどれだけ多くの割合

性の近似値をインクリメンタルに計算する手法を初めて提案に含まれているかによって定めた指標であり、ネットワークのした。彼らは百万頂点を超えるネットワークにおいても 1 秒程

解析に盛んに使用されている [1, 8, 9, 16]。

度で媒介中心性の近似値を更新できることを示し、大幅なス

厳密手法の中では Brandes によって提案されたアルゴリズ

ケーラビリティの向上を実現したと言える。しかし、Bergamini

ム [4] が漸近的に高速であることが知られているが、頂点数がら [3] は辺の挿入に対してしか対応しておらず、辺の削除に対n、辺数が m のグラフに対して O(n2 + nm) 時間かかるため大して高速に近似値を更新することはできていなかった。

規模なネットワークに対して厳密な媒介中心性を求めることは

本論文では、辺の挿入・削除の両方が行われるネットワーク

困難である。そのため、高いスケーラビリティを実現するためにおいて媒介中心性の近似計算を行う方法を初めて提案する。

に媒介中心性の厳密な値ではなく近似値を求めるのは自然なア

我々の手法は、ソーシャルネットワーク・ウェブグラフなどがプローチであると言える。特に、ランダムサンプリングに基づ持つスモールワールド性 [15, 20] を利用したデータ構造を構築

く手法はいくつも提案されており [2, 5, 7, 18, 21]、数百万点規することにより、元のグラフサイズとさほど変わらない使用空模のネットワークに対しても現実的な時間で高精度な近似値を間量にも関わらず、辺の挿入・削除の両方に対して高精度な近計算することが可能になっている。

似値のインクリメンタルな計算を数ミリ秒で行うことを可能に一方、現実のネットワークは絶えず変化を繰り返しており、した。計算機実験によって、我々の提案手法は特にソーシャル

辺の挿入・削除といった変化が起こるグラフにおいて媒介中心

ネットワークにおいて効率良く動作し、1.6M 個の頂点と 44M性の計算を行うことは、ネットワークの解析を行う上で有用で本の辺からなるネットワークにおいて、辺の更新・削除の両方ある。そのような更新が高頻度で行われるグラフにおいて、グに対して数ミリ秒で近似値を更新できることを示した。

ラフが更新されるたびに媒介中心性を全て計算し直すのは多大な時間を要するため現実的ではない。
そのため、グラフが更新されるたびに元のグラフに対する媒2. 関 連 研 究
2. 1 静的なネットワークに対する手法

介中心性の値をインクリメンタルに更新することで、再計算を前述したように、厳密に媒介中心性を計算する手法の中で漸避ける方法が [10–13] などで提案されてきた。これらの手法は近的に最も高速なものは Brandes [4] によるアルゴリズムであ厳密な媒介中心性の値の更新を行うことができるものの、インる。このアルゴリズムでは各頂点からの単一始点最短路を計算

し、最短路木を始点から遠い順にたどりながら計算を行うこと

介中心性の近似値を効率良く更新する手法を初めて提案した。

で、その頂点による他の頂点の媒介中心性への寄与を一度に求Riondato ら [18] の手法を元に、Riondato らと同様のサンプ

める。n 個の頂点に対する単一始点最短路を求めることで、重リングをした 2 点間最短路と各最短路の始点を根とする最短

2

みなしグラフにおいて O(n + nm) 時間、重みありグラフにお2路木を保持する。最短路木の情報を用いることで、辺の挿入がいて O(nm + n log n) 時間で厳密な媒介中心性を計算するこ行われた際に 2 点間最短路の距離が変化するかを判定し、更とができる。しかし、頂点数の 2 乗に比例する計算を大規模な新後のグラフに合わせてサンプリングされた 2 点間最短路をグラフにおいて行うことは多大な計算資源を要する。

効率良く更新する方法を提案した。しかし、辺の削除に対してそのため、多くの近似計算手法、特にランダムサンプリング

Bergamini らの手法 [3] は対応することができておらず、各最を用いた媒介中心性の近似計算アルゴリズムが多く提案され短路木に対して O(m + n) の空間が使用されるため、大規模なてきた [2, 5, 7, 18]。Brandes と Pich [5] はグラフの一部の頂

ネットワークにおいて高精度な近似値を計算するには元のグラ

点をサンプリングし、それらに対してのみ単一始点最短路を

フサイズの数百倍以上の空間が必要になる。

求めることで媒介中心性の近似値を推定する方法を提案した。

3. 準

備

リングされた頂点の近くにある媒介中心性が高く見積もられす

3. 1 表記

ぎてしまうことを指摘し、その手法を一般化することで媒介中

本論文ではネットワークを辺に重みのないグラフ G = (V, E)

心性の低い頂点に対しても高い精度での近似を可能にした。まで表す。V はサイズが n の頂点集合であり、E はサイズがた、Bader ら [2] はすべての頂点ではなく、指定された頂点のm の頂点集合である。グラフ G 上の 2 点 u, v ∈ V 間の距

媒介中心性を適応的サンプリングを用いて推定する方法を提案

離を distG (u, v) と書き、u から v へ経路が存在しない場合はGeisberger ら [7] は Brandes と Pich による手法では、サンプした。Riondato ら [18] は頂点ではなく 2 点間最短路をサンプ

distG (u, v) = ∞ とする。s から t への経路が存在するとき、s, t

リングすることにより、媒介中心性を推定する手法と媒介中心の最短路の少なくとも 1 つが通る点の集合を Ps,t と書く。すな

性の上位 k 頂点を推定する方法を提案した。吉田 [21] は適応

わち Ps,t = {v ∈ V | distG (s, v) + distG (v, t) = distG (s, t)}

的に媒介中心性の高い頂点を求めていくための近似手法を提案である。Ps,t に含まれる辺 e ∈ E に対して、s から距離が近い

し、頂点対をサンプリングすることで得られた最短路 DAG か

頂点から遠い頂点へ向くようにすることで、Ps,t を頂点集合と

ら媒介中心性を推定する方法を示した。これらのサンプリング

する有向非循環グラフ (DAG) を得ることができる。以下では、に基づく手法によって高精度な近似値をほぼ線形時間で計算すPs,t をそのような DAG としてみなし、s, t 間の最短路 DAGることが可能になった。

と呼ぶことがある。

2. 2 動的なネットワークに対する手法

3. 2 媒介中心性

動的なネットワークに対する媒介中心性の計算手法は比較的σst で s, t 間の最短路の個数を表し、σst (v) で s, t 間の最短

最近になって研究されるようになってきた。厳密な媒介中心性路のうち v を通る経路の個数を表す。ただし、s = v またはの値をグラフの変化のたびに更新する手法は [10–13] などが知

t = v のとき σst (v) = 0 とする。このとき、グラフ G 上の頂点∑(v)v の媒介中心性は CB (v) = v∈V σstで表される。
σst

られている。Lee ら [13] はグラフを複数の部分グラフに分割して管理し、辺の挿入・削除によって媒介中心性の更新が必要に

3. 3 ハイパーグラフスケッチによる近似

なる頂点集合を限定した。それにより、グラフが更新されたと我々の提案手法は吉田 [21] のハイパーグラフスケッチによる

きに Brandes のアルゴリズム [4] による再計算よりも大幅に速

媒介中心性の近似計算手法をベースとしている。吉田の手法は

く媒介中心性の値を更新することを可能にした。Kas ら [11] は

本来頂点の媒介中心性だけではなく頂点集合の適応的媒介中心

Ramalingam ら [17] による動的グラフにおける全点間最短路の性を求めるために提案されたが、本節では頂点の媒介中心性の更新手法を媒介中心性の更新に拡張することで、Lee ら [13] よ近似に関する部分のみ説明する。

りも 10 倍以上高速な更新を実現した。Green ら [10] は各頂点

3. 3. 1 近似値の推定に対して最短路木を構築し、各最短路木の中で媒介中心性の値与えられたグラフ G = (V, E) に対して、ハイパーグラフスが変化する部分のみ更新することで、辺の挿入が行われるグラ

ケッチ H を構築する方法の概要を Algorithm 1 に示す。まず、

フにおいて媒介中心性の更新を高速化した。Kourtellis ら [12]与えられたパラメタ M に対して、M 個の頂点対をランダムにも [10] と同様に、各頂点に対して構築した最短路木を更新す選択する。そして、選択した各頂点対 (s, t) に対して各頂点にることで辺と頂点の挿入・削除が行われるネットワークにおい重みがついたハイパーエッジを追加していくことでハイパーグて媒介中心性の更新を行った。コンパクトな形式でデータ構造

ラフ H を構築する。ハイパーエッジの頂点集合は s, t 間の最短をディスク上に保持し、並列計算を行うことで、数百万頂点か路が通る点の集合 v ∈ Pst であり、v に対応する重みは v を通らなるネットワークにおける媒介中心性の更新を可能にした。
しかし、これらの厳密手法は頂点の 2 乗に比例する空間を使用(v)
る最短路の割合 σstである。以降は頂点と重みのペアの集合
σst }{σst (v)(v, σst ) | v ∈ Pst を単にハイパーエッジと呼ぶ。V (e) でし、ネットワークが大規模化に対して十分にスケールするとは

ハイパーエッジ e に含まれる頂点集合を表し、we (v) で e にお言えない。

ける頂点 v の重みを表す。v ∈/ V (e) であるときは we (v) = 0

Bergamini ら [3] はグラフに対して辺が挿入された際に媒とする。

Algorithm 1 ハイパーグラフスケッチの構築 [21]3. 3. 3 計 算 時 間
近 似 精 度 に 関 す る パ ラ メ タ ϵ, δ が 与 え ら れ た と き に 、eB (v) − CB (v) > ϵn2 ] < δ にするようなハイパーグラ
Pr[ C
=
=
フスケッチの構築時間について考える。まず、各ハイパーエッジ

procedure BuildHypergraph(G, M )H←∅
for i = 1 to M do
頂点対 (s, t) をランダムに選択する。
{
}
σ (v)
ハイパーエッジ e = (v, st) | v ∈ Pst を計算。
σst

H に e を加える。

の計算は選択肢した頂点対の片方から最短路木を計算することによって行うことができる。そのため、重みなしグラフにおいては幅優先探索 (BFS) を用いて O(n + m) の計算時間で 1 つの与えられた頂点 v に対してハイパーグラフスケッチ H にお∑ける重み wH (v) を e∈H we (v) で定義し、ハイパーグラフスeB (v) = n2 wH (v) として計
ケッチによる CB (v) の推定値を C
M

ハイパーエッジを計算することができる。また、Lemma 3 よりeB (v) − CB (v) > ϵn2 ] < δ
M = O( ϵ12 log 1δ ) とすれば、Pr[ C==が成り立つ。したがって、求める近似精度のに要する計算時間は、重みなしグラフにおいて O( n+mlog 1δ ) である。
ϵ2

算する。

3. 3. 2 近 似 精 度

4. 提 案 手 法eB (v) が高
ハイパーグラフスケッチによって得られた近似値 C

この章では、動的なグラフ上で媒介中心性の近似値のインクい精度で CB (v) を近似することができることを説明する。まリメンタルな計算を効率良く行う提案手法について説明する。

ず、wH (v) に関して以下の性質が成立する。

我々の手法は吉田 [21] によるハイパーグラフスケッチを用い

Lemma 1. 各頂点 v ∈ V で、EH [wH (v)] = nM2 CB (v)た近似手法をベースとしている。ハイパーグラフスケッチと同様に M 個の頂点対をランダムに選択し、選択した各頂点対に(v)
Proof. 頂点対 (s, t) を選択した場合の wH (v) への寄与は σst
σst

対してハイパーエッジに加え追加の情報も含んだ索引を構築すである。そのため、頂点対をランダムに選択した場合の wH (v)る。索引が保持する情報を利用することで、グラフに対して辺への寄与の期待値は n12 CB (v) である。したがって、期待値のの挿入・削除が行われるたびに、近似値と索引を更新後のグラ線形性より本補題は成り立つ。

フに対応するものに効率良く更新する。

eB (v) の近似精度を示すための前準備として、Hoeﬀd次に、C
ing の不等式を導入する。

以下ではまず、提案手法の索引が保持するデータ構造について説明し、与えられたグラフから索引を構築する手法について述べる。次に、辺の挿入・削除に対して索引を効率良く更新すLemma 2 (Hoeﬀding の不等式). X1 , X2 , . . . , Xn を値域が∑[0, 1] の独立な確率辺数とし、X = n1 n
i=1 Xi とする。このと
2<
き Pr[ X − E[X] >t]2exp(−2tn)が成り立つ。
= =る手法について述べる。

eB (v) が CB (v) を高い
Hoeﬀding の不等式を用いることで、CeB (v) の絶対誤差に関精度で近似しているということを示す。Cるのは辺 (u, v) の挿入によって新しい最短路が生じるときと、eB (v) の絶対誤差が ϵn2 以下になる確率 δするパラメタ ϵ と、Cが与えられたときに、以下が成立する。

4. 1 索引のデータ構造
辺の挿入・削除のときに、ハイパーエッジの更新が必要にな
辺 (u, v) の削除によって今まであった最短路がなくなるときである。ソーシャルネットワーク・ウェブグラフなどの平均経路長の短いネットワークにおいては、2 頂点間の最短路に含まれる頂点はネットワーク全体と比べてごく一部であり、M 個の頂

Lemma 3. 与 え ら れ た パ ラ メ タ ϵ, δ に 対 し て 、M =eB (v) − CB (v) > ϵn2 ] < δO( 12 log 1 ) とすることで、Pr[ C==

点対の中で辺の挿入・削除によって最短路の集合が変化するもが成り立つ。

パーグラフスケッチを更新するには 2 頂点間の最短路の変化をϵδeB (v)] = CB (v) が成り立つ。CeB (v)
Proof. Lemma 1 より E[Cは値域が [0, 1] となる M 個の確率変数の和になっている。したがって、Hoeﬀding の不等式より以下が成り立つ。

eB (v) − CB (v) > ϵn ] =
Pr[ C
=
2

Pr[
Pr[

n2
n2
2
wH (v) −E[wH (v)] >= ϵn ] =MM
1
1
2
wH (v) −E[wH (v)] >= ϵ] <= 2 exp(−2ϵ M )M
M

したがって、M = 2ϵ12 log 2δ = O( ϵ12 log 1δ ) とすることで、求める近似精度を実現できる。

のは M 個よりもはるかに少ない。したがって、効率的にハイ高速で検知することが重要となる。
各頂点対 (s, t) は最短路の変化の検知を効率良く行うために、与えられたパラメタ x に応じて次のようなデータ構造を保持する。パラメタ x は、索引サイズと辺挿入時の更新時間のトレードオフを実現するためのパラメタで、x の値を大きくするにつれて索引サイズは減少し、辺挿入時の更新時間は増加する。

•

s, t 間 の 最 短 路 DAG Pst の 各 頂 点 v と s か ら の(v)
距 離 dsv と 重 み σstの 3 つ 組 か ら な る 集 合 Hst =σst }{σst (v)(v, dsv , σst ) | v ∈ Pst 。s, t 間の最短路が通る各頂点 v に対して、s からの距離 dsv とハイパーグラフスケッチと同様の重みを保持する。重みに加えて s からの距離を保持することによって辺の削除を行ったときに、最短路の集合が変化するかを簡単に判定できるようになる。V (Hst ) で、s, t 間の最短路が通る頂点の集合を表す。以下では Hst をハイパーエッジと呼ぶ。

•

頂点 s から距離 ds 以下の頂点 v と v への距離のペ述べる。方法の概要は Algorithm 3 に示す。まず s を始点とす

ア の 集 合 Bs = {(v, distG (s, v)) | distG (s, v) <= ds } と 、頂点 t から距離 dt 以下の頂点 v と v への距離のペアの集合
Bt = {(v, distG (t, v)) | distG (t, v) <= dt }。ds , dt は与えられた

る BFS によって P 上の各頂点 v に対して s からの距離 dsv とパラメタ x に対して ds + dt + 1 = distG (s, t) − x を満たす非負整数であり、その値は Bs , Bt を求める際に決定される。以下

個数は σsv σvt となるから、v を通る s, t 間の最短路の割合は{}σvt
σsv σvt である。Hst = (v, dsv , σsv) | v ∈ Pst としてハイ
σst

では頂点 v から距離 d 以下の頂点と w への距離のペアの集合

パーエッジを求めることができる。

Bv = {(w, distG (v, w)) | distG (v, w) <= d} を v を中心とする
半径 d のボールと呼ぶ。R(Bv ) でボールの半径 d を表し、V (Bv )Algorithm 2 共通部分を持つボールから最短路 DAG を計算

で v からの距離が d 以下の頂点集合を表す。また、w ∈ V (Bv )ならば distBv (w) で distG (v, w) を表し、w ∈/ V (Bv ) ならば

distBv (w) = ∞ とする。2 つのボール Bs , Bt を利用することによって、辺の挿入が行われたときに新しい最短路が生じるかの判定を効率良く行うことができるようになる。
各頂点対に対する 3 つ組 (Hst , Bs , Bt ) からなる集合がグラs からの最短路の数 σsv を計算する。次に同様にして P 上の各
頂点 v に対して dtv と σtv を計算する。頂点 v を通る最短路のprocedure TwoBallsToDAG(Bs , Bt )S ← V (Bs ) ∩ V (Bt )P ←S▷ Pst を求めるための変数

Qs ← S の頂点を含む FIFO キュー
while not Qs .empty() dofor each (v, w) ∈ E s.t. w ∈/ P doif distBs (w) + 1 = distBs (v) then

フ G に対する索引である。

P ← P ∪ {w}

4. 2 索引の構築
本節では、与えられた無向グラフ G = (V, E) と索引のボールの半径に関するパラメタ x に対して、サンプリングされた▷ s に向かって Bs をたどる。

v = Qs .pop()

Qs .push(w)上記と同様にして t に向かって Bt をたどる。

return P

各頂点対 (s, t) の 3 つ組 (Hst , Bs , Bt ) を計算する方法を説明する。
まず s, t を中心とする 2 つのボール Bs , Bt を計算する。

Bs , Bt をそれぞれ半径 0 のボールとして初期化する。2 つのボールの計算は双方向 BFS に基づき、V (Bs ) と V (Bt ) がAlgorithm 3 Pst ⊂ P となる頂点集合 P が与えられた元で頂点対 (s, t) に対するハイパーエッジを計算
procedure ComputeHyperedge(s, t, P )共通部分を持つか s, t が非連結であるということが判明す

s からの P 上の BFS で各頂点 v ∈ P に対し dsv , σsv を計算

るまで、Bs , Bt のうち含む頂点数が小さいボールの半径をt からの P 上の BFS で各頂点 v ∈ P に対し dvt , σvt を計算

1 つずつ増やしていく。Bs の半径の増加は、distG (s, v) =e←∅

R(Bs ) と な る 各 頂 点 v に 対 し て 隣 接 す る 頂 点 w を 走 査 しfor each v ∈ P do

B ← B ∪ {(w, R(Bs ) + 1) | distG (s, w) = R(Bs )} とすることで行う。Bt についても同様である。
もし s, t が非連結であるということが双方向 BFS の過程で判

if dsv + dvt = dst then

▷ v が Pst 上の頂点か確認

σvt)e ← e ∪ (v, dsv , σsv
σstreturn e

明したならば、頂点対 (s, t) に関する 3 つ組は (∅, ∅, ∅) とする。

s, t が連結であるならば、計算された Bs , Bt から s, t 間の最短路

4. 3 索引の更新

DAG を計算する。Algorithm 2 に概要を示す。まず V (Bs ) と

本節では、辺の挿入・削除が行われた際に索引に含まれる

V (Bt ) の共通部分 S を求め、S と 2 つのボール Bs , Bt を用いて

各 3 つ組 (Hst , Bs , Bt ) を効率良く更新する方法について説明

Pst を計算する。S に含まれる頂点 v はボール Bs , Bt の計算方法

する。簡単のため、挿入・削除された辺 (u, v) を u から v へ

より distG (s, v) + distG (v, t) = R(Bs ) + R(Bt ) = distG (s, t)の有向辺として扱った際の更新方法について説明する。有向辺を満たすため、S ⊂ Ps,t が成り立つ。S に含まれる頂点から(u, v), (v, u) の両方に対して更新を行うことで無向辺の挿入・

ボール Bs , Bt を s, t からの距離が小さくなる方向に向かって削除に対する更新を完了できる。

BFS を用いてたどる。その過程で訪れた頂点は s または t から

4. 3. 1 辺 の 挿 入

S のいずれかの頂点への最短路上に存在するので Pst に含まれ

辺 (u, v) が挿入されたとき、まず 2 つのボール Bs , Bt の更る。したがって、Bs を S からたどる過程で訪れた頂点集合を新を行い、その後でハイパーエッジ Hst を更新する。更新方法

Ps 、Bt を S からたどる過程で訪れた頂点集合を Pt とするとの概要は Algorithm 5 に示す。

Pst = Ps ∪ Pt ∪ S となる。

まず、ボールの更新手法について説明する。ボールの更新をPst が求まった後は、R(Bs ) + R(Bｔ ) + 1 = distG (s, t) − x

行う際に Tretyakov ら [19] のように、s からの距離が短くなが成立するようになるまで、Bs , Bt の半径を減らす。このとる頂点のみ更新することで、ボール全体を再計算するよりも高き、Bs , Bt のサイズが大きい方から半径を 1 ずつ減らしていく

速に計算する。辺 (u, v) が挿入されたときのボール Bs の更新

ことで Bs , Bt のサイズの和を小さくする。

手法の概要は Algorithm 4 に示す。distBs (u) + 1 < distBs (v)

最後に、Pst 上で BFS を行うことで Hst を計算する。ここであるとき、s から v への最短距離が辺 (u, v) を通ることにでは Pst ⊂ P となる頂点集合に対して Hst を計算する方法を

よって短くなる。このとき、distBs (v) ← distBs (u) + 1 と v

までの最短距離を更新する。この更新によって v に隣接する頂
点 w への s からの最短距離が短くなる可能性がある。実際に𝐵𝑢

distBs (v) + 1 < distBs (w) ならば distBs (w) も更新し、w に

𝑢

𝑣

𝐵𝑣
𝑣

𝑢

隣接する頂点への距離についても同様にして更新していく。こ𝑡𝑠のような操作を Algorithm 4 のような BFS によって s からの距離が R(Bs ) 以下である頂点に対して行うことで、Bs の更新

𝐵𝑣

𝑅 𝐵𝑡

𝑅 𝐵𝑠

𝑡

𝑠

𝑅 𝐵𝑡

𝑅 𝐵𝑠

をボールの一部を走査するだけで行うことができる。Bt につ𝐵𝑠

いても Bs と同様に更新を行う。

𝐵𝑡(a) u, v のどちらも V (Bs ) ∪ V (Bt ) に

Algorithm 4 辺 (u, v) の挿入によるボール Bs の更新

𝐵𝑠𝐵𝑡(b) u ∈ V (Bs ) の場合含まれない場合

procedure BallInsertEdge(Bs , u, v)

図 1 辺挿入時における s, t 間の最短路の検出

if distBs (u) < R(Bs ) thenQ ← 空の FIFO キュー
if distBs (v) > distBs (u) + 1 thendistG (s, u) + distG (u, v) + distG (v, t) >=distBs (v) ← distBs (u) + 1

distG (s, u) + 1 + R(Bt ) >Q.push(v)R(Bs ) + x + 1 + R(Bt ) = distG (s, t)

while not Q.empty() dov ← Q.pop()と な る た め 、u, v を 通 る s, t 間 の 最 短 路 は 存 在 し な い 。

if distBs (v) = R(Bs ) then continue;

V (Bv ) ∩ V (Bt ) = ∅ のときも同様である。したがって、対for each (v, w) ∈ E do

偶が成立することから本補題は成立する。

if distBs (w) > distBs (v) + 1 then
distBs (w) ← distBs (v) + 1
Q.push(w)

上記補題より、R(Bu ), R(Bv ) の上限を x として良い。
（ 2 ） u ∈ V (Bs ) の場合 (図 1b)
このとき、distG (s, u) は distBs (s, u) となり既知であるため、

u, v を通る経路に関して以下が成立する。
ここからは、更新後のボールを利用してハイパーエッジのLemma 5. u, v を通る s, t 間の最短路が存在するならば、頂更新を行う手法を示す。ハイパーエッジの更新が必要になるの

点 v を中心とする半径 dst − distBs (u) − R(Bt ) − 1 以下のボーは有向辺 (u, v) の挿入によって新しい最短路が生じるときでル Bv で、V (Bv ) ∩ V (Bt ) =| ∅ を満たすものが存在する。

ある。新しい最短路が生じるかの判定を行うために、u, v をそしたがって、R(Bv ) の上限を dst − distBs (u) − R(Bt ) − 1 とれぞれ中心とするボール Bu , Bv を計算する。u を始点とする

することができる。また、既に u ∈ V (Bs ) であるため R(Bu )BFS をしながら Bu の半径を 0 から 1 つずつ増加させていき、の上限は 0 で良い。

V (Bs ) ∩ V (Bu ) =| ∅ となるような最小の半径を持つボール Bu（ 3 ） v ∈ V (Bt ) の場合を求める。Bv もこれと同様にして求める。しかし、u, v がグ

(2) の場合と同様に、R(Bu ) の上限を dst −distBt (v)−R(Bs )−ラフ G 上において s, t から遠く離れている頂点だった場合、辺

1、R(Bv ) の上限を 0 として良い。

(u, v) を通る s, t 間の最短路が存在しないにも関わらず、Bu , Bv

上記の場合分けのうち (2),(3) は同時に成り立つことがあるが、の計算のためにグラフの大部分を探索してしまうことが起こりその場合は (2) の更新方法を使用する。

うる。そのような事象を避けるために、R(Bu ) と R(Bv ) の上

半 径 の 大 き さ に 上 限 値 を 定 め て 計 算 し た Bu , Bv が 、限値を求め、その値を超えたら探索を打ち切ることで探索空間

V (Bu ) ∩ V (Bs ) = ∅ と V (Bv ) ∩ V (Bt ) = ∅ を満たしていを狭める。Bs , Bt とパラメタ x から R(Bu ) と R(Bv ) の上限

るならば辺 (u, v) を含む最短路が生じた可能性がある。こ

値を求めることができるが、u, v とボール Bs , Bt の包含関係にの 場 合 、s, t の 新 し い 最 短 路 DAG に な る 候 補 の 頂 点 集 合よって以下のような場合分けがある。

P = V (Hst ) ∪ Psu ∪ Pvt を計算する。ComputeHyperedge（ 1 ） u と v が V (Bs ) ∪ V (Bt ) に含まれない場合 (図 1a)を呼び出して s, t, P からハイパーエッジ Hst を計算する。ソー

このとき、u, v を通る経路に関して以下が成立する。

シャル・ネットワークにおいて最短路 DAG の平均サイズは非Lemma 4. u, v を通る s, t 間の最短路が存在するならば、頂常に小さいため、ハイパーエッジの更新は高速に行うことがで

点 u, v をそれぞれ中心とする半径 x 以下のボール Bu , Bv できる。

V (Bs ) ∩ V (Bu ) =| ∅,V (Bv ) ∩ V (Bt ) =| ∅ を満たすものが存在する。

以上で有向辺 (u, v) が挿入されたときの 3 つ組 (Hst , Bs , Bt )の更新が完了する。

Proof. 半径 x 以下のボール Bu , Bv では必ず V (Bs )∩V (Bu ) =4. 3. 2 辺 の 削 除∅ ま た は V (Bv ) ∩ V (Bt ) = ∅ と なって し ま う と す る 。

ま ず、辺の挿入を行ったときと同様にまずボール Bs , Bt

V (Bs ) ∩ V (Bu ) = ∅ であるならば、の 更 新 を 行 う。辺 (u, v) が 削 除 さ れ た と き 、Bs の 更 新 はdistBs (u) + 1 = distBs (v) が成り立つときに行う。Bs の更新が必要になったときは、頂点 s を始点とする BFS によって

Algorithm 5 辺 (u, v) の挿入によるハイパーエッジの更新

で頂点対を 10,000 個選び、その中で連結な頂点対を結ぶ最短距

procedure UpdateHyperedge(u, v)

離の平均を求めたものである。

Bu ← {(u, 0)} , Bv ← {(v, 0)}du ← 0, dv ← 0

表 1 データセットの情報。 d は頂点の平均次数でり、D はグラフ内▷ Bu , Bv の半径の上限

if u ∈/ V (Bs ) ∪ V (Bt ) and v ∈/ V (Bs ) ∪ V (Bt ) thendu ← x, dv ← xelse if u ∈ V (Bs ) thendv ← dst − distBs (u) − R(Bt ) − 1
else if v ∈ V (Bt ) thendu ← dst − distBt (v) − R(Bs ) − 1
while V (Bs ) ∩ V (Bu ) = ∅ and R(Bu ) < du do
Bu の半径を 1 大きくする
while V (Bv ) ∩ V (Bt ) = ∅ and R(Bv ) < dv do
Bv の半径を 1 大きくする

名前

種類

GrQc

ソーシャル

5,242

28,980 11.1 6.1

Enron

ソーシャル

36,692367,662 20.0 4.0

Epinions1

ソーシャル

75,879811,480 21.4 4.3

Slashdot0811 ソーシャル

77,3601,092,974 28.3 4.0

n

m

d

D

Pokec

ソーシャル 1,632,803 44,603,928 54.6 4.7

Stanfordウェブ

281,9033,985,272 28.3 6.9

NotreDameウェブ

325,7292,235,126 13.7 7.2

Googleウェブ

875,7138,644,102 19.7 7.1

BerkStanウェブ

685,230 13,298,940 38.8 6.4

Patents

引用3,774,768 33,037,896 17.5 8.2

if V (Bs ) ∩ V (Bu ) =| ∅ or V (Bv ) ∩ V (Bt ) =| ∅ thenP ← V (Hst )▷ Pst の候補となる頂点集合

P ← P ∪ TwoBallsToDAG(Bs , Bu )P ← P ∪ TwoBallsToDAG(Bv , Bt )Hst ← ComputeHyperedge(s, t, P )5. 2 実 験 環 境
提案手法を C++11 と Google Sparse Hash（注 1） を用いて実装し、gcc 4.8.3 を用いて最適化オプション-O3 の設定でコンパイルした。本実験は Linux サーバー (CPU: Intel(R) Xeon(R)CPU E5-2670 2.60GHz、メモリ: 512GB) で行われた。
再度同じ半径のボールを計算する。挿入と同様に Tretyakov

5. 3 実 験 方 法

ら [19] の手法を利用することによって、より高速なボールの更まず、与えられたグラフから 200 本の辺をランダムに選びグ新が期待できるが、今回は簡単のためにそれを行わない。

ラフから削除した。そのグラフから 1024 個の頂点対をランダ

次にハイパーエッジ Hst の更新を行う。有向辺 (u, v) の削除

ムに選択して索引を構築し、索引の構築時間を測定した。次に、を行った際には Hst の更新にボールの情報を利用しない。ハ

一度削除した辺を削除した順に挿入し索引の更新に要する時間

イパーエッジの更新が必要になるのは {u, v} ∈ V (Hst ) かつを測定した。すべての辺の挿入が終わったのち、再度それらのdsu + 1 = dsv のときだけである。辺 (u, v) を削除したとき、2辺を削除し索引の更新に要する時間を測定した。このような試通りの場合がある。

行を 5 回繰り返し、各測定値の平均をとった。

（ 1 ） 頂点 s, t 間の距離が増加する場合

5. 4 実 験 結 果(u)(v)
頂点 , t 間の距離が変化するのは σst= 1 かつ σst
=1と
σst
σst

5. 4. 1 索引サイズなるときであるので、Hst が持つ情報だけで判定を行うことが各データセットに対するボールとハイパーエッジのサイズをできる。実際に頂点 s, t 間の距離が増加したときは、索引を構

表 5. 4. 1 示す。表中の |V (Bs )| + |V (Bt )| は選択された 1 つの築したときと同様の双方向 BFS によって (Hst , Bs , Bt ) を計算

頂点対 (s, t) に対して計算されたボール Bs , Bt のサイズの和のし直す。

平均値になっている。ハイパーエッジのサイズ |V (Hst )| は x（ 2 ） 頂点 s, t 間の距離が変化しない場合の値に依存しないため、x = 0 としたときの平均値のみを記載

このとき、更新後の s, t 間の最短路 DAG は V (Hst ) に含まれてしている。

いる。したがって、Hst ← ComputeHyperedge(s, t, V (Hst ))とすることでハイパーエッジを更新できる。

5. 計算機実験

x = 0 のとき、構築されるボールのサイズがグラフの頂点数に比べて 30 から 1000 分の 1 になっている。x の値が大きくなるにつれてボールのサイズが小さくなり、x = 2 になると頂点数に比べて 130 から 20,000 分の 1 の大きさになる。例えば複数のネットワークに対して計算機実験を行い、提案手法の性能を評価した。

2,000 個の頂点対から索引を構築すれば各頂点の媒介中心性の誤差を 99%の確率で 0.05n2 以下にすることができるが、元の5. 1 データセット

グラフサイズとさほど変わらない空間しか必要としないことがStanford Network Analysis Project (SNAP) のデータセッ

わかる。また、ハイパーエッジのサイズはボールのサイズに比ト [14] で公開されている様々なソーシャルネットワーク・ウェ

べて小さく、索引全体でのサイズはボールのサイズに依存する

ブグラフ・引用ネットワークを用いて実験を行った。有向なネッことがわかる。

トワークの場合は各辺に対して反対側を向く辺を追加すること

ソーシャルネットワークとウェブグラフにおけるボールグラ

によって無向グラフとして扱った。表 1 に各データセットの概フのサイズを比較すると、総じてウェブグラフに対して計算さ要を示す。

れるボールのサイズが大きくなっていることがわかる。これは、（注 1）：https://code.google.com/p/sparsehash/今回使用したネットワークにおいて、ソーシャルネットワーク

媒介中心性の近似値を更新することができることを示した。さに比べてウェブグラフのほうが平均最短路長が長いことが原因

らに、構築される索引のサイズは十分な精度を実現しようとしであると考えられる。また、ウェブグラフ同士の結果を比較すても十分に小さくなり、大規模なネットワークに対しても動作ると、Stanford・BerkStan のほうが平均最短路長が短いにもすることが可能であることを示した。

関わらず、NotreDame・Google よりもボールのサイズが大きくなることから、グラフの平均次数もボールのサイズに強く関係していることが推測できる。
表 2 ボールとハイパーエッジのサイズ
名前|V (Bs )| + |V (Bt )|x=0

x=1 x=2|V (Hst )|

GrQc

123

64

38

13

Enron

282

49

29

23

Epinions1

174

44

33

28

Slashdot0811

191

42

31

27

Pokec

1,674

264

79

47

Stanford

6,807

3,454

1,013

66

NotreDame

3,026

1,308

629

24

Google

2,943

427

145

28

BerkStan

25,677 12,707

4,204

55

Patents

5,680

700

37

1,978

5. 4. 2 実 行 時 間
各データセットに対する挿入・削除に要する時間を表 3 に示す。表内の挿入・削除時間は 1024 個のハイパーエッジからなる索引全体の更新に要した時間である。提案手法はソーシャル
ネットワークにおいて特に高速な性能を実現している。x = 0のとき辺の挿入・削除ともに数ミリ秒で索引の更新を行うことができ、特に Pokec においてはハイパーグラフスケッチ全体を再計算するのと比べて一万倍以上高速に更新を行うことができる。一方、ウェブグラフにおいては辺の挿入による更新は数十ミリ秒を要し、辺の削除による更新は更に多くの時間を要し、特に BerkStan においては 3 秒以上の時間を要する。これ
はボールのサイズが大きくなるにつれて、その更新に多くの時間を要するためである。

x の値を大きくなるにつれて挿入に要する時間は大きくなっていく。辺から作るボールのサイズが大きくなるために、最短路の検出により多くの時間を要するためである。一方、辺の削
除は x の値が大きくなるにつれて高速に行えるようになる。これはハイパーエッジの更新でボールを必要とせず、ボールが小さくなったことでボールの更新に要する時間が少なくなるためである。

6. お わ り に
本論文では、動的なネットワークにおいて媒介中心性の近似
値を効率良く計算する手法を提案した。ハイパーグラフスケッ
チにおいて、サンプリングされた各頂点対に対してハイパー
エッジに追加の情報を保持した索引を提案し、その効率的な計算方法を説明した。また、構築した索引を利用し辺の挿入・削除に対して効率良く媒介中心性の近似値を更新する方法を示した。複数のデータセットに対する実験によって、本手法が数百万頂点からなるソーシャルネットワークに対しても数ミリ秒で文

献[1] A. Abbasi, L. Hossain, and L. Leydesdorﬀ. Betweenness centrality as a driver of preferential attachment in the evolutionof research collaboration networks. Journal of Informetrics,
6(3):403–412, 2012.
[2] D. A. Bader, S. Kintali, K. Madduri, and M. Mihail. Approximating Betweenness Centrality. In WAW, pp. 124–137,
2007.
[3] E. Bergamini, H. Meyerhenke, and C. L. Staudt. Approximating Betweenness Centrality in Large Evolving Networks.
In ALENEX, pp. 133–146, 2015.
[4] U. Brandes. A Faster Algorithm for Betweenness Centrality.
J. Math. Sociol., 25(2):163–177, 2001.
[5] U. Brandes and C. Pich. Centrality Estimation in Large
Networks. Int. J. Bifurcat. Chaos, 17(07):2303–2318, 2007.
[6] L. C. Freeman. A Set of Measures of Centrality Based on
Betweenness. Sociometry, 40(1):35–41, 1977.
[7] R. Geisberger, P. Sanders, and D. Schultes. Better Approximation of Betweenness Centrality. In ALENEX, pp. 90–100,
2008.
[8] M. Girvan and M. E. J. Newman. Community structure
in social and biological networks. P. Natl. Acad. Sci.,
99(12):7821–6, 2002.
[9] K.-I. Goh, E. Oh, B. Kahng, and D. Kim. Betweenness
centrality correlation in social networks. Phys. Rev. E,
67:017101, 2003.
[10] O. Green, R. McColl, and D. A. Bader. A fast algorithm forstreaming betweenness centrality. In SocialCom/PASSAT,
pp. 11–20, 2012.
[11] M. Kas, M. Wachs, K. M. Carley, and L. R. Carley. Incremental Algorithm for Updating Betweenness Centrality in
Dynamically Growing Networks. In ASONAM, pp. 33–40,
2013.
[12] N. Kourtellis, G. D. F. Morales, and F. Bonchi. Scalable
Online Betweenness Centrality in Evolving Graphs. CoRR,
abs/1401.6981, 2014.
[13] M.-J. Lee, J. Lee, J. Y. Park, R. H. Choi, and C.-W. Chung.
QUBE: a Quick algorithm for Updating BEtweenness centrality. In WWW, pp. 351–360, 2012.
[14] J. Leskovec and A. Krevl. SNAP Datasets: Stanford large
network dataset collection. http://snap.stanford.edu/
data, June 2014.
[15] S. Milgram. The Small World Problem. Psychology today,
2(1):60–67, 1967.
[16] M. E. J. Newman and M. Girvan. Finding and evaluating
community structure in networks. Phys. Rev. E, 69:026113,
2004.
[17] G. Ramalingam and T. W. Reps. On the Computational Complexity of Incremental Algorithms. University of
Wisconsin-Madison, Computer Sciences Department, 1991.
[18] M. Riondato and E. M. Kornaropoulos. Fast Approximationof Betweenness Centrality Through Sampling. In WSDM,
pp. 413–422, 2014.
[19] K. Tretyakov, A. Armas-cervantes, L. Garcı́a-ba nuelos, and
M. Dumas. Fast Fully Dynamic Landmark-based Estimation of Shortest Path Distances in Very Large Graphs Categories and Subject Descriptors. In CIKM, pp. 1785–1794,
2011.
[20] D. J. Watts and S. H. Strogatz. Collective dynamics of’small-world’ networks. Nature, 393(6684):440–442, 1998.

表3

索引の構築及び更新に要する時間

索引更新時間 (ms)
名前索引構築時間 (s)

x=0

x=1

挿入

削除

速度向上比

x=2

挿入

削除

挿入

x=0
削除

挿入

x=1
削除

挿入

x=2

削除

挿入

削除

GrQc

0.1

1.7

2.2

4.7

0.8

8.8

0.4

76

57

27

149

14

333

Enron

1.9

3.9

5.4

12.9

0.4

242.8

0.3

477

346

145

4,415

8

5,557

Epinions1

2.0

2.3

1.2

15.9

0.4

633.9

0.3

865

1,646

123

5,331

3

5,748

Slashdot0811

2.4

1.8

1.2

13.6

0.5

478.8

0.3

1,291

1,948

173

5,098

5

6,867

Pokec

18.8

1.0

1.5

11.4

0.5

451.0

0.4 17,931 12,149 1,652 34,678

42 46,892

Stanford

23.0 55.5

348.6

256.3

118.2 1,401.0

28.2

414

66

90

195

16

814

NotreDame

9.9

3.5

287.7

69.1

107.3

612.3

9.7

2,784

34

143

92

16

1,013

8.3

4.2

11.7

19.7

1.1

193.0

Google

0.5

1,952

707

421

7,287

BerkStan

134.1 92.2 3,789.3 1,943.3 1,046.8 7,481.4 224.3

1,454

35

69

128

Patents

20.0

1.1

6.2

6.8

1.4

[21] Y. Yoshida. Almost Linear-Time Algorithms for Adaptive Betweenness Centrality using Hypergraph Sketches. In
KDD, pp. 1416–1425, 2014.

41.7

0.7 18,513

3,238 2,948 13,872

43 15,44518598

478 30,270