DEIM Forum 2019 D2-1

曖昧グラフにおける効率的なネットワーク信頼性の近似計算
佐々木勇和†

藤原

靖宏††,†

鬼塚真†† 大阪大学大学院情報科学研究科†† NTT ソフトウェアイノベーションセンタ
E-mail: †{sasaki,onizuka}@ist.osaka-u.ac.jp, ††fujiwara.yasuhiro@lab.ntt.co.jp
あらましネットワーク信頼性は曖昧グラフにおいて与えられた節点間の接続確率を評価する重要な指標のひとつである．ネットワーク信頼性の計算は #P 完全問題であるため，近似解を計算する手法が提案されている．本稿では，
サンプリングに基づく新たな近似解計算手法を提案する．提案アプローチは層化サンプリングを拡張し，下限値と上限値を用いてサンプル数を削減する．これにより近似計算の効率化と近似解の精度の向上を可能にする．下限値と上限値を効率的に計算するために，二分決定図を拡張した S2 BDD を開発する．提案アプローチは S2 BDD を構築しながら，動的計画法を用いて効率的なサンプリングも実現する．実データを用いた実験により，提案アプローチが高精度を保ちながら，既存のサンプリングに基づくアプローチより最大で 51.2 倍高速であることを示す．
キーワード 曖昧グラフ, ネットワーク信頼性, 二分決定図, サンプリング

1. は じ め に
世の中の理解と設計のためには，オブジェクト間の関係性をモデル化し解析することが必要である．実世界のオブジェクト間の関係性は，グラフによりモデル化することができる．グラフの解析における基礎的なトピックとして，ネットワーク信頼b e e d
3
4

e2

c

b

e6

e e5
a 1
e

d

b

c
a

d

b

e

a

d
c

c
e

a

e

(b) íšb›‡(a) J×b›‡

図 1: 曖昧グラフ

性の計算がある [1], [2]．ネットワーク信頼性は枝に存在確率が付与されている曖昧グラフにおいて，与えられた複数の節点

ターミナル集合 T，およびサンプル数 s が与えられたとき， ネッ（ターミナルと呼ぶ）の相互接続する確率である．例えば，タトワーク信頼性の近似値 R̂[G, T] を効率的に計算する．

ンパク質相互反応は気温や湿度等の状況により常に反応が行われるわけではなため，曖昧グラフとしてモデル化することができる [3]．タンパク質の機能の解明のために，分析者は複数のタンパク質間の関係の強さをネットワーク信頼性を用いて評価している．その他にも，通信ネットワーク [1] や都市計画 [4] などの応用にてネットワーク信頼性は広く利用されている．

サンプリングの計算コストはサンプル数が増加に従い大きくなる．近似計算を効率的に行うために，近似精度を損なわずに
サンプル数を削減させる．研究課題は，(1) どのように精度を理論的に保証しながらサンプル数の削減させるか，および (2)どのように理論的な結果を効率的に実現するかである．まず，最初の課題においては，層化サンプリング [5] を拡張する．層

ネットワーク信頼性の計算は #P 完全問題として知られてお化サンプリングは予測値の下限値と上限値を用いることにより

り，計算コストは非常に大きい [2]．これは，可能グラフを列挙

予測値の精度を向上させることが可能である．層化サンプリン

することが必要であることに起因する．可能グラフは，元々の曖昧グラフと同じ節点および枝のサブセットを持つグラフである．可能グラフは存在確率をもち，枝の存在確率から計算される．ターミナルが全て接続となる可能グラフの確率を足し合わせることで，ネットワーク信頼性を計算できる．図 1 は曖昧グ
ラフと 3 つの可能グラフの例を示す．図のグラフにおいて黒のグを用いることにより，近似精度を損なわずにサンプル数を削減可能なことを証明する．
理論的な結果によりサンプル数を削減することが可能であるが，この結果には二つの制約 (1) 効率的なネットワーク信頼性
近似計算のために，ネットワーク信頼性の下限値と上限値を効率的に求める必要，および (2) 精度の保証のために，下限値

点はターミナルを示す．枝の存在確率は 0.7 とする場合，全てと上限値の計算に用いた可能グラフをサンプリング対象としの可能グラフは 4 つの枝が存在枝（2 つが非存在枝）であるたてはいけないことがある．これらを達成する効果的な方法は自め，可能グラフの存在確率は 0.0216 (0.74 · (1 − 0.7)2 ) である．

明ではない．そこで， 二分決定図を拡張した scalable and左と中央の可能グラフのみターミナルが接続しているため，これらの存在確率がネットワーク信頼性に加算される．
本稿では，ネットワーク信頼性をサンプリング技術を用いて近似計算する．問題定義は以下となる．
問題定義 (ネットワーク信頼性の近似計算)：曖昧グラフ G ，sampling BDD (S2 BDD) を開発する．S2 BDD はターミナ
ルが接続または非接続となる可能グラフを優先的に探索することにより，下限値と上限値を効果的に求めることができる．また提案アプローチでは，S2 BDD を構築しながら，動的計画法を実施し，効率的に可能グラフをサンプリングする．このサンプリングは，下限値および上限値の計算に用いられた可能グラ

ネットワーク信頼性の定義は以下である．

フをサンプリングすることを避けることができる．さらに，提［Definition 1］（ネットワーク信頼性） 任意の k 個のターミナ

案アプローチは，曖昧グラフのサイズが減少することにより，

ル集合 T と曖昧グラフ G が与えられたとき, ネットワーク信頼

さらに効率化可能である．そこで 2 枝連結グラフを用いた拡性 R[G, T] は下記の式で計算される．

張技術を提案する．拡張技術は，ネットワーク信頼性を損なうことなく，不必要な部分グラフの枝刈り，グラフの分割，およR[G, T] =∑Gp ∈WG I(Gp , T) · P r[Gp ],(3)

びより小さいグラフへの変換を行う．実データを用いた評価実

Gp は可能グラフを示し， I(Gp , T) は Gp において全てのター験を行い，提案アプローチは既存のサンプリングに基づくアプ

