日本データベース学会和文論文誌
一般論文

Vol. 18-J, Article No. 7, 2020 年 3 月

b e e d34

曖昧グラフにおける効率的なネット

e2

ワーク信頼性の近似計算

c

b

e6

e e5
a 1
e
(a) J×b›‡

佐々木 勇和 1

藤原 靖宏 2

鬼塚 真 3

d

b

c
a

d

b

e

a

d
c

c
e

a

e

(b) íšb›‡図 1: 曖昧グラフ

ネットワーク信頼性は曖昧グラフにおいて与えられた節点間の接続確率を評価する重要な指標のひとつである．ネットワーク信存在（2 つが非存在）するため，可能グラフの存在確率は 0.0216

頼性の計算は #P 完全問題であるため，近似解を計算する手法が(0.74 · (1 − 0.7)2 ) となる．左と中央の可能グラフのみターミナル

提案されている．本稿では，サンプリングに基づく新たな近似解が接続しているため，これらの存在確率はネットワーク信頼性に計算手法を提案する．提案アプローチは層化サンプリングを拡張加算される．

し，下限値と上限値を用いてサンプル数を削減する．これによ

本稿では，ネットワーク信頼性をサンプリング技術を用いて近り近似計算の効率化と近似解の精度の向上を可能にする．下限似計算する．問題定義は以下となる．

値と上限値を効率的に計算するために，二分決定図を拡張した問題定義 (ネットワーク信頼性の近似計算)：曖昧グラフ G ，

S2 BDD を開発する．提案アプローチは S2 BDD を構築しながら，
動的計画法を用いて効率的なサンプリングも実現する．実データ

ターミナル集合 T，およびサンプル数 s が与えられたとき， ネッ

を用いた実験により，提案アプローチが高精度を保ちながら，既トワーク信頼性の近似値 R̂[G, T] を効率的に計算する．
サンプリングの計算コストはサンプル数の増加に従い大きくな

存のサンプリングに基づくアプローチより最大で 51.2 倍高速でる．本研究では，近似精度を損なわずにサンプル数を削減させ，あることを示す．

効率的な計算を行う．研究課題は，(1) どのように精度を理論的1に保証しながらサンプル数の削減させるか，および (2) どのようはじめにに理論的な結果を効率的に実現するかである．まず，最初の課題
世の中の理解と設計のためには，オブジェクト間の関係性をモ

においては，層化サンプリング [14] を拡張する．層化サンプリ

デル化し解析することが必要であり，実世界のオブジェクト間のングは予測値の下限値と上限値を用いることにより予測値の精度

関係性はグラフによりモデル化することができる．グラフの解析を向上させることが可能であり，近似精度を損なわずにサンプルにおける基礎的なトピックとして，ネットワーク信頼性の計算が数を削減可能なことを証明する．

ある [2, 15]．ネットワーク信頼性は枝に存在確率が付与されてい精度を保ちつつサンプル数を削減できることを理論的な結果にる曖昧グラフにおいて，与えられた複数の節点（ターミナルと呼より保証することができるが，ネットワーク信頼性の効率的な計ぶ）が相互接続する確率である．例えば，タンパク質相互反応は算に用いるには二つの課題ある．一つ目の課題は，効率的なネッ

気温や湿度等の状況により反応が常に行われるわけではないた

トワーク信頼性近似計算のために，ネットワーク信頼性の下限値

め，曖昧グラフとしてモデル化することができる [1]．タンパクと上限値を効率的に求めることが必要がある．二つ目は，精度の質の機能の解明のために，分析者は複数のタンパク質間の関係の保証のために，下限値と上限値の計算に用いた可能グラフをサ

強さをネットワーク信頼性を用いて評価している．その他にも，ンプリング対象としてはいけないことである．これらを達成す通信ネットワーク [2] や都市計画 [5] などの応用にてネットワー

る効果的な方法は自明ではない．そこで， 二分決定図を拡張し

ク信頼性は広く利用されている．

た scalable and sampling BDD (S2 BDD) を開発する．S2 BDD は

ネットワーク信頼性の計算は #P 完全問題として知られており，ターミナルが接続または非接続となる可能グラフを優先的に探計算コストは非常に大きい [15]．これは，可能グラフを列挙する

索することにより，下限値と上限値を効果的に求めることができことが必要であることに起因する．可能グラフは，元々の曖昧グる．また提案アプローチでは，S2 BDD を構築しながら，動的計

ラフと同じ節点および枝のサブセットを持つグラフである．可能

画法を実施し，効率的に可能グラフをサンプリングする．このサグラフは存在確率をもち，枝の存在確率から計算される．ターンプリングは，下限値および上限値の計算に用いられた可能グラ

ミナルが全て接続となる可能グラフの確率を足し合わせること

フをサンプリングすることを避けることができる．さらに，提案

で，ネットワーク信頼性を計算できる．図 1 は曖昧グラフと 3 つアプローチは，曖昧グラフのサイズが減少することにより，さらの可能グラフの例を示し，黒の点はターミナルを表す．枝の存に効率化可能である．そこで 2 枝連結グラフを用いた拡張技術を

在確率を 0.7 とする場合，それぞれの可能グラフは 4 つの枝が提案する．拡張技術は，ネットワーク信頼性を損なうことなく，不必要な部分グラフの枝刈り，グラフの分割，およびより小さい

1 正会員

大阪大学大学院情報科学研究科

グラフへの変換を行う．実データを用いた評価実験を行い，提案

