BDDによるネットワーク信頼性の近似計算

全文

(1)情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2017-DBS-166 No.16 2017/12/23. BDD によるネットワーク信頼性の近似計算佐々木勇和1,a). 藤原靖宏2,1,b). 鬼塚真1,c). 概要：ネットワーク信頼性は任意の節点郡の接続性を評価するための重要な指標である．通信ネットワークの設計やバイラルマーケティングなど様々な応用があるが，#P 完全問題であるため計算コストが非常に大きい．ネットワーク信頼性を求める手法としての主流は，Binary decision diagram (BDD) を用いた厳密解を求めるアルゴリズムとサンプリングによる近似解を求めるアルゴリズムである．本研究では，グラフ規模に応じて適応的に近似解もしくは厳密解を計算する BDD を用いたアルゴリズムを提案する．. BDD の最も大きな欠点はメモリ消費量が大きいことである．そこで，メモリ使用量を削減する Relaxed and Restricted BDD (R2 BDD) を提案する．R2 BDD はメモリ使用量を抑えつつ，下限値と上限値を算出可能である．また，上限値，下限値，および近似解を一度の R2 BDD の構築で算出するアルゴリズムを提案する．実データを用いた実験を行い，提案手法の性能を確認する．キーワード：Binary decision diagram, ネットワーク信頼性，曖昧グラフ. Yuya Sasaki1,a). Yasuhiro Fujiwara2,1,b). 1. はじめにグラフはデータの関係性を表すための基礎的なデータ構. Makoto Onizuka1,c). 標としてよく使われており盛んに研究されている [7]．ネットワーク信頼性問題は，与えられた節点集合（ターミナルと呼ばれる）が相互接続する確率を求める問題である．ネッ. 造であり，多くのアプリケーションで利用されている．例. トワーク信頼性問題は，与えられるターミナル数により，. えば，ソーシャルグラフやタンパク質ネットワーク，道路. 全ターミナル問題，2 ターミナル問題，k ターミナル問題. ネットワーク等のモデル化に用いられている．グラフは曖. と分けることができる．そのなかで k ターミナル問題が最. 昧性を含んでることが多々ある [1]．例えば，タンパク質. も一般的で，任意の数のターミナルが与えられた問題であ. ネットワークにおいてはタンパク質の反応は確率的であり，. る．ネットワーク信頼性問題は重要であるが，#P 問題と. 道路ネットワークにおいては突然の渋滞や事故により道路. して知られている．そのため，計算コストの大きさが問題. が使用不可能になることがある．このようなグラフは，枝. である．最も単純なネットワーク信頼性を求める方法は，. に存在確率がある曖昧グラフとしてモデル化することがで. グラフの枝の全ての有無のパターンを列挙し，それぞれの. きる．. パターンのグラフに対してターミナルが接続するかを求め. 曖昧グラフにおいて，ネットワーク信頼性は接続性の指. る．その後，接続となったグラフの存在確率の総和を求めることで求めることができる．節点数を |V |，枝数を |E|. 1 2 a) b) c). 大阪大学大学院情報科学研究科 NTT ソフトウェアイノベーションセンタ [email protected] [email protected] [email protected]. ⓒ 2017 Information Processing Society of Japan. とおいたとき，パターン数は 2|E| となり，接続確認の計算量が O(|V | + |E|) であるため，ネットワーク信頼性問題の計算量は，O(2|E| (|V | + |E|)) となる．ネットワーク信頼. 1.