ミナルが接続なっている場合に 1 を返し, その他の場合 0 を返

ローチより最大 51.2 倍高速かつ高精度であること示す．

す関数を示す．

本稿の構成は次の通りである．まず，2. にて事前知識についR̂[G, T] をネットワーク信頼性の近似解と定義する．簡単化のて説明する．3. にて提案アプローチ，4. にて拡張手法を説明すため，R と R̂ を R[G, T] と R̂[G, T] の代わりにそれぞれ用いる．

る．5. にて提案アプローチのアルゴリズムを述べる． 6. にてターミナル数が k であるネットワーク信頼性は k ターミナル信実験結果を示し， 7. にて本稿をまとめる．

頼性と呼ばれ，最も一般的なネットワーク信頼性である [6]．
二分決定図 [6] とサンプリング [7] がネットワーク信頼性計算

2. 事 前 知 識のための主要な技術である．二分決定図に基づくアプローチは
本章では，事前知識として，曖昧グラフ，ネットワーク信頼性，二分決定図，およびサンプリングについて説明する．

2. 1 曖昧グラフ

小規模なグラフに対して効率的に厳密解を計算可能で，サンプリングに基づくアプローチは大規模なグラフに対して近似解を計算可能である．

連結かつ無向な曖昧グラフを G = (V, E, p) と定義する．V は節点集合， E⊂
=V × V は，曖昧枝の集合，および p : E → (0, 1]
は，曖昧枝 e ∈ E の存在確率 p(e) を決定する関数である．節
点 v と v ′ 間の枝 e ∈ E を e = (v, v ′ ) と定義する. 曖昧枝 e の状態は，確率 p(e) で存在または確率 1 − p(e) で非存在である．

2. 3 二分決定図
二分決定図（BDD）は有向非循環グラフ D = (N, A) で表現される．二分決定図のノード集合を N，二分決定図のアーク集
合を A と定義する（注 1）．図 2(a) は図 1 のグラフにおける二分決定図を示す. 各ノードは中間グラフに対応しており，アーク

曖昧枝の存在確率は，他の枝の存在確率と独立に計算されるとは存在枝または非存在枝と対応している．二分決定図は，入次想定する．

数が 0 の枝が一つあり，ルートノードと呼ばれる (図 2(a) にお可能グラフ Gp = (V, Ep ) は，曖昧グラフ G の全節点と枝のける G1 ). それぞれのノードは，二つの outgoing アークがあ

サブセットから成る. 枝には存在確率は無く，E\Ep は非存在

り，0-アークおよび 1-アークと呼ばれる (図 2(a) ではそれぞれ枝である．可能グラフは存在確率を P r[Gp ] をもち，以下の式

点線と実線で表されている)．0-アークおよび 1-アークはそれで計算される．

ぞれ非存在枝と存在枝を表しており，それぞれのアークは重みP r[Gp ] =∏e∈Ep p(e) ·∏e∈E\Ep (1 − p(e)).

(1)

は枝の存在確率または非存在確率を表している．ルートノードからの深さを層 l と定義する．層 l のノードは，枝 e1 から el−1

曖昧グラフ G の可能グラフの数は，それぞれの枝が存在と非存在の二つの状態を取りうるため，2|E| である．G の全ての可能グラフの集合を WG と定義する．

が存在または非存在の中間グラフを表す（el から e|E| は曖昧枝である）．二分決定図は出次数がゼロのノードが 2 つあり，それぞれ 0-シンクと 1-シンクと呼ばれる（図 2(a) ではそれぞれ中間グラフ GE (E∃ , E¬ ) は，存在枝集合 E∃ , 非存在枝集合 E¬ ，

ラベル 0 と 1 の四角で表されている）．中間グラフのターミナ

および曖昧枝の集合 E\(E∃ ∪ E¬ ) から構成される曖昧グラフで

ルが接続した場合，対応するノードは 1-シンクに遷移する．一ある．中間グラフの存在確率 P r[GE (E∃ , E¬ )] は以下の式で計方，中間グラフのターミナルが非接続した場合，対応するノー

算される．

ドは 0-シンクに遷移する．ルートノードから 1-シンクまでのP r[GE (E∃ , E¬ )] =∏e∈E∃ p(e) ·∏e∈E¬ (1 − p(e)).

(2)

アークを辿ることにより，ターミナルが接続となる中間グラフを得ることができる．そのため，1-シンクにアークが遷移して簡単化のため，P r[GE (E∃ , E¬ )] の代わりに P r[GE ] を使用する.

いるノードの確率値の総和を取ることにより，ネットワーク信中間グラフ GE (E∃ , E¬ ) の可能グラフの数は，2|E\(E∃ ∪E¬ )| であ

頼性を計算することができる．

る．GE の全ての可能グラフの集合を WGE と定義する．中間グ

ネットワーク信頼性計算のために二分決定図を構築する方法

ラフにおいて，存在枝を用いて節点間に経路がある場合，節点として，フロンティアに基づく手法がよく用いられている [8]．

は接続している呼び，存在枝と曖昧枝を用いて経路が無い場合，

この手法はまず枝を順序付けし，順序に従って枝の状態を決定

節点は非接続していると呼ぶ．ここで，曖昧枝を用いて節点にしていく．二分決定図が既に層 l まで構築済みの場合，この手経路がある場合，節点が接続か非接続はあきからではない．

法は el の状態を決定し，層 l + 1 の節点集合を構築する．フロ2. 2 ネットワーク信頼性
ネットワーク信頼性は，全てのターミナルが接続となっている可能グラフの確率を全て足し合わせることで計算できる．

（注 1）：本論文では，グラフの節点と枝を “節点” および “枝” とそれぞれ呼び，二分決定図の節点と枝を “ノード” と “アーク” とそれぞれ呼ぶ．

½1

G4

G1

½2

0.3

0.7

G2

G3

0.3

½3

e2
0.7

0.7 0.3

G4
G5
G6
0.3
0.3 0.7
0.7
0.7
0.3