sasaki@ist.osaka-u.ac.jp
NTT コミュニケーション科学基礎研究所
yasuhiro.fujiwara.kh@hco.ntt.co.jp

アプローチは既存のサンプリングに基づくアプローチより最大

2 正会員
3 正会員

51.2 倍高速かつ高精度であること示す．

大阪大学大学院情報科学研究科

本稿の構成は次の通りである．まず，2 にて事前知識について

onizuka@ist.osaka-u.ac.jp

1

日本データベース学会和文論文誌
一般論文

Vol. 18-J, Article No. 7, 2020 年 3 月

R̂[G, T] をネットワーク信頼性の近似解と定義する．簡単化の説明する．3 にて提案アプローチ，4 にて拡張手法を説明する．5
にて提案アプローチのアルゴリズムを述べる． 6 にて実験結果をため， R と R̂ を R[G, T] と R̂[G, T] の代わりにそれぞれ用いる．

示し， 7 にて本稿をまとめる．

ターミナル数が k であるネットワーク信頼性は k ターミナル信頼性と呼ばれ，最も一般的なネットワーク信頼性である [6]． k

事前知識

2

が 2 の場合でも，ネットワーク信頼性は #P 完全問題である [15]．

本章では，事前知識として，曖昧グラフ，ネットワーク信頼性，二分決定図 [6] とサンプリング [7] がネットワーク信頼性計算

二分決定図，およびサンプリングについて説明する．
2.1のための主要な技術である．二分決定図に基づくアプローチは小曖昧グラフ

規模なグラフに対して効率的に厳密解を計算可能で，サンプリン

連結かつ無向な曖昧グラフを G = (V, E, p) と定義する．V はグに基づくアプローチは大規模なグラフに対して近似解を計算可節点集合， E ⊆ V × V は，曖昧枝の集合，および p : E → (0, 1]

能である．

は，曖昧枝 e ∈ E の存在確率 p(e) を決定する関数である．節点 v

2.3

二分決定図

と v ′ 間の枝 e ∈ E を e = (v, v ′ ) と定義する. 曖昧枝 e の状態は，二分決定図（BDD）は有向非循環グラフ D = (N, A) で表現さ確率 p(e) で存在または確率 1 − p(e) で非存在である．曖昧枝のれる．二分決定図のノード集合を N，二分決定図のアーク集合を存在確率は，他の枝の存在確率と独立に計算されると想定する．

A と定義する *1．図 2(a) は図 1 のグラフにおける二分決定図を可能グラフ G p = (V, E p ) は，曖昧グラフ G の全節点と枝のサ

示す. 各ノードは中間グラフに対応しており，アークは存在枝ま

ブセットから成る. 枝には存在確率は無く，E\E p は非存在枝でたは非存在枝と対応している．二分決定図は，入次数が 0 の枝がある．可能グラフは存在確率を Pr[G p ] をもち，以下の式で計算一つあり，ルートノードと呼ばれる (図 2(a) における G1 ). それされる．

ぞれのノードは，二つの出次 outgoing アークがあり，0-アークおPr[G p ] =∏e∈E p p(e) ·∏e ∈E\E p (1 − p(e)).

よび 1-アークと呼ばれる (図 2(a) ではそれぞれ点線と実線で表さ(1)れている)．0-アークおよび 1-アークはそれぞれ非存在枝と存在枝を表しており，それぞれのアークの重みは枝の存在確率または曖昧グラフ G の可能グラフの数は，それぞれの枝が存在と非存

非存在確率を表している．ルートノードからの深さを層 l と定義

在の二つの状態を取りうるため，2 |E | である．G の全ての可能グ

する．層 l のノードは，枝 e1 から el−1 が存在または非存在の中ラフの集合を W G と定義する．

間グラフを表し，el から e |E | は曖昧枝である．二分決定図は出次中間グラフ GE (E ∃, E¬ ) は，存在枝集合 E ∃ , 非存在枝集合 E¬ ，数がゼロのノードが 2 つあり，それぞれ 0-シンクと 1-シンクとおよび曖昧枝の集合 E\(E ∃ ∪ E¬ ) から構成される曖昧グラフであ呼ばれる（図 2(a) ではそれぞれラベル 0 と 1 の四角で表されてる．中間グラフの存在確率 Pr[GE (E ∃, E¬ )] は以下の式で計算さいる）．中間グラフのターミナルが接続した場合，対応するノー

れる．

∏

∏

ドは 1-シンクに遷移する．一方，中間グラフのターミナルが非接(2)

続した場合，対応するノードは 0-シンクに遷移する．ルートノー

簡単化のため， Pr[GE (E ∃, E¬ )] の代わりに Pr[GE ] を使用する.

続となる中間グラフを得ることができる．そのため，1-シンクに中間グラフ GE (E ∃, E¬ ) の可能グラフの数は，2 |E\(E∃ ∪E¬ )| である．

アークが遷移しているノードの確率値の総和を取ることにより，

Pr[GE (E ∃, E¬ )] =GEe ∈E∃ p(e) ·e ∈E¬ (1 − p(e)).

ドから 1-シンクまでのアークを辿ることにより，ターミナルが接の全ての可能グラフの集合を W GE と定義する．中間グラフ

ネットワーク信頼性を計算することができる．

において，存在枝を用いて節点間に経路がある場合，節点は接続

ネットワーク信頼性計算のための二分決定図を構築する方法としていると呼び，存在枝と曖昧枝を用いて経路が無い場合，節点

して，フロンティアに基づく手法がよく用いられている [8]．こは非接続していると呼ぶ．ここで，曖昧枝を用いて節点に経路がの手法はまず枝を順序付けし，順序に従って枝の状態を決定してある場合，節点が接続か非接続はあきらかではない．