(2) 情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2017-DBS-166 No.16 2017/12/23. 性の厳密解を求めるアルゴリズムとして，binary decision. diagram (BDD) を用いた方法が最も効率的と知られている [8], [15]．BDD を用いたアルゴリズムは効率的であるが，メモリ使用量が O(2|E| ) となる問題点がある．そのため，非常に小さいグラフが限界である．また，実際のメモリ使用量を事前に算出できないという問題点もある．グラフの増大化に伴って，サンプリングにより近似解を求めるアプローチが近年では多く提案されている [6], [11], [12]．サンプリングを用いたアルゴリズムは，グラフの規模に関わらず近似解を求めることが可能であるが，2 つの大きな欠点がある．まず，小さいグラフに対しても厳密解を求めることができないことである．2 つ目は，中心極限定理やモンテカルロシミュレーションのような統計手法を用いるため，下限値および上限値を求めることができない [16]．これら 2 つの手法の欠点を避けつつ，利点をもつようなアルゴリズムは筆者らの知る限り存在していない．そこで，本研究では，新たな BDD である R2 BDD を提案し，下限値，上限値，および近似解を一度の BDD 構築で求めるアルゴリズムを提案する．R2 BDD は，許容解を上限近似と下限近似の両方を同時に行うことで可能である [3]．一般的な BDD はメモリ使用量が大きいため，R2 BDD は. Augumented ordered binary decision diagram (OBDD-A) をベースとして用いる [9]．OBDD-A は，それぞれの BDD 節点が確率値を追加情報を持つことが可能であり，BDD の子節点を計算した後，親節点は削除してもよい．そのため，メモリ使用量が BDD の高さに依存しなくなる．しかし，一層の BDD 節点の数が多くなると，BDD のメモリ使用量は非常に大きくなるため，一層毎の BDD 節点の数を抑制する最大幅を設けることで，メモリ使用量を小さくする．BDD 節点数が最大幅を超えた場合，その節点を削除し確率値のみを記憶する．また，削除した点に関してランダムサンプリングすることにより近似値も推定する．これにより，メモリ使用量を抑えつつ，上限値，下限値，近似値を求めることができる．メモリ使用量が大きくならない場合では，厳密解が計算可能である．. BDD の構築では，事前にグラフを小規模化することにより計算量を削減することができる．そこで，計算値の結果を変えずに小規模化するために，トポロジ情報を用いて行う．まず，ネットワーク信頼性計算に関係がない部分を枝刈りする．次に，グラフの等価性を保ちつつ枝および節点の削減を行う．最後に，グラフを分解することにより，複数のグラフに対してネットワーク信頼性を個別に計算可能にする．本稿の構成は以下の通りである．2 章で関連研究，3 章で事前準備ついて述べる．4 章で提案手法の詳細を説明する．5 章で提案手法の評価を行い，6 章で本稿のまとめと. 2. 関連研究曖昧グラフにおけるマイニングや問合せに関する研究はデータマイニングやデータベース分野で広く行われている．ネットワーク信頼性問題:. ネットワーク信頼性の計算. 方法は様々な提案手法が提案されており，BDD を用いる手法の他に最小カットや Factoring 定理に基づく手法等がある [2], [8], [9], [15], [18]．近年の研究成果により，BDD を用いた手法が最も効率的ということが一般的である．しかし，BDD はメモリ使用量が膨大であり，100 から 200 程度の枝数の処理が限界と知られている [8], [15]．そのため，大規模なグラフに適応することができない．曖昧グラフにおける到達可能性問合せ: 到達可能性問合せは，s-t ネットワーク信頼性問題（節点 s から節点 t への接続確率）という特殊なネットワーク信頼性問題である．. Jin らは，距離制約を加えた到達可能性問合せを対象として，サンプリングによる近似解手法を提案している [11]．. Cheng らは，DAG を対象として到達可能性問合せを分散環境で計算する手法を提案している [5]．曖昧グラフにおける他の問題: データマイニング分野に置いて曖昧グラフを対象としたマイニングが盛んに行われている．ネットワーク信頼性問題に関係する問題をいくつか述べる．まず，節点間の接続性を基にしたクラスタリングやサブグラフマッチがある [10], [19], [20]．Jin ら [10] は接続確率が閾値より高い節点集合の検出を行っており，モンテカルロシミュレーションを基にしたアルゴリズムを提案している．Zou ら [19] は，曖昧グラフのセットから頻出サブグラフの検出をモンテカルロシミュレーションにより行っている．さらに，Zou ら [20] は極大クリークの検出も行っている．Liu ら [14] は k-means を基にしたアルゴリズム Kollios ら [13] は編集距離を最大化するクラスタリングアルゴリズムを提案している．Bonch ら [4] は曖昧グラフにおけるコア分解アルゴリズムを提案している.. 3. 事前知識 3.1 曖昧グラフ曖昧グラフは G = (V, E, P) と表し，V， E ⊆ V × V，. P : E = (0, 1] は，それぞれ節点集合，枝集合，および枝の存在確率値 p(e) を計算する関数を表す．それぞれの枝の存在確率は他の枝と独立と想定する．曖昧グラフの枝のサブセットをもつグラフを可能グラフとよぶ．可能グラフは Gp = (V, EG ) と表す．可能グラフは，曖昧グラフとは異なり，枝は確率値を持たないかわりに，グラフそのものに存在確率をもつ．可能グラフの存在確率 P r[Gp ] を以下の式で表される．. 今後の課題について論ずる．. P r[Gp ] = Σe∈EG p(e) · Σe∈E\EG (1 − p(e)). ⓒ 2017 Information Processing Society of Japan. (1). 2.