½4

G7
0.3

½5

0.7

3. 1 サンプル数の削減

b e e d
3
4
a

c

e6

e1 e5 eリングはネットワーク信頼性の近似計算の分散を小さくするこG5 b e3 e4 d
e2
e6
c
e
e
1
5
a
e

G8
0.3

½6

0.7
G9

0.3

i¥a

0.7

0

1

(a) xÀàÒÕ

本節では，層化サンプリング [10], [11] に基づいて高精度を維持しつつサンプル数を削減できることを証明する．層化サンプ

G6 b e e d
4
3
e2
e6
c
e
e
a 1 5 e(b) ½3-°Ñb›‡

図 2: 図 1(a) のグラフにおける二分決定図.

ンティアに基づく手法では，存在/非存在枝と曖昧枝の両方をができるため，近似精度を損なわずにサンプル数を削減することができる．
層化サンプリングを適用するために，可能グラフの集合 WG
GG
を 3 つのサブ集合グループ WG
c , Wd , および Wu に分ける．

WGc および WGd は，それぞれターミナルが接続および非接続となる可能グラフのみを含んでおり，WG
u は二つの集合に含まれGていない可能グラフが含まれている．WG
c と Wd に含まれる可能グラフの確率の総和をそれぞれ pc と pd とする．ここで，定義 1 より，上限値と下限値は下記の式により計算できる．

R =∑P r[Gp ] +Gp ∈WGc

もつ節点はフロンティア f と呼ばれ，層 l でのフロンティアの= pc +

集合を Fl とする．図 2(b) は，枝 e1 と e2 を処理した後の中間>= pc .

グラフを表し，黒の実線，黒の破線，および灰色の破線はそれ

R = 1−

ぞれ存在枝，非存在枝，および曖昧枝を示す．節点 b と c は存
在/非存在と曖昧枝の両方をもつため，フロンティアである．同
じ層のノードは全て同じフロンティア集合をもつ．フロンティアに基づく手法は，フロンティアの変数（例えば，曖昧枝の数∑∑

I(Gp , T)P r[Gp ]Gp ∈WGu

I(Gp , T)P r[Gp ]Gp ∈WGu∑

P r[Gp ] −Gp ∈WGd= 1 − pd −∑∑(P r[Gp ] − I(Gp , T)P r[Gp ])Gp ∈WGu(P r[Gp ] − I(Gp , T)P r[Gp ])Gp ∈WGu<= 1 − pd .
これらの式より，pc <=R<= 1 − pd を得ることができる．

や接続済みのターミナル数など）を保持しており，フロンティ

分散は予測手法にも依存する．提案アプローチでは，代表的アの変数が同じになった場合にノードを結合することで，ノーな二つの予測手法であるモンテカルロ法と Horvitz-Thompson

ドの数を効果的に削除することができる．

法を用いる．それぞれの手法について，下限値と上限値を用い二分決定図のサイズはノードの数で定義され，メモリ使用量は二分決定図のサイズに依存する [6]．実際のメモリ使用量は事前に推定することができないため，小規模なグラフに対してもてサンプル数を削減できることを下記で述べる．
モンテカルロ法:となる．

メモリが枯渇する可能性がある．

2. 4 サンプリング
サンプリングは近似解を計算するために一般的な方法である．

モンテカルロ法による R̂ の計算式は下記
∑s

R̂ =

i=1 I(Gpi ,T).

(4)

V ar[R̂] = R(1−R)
.
s

(5)

s

分散は下記の式で計算される [10]．

サンプル数 s が与えられたとき，サンプリングに基づくアプ
ローチは次に示す処理を s 回繰り返す．曖昧グラフから可能グ
ラフを取り出し，その可能グラフにおいてターミナルが接続かどうかを計算する．可能グラフを取り出すために O(|E|) 必要

不偏サンプリングであるため（つまり E(R̂) = R），分散は下記の式で計算できる [11]．