いく．二分決定図が既に層 l まで構築済みの場合，この手法は el

2.2の状態を決定し，層 l + 1 の節点集合を構築する．フロンティア

ネットワーク信頼性

ネットワーク信頼性は，全てのターミナルが接続となっているに基づく手法では，存在/非存在枝と曖昧枝の両方をもつ節点は可能グラフの確率を全て足し合わせることで計算できる．ネット

フロンティア f と呼ばれ，層 l でのフロンティアの集合を Fl とワーク信頼性の定義は以下である．

する．図 2(b) は，枝 e1 と e2 を処理した後の中間グラフを表し，Definition 1（ネットワーク信頼性）

黒の実線，黒の破線，および灰色の破線はそれぞれ存在枝，非存任意の k 個のターミナル集

在枝，および曖昧枝を示す．節点 b と c は存在/非存在と曖昧枝合 T と曖昧グラフ G が与えられたとき, ネットワーク信頼性の両方をもつため，フロンティアである．同じ層のノードは全て

R[G, T] は下記の式で計算される．
R[G, T] =∑G p ∈WG I(G p , T) · Pr[G p ],同じフロンティア集合をもつ．フロンティアに基づく手法は，フロンティアの変数（例えば，曖昧枝の数や接続済みのターミナル(3)

数など）を保持しており，フロンティアの変数が同じになった場

G p は可能グラフを示し， I(G p , T) は G p において全てのターミナルが接続なっている場合に 1 を返し, その他の場合 0 を返す関*1 本論文では，グラフの節点と枝を “節点” および “枝” とそれぞれ呼び，二分決定図の節点と枝を “ノード” と “アーク” とそれぞれ呼ぶ．

数を示す．

2

日本データベース学会和文論文誌
一般論文

Vol. 18-J, Article No. 7, 2020 年 3 月

½1

G4

G1

½2

0.3

0.7

G2

G3

0.3

½3

e2

G4
G5
G6
0.3
0.3 0.7
0.7
0.7
0.3

½4

G7
0.3

½5

0.7

c

きるため，近似精度を損なわずにサンプル数を削減することがで

e6

きる．

e e
a 1 5 e0.7

0.7 0.3

グはネットワーク信頼性の近似計算の分散を小さくするこがで

b e e d3
4

層化サンプリングを適用するために，可能グラフの集合 W G を

3 つのサブ集合グループ WcG , WdG , および WuG に分ける．WcG お

G5 b e3 e4 d
e2
e6
c
e
e
1
5 e
a

G

よび Wd は，それぞれターミナルが接続および非接続となる可G能グラフのみを含んでおり，Wu は二つの集合に含まれていない
G

½6

0.7
G9

0.3

i¥a

0

0.7

1

(a) xÀàÒÕ

G

可能グラフが含まれている．Wc と Wd に含まれる可能グラフ

G8
0.3

G6 b e e d
4
3
e2
e6
c
e
e
1
5
a
e

の確率の総和をそれぞれ pc と pd とする．ここで，定義 1 より，上限値と下限値は下記の式により計算できる．

R=(b) ½3-°Ñb›‡∑G p ∈WGc= pc +

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

≥ pc .
R = 1−∑∑

G p ∈WGu

G p ∈WGd= 1 − pd −合にノードを結合することで，ノードの数を効果的に削除するこPr[G p ] +∑∑G p ∈WGu

I(G p , T)Pr[G p ]I(G p , T)Pr[G p ]Pr[G p ] −G p ∈WGu∑

G p ∈WGu(Pr[G p ] − I(G p , T)Pr[G p ])(Pr[G p ] − I(G p , T)Pr[G p ])≤ 1 − pd .

とができる．
二分決定図のサイズはノードの数で定義され，メモリ使用量はこれらの式より， pc ≤ R ≤ 1 − pd を得ることができる．

二分決定図のサイズに依存する [6]．実際のメモリ使用量は事前

分散は予測手法にも依存する．提案アプローチでは，代表的なに推定することができないため，小規模なグラフに対してもメモ二つの予測手法であるモンテカルロ法と Horvitz-Thompson 法を

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

用いる．それぞれの手法について，下限値と上限値を用いてサン

2.4

サンプリング

プル数を削減できることを下記で述べる．

サンプリングは近似解を計算するために用いられる一般的な方

モンテカルロ法: モンテカルロ法による R̂ の計算式は下記と法である．サンプル数 s が与えられたとき，サンプリングに基づなる．

くアプローチは，(1) 曖昧グラフから可能グラフを取り出す，(2)
その可能グラフにおいてターミナルが接続かどうかを計算する，という処理を s 回繰り返す．可能グラフを取り出しと接続確認の∑s

i=1 I(G p i ,T).

(4)

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

(5)

R̂ =

s

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

ために，それぞれ時間計算量 O(|E|) および O(|V| + |E|) が必要であるため，サンプリングに基づく手法の計算量は O(s · (|V| + |E|))となる．
サンプリングに基づく手法は乱択アルゴリズム [12] であるた

不偏サンプリングであるため（つまり E[ R̂] = R），分散は下記

め，その精度は分散により評価される．そのため，分散が小さいの式で計算できる [11]．