(3) 情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2017-DBS-166 No.16 2017/12/23. 可能グラフの数は，それぞれの枝に対して有無を判定する. トワーク信頼性の計算のために，フロンティアはコンポー. ため，2|E| となる．. ネント識別子，次数，およびターミナル数を保持する．既. さらに，中間グラフ Gi = (V, Ef , Ed ) を定義する．中間. に接続された節点は同じコンポーネント識別子を持ち，次. グラフ Gi は，削除された枝と固定された枝のセットを持. 数は接続されたそのコンポーネントの枝のうち未探索の. ち，それ以外の枝は曖昧な枝として存在する．中間グラフ. 数，およびターミナル数はコンポーネント内のターミナル. の確率値 P r[Gi ] は以下の式で表される．. 数を表す．. R2 BDD の具体的な構築手順は，あらかじめ順序付けさ. P r[Gi ] = Σe∈Ef p(e) · Σe∈E (1 − p(e)).. (2). れた枝を固定もしくは削除をしながらフロンティアを広げながら行う．固定および削除は，BDD の枝における 1-枝. 3.2 ネットワーク信頼性. と 0-枝を示す．また，それぞれの節点は，中間グラフを表. ネットワーク信頼性はターミナルが相互接続している可能グラフの確率の総和で求めることができる．. しており，その確率値を追加情報として保持する．フロンティアのターミナル数が k となった場合，その内部節点の. 定義：(k-terminal reliability). 任意の k 個の節点と曖昧グラフ G が与えられたとき, k ターミナル信頼性問題は接続確率 R[G] を求める．. 中間グラフは既に接続済みであるため，1-節点に遷移する．一方，ターミナル数が 1 以上の節点の次数が 0 となった場合，その内部節点の中間グラフはターミナルが接続するこ. R[G] = ΣG∈G I(G, Vk ) · P r[G],. (3). とはないため，0-節点に遷移する．また，ある内部節点が. 0-枝と 1-枝の遷移先となる内部節点を追加した後は，その. G は可能グラフ，I(G, Vk ) は G が相互接続している場合，. 遷移元となった内部節点を削除する．これにより，R2 BDD. 1 を返す関数である（接続していない場合は 0 を返す）．. では，メモリ使用量が高さに依存しなくなり，レベル毎の. ネットワーク信頼性問題は，#P 完全問題である [17].. 内部節点数がメモリに依存する．ここで，レベル毎 l の最大内部節点数は以下の第 2 種スターリング数とベル数により表すことができる．. 3.3 Binary decision diagram Binary decision diagram (BDD) はデータ構造である． BDD は DAG で表すことができ，内部節点，0-枝，1-枝，0-節点，および 1 節点から成る．それぞれの内部節点は，0-枝と. 1-枝を持つ．ルートから 0-節点および 1-節点までの経路は，. Ai,j j = ·Ai−1,j + Ai−1,j−1. (4). ここで，Ai,1 = 1，0 < j ≤ i の場合，Ai−1,j−1 = 1 となる．. ブール値が真および偽となる変数状態を表す．BDD の特別. |F |. k B|Fl | = Σj=1 A|Fk |,j. な形として，augmented ordered binary decision diagram. (5). (OBDD-A) がある．OBDD-A はルートからの全ての経路. 内部節点数を抑制することがメモリ使用量の減少に重要. が同じ変数順で表され，さらにそれぞれの節点が追加の情. である．そこで，R2 BDD では，内部節点数の最大数を決. 報をもつ．ネットワーク信頼性においては，それぞれの節. 定する閾値を与える．これにより，メモリ使用量を計算す. 点は，中間グラフを保持するとみなすことができ，その確. ることができる．一方で，このときどの内部節点を削除す. 率値を追加の情報として保持する．. るかが重要である．ネットワーク信頼性の計算では，内部節点が保持する確率が大きいものが計算に与える影響が大. 4. 提案アルゴリズム. きい．そこで，内部節点を確率値の降順に並べ替え，確率 2. 提案するアルゴリズムでは，新たな BDD である R BDD. 値が大きい内部節点を優先的に残す．また，削除した内部. を構築しながら，ネットワーク信頼性を計算する．まず，. 節点の確率を保持することにより，上限値・下限値の算出. R2 BDD について述べ，上限値，下限値，近似値の計算方. に用いる．. 法ついて説明する．その後，効率的にネットワーク信頼性を計算するための最適化について述べる．. 4.2 上限値，下限値，近似値の算出. 4.1 R2 BDD. および削除した節点の確率を用いて計算することができ. 上限値と下限値は，0-節点および 1-節点が保持する確率. R2 BDD の構築は，グラフ問題においてサブグラフ列挙. る．一方，近似値は通常の BDD では計算することができ. のフレームワークであるフロンティア法を用いる．フロン. ない．そこで，削除した内部節点の中間グラフから可能グ. ティア法は，グラフ探索において境界となる節点（フロン. ラフをサンプリングすることにより近似値を計算する．. ティア）の情報を保持し，フロンティアの情報が同じサブグラフをマージする方法である．これにより，探索空間が 2. 大幅に削減される．提案手法における R BDD では，ネッ ⓒ 2017 Information Processing Society of Japan. 4.3 最適化ネットワーク信頼性の計算では，グラフのサイズを事前. 3.