であり，接続の確認のために O(|V| + |E|) 必要であるため，サR̂)V ar[R̂] = R(1−R)≈ R̂(1−.
ss

ンプリングに基づく手法の計算量は O(s · (|V| + |E|)) である．
サンプリングに基づく手法の精度は分散により評価される．
この手法は乱択アルゴリズム [9] であるため，平均のネットワー
ク信頼性が最も真の値に高確率で近いためである．そのため，分散が小さいとエラー率が小さいことを示す．理論的な分散値(6)

上限値と下限値を用いた場合，分散は下記の式で計算できる [10], [11]．
d −R̂)V ar[R̂]′ = (R̂−pc )(1−p
.
s

(7)

下記の式を得ることできる．

を達成するためには，可能グラフをその存在確率に基づいて取り出す不編サンプリング (unbiased sampling) が必要である．
サンプル数が増加すると，分散は減少するが計算量が増加する．
そのため，精度と時間計算量の間にはトレードオフが存在する．

3. 提案アプローチ
本章では，提案アプローチを説明する．3. 1 にて，サンプル数の削減方法について述べ，3. 2 にて S2 BDD を説明する.

R̂(1−R̂) > (R̂−pc )(1−pd −R̂)
.
=
s
s

(8)

式 (8) より, 下記の定理を得られる．
［Theorem 1］ サンプル数 s, 下限値 pc , および上限値 1 − pdが与えられたとき，サンプル数 s′ (<= s) が下記となる場合，サンプル数が s′ の上限値と下限値を用いたモンテカルロ法によるネットワーク信頼性の分散は，サンプル数 s の場合と分散が等しく，もしくは小さくなる．

⌊s(1 − pd )⌋.






⌊s(1 − pc )⌋.





⌊s(1 − 4 · pc (1 − pc ))⌋.
s′ =
⌊s(1 − 4 · p (1 − p ))⌋.

c
d







⌊s(1 − min(4pc (1 − pc ),





4(p (1 − p ) + (p − p )))⌋.
cd(R̂−pc )(1−pd −R̂)−s′

(pd = 0)∑s′2i=1 (s −1)I(Gpi ,T)P r[Gpi ]2s′R̂)= R̂(1−−s(pc = pd )(pc < pd )∑si=1 (s−1)I(Gpi ,T)P r[Gpi ]

2

2s

.

Horvitz-Thompson 法は不偏サンプリングであるため，右項は同じ値となる．証明は定理 1 と同様である．

□

提案アプローチは定理 1 と 2 に従い，サンプル数を削減する(pc > pd )cdProof: 式 (10)，(11) より，以下の式を得る．

(pc = 0)

ことができるため，既存のサンプリングに基づく手法より効率

Proof: 式 (8) より，下記の不等式を得る:

的に近似値を計算可能である．

3. 2 Scalable and Sampling BDD: S2 BDD(pc −R̂)(1−pd −R̂) < R̂(1−R̂)=s′s

ネットワーク信頼性の下限値と上限値を用いることにより，

s′ は下記で計算される:′s

サンプル数を削減することができる．効率的な下限値と上限値の計算方法として，S2 BDD を開発する．S2 BDD を用いること

c )(1−pd −R̂)
= s · (R̂−pR̂(1−R̂)()
d (R̂−pc )= s · 1 − pc (1−R̂)+pR̂(1−R̂)

により，ターミナルが接続もしくは非接続となる可能グラフの

(9)

′ <

pc <
= R̂ <= 1 − pd となるため, s = s である. R̂ を式 (9) から取り除くために pc と pd のパターンを分ける.
(
)
pd R̂
>
(1) pc = 0 : s′ = s 1 − R̂(1−= s(1 − pd ).
R̂)()
pc (1−R̂)′(2) pd = 0 : s = s 1 − R̂(1−R̂) >= s(1 − pc ).
)
(
p
(1−
R̂)+p
(R̂−pc ) >(3) pc = pd : s′ = s 1− c R̂(1−cR̂)=s(1 − 4pc (1 − pc )).
)(pc (1−R̂)+pd (R̂−pc ) >′(4) pc<pd : s =s 1−=s(1 − 4pc (1 − pd )).
R̂(1−R̂)′ >(5) pc>pd : (i) s = s(1 − 4pc (1 − pc )).(ii) s′ >= s(1 − 4(pc (1 −′pc ) + (pd − pc )). よって，s = s(1 − min(4pc (1 − pc ), 4(pc (1 −pd ) + (pd − pc )))).
□

従って，定理 1 が成り立つ．

Horvitz-Thompson 法: Horvitz-Thompson 法による R̂

らに，S2 BDD を構築しながら，上限値と下限値の計算に用いていない可能グラフのサンプリング行う．S2 BDD はメモリ使用量を抑えるため，一層のみから構成される．これは，l 層のBDD を構築した後は，l + 1 層の構築および下限値と上限値の計算に l − 1 層が必要ないという観測に基づく．

S2 BDD を下記に定義し，構築方法について述べる．
［Definition 2］ S2 BDD は層 l のノード集合 N および 1-シン
クと 0-シンクから構成される．S2 BDD は下記に示す変数をノード毎 n ∈ N に保持する:•

pn : n が対応する中間グラフの確率．

•

全ての f ∈ Fl における {cn,f } : 接続している節点の識

別子．フロンティア f と f ′ が存在枝にて接続している場合，cn,f と cn,f ′ は同じ値である．

の計算式は下記となる．

•

∑s

R̂ =

うち存在確率が高いものを効率的に探索することが出来る．さi=1 P r[Gpi ]·I(Gpi ,T),πiとなるフロンティアに接続している曖昧枝の総数 {f ′ ∈ Fl |cn,f =

πi = 1 − (1 − P r[Gpi ])s である．分散は下記で計算される．
∑s ( 1−πi )V ar[R̂] =I(Gpi , T)P r[Gpi ]2
i=1
πi
(
)
∑ ∑
πij −πi πj+ si sj,i=j
I(Gpi ,T)I(Gpj ,T)P r[Gpi ]P r[Gpj ],|πi π jπij = 1 − (1 − P r[Gpi ])s − (1 − P r[Gpj ])2 + (1 − P r[Gpi ] −P r[Gpj ])s である．分散は下記のように表現することができる [7]．

V ar[R̂] = R(1−R)−
s

全ての f ∈ Fl における {dn,f } : {f ′ ∈ Fl |cn,f = cn,f ′ }cn,f ′ }.
• 全ての f ∈ Fl における {tn,f } : 存在枝によって f に接続しているターミナルの数.

1-シンクと 0-シンクはターミナルが接続または非接続となった
確率 pc と pd をそれぞれ保持している．
提案アプローチは，S2 BDD を用いて下限値と上限値の計算
およびサンプリングの両方を行う．通常の BDD と S2 BDD の違いについて述べると，BDD は全ての層を保持するのに対し，S2 BDD は一層とシンクのみ保持する．例えば，図 2 では，

2Σsi=1 (s−1)I(Gpi ,T)P r[Gpi ]
.
2s

(10)

S2 BDD は三層目とシンクを保持するが，一層目と二層目は保持しない．

下限値と上限値を用いた分散は下記により計算できる．
d −R̂)V ar[R̂]′ = (R̂−pc )(1−p
−
s

∑s

.

ド集合 Nnext を計算する．構築法は，生成，結合，削除，サン(11)

プリングの 4 つの手順からなる．下記にそれぞれの手順を説明

i=1 (s−1)I(Gpi ,T)P r[Gpi ]2s

S2 BDD の構築のためには，枝 el を処理，l + 1 におけるノー

2［Theorem 2］ サンプル数 s, 下限値 pc , および上限値 1 − pd

する．

が与えられたとき，サンプル数が s′ の上限値と下限値を用いた

3. 2. 1 生成手順と結合手順

Horvitz-Thompson 法によるネットワーク信頼性の分散は，サ二分決定図に基づくアプローチは，二分決定図を構築する

ンプル数 s（1 と同式）の場合と分散が等しく，もしくは小さために生成と結合手順を実行する．この二つの手順を拡張し，くなる．

ネットワーク信頼性の精度を損なわずに，S2 BDD のサイズを効果的に小さくする．

まず，生成手順について説明する．生成手順では，枝 el を処

ため，まだターミナルが接続または非接続となっていない可能

理し，層 l + 1 のノード集合 Nnext を生成する．基本的な手順

グラフをサンプリングする．このような可能グラフのセットをと同様に，枝 el の状態を決定し，層 l のノードから層 l + 1 のWGu とする．WGu は，削除されたノードと S2 BDD に存在するノードを二つ生成する．新しいノードを生成するために，ノーノードに対応する中間グラフから得ることができる．効率的なドが保持する変数 (つまり，pn , {cn,f }, {dn,f }, および {tn,f })サンプリングのために，WG
u から動的計画法を用いてサンプリを更新する．

ングを実施する．加えて，層化ランダムサンプリングの考えを

2

S BDD のサイズを減少させるためには，ターミナルが接続か非接続かを早い段階で判断することが必要である．しかし，
2用いて，サブグループ毎のサンプル数を決定する．
まず，WG
u をサブグループにわけ，その後それぞれのサブグ

S BDD におけるノードはフロンティアの変数しか保持しておループから可能グラフをサンプリングする．サブグループ毎のらず，中間グラフ全体を保持しているわけではない．そのため，サンプル数は，サブグループ内の中間グラフの確率の総和に比中間グラフにおいてターミナルが接続か非接続かをフロンティ

例して決定する．ここでは，削除されたノードと S2 BDD 内のアの変数を用いて判断する．

ノードに分けて説明する．削除されたノードにおけるサブグ

次に，結合手順を説明する．S BDD における中間グラフは

ループは S2 BDD の同じ層で削除されたものをサブグループとそれぞれ異なる存在枝と非存在枝から構成されるため，フロン

する．これは削除された節点の確率がサンプル数を決定するに

ティアの変数も通常異なる．結合手順では，同じシンクに遷移は小さすぎるためである．層 l におけるサンプル数 sl は，s と2するノードを結合し，その確率値を足し合わせる．

層 l で削除されたノードの確率の総和 pˆsl の掛け合わせで求め［Lemma 1］ 層 l のノード n1 と n2 が与えられたとき, もしることができる．S2 BDD に存在するノードにおいては，それ∀f ∈ Fl において (1) cn1 ,f = cn2 ,f , および (2) (tn1 ,f = 0 and

ぞれのノードに対応する中間グラフそのものがサブグループに

tn2 ,f = 0) or (tn1 ,f > 0 and tn2 ,f > 0) の場合, el+1 , . . . , e|E|

対応し，ノードがもつ確率に従ってサンプル数を決定できる．

の状態が同じである n1 と n2 の子孫ノードは同じシンクに遷3. 3 計 算 量
提案アプローチの時間と空間計算量について説明する．

移する．

□

Proof: 割愛する．[12] を参照されたい．

［Theorem 3］ 曖昧グラフ G ，更新後のサンプル数 s′ ，およ3. 2. 2 削 除 手 順

び S2 BDD の最大幅 w が与えられたとき，提案アプローチの二分決定図のサイズはグラフサイズの増加に伴い指数関数的

時間と空間計算量はそれぞれ O(w2 log w + s′ (|V| + |E|)) とに増加するため，メモリ制約の問題上全てのノードを保持する
2ことは難しく，S BDD のサイズが w を超えないようにノード

O(w log w + |V| + |E|) なる．
Proof:

まず時間計算量について述べる．提案アプローチは，2を削除する．削除手順における課題は，高い効率性と精度を保

S BDD の構築とサンプリングの二つに分けることができる．

つために，どのノードを S2 BDD から削除するかである．定理

S2 BDD の構築では，生成および結合の処理にて，それぞれの1 と 2 より，pc と pd が少ない枝の処理により大きく増加する

ノードの属性を比較する．ノードの属性数はフロンティアの数場合，効果的にサンプル数を減少させることができる．ターミに比例し，フロンティア数は O(log w) となる．これは，存在まナルの接続性において n に対応する中間グラフのターミナルは

たは非存在となる枝数が最大で log w となるためである．そのtn,f が大きい f が存在するほど接続となりやすく，n に対応すため，S2 BDD 構築の時間計算量は O(w2 log w) となる．サン

る中間グラフのターミナルは dn,f が小さく，tn,f > 0 となる

プリングの時間計算量は O(s′ (|V| + |E|)) である．従って，時f が存在するほど非接続となりやすい．さらに，ノードの確率間計算量は O(w2 log w + s′ (|V| + |E|)) となる．

値 pn が大きい場合，n がシンクに遷移したときに pc と pd が空間計算量について述べる．空間計算量は S2 BDD のサイ

大きく増加する．これらの考えに基づいて，ノードの優先度をズと曖昧グラフのサイズに依存する．S2 BDD のサイズは，決定するヒューリスティック関数 h を定義する．
()
th(n) = pn · maxf ∈F n,f, d1
if tn,f > 0.
k

ノード数と属性数を掛けたものとなる．従って，空間計算量は

n,f

(12)

ターミナルが少なくとも一つがつながってるフロンティアに対O(w log w + |V| + |E|) となる．

□

4. 拡 張 手 法

して，フロンティアが多くのターミナルに接続している，もしネットワーク信頼性を計算する際，グラフのサイズが小さく

くはフロンティアが少ない曖昧枝をもっている場合に，この関なると，計算コストおよびメモリ使用量が小さくなる．そのた

数値は大きくなる．優先度が低いノードは削除され，削除されめ，S2 BDD 構築の前に曖昧グラフを前処理し，ネットワーク

たノードの確率値はネットワーク信頼性に加算されない．その信頼性を保ちながらサイズを小さくする．拡張手法は 2 枝接続ため，削除したノードを近似解を求めるためにサンプリング手コンポーネントを用いる [13]．

順で用いる．

［Definition 3］（2 枝接続コンポーネント） グラフ G = (V, E)

3. 2. 3 サンプリング手順が与えられたとき, サブグラフ C = (VC , EC ) は，EC からいか

提案アプローチは，層化サンプリングを用いた理論を達成す

なる枝を一つ取り除いてもグラフが分割されない場合，2 枝接るために，下限値と上限値の計算に用いた可能グラフのサンプ

続コンポーネントである．E から枝を取り除いた時，グラフがルとせずに，可能グラフをサンプリングする必要がある．その分割される場合，その枝は橋と呼ばれる. 橋に接続する節点は，

Algorithm 1: Computing the approximate network re-

Algorithm 2: Constructing S2 BDD

liability

input : Uncertain graph G, maximum size w, number of samples

input : Uncertain graph G, terminals T, maximum BDD size w,ssize of samples s, 2-edge connected components C,

output: Approximate network reliability R̂

bridges B, articulation points A

1

procedure Construction(G, w, s)

output: Approximate network reliability R̂

2Ordering(E);1procedure our approach3

pc , pd , pˆsl , c ← 0;2

set T to G;

3R̂, SG ← Preprocess(G, T, C, B, A);

4

4

for Gi ∈ SG do5

N ← CreateRoot; F ← null;
for l for 1, · · · , |E| do/* initialize probabilities and sampling

count */s′ ← s;5r ← Construction(Gi , w, s);6

6R̂ ← R̂ · r;

7pN , psi ← 0;

8F′ ← F; compute F based on el ;9while N is empty do

7return R̂;8

end procedure10n ← N.pop;

11

for state ∈ { non-existent, existent} do

12set(n, F′ , F, state, G, el );関節点と呼ばれる．2 枝接続コンポーネントの集合，橋の集合，

13

if n is 0-sink then pd ← pd + pn ;および関節点の集合をそれぞれ C, B, および A とする．

14

else if n is 1-sink then pc ← pc + pn ;

15

else

ある枝および節点を削除した際にグラフが分割されるか，さif hashmap[n] is not null then

16

れないかを 2 枝接続コンポーネント，橋，および間接点から把17握することができる．2 枝接続コンポーネントはネットワーク

18

トポロジからのみ計算できるため事前に計算する．

19

if |Nnext | <= w then20hn ← h(n);21Nnext .add(n); hashmap[n] ← n;

拡張手法は，枝刈り，分解，変換の 3 つのステップからなる．
枝刈りは不必要な枝と節点を削除し，分解は曖昧グラフを複数のグラフに分解，変換はグラフの変換を行う．枝刈りでは，

R[G] = R[G ′ ] となる G ′ を求める．G ′ の枝数は，ネットワーク
信頼性に影響しない枝を削除するため，G より小さい．分解でphashmap[n] ← phashmap[n] + pn ;else

pNnext ← pNnext + pn ;
else

22
23

p s i ← p si + p n ;24

for i for
1, · · · , ⌊s′ · (1 − pˆsl − pNnext − pc − pd )⌋は，R[G ′ ] = Πmi=1 R[Gi ] となるサブグラフ G1 , . . . , Gm を求める．変換では R[Gi ] = R[Gi′ ] となる Gi′ を求める．より小さいグ

doif Sampling(G, n) then c ← c + 1;

25

ラフになるよう変換するため，Gi′ の枝数は Gi より小さい．より具体的な処理においては [12] を参照されたい．

26

拡張技術はネットワーク信頼性の計算にかかる計算コストを

27

効果的に小さくすることができる．さらに，サンプリングの精28

for n ∈ N do
for i for 1, · · · , ⌊s′ · pNnext ⌋ do
if Sampling(G, n) then c ← c + 1;

29

度も向上することができる．
［Theorem 4］ R[G] =′if c + ⌊s′ · pNnext ⌋ >= s thenpb Πm
i=1 R[Gi ] となる G1 , . . . , Gm がbreak;

30

if Nn is empty then

与えられたとき，0 < R̂ < 1 and 0 < pb < 1 の場合において，

31

ネットワーク信頼性の分散は小さくなる．

32

break;

Proof: ネットワーク信頼性は R̂ = pb · Πi R̂[Gi ] となり，分散

33

N ← Nnext ;は下記の式により計算できる．

V ar[R̂] = V ar[pb · Πi R̂[Gi ]]2= (V ar[pb ] + pb 2 )(V ar[R̂[G1 ]] + R̂[G1 ] ) · · ·34sort N in descending order of h(n);35pˆsl ← pˆsl + psi ; compute s′ ; clear Nnext ; clear hashmap;

36

compute R̂ based on the sampling;37

return R̂;38

end procedure2(V ar[R̂[Gm ]] + R̂[Gm ]2 ) − pb 2 · Πm
i=1 R̂[Gi ]2= pb 2 Πi (V ar[R̂[Gi ]] + R̂[Gi ]2 ) − pb 2 Πi R̂[Gi ]2

R̂[Gi ])
= pb 2 Πi ( R̂[Gi ](1−+ R̂[Gi ] ) − pb 2 Πi R̂[Gi ]s
R̂[Gi ])
= pb 2 Πi R̂[Gi ]( (1+(s−1)) − pb 2 Πi R̂[Gi ]s<2
pb 2 Πi R̂[Gi ]− pb ΠisR̂[Gi ]s

5. 提案アプローチのアルゴリズム

2

2

本章では，提案アプローチのアルゴリズムについて述べる．

2

R̂[Gi ])
R̂)
= pb R̂[Gi ](1−< R̂(1−ss

アルゴリズム 1 は，提案アプローチの概要の疑似コードである．提案アプローチはまずグラフの前処理を行う (line 3)．そ(13)

れぞれの分解されたグラフに対して，S2 BDD を構築し，ネッ

ここで，V ar[pb ] = 0 である． V ar[R̂] は分解せずにネットワー

トワーク信頼性の近似解を得る (lines 4–5)．全ての近似解を掛□け合わせたものが，全体のグラフのネットワーク信頼性となる

ク信頼性を計算した場合に比べて小さい．

する．提案アプローチ，拡張技術を用いない提案アプローチ，

表 1: データセット
名称
Zachary-karate-clubAmerican-Revolution
DBLP before 2000
DBLP after 2000
Tokyo
New York City
Hit-direct

略称Karate
Am-Rv
DBLP1
DBLP2
Tokyo
NYC
Hit-d

タイプ
SocialAﬃliation
Coauthorship
Coauthorship
Road network
Road network
Protein

節点数
34
141
25,871
48,93826,370180,188
18,256

サンプリングに基づくアプローチ，および二分決定図に基づ

枝数
78
160
108,459
136,034
32,298208,441
248,770

くアプローチの凡例をぞれぞれ Pro(MC)，Pro(MC)w/o ext，

Sampling(MC)，および BDD とする．Horvits-Thompson 法は同傾向の結果であるため割愛する．
図 3 は k が 5，10，20 の場合における応答時間を示す．DNF
はメモリ制限により計算できなかった場合を表す．図 3 より，

2(line 6)．アルゴリズム 2 は S BDD 構築の疑似コードである．

提案アプローチはサンプリングに基づくアプローチより高性能

予め決められた枝の順序に従い，枝を選択しフロンティア集合

であることを示している．二分決定図に基づくアプローチは大を計算する (lines 6–8)．update 関数 (line 12) はノードの変数

規模なグラフではメモリ枯渇により計算ができない．提案アプを更新し，ターミナルが接続しているかどうかを計算する．更

ローチは Tokyo と NYC データセットにおいての効率性が高い．

新されたノードが 0 シンクの場合, pn を pd に足し (line 13)，1

これは，道路ネットワークは平面グラフに近いため，S2 BDD

シンクの場合，pn を pc に足す (line 14). その他の場合は, ハッの構築が効率的および前処理によるグラフサイズの削減が大きシュ値を計算し，n のハッシュが空ではない場合，n の確率値

いためである．一方で，Hit-direct データセットでは，節点のをハッシュ値に対応するノードの確率値に足す (lines 16–17)．

平均次数が大きく上限値と下限値の幅が狭まらないため，効率ハッシュが空の場合, n の優先度を更新した後，n を Nnext お性が低いが，それでもサンプリングに基づくアプローチより効

よびハッシュに挿入する (lines 19–21). Nn の中のノード数が率的である．

w を超えたとき，n を削除し n に対応する中間グラフから可能

6. 4 最大幅の影響

グラフをサンプリングする (lines 22–25). 拡張手法のアルゴリ

S2 BDD の最大幅を変化させた場合のメモリ使用量と応答時間を評価する．図 4 は，(a) メモリ使用量と (b) 応答時間を示

ズムにおいては [12] を参照されたい．

す．図 4(a) より，最大幅を大きくするとメモリ使用量が大きく

6. 評 価 実 験なることがわかる．一方で，グラフサイズには影響されていな

提案アプローチを計算効率，精度，およびメモリ使用量の観

いことがわかる．提案アプローチはメモリ使用量の観点では，大規模なグラフに対応することができることを示している．図点から評価を行う．

6. 1 データセット

4(b) より，最大幅は応答時間にそれほど影響していないことが実験にて使用したデータセットを表 1 にまとめる. 最初の 2 つわかる．最大幅が大きいとき，サンプル数はより削減可能だが，のデータセット; Zachary-karate-club と American-revolution

S2 BDD の構築に時間がかかる．提案アプローチの応答時間はは，KONECT（注 2）からダウンロードした小規模なグラフデー

最大幅にロバストであることがわかる．これらの結果は，提案タである．小規模なグラフでは，枝の存在確率は一様分布にアプローチは大規模なグラフに対しても効果的に応答時間を削基づいてランダムに与えた．他の 5 つのデータセット; DBLP

減できることを示している．

before 2000, DBLP after 2000, Tokyo, New York City, および Hit-direct は，大規模なグラフデータである．枝の存在確率

6. 5 精度

次に，提案アプローチとサンプリングに基づくアプローチの精度を検証する．サンプリング手法として，モンテカルロ

は，それぞれのデータの枝の属性値に基づいて計算した．

6. 2 設定と実装

法と Horvitz-Thompson 法（Pro(HT) と Sampling(HT)）の両それぞれのデータセットに対して，ターミナルをランダムに方を用いる．大規模なグラフでは厳密解を計算できないため，選び 20 回の検索を行う (ただし，精度の評価は除く）．ターミナ

厳密解が計算できた Karate と Am-Rv データセットを評価に

ル数 k ，および S2 BDD の最大幅を w 変化させる. 比較手法と用いる．分散とエラー率を近似解の精度の指標とし，それぞして，サンプリングに基づく手法と BDD に基づく手法を用いれ次の式で計算する．variance =

q

q

（注 3）

る．BDD に基づく手法は最新ライブラリである TdZDDを

error rate =q

1 Σ 2 |R −R̂
Σi=1
i
i,j |
j=1

q1 ·q2 ·Riq2
1 Σ 2 (R −R̂
Σi=1
i
i,j )
j=1

q1 ·q2

およびとし，Ri と R̂i,j は i 番目の用いる．全てのアルゴリズムは C++で実装され，Intel Xenon

ネットワーク信頼性の厳密解と，i 番の計算における j 番目のE7-8860v4，256GB RAM が搭載された計算機にて実験を行う.

近似解をそれぞれ示す．100 回の計算を行い，それぞれに対し

6. 3 効 率 性て 100 回近似解を計算する．

提案アプローチ，拡張技術を用いない提案アプローチ，サン

表 2 は Karate と Am-Rv データセットにおける精度を示す．

プリングに基づくアプローチ，および二分決定図に基づくアプ

表 2 より，提案アプローチは精度においてサンプリングに基づ

ローチの効率性を比較する．提案アプローチとサンプリング

くアプローチを上回っていることがわかる．また，Am-Rv デーに基づくアプローチにおいて，モンテカルロ法を用いて s を

タセットでは，提案アプローチのエラー率が常にゼロであるた

は 10,000 とする．提案アプローチにおいては，w を 10,000 とめ，常に厳密解を計算できていることがわかる．サンプリン（注 2）：http://konect.uni-koblenz.de/

ラー率が大きくなっている．これは，ネットワーク信頼性が非グに基づくアプローチは k が 20 の場合に，分散は小さいがエ（注 3）：https://github.com/kunisura/TdZdd

2500

2000

1000

DBLP1

DBLP2

Tokyo

NYC

DBLP1

DBLP2

(a) k = 5

Tokyo

NYC

0

Hit-d

DBLP1

DBLP2

(b) k = 10

Tokyo

NYC

DNF

DNF

DNF

DNF

DNF

0

Hit-d

1000

500
DNF

DNF

DNF

DNF

0

DNF

500
DNF

500

1500

DNF

1000

1500

DNF

1500

2000

Pro(MC)
Pro(MC)w/o ext
Sampling(MC)
BDD

DNF

Response time [sec]Response time [sec]

2000

2500
Pro(MC)
Pro(MC)w/o ext
Sampling(MC)
BDD

DNF

Pro(MC)
Pro(MC)w/o ext
Sampling(MC)BDD

Response time [sec]

2500

Hit-d

(c) k = 20

図 3: 効率性

10

謝

2000
DBLP1
DBLP2
Tokyo
NYC
Hit-d

Responce time [sec]Memory usage [GB]

100

1
0.1
0.01
1K

10K
100K
Maximum width

1500
1000

本研究は JST ACT-I（JPMJPR18UD）および科学研究費

DBLP1
DBLP2
Tokyo
NYC
Hit-d

（JP15K21069）の支援によって行われた．謝意を表す．
文

500
0
1K

1M

(a) メモリ使用量

10K
100K
Maximum width

1M(b) 応答時間

図 4: 最大幅の影響

表 2: 精度kKarateMethod

5

10

20

分散

辞

Am-Rv

エラー率

分散

エラー率

Pro(MC)

0.025

0.036

0

0

Pro(HT)

0.025

0.036

0

0

Sampling(MC) 0.025

0.037

0.43·10−4

0.061

Sampling(HT)

0.029

0.042

0.31·10−4

0.059

Pro(MC)

0.013

0.058

0

0

Pro(HT)

0.014

0.059

0

0

Sampling(MC) 0.013

0.058

0.099·10−5

0.38

Sampling(HT)

0.015

0.062

0.12·10−5

0.37

Pro(MC)

0.76 ·10−3

0.054

0

0

Pro(HT)

0.85·10−3

0.057

0

0

Sampling(MC)0.78·10−3

0.056

0.10·10−3

1.00

Sampling(HT)0.86·10−3

0.057

0.10·10−3

1.00

常に小さいため，サンプリングに基づくアプローチでは，ターミナルが接続している可能グラフをサンプリングすることができないためである．これにより，近似解は頻繁にゼロとなり，エラー率は 1 となりやすい．これらの結果より，提案アプロー
チは少ないサンプル数で高い精度を達成し，小規模グラフにおいては厳密解を計算できることがわかる．

7. ま と め
本論文では，ネットワーク信頼性において高い効率性と精度を達成するアプローチを提案した．提案アプローチは精度を損なわずにサンプリング数を削減させた．S2 BDD より効果的に下限値と上限値を求め，ネットワーク信頼性の効率的な近似計算を実現した．実験結果より，提案アプローチは既存の手法より 51.2 倍高速かつ高精度であることを示した．

献[1] Michael O Ball, Charles J Colbourn, and J Scott Provan.
Network reliability. Handbooks in operations research andmanagement science, Vol. 7, pp. 673–762, 1995.
[2] Leslie G Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, Vol. 8,
No. 3, pp. 410–421, 1979.
[3] Saurabh Asthana, Oliver D King, Francis D Gibbons, andFrederick P Roth. Predicting protein complex membershipusing probabilistic network reliability. Genome research,
Vol. 14, No. 6, pp. 1170–1175, 2004.
[4] R Hamer, G De Jong, E Kroes, and P Warﬀemius. The
value of reliability in transport–provisional values for the
netherlands based on expert opinion. Transport ResearchCentre of the Dutch Ministry of Transport, 2005.
[5] S Thompson. Sampling. Wiley, 2002.
[6] Gary Hardy, Corinne Lucet, and Nikolaos Limnios. Kterminal network reliability measures with binary decision
diagrams. IEEE Transactions on Reliability, Vol. 56, No. 3,
pp. 506–515, 2007.
[7] Ruoming Jin, Lin Liu, Bolin Ding, and Haixun Wang.
Distance-constraint reachability computation in uncertain
graphs. PVLDB, Vol. 4, No. 9, pp. 551–562, 2011.
[8] Jun Kawahara, Takeru Inoue, Hiroaki Iwashita, andShinichi Minato. Frontier-based search for enumerating all
constrained subgraphs with compressed representation. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol. 100, No. 9, pp.
1773–1784, 2017.
[9] Rajeev Motwani and Prabhakar Raghavan. Randomized algorithms. Chapman & Hall/CRC, 2010.
[10] George S Fishman. A comparison of four monte carlo methods for estimating the probability of st connectedness. IEEE
Transactions on reliability, Vol. 35, No. 2, pp. 145–155,
1986.
[11] Eugène Manzi, Martine Labbé, Guy Latouche, andFrancesco Maﬃoli. Fishman’s sampling plan for computing network reliability. IEEE Transactions on Reliability,
Vol. 50, No. 1, pp. 41–46, 2001.
[12] Yuya Sasaki, Yasuhiro Fujiwara, and Makoto Onizuka. Efficient network reliability computationin uncertain graphs. In EDBT, 2019.
[13] Lijun Chang, Jeﬀrey Xu Yu, Lu Qin, Xuemin Lin, Chengfei
Liu, and Weifa Liang. Eﬃciently computing k-edge connected components via graph decomposition. In SIGMOD,
pp. 205–216, 2013.