とエラー率が小さいことを示す．理論的な分散値を達成するためには，可能グラフをその存在確率に基づいて取り出す不編サンプR̂)V ar[ R̂] = R(1−R)≈ R̂(1−.
ss

リング (unbiased sampling) が必要である．また，サンプル数が増加すると，分散は減少するが計算量が増加するため，精度と時(6)

上限値と下限値を用いた場合，分散は下記の式で計算でき間計算量にはトレードオフが存在する．

る [4, 11]．

サンプリングに基づく s-t 到達可能性問合せ [9, 10] に関する研d − R̂)V ar[ R̂]′ = (R̂−pc )(1−p.
s

究は活発に行われている．しかし，これは 2 点のターミナル間の接続性にのみ着目しており，k 点のターミナルには単純には拡張(7)

式 6 および式 7 より，下記の式を得ることできる．

できない．筆者らの知る限り，ネットワーク信頼性を効率的に近似計算可能な乱択アルゴリズムは提案されていない．

R̂(1− R̂)d − R̂)≥ (R̂−pc )(1−p
.
s
s

(8)

提案アプローチ3

式 (8) より, 下記の定理を得られる．

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

Theorem 1

サンプル数 s, 下限値 pc , および上限値 1 − pd が与えられたとき，サンプル数 s ′ (≤ s) が下記の式となる場合，サンプ

サンプル数の削減

本節では，層化サンプリング [4, 11] に基づいて高精度を維持

ル数が s ′ の上限値と下限値を用いたモンテカルロ法によるネッ

しつつサンプル数を削減できることを証明する．層化サンプリン

トワーク信頼性の分散は，サンプル数 s の場合と分散が等しい，

3日本データベース学会和文論文誌
一般論文

Vol. 18-J, Article No. 7, 2020 年 3 月

もしくは小さくなる．

Proof: 式 (10)，(11) より，以下の式を得る．

⌊s(1 − pd )⌋.
⌊s(1 − pc )⌋.






⌊s(1
− 4 · pc (1 − pc ))⌋.
s′ =
⌊s(1 − 4 · pc (1 − pd ))⌋.
 ⌊s(1 − min(4pc (1 − pc ), 4(pc (1 − pd ) + (pd − pc )))⌋.
( R̂−pc )(1−p d − R̂)−s′(pc = 0)(pd = 0)(pc = pd )(pc < pd )ネットワーク信頼性の下限値と上限値を用いることにより，サンプル数を削減することができる．効率的な下限値と上限値の計算方法として，S2 BDD を開発する．S2 BDD を用いることにより，ターミナルが接続もしくは非接続となる可能グラフのうち存在確率が高いものを効率的に探索することが出来る．さらに，(9)

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

S2 BDD を下記に定義し，構築方法について述べる．
Definition 2• pn : n が対応する中間グラフの確率．
• 全ての f ∈ Fl における {cn, f } : 接続している節点の識別子．

□

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

フロンティア f と f ′ が存在枝にて接続している場合，cn, fHorvitz-Thompson 法: Horvitz-Thompson 法による R̂ の計算と cn, f ′ は同じ値である．

式は下記となる．

• 全ての f ∈ Fl における {dn, f } : { f ′ ∈ Fl |cn, f = cn, f ′ } とな∑si=1 Pr[G p i ]·I(G p i ,T)

πi

るフロンティアに接続している曖昧枝の総数 { f ′ ∈ Fl |cn, f =,cn, f ′ }.
• 全ての f ∈ Fl における {tn, f } : 存在枝によって f に接続しπi = 1 − (1 − Pr[G pi ])s である．分散は下記で計算される．

+

i

1−πi
πi

)

)

S2 BDD は層 l のノード集合 N および 1-シンクと0-シンクから構成される．S2 BDD は下記に示す変数を各ノード
n ∈ N が保持する:(pd − pc )))).

πi j −πi π jj,i,j
πi π j□Scalable and Sampling BDD: S2 BDD

3.2