(4) 情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2017-DBS-166 No.16 2017/12/23. に小さくすることにより，全体の計算量を小さくすること. 表 1: データセット. ができる．また，BDD の構築では枝の順序付けが内部節. 記号. 節点数. 枝数. 点の数に大きな影響があることが知られている．. CA-GrQc. 4,158. 13,428. トポロジベースのグラフ最適化：グラフのサイズが小さく. DBLP. 26,178. 108,662. なれば，計算する変数が減るだけでなく，フロンティア数を減らすことができる．また，トポロジベースでグラフを. さくなることが知られている幅優先探索を使用する．より. 最適化することにより，ネットワーク信頼性の精度を下げ. よい枝の順序付けについては今後の課題である．. ることなくサイズを小さくすることが可能である．グラフの最適化として，3 つの方法: 枝刈り，等価変換，分解を実. 5. 実験. 施する．. 全てのアルゴリズムは C++で実装され，CPU が Intel. まず，枝刈りでは，枝接続によりグラフを再構築し，シュ. Xenon E7-8860v4 @2.20GHz で，メモリが 256GB の計算. タイナー木を計算し，シュタイナー木に含まれる枝と節点. 機を用いた．アルゴリズムの評価としては，応答時間と上. がネットワーク信頼性の計算に必要なグラフとなる．グラ. 限値・下限値の幅を評価する．提案手法としては，グラフ. フの再構築の方法は，まず 1-辺連結グラフを構築し，連. の最適化の有り，無しの場合を用いる．. 結点と橋を求める．連結点と連結グラフそのものを一つの. 5.0.1 データセット. 節点（連結グラフ点と呼ぶ）とし，連結点と連結グラフ点. データセットの概要を表 1 に示す．データセットとして. を接続する．その後，それぞれの連結点を対応する橋で接. 2 つの共著関係を表すグラフを用いた．節点と枝は，それ. 続することにより，一つの木が生成できる．ターミナルと. ぞれ著者と共著関係を表す．CA-GrQc データセットは，. なっている連結点と連結点以外のターミナルを含む連結グ. Arkive の共著関係のグラフである. ラフ点が接続するよにシュタイナー木を構築する．構築さ. 正規分布に基づきランダムに決定する．DBLP データセッ. れたシュタイナー木に含まれる節点と枝（および連結グラ. トは，DBLP から取得したデータを用い，枝の確率は共著. フ）が必要なサブグラフとなる．ここで，一般グラフにお. 数に基づいて決定する．具体的には，α と αM をそれぞれ. けるシュタイナー木を求めるのは NP 困難であるが，木構. 共著数と最大共著数として，枝の存在確率を. 造におけるシュタイナー木は 0(|V | + |E|) となる．. する．. *1 ．枝の存在確率は，. log(α+1) log(αM +2). と. 次に，グラフをより小さいものへ等価変換を実施する．まず，次数 2 が 2 である節点と隣接する二つの枝を削除. 5.1 結果. し，削除した二つの枝の存在確率を掛けた存在確率をもつ. 図 1 に CA-GrQc データセットにおける最大の幅を変え. 枝を追加する．次に，並列（つまり，同じ端点をもつ枝）. た場合の応答時間および探索済み領域の結果を示す．探索. となっている枝を削除し，(1 − (1 − p(e1 ) · (1 − p(e2 )) の. 済み領域は，提案手法において接続もしくは非接続を厳密. 存在確率をもつ枝を追加する．また，上記二つの処理によ. に判定した割合を表す．そのため，探索済み領域が大きい. り，ループとなる枝が生成される可能性があるため，ルー. ほど，上限値下限値の幅は狭くなる．提案手法の評価とし. プとなっている枝は削除する．これらの処理をグラフに変. て，ターミナル数を 2 および 5 と設定し，グラフの最適. 化がなくなるまで繰り返す．等価変換では，ネットワーク. 化の有無を評価する．まず，図 1(a) よりターミナル数が. 信頼性の正確性を損なうことなくグラフサイズを小さくす. 2 の場合，探索時間はほぼ変わらないことがわかる．これ. ることができる．. は，グラフの最適化に時間を要しているため，ネットワー. 最後に，グラフを分解することにより，ネットワーク信. ク信頼性の計算時間を削減しても同程度となっている．一. 頼性をそれぞれのグラフで計算することを可能にする．グ. 方で，ターミナル数が 5 の場合，最適化有りではターミナ. ラフの分解では，橋で接続されているコンポーネントに分. ル数が 2 と同程度に対して，最適化無しの場合では非常に. 解する．橋に接続する節点は，ターミナルがすべて接続す. 大きな時間が掛かっている．これは，グラフを小規模化す. るためには，必ず接続されていなければならない．そのた. ることにより，複数のターミナルの接続性を判定しやすい. め，グラフ分解後にネットワーク信頼性を計算する場合，. ことに起因する．最大幅を 10,000 以上とした場合，1 日で. それぞれのコンポーネントの橋との連結点をターミナルと. は終了しなかったため処理を終了している．図 1(b) より，. して追加する．グラフを分解することにより，ネットワー. 最適化の有無により，探索済み領域に大きな差があること. ク信頼性の計算量およびメモリ使用量を削減することがで. がわかる．ターミナル数が 2 の場合，応答時間は同程度で. きる．. あるが，探索済み領域は 7 倍程度の差が開いている．これ. 枝の順序付け：BDD における重要な課題は，フロンティ. は，不要な枝および節点を削除することにより，そもそも. ア数を削減することである．フロンティア数は枝の順序に. の探索領域を削減しているためである．. 大きく依存する．本研究では，フロンティア数が比較的小. *1. ⓒ 2017 Information Processing Society of Japan. http://snap.stanford.edu/data/. 4.

(5) 情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2017-DBS-166 No.16 2017/12/23. 104. 0.6 2Rel /w Opt 2Rel w/o Opt 5Rel /w Opt 5Rel w/o Opt. 3. Exact search area. Response time [sec]. 10. 2Rel /w Opt 2Rel w/o Opt 5Rel /w Opt 5Rel w/o Opt. 102 101 100. 0.4. 0.2. 10-1 10-2. 1K. 10K. 0 1K. 100K. 10K. Maximum width. 100K. Maximum width. (a) 応答時間. (b) 探索済み領域. 図 1: CA-GrQc データセットにおける提案手法の比較. Response time [sec]. 103. 0.6 2Rel /w Opt 2Rel w/o Opt 5Rel /w Opt 5Rel w/o Opt Exact search area. 104. 102 1. 10. 100. 0.4. 0.2 2Rel /w Opt 2Rel w/o Opt 5Rel /w Opt 5Rel w/o Opt. -1. 10. -2. 10. 1K. 10K. 0 1K. 100K. 10K. Maximum width. 100K. Maximum width. (a) 応答時間. (b) 探索済み領域. 図 2: DBLP データセットにおける提案手法の比較次に図 2 に DBLP データセットにおける最大の幅を変. とにより，改善することが期待できる．計算の効率化では，. えた場合の応答時間および探索済み領域の結果を示す．. 並列計算をすることが求められる．メモリ使用量を大きく. CA-GrQc データセットと異なり，ターミナル数が 2 の場. しない並列計算方法を考案する．. 合は，最適化無しの方が応答時間も短く，探索済み検索領域も大きい．これは，枝の順序付けにより最適化しない方がよいというケースになったためと考えられる．. 7. 謝辞本研究は科学研究費（15K21069）の支援によって行われた．ここに記して謝意を表す．. 6. おわりに本研究は，ネットワーク信頼性の上限値，下限値，近似値を同時に出力可能なアルゴリズムを提案した．また，そ. 参考文献 [1]. 2. のためのデータ構造として，R BDD を提案した．今後の課題は，精度の向上と効率的な計算である．まず，. [2]. 精度の向上では，サンプリングによる定理を用いた精度の証明が第一の課題である．次に，より最適な BDD の節点の削除方法，および枝の順序を考案する予定である．さらに，上限値と下限値をそれぞれの別の BDD の構築するこ. ⓒ 2017 Information Processing Society of Japan. [3] [4]. Aggarwal, C. C.: Managing and Mining Uncertain Data, Vol. 35, Kluwer (2009). Agrawal, A. and Satyanarayana, A.: An O (— E—) time algorithm for computing the reliability of a class of directed networks, Operations research, Vol. 32, No. 3, pp. 493–515 (1984). Bergman, D., Cire, A. A., van Hoeve, W.-J. and Hooker, J.: Decision diagrams for optimization, Springer (2016). Bonchi, F., Gullo, F., Kaltenbrunner, A. and Volkovich,. 5.

(6) 情報処理学会研究報告 IPSJ SIG Technical Report. [5]. [6]. [7] [8]. [9]. [10]. [11]. [12]. [13]. [14]. [15]. [16]. [17]. [18]. [19]. [20]. Vol.2017-DBS-166 No.16 2017/12/23. Y.: Core decomposition of uncertain graphs, SIGKDD, pp. 1316–1325 (2014). Cheng, Y., Yuan, Y., Chen, L. and Wang, G.: The reachability query over distributed uncertain graphs, ICDCS, pp. 786–787 (2015). Cheng, Y., Yuan, Y., Chen, L., Wang, G., GiraudCarrier, C. and Sun, Y.: Distr: a distributed method for the reachability query over large uncertain graphs, IEEE Transactions on Parallel and Distributed Systems, Vol. 27, No. 11, pp. 3172–3185 (2016). Colbourn, C. J.: The combinatorics of network reliability, Vol. 200, Oxford University Press New York (1987). Hardy, G., Lucet, C. and Limnios, N.: K-terminal network reliability measures with binary decision diagrams, IEEE Transactions on Reliability, Vol. 56, No. 3, pp. 506–515 (2007). Herrmann, J. U. and Soh, S.: A memory eﬃcient algorithm for network reliability, Communications, 2009. APCC 2009. 15th Asia-Pacific Conference on, IEEE, pp. 703–707 (2009). Jin, R., Liu, L. and Aggarwal, C. C.: Discovering highly reliable subgraphs in uncertain graphs, SIGKDD, pp. 992–1000 (2011). Jin, R., Liu, L., Ding, B. and Wang, H.: Distanceconstraint reachability computation in uncertain graphs, PVLDB, Vol. 4, No. 9, pp. 551–562 (2011). Khan, A., Bonchi, F., Gionis, A. and Gullo, F.: Fast Reliability Search in Uncertain Graphs., EDBT, pp. 535– 546 (2014). Kollios, G., Potamias, M. and Terzi, E.: Clustering large probabilistic graphs, TKDE, Vol. 25, No. 2, pp. 325–336 (2013). Liu, L., Jin, R., Aggarwal, C. and Shen, Y.: Reliable clustering on uncertain graphs, ICDM, pp. 459–468 (2012). Maehara, T., Suzuki, H. and Ishihata, M.: Exact Computation of Influence Spread by Binary Decision Diagrams, Proceedings of the 26th International Conference on World Wide Web, International World Wide Web Conferences Steering Committee, pp. 947–956 (2017). Rosenblatt, M.: A central limit theorem and a strong mixing condition, Proceedings of the National Academy of Sciences, Vol. 42, No. 1, pp. 43–47 (1956). Valiant, L. G.: The complexity of enumeration and reliability problems, SIAM Journal on Computing, Vol. 8, No. 3, pp. 410–421 (1979). Yeh, F.-M., Lu, S.-K. and Kuo, S.-Y.: OBDD-based evaluation of k-terminal network reliability, IEEE Transactions on Reliability, Vol. 51, No. 4, pp. 443–451 (2002). Zou, Z., Gao, H. and Li, J.: Discovering frequent subgraphs over uncertain graph databases under probabilistic semantics, SIGKDD, pp. 633–642 (2010). Zou, Z., Li, J., Gao, H. and Zhang, S.: Finding top-k maximal cliques in an uncertain graph, ICDE, pp. 649– 652 (2010).. ⓒ 2017 Information Processing Society of Japan. 6.

(7)