p d 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 ).
)(c ( R̂−p c )≥s(1 − 4pc (1 − pc )).
(3) pc = pd : s ′ = s 1− pc (1−R̂)+p
R̂(1−
R̂)
(
)
p
(1−
R̂)+p
(
R̂−p
)
(4) pc <pd : s ′=s 1− c R̂(1−dR̂) c ≥s(1 − 4pc (1 − pd )).
(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 ) +

∑s ∑s

.

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

除くために pc と (pd のパターンを分ける
.
)

i=1

2

とができるため，既存のサンプリングに基づく手法より効率的にpc ≤ R̂ ≤ 1 − pd となるため, s ′ ≤ s である. R̂ を式 (9) から取り(

2s

提案アプローチは定理 1 と 2 に従い，サンプル数を削減するこ(pc > pd )c )(1−p d − R̂)s ′ = s · (R̂−pR̂(1−R̂)()
pc (1− R̂)+p d ( R̂−pc )= s· 1−R̂(1− R̂)V ar[ R̂] =i=1 (s−1)I (G p i ,T)Pr[G p i ]じ値となる．証明は定理 1 と同様である．

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

Horvitz-Thompson 法は不偏サンプリングであるため，右項は同(pc − R̂)(1−p d − R̂)R̂)≤ R̂(1−
s′
s

∑s

′
2
i=1 (s −1)I(G p i ,T)Pr[G p i ]2s′R̂)= R̂(1−−s

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

R̂ =

∑s

ているターミナルの数.

I(G pi , T)Pr[G pi ]2

1-シンクと 0-シンクはターミナルが接続または非接続となった確率 pc と pd をそれぞれ保持している．

I(G pi ,T)I(G p j ,T)Pr[G pi ]Pr[G p j ],提案アプローチは，S2 BDD を用いて下限値と上限値の計算おπi j = 1−(1− Pr[G pi ])s −(1− Pr[G p j ])2 +(1− Pr[G pi ]− Pr[G p j ])s

よびサンプリングの両方を行う．通常の BDD と S2 BDD の違いである．分散は下記の式で計算できる [7]．

V ar[ R̂] = R(1−R)−
sについて述べると，BDD は全ての層を保持するのに対し，S2 BDDs (s−1)I(G ,T)Pr[G ]2
Σi=1
pi
pi
.
2s

は一層とシンクのみ保持する．例えば，図 2 では，S2 BDD は三(10)

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

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

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

2s

2

.

ド集合 Nnext を計算する．構築法は，生成，結合，削除，サンプリ
ングの 4 つの手順からなる．下記にそれぞれの手順を説明する．

(11)

3.2.1

生成手順と結合手順

サンプル数 s, 下限値 pc , および上限値 1 − pd が与え二分決定図に基づくアプローチは，二分決定図を構築するためられたとき，サンプル数が s ′ の上限値と下限値を用いた Horvitz-に生成と結合手順を実行する．この二つの手順を拡張し，ネット

Thompson 法によるネットワーク信頼性の分散は，サンプル数 s

ワーク信頼性の精度を損なわずに，S2 BDD のサイズを効果的に（1 と同式）の場合と分散が等しく，もしくは小さくなる．

小さくする．

Theorem 24

日本データベース学会和文論文誌
一般論文

Vol. 18-J, Article No. 7, 2020 年 3 月

Gまず，生成手順について説明する．生成手順では，枝 el を処理する．Wu は，削除されたノードと S2 BDD に存在するノードにし，層 l + 1 のノード集合 Nnext を生成する．基本的な手順と同対応する中間グラフから得ることができる．効率的なサンプリン

様に，枝 el の状態を決定し，層 l のノードから層 l + 1 のノード

グのために，Wu から動的計画法を用いてサンプリングを実施す

を二つ生成する．新しいノードを生成するために，ノードが保持

る．加えて，層化ランダムサンプリングの考えを用いて，サブグする変数 (つまり， pn , {cn, f }, {dn, f }, および {tn, f }) を更新する．

ループ毎のサンプル数を決定する．

G

G

S2 BDD のサイズを減少させるためには，ターミナルが接続

まず，Wu をサブグループにわけ，その後それぞれのサブグか非接続かを早い段階で判断することが必要である．しかし，ループから可能グラフをサンプリングする．サブグループ毎のサ

S2 BDD におけるノードはフロンティアの変数しか保持しておら

ンプル数は，サブグループ内の中間グラフの確率の総和に比例しず，中間グラフ全体を保持しているわけではない．そのため，中て決定する．ここでは，削除されたノードと S2 BDD 内のノード

間グラフにおいてターミナルが接続か非接続かをフロンティアのに分けて説明する．削除されたノードにおけるサブグループは変数を用いて判断する．

S2 BDD の同じ層で削除されたものをサブグループとする．これ

次に，結合手順を説明する．S2 BDD における中間グラフはそは削除された節点の確率がサンプル数を決定するには小さすぎる

れぞれ異なる存在枝と非存在枝から構成されるため，フロンティためである．層 l におけるサンプル数 sl は，s と層 l で削除されアの変数も通常異なる．結合手順では，同じシンクに遷移する

たノードの確率の総和 pˆsl の掛け合わせで求めることができる．

ノードを結合し，その確率値を足し合わせる．

S2 BDD に存在するノードにおいては，それぞれのノードに対応

Lemma 1する中間グラフそのものがサブグループに対応し，ノードがもつ層 l のノード n1 と n2 が与えられたとき, もし ∀ f ∈ Fl

確率に従ってサンプル数を決定できる．

において (1) cn1 , f = cn2 , f , および (2) (tn1 , f = 0 and tn2 , f = 0) or

3.3(tn1 , f > 0 and tn2 , f > 0) の場合, el+1, . . . , e |E | の状態が同じである

提案アプローチの時間と空間計算量について説明する．

n1 と n2 の子孫ノードは同じシンクに遷移する．

3.2.2

Theorem 3□

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

計算量曖 昧 グ ラ フ G ，更 新 後 の サ ン プ ル 数 s ′ ，お よ び

S2 BDD の 最 大 幅 w が 与 え ら れ た と き ，提 案 ア プ ロ ー チ の削除手順

時 間 と 空 間 計 算 量 は そ れ ぞ れ O(w 2 log w + s ′ (|V| + |E|)) と二分決定図のサイズはグラフサイズの増加に伴い指数関数的にO(w log w + |V| + |E|) なる．

増加するため，メモリ制約の問題上全てのノードを保持することは難しく，S 2 BDD のサイズが w を超えないようにノードを削

Proof:

除する．削除手順における課題は，高い効率性と精度を保つため

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

に，どのノードを S2 BDD から削除するかである．定理 1 と 2 よ

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

ドの属性を比較する．ノードの属性数はフロンティアの数に比的にサンプル数を減少させることができる．ターミナルの接続性

例し，フロンティア数は O(log w) となる．これは，存在またはにおいて n に対応する中間グラフのターミナルは tn, f が大きい

非存在となる枝数が最大で log w となるためである．そのため，

f が存在するほど接続となりやすく，n に対応する中間グラフのS2 BDD 構築の時間計算量は O(w 2 log w) となる．サンプリング

ターミナルは dn, f が小さく，tn, f > 0 となる f が存在するほど非の時間計算量は O(s ′ (|V| + |E|)) である．従って，時間計算量は接続となりやすい．さらに，ノードの確率値 pn が大きい場合，nO(w 2 log w + s ′(|V| + |E|)) となる．

まず時間計算量について述べる．提案アプローチは，がシンクに遷移したときに pc と pd が大きく増加する．これら

空間計算量について述べる．空間計算量は S2 BDD のサイズとの考えに基づいて，ノードの優先度を決定するヒューリスティッ

曖昧グラフのサイズに依存する．S2 BDD のサイズは，ノード数

ク関数 h を定義する．

と属性数を掛けたものとなる．従って，空間計算量は O(w log w +h(n) = pn · max f ∈F

(

tn, f
1
k , dn, f)

if tn, f > 0.

|V| + |E|) となる．

(12)

4

ターミナルが少なくとも一つがつながってるフロンティアに対し

□

拡張手法

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

フロンティアが少ない曖昧枝をもっている場合に，この関数値はると，計算コストおよびメモリ使用量が小さくなる．そのため，大きくなる．優先度が低いノードは削除され，削除されたノード

S2 BDD 構築の前に曖昧グラフを前処理し，ネットワーク信頼性の確率値はネットワーク信頼性に加算されない．そのため，削除を保ちながらサイズを小さくする．拡張手法は 2 枝接続コンポー

したノードを近似解を求めるためにサンプリング手順で用いる．

ネントを用いる [3]．

3.2.3

サンプリング手順

Definition 3（2 枝接続コンポーネント）

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

グラフ G = (V, E) が与えられたとき, サブグラフ C = (VC , EC ) は，EC からいかなる枝

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

せずに，可能グラフをサンプリングする必要がある．そのため，

ポーネントである．E から枝を取り除いた時，グラフが分割され

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

る場合，その枝は橋と呼ばれる. 橋に接続する節点は，関節点とGをサンプリングする．このような可能グラフのセットを Wu と5

日本データベース学会和文論文誌
一般論文

Vol. 18-J, Article No. 7, 2020 年 3 月

Algorithm 1: Computing the approximate network reliabil-

Algorithm 2: Constructing S2 BDD

ity

input : Uncertain graph G, maximum size w, number of samples s
output Approximate network reliability R̂
:1 procedure Construction(G, w, s)
2 Ordering(E);input : Uncertain graph G, terminals T, maximum BDD size w, size ofsamples s, 2-edge connected components C, bridges B, articulation
points A
output Approximate network reliability R̂
:1 procedure our approach
2 set T to G;
3 R̂, SG ← Preprocess(G, T, C, B, A);

pc , p d , pˆsl , c ← 0; /* initialize probabilities and sampling
count */′
4 s ← s;5 N ← CreateRoot; F ← null;
6 for l for 1, · · · , |E | do
7
pN , psi ← 0;
8F′ ← F; compute F based on el ;9while N is empty do
10n ← N.pop;
3

for Gi ∈ SG dor ← Construction(Gi , w, s);
6R̂ ← R̂ · r;

4

5

7

return R̂;8

end procedure

11
12
13

呼ばれる．2 枝接続コンポーネントの集合，橋の集合，および関14

節点の集合をそれぞれ C, B, および A とする．

15
16

ある枝および節点を削除した際にグラフが分割されるか，され17

ないかを 2 枝接続コンポーネント，橋，および間接点から把握す18

for state ∈ { non-existent, existent } doset(n, F′ , F, st ate, G, el );if n is 0-sink then p d ← p d + pn ;else if n is 1-sink then pc ← pc + pn ;else
if hashmap[n] is not null thenphashmap[n] ← phashmap[n] + pn ;else
if |Nnext | ≤ w thenh n ← h(n);Nnext .add(n); hashmap[n] ← n;
pN ne x t ← pN ne x t + pn ;19

ることができる．2 枝接続コンポーネントはネットワークトポロ

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

21

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

22

複数のグラフに分解，変換はグラフの変換を行う．枝刈りでは，

23

信頼性に影響しない枝を削除するため，G より小さい．分解で1, · · · , ⌊s′ · (1 − pˆsl − pNnext − pc − p d )⌋ do
if Sampling(G, n) then c ← c + 1;

25

m R[G ] となるサブグラフ G , . . . , G を求める．
は， R[G ′ ] = Πi=1i1m

変換では R[Gi ] = R[Gi′ ] となる Gi′ を求める．より小さいグラフ26になるよう変換するため，Gi′ の枝数は Gi より小さい．より具体

27
28

的な処理においては [13] を参照されたい．

29

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

果的に小さくすることができる．さらに，サンプリングの精度も31向上することができる．

R[G] =psi ← psi + pn ;for i for

24

R[G] = R[G ′] となる G ′ を求める．G ′ の枝数は，ネットワーク

Theorem 4

else

32
33

m R[G ] となる G , . . . , G が与えら
pb Πi=1i
1m

34

れたとき，0 < R̂ < 1 and 0 < pb < 1 の場合において，ネット

35

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

if c + ⌊s′ · pNnext ⌋ ≥ s′ thenfor n ∈ N do
for i for 1, · · · , ⌊s′ · pNnext ⌋ do
if Sampling(G, n) then c ← c + 1;
break;
if N n is empty thenbreak;N ← Nnext ;sort N in descending order of h(n);pˆsl ← pˆsl + psi ; compute s′ ; clear Nnext ; clear hashmap;

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

compute R̂ based on the sampling;
return R̂;

下記の式により計算できる．

38

end procedure36

V ar[ R̂] = V ar[pb · Πi R̂[Gi ]]2

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

= (V ar[pb ] + pb 2 )(V ar[ R̂[G1 ]] + R̂[G1 ] ) · · ·mR̂[Gi ]2
(V ar[ R̂[Gm ]] + R̂[Gm ] ) − pb · Πi=1
2
= pb 2 Πi (V ar[ R̂[Gi ]] + R̂[Gi ]2 ) − pb 2 Πi R̂[Gi ]2
2R̂[Gi ])
= pb 2 Πi ( R̂[Gi ](1−+ R̂[Gi ] ) − pb 2 Πi R̂[Gi ]
s
2

2

5

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

ルゴリズム 1 は，提案アプローチの概要の疑似コードである．提= pb 2 Πi R̂[Gi ]( (1+(s−1)s R̂[Gi ]) ) − pb 2 Πi R̂[Gi ]2

案アプローチはまず拡張手法を用いてグラフを分割する (line 3)．

222< pb ΠisR̂[Gi ] − pb ΠisR̂[Gi ]R̂[Gi ])
R̂)
= pb R̂[Gi ](1−< R̂(1−ss□

拡張手法のアルゴリズムにおいては [13] を参照されたい．それぞれの分解されたグラフに対して，S2 BDD を構築し，ネットワー(13)

ク信頼性の近似解を得る (lines 4–5)．全ての近似解を掛け合わせ

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

たものが，全体のグラフのネットワーク信頼性となる (line 6)．

6

日本データベース学会和文論文誌
一般論文

Vol. 18-J, Article No. 7, 2020 年 3 月

拡張手法を用いない提案アプローチ，サンプリングに基づくアプ

表 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,25678
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 は S2 BDD 構築の疑似コードである．予め決めらグラフではメモリ枯渇により計算ができない．提案アプローチはれた枝の順序に従い，枝を選択しフロンティア集合を計算する

Tokyo と NYC データセットにおいての効率性が高い．これは，(lines 6–8)．update 関数 (line 12) はノードの変数を更新し，ター道路ネットワークは平面グラフに近いため，S2 BDD の構築が効

ミナルが接続しているかどうかを計算する．更新されたノード

率的および前処理によるグラフサイズの削減が大きいためであが 0 シンクの場合, pn を pd に足し (line 13)，1 シンクの場合，る．一方で，Hit-direct データセットでは，節点の平均次数が大pn を pc に足す (line 14). その他の場合は, ハッシュ値を計算し，きく上限値と下限値の幅が狭まらないため，効率性が低いが，そn のハッシュが空ではない場合，n の確率値をハッシュ値に対応

れでもサンプリングに基づくアプローチより効率的である．

するノードの確率値に足す (lines 16–17)．ハッシュが空の場合,

6.4

最大幅の影響n の優先度を更新した後，n を Nnext およびハッシュに挿入する

S2 BDD の最大幅を変化させた場合のメモリ使用量と応答時間(lines 19–21). Nn の中のノード数が w を超えたとき，n を削除を評価する．図 4 は，(a) メモリ使用量と (b) 応答時間を示す．図

し n に対応する中間グラフから可能グラフをサンプリングする

4(a) より，最大幅を大きくするとメモリ使用量が大きくなること(lines 22–25).

がわかる．一方で，グラフサイズには影響されていないことがわかる．提案アプローチはメモリ使用量の観点では，大規模なグラ

評価実験

6

フに対応することができることを示している．図 4(b) より，最大幅は応答時間にそれほど影響していないことがわかる．最大幅

提案アプローチを計算効率，精度，およびメモリ使用量の観点から評価を行う．

が大きいとき，サンプル数はより削減可能だが，S2 BDD の構築

データセット

に時間がかかる．提案アプローチの応答時間は最大幅にロバスト

6.1

実験にて使用したデータセットを表 1 にまとめる. 最初の 2 つであることがわかる．これらの結果は，提案アプローチは大規模のデータセット; Zachary-karate-club と American-revolution は，なグラフに対しても効果的に応答時間を削減できることを示して

KONECT *2からダウンロードした小規模なグラフデータである．

いる．

小規模なグラフでは，枝の存在確率は一様分布に基づいてランダ

6.5

精度

ムに与えた．他の 5 つのデータセット; DBLP before 2000, DBLP

次に，提案アプローチとサンプリングに基づくアプローチのafter 2000, Tokyo, New York City, および Hit-direct は，大規模な精度を検証する．サンプリング手法として，モンテカルロ法とグラフデータである．枝の存在確率は，それぞれのデータの枝のHorvitz-Thompson 法（Pro(HT) と Sampling(HT)）の両方を用い

属性値に基づいて計算した．

る．大規模なグラフでは厳密解を計算できないため，厳密解が6.2計算可能な小規模なグラフである Karate と Am-Rv データセッ

設定と実装

トを評価に用いる．分散とエラー率を近似解の精度の指標とし，それぞれのデータセットに対して，ターミナルをランダムに選qび 20 回の検索を行う．ターミナル数 k ，および S2 BDD の最大

それぞれ次の式で計算する．variance =幅を w 変化させる. 比較手法として，サンプリングに基づく手法

error rate =qと BDD に基づく手法を用いる．BDD に基づく手法は最新ライ

1 Σ 2 |R − R̂Σi=1ii, j |
j=1とし， Ri と R̂i, j は i 番目の検索のq1 ·q2 ·Ri

ネットワーク信頼性の厳密解と，i 番の検索における j 番目の近ブラリである TdZDD *3 を用いる．全てのアルゴリズムは C++ で似解をそれぞれ示す．検索回数を 100 回とし，それぞれの検索に実装され，Intel Xenon E7-8860v4，256GB RAM が搭載された計対して 100 回近似解を計算する．

算機にて実験を行う.
6.3

q

q

2
1 Σ 2 (R − R̂Σi=1ii, j )
j=1
および
q1 ·q2表 2 は Karate と Am-Rv データセットにおける精度を示す．

効率性

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

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

アプローチを上回っていることがわかる．また，Am-Rv データ

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

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

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

常に厳密解を計算できていることがわかる．サンプリングに基づアプローチは，モンテカルロ法を用い，s を 10,000 とする．提くアプローチは k が 20 の場合に，分散は小さいがエラー率が大案アプローチにおいては，w を 10,000 とする．提案アプローチ，

きくなっている．これは，ネットワーク信頼性が非常に小さいため，サンプリングに基づくアプローチでは，ターミナルが接続している可能グラフをサンプリングすることができないためであ*2 http://konect.uni-koblenz.de/*3 https://github.com/kunisura/TdZdd

7日本データベース学会和文論文誌
一般論文

Vol. 18-J, Article No. 7, 2020 年 3 月

2500

2000

DBLP1

DBLP2

Tokyo

NYC

DBLP1

DBLP2

(a) k = 5

Tokyo

NYC

Hit-d

0

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

1000

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

謝辞

DBLP1
DBLP2
Tokyo
NYC
Hit-d

本 研 究 は JST ACT-I（JPMJPR18UD）お よ び 科 学 研 究 費（JP15K21069）の支援によって行われた．謝意を表す．

500
0
1K

1M

(a) メモリ使用量

10K
100K
Maximum width

参考文献

1M

[1] Saurabh Asthana, Oliver D King, Francis D Gibbons, and Frederick P
Roth. Predicting protein complex membership using probabilistic
network reliability. Genome research, 14(6):1170–1175, 2004.
[2] Michael O Ball, Charles J Colbourn, and J Scott Provan. Network reliability. Handbooks in operations research and management science,
7:673–762, 1995.
[3] Lijun Chang, Jeﬀrey Xu Yu, Lu Qin, Xuemin Lin, Chengfei Liu, andWeifa Liang. Eﬃciently computing k-edge connected components via
graph decomposition. In SIGMOD, pages 205–216, 2013.
[4] George S Fishman. A comparison of four monte carlo methods for
estimating the probability of st connectedness. IEEE Transactions on
reliability, 35(2):145–155, 1986.
[5] 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 Research Centre of the Dutch Ministry ofTransport, 2005.
[6] Gary Hardy, Corinne Lucet, and Nikolaos Limnios. K-terminal network reliability measures with binary decision diagrams. IEEE Transactions on Reliability, 56(3):506–515, 2007.
[7] Ruoming Jin, Lin Liu, Bolin Ding, and Haixun Wang. Distanceconstraint reachability computation in uncertain graphs. PVLDB,
4(9):551–562, 2011.
[8] Jun Kawahara, Takeru Inoue, Hiroaki Iwashita, and Shinichi Minato.
Frontier-based search for enumerating all constrained subgraphs withcompressed representation. IEICE Transactions on Fundamentals ofElectronics, Communications and Computer Sciences, 100(9):1773–
1784, 2017.
[9] Xiangyu Ke, Arijit Khan, and Leroy Lim Hong Quan. An in-depth
comparison of st reliability algorithms over uncertain graphs. PVLDB,
12(8):864–876, 2019.
[10] Rong-Hua Li, Jeﬀrey Xu Yu, Rui Mao, and Tan Jin. Recursive stratified
sampling: A new framework for query evaluation on uncertain graphs.
IEEE Transactions on Knowledge and Data Engineering, 28(2):468–
482, 2015.
[11] Eugène Manzi, Martine Labbé, Guy Latouche, and Francesco Maﬃoli. Fishman’s sampling plan for computing network reliability. IEEE
Transactions on Reliability, 50(1):41–46, 2001.
[12] Rajeev Motwani and Prabhakar Raghavan. Randomized algorithms.
Chapman & Hall/CRC, 2010.
[13] Yuya Sasaki, Yasuhiro Fujiwara, and Makoto Onizuka. Eﬃcient network reliability computationin uncertain graphs. In EDBT, 2019.
[14] S Thompson. Sampling. Wiley, 2002.
[15] Leslie G Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3):410–421, 1979.

(b) 応答時間

図 4: 最大幅の影響

表 2: 精度k

MethodPro(MC)

5

Pro(HT)
Sampling(MC)Sampling(HT)Pro(MC)10

Pro(HT)
Sampling(MC)Sampling(HT)Pro(MC)20

Pro(HT)
Sampling(MC)Sampling(HT)Karate
分散

0.025
0.025
0.025
0.029
0.013
0.014
0.013
0.015
0.76 ·10−3
0.85·10−3
0.78·10−3
0.86·10−3

エラー率

0.036
0.036
0.037
0.042
0.058
0.059
0.058
0.062
0.054
0.057
0.056
0.057

Am-Rv
分散

0
0
0.43·10−4
0.31·10−4000.099·10−5
0.12·10−5000.10·10−3
0.10·10−3

エラー率

0
0
0.061
0.059
0
0
0.38
0.37
0
0
1.00
1.00

る．これにより，近似解は頻繁にゼロとなり，エラー率は 1 とな
りやすい．これらの結果より，提案アプローチは少ないサンプル数で高い精度を達成し，小規模グラフにおいては厳密解を計算できることがわかる．

7

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

8