(57)【特許請求の範囲】
【請求項１】
複数のノードが複数のリンクで接続されたネットワークにおけるノード間の連結確率を、二分決定図を用いて算出するネットワーク評価装置であって、
ノードとリンクの接点を示す頂点を前記接点ごとに生成し、
共通のノードに接続される全てのリンクの前記頂点を包含するノード領域をノードごとに生成し、
共通のリンクに接続される全てのノードの前記頂点を包含するリンク領域をリンクごとに生成し、
前記ノード領域のうちの連結対象のノードのノード領域内に、連結対象のノードであることを示す頂点を生成する、ハイパーグラフ生成部と、
前記連結対象のノードのうちの一方を示す前記頂点の状態を根節点とし、
前記連結対象のノードのうちの他方を示す前記頂点に連結されるか否かを終端節点とし、
前記連結対象のノードのうちの一方から他方までの間に経由する前記ノード領域及び前記リンク領域の各状態を節点とする二分決定図を構築する、二分決定図構築部と、
前記二分決定図における各節点の確率を算出し、算出した確率を用いて、前記ネットワークにおける前記連結対象のノード間の連結確率を算出する、確率算出部と、
を備えるネットワーク評価装置。
【請求項２】
複数のノードが複数のリンクで接続されたネットワークにおけるノード間の連結確率を、二分決定図を用いて算出するネットワーク評価装置が実行する方法であって、
ノードとリンクの接点を示す頂点を前記接点ごとに生成し、
共通のノードに接続される全てのリンクの前記頂点を包含するノード領域をノードごとに生成し、
共通のリンクに接続される全てのノードの前記頂点を包含するリンク領域をリンクごとに生成し、
前記ノード領域のうちの連結対象のノードのノード領域内に、連結対象のノードであることを示す頂点を生成する、ハイパーグラフ生成手順と、
前記連結対象のノードのうちの一方を示す前記頂点の状態を根節点とし、
前記連結対象のノードのうちの他方を示す前記頂点に連結されるか否かを終端節点とし、
前記連結対象のノードのうちの一方から他方までの間に経由する前記ノード領域及び前記リンク領域の各状態を節点とする二分決定図を構築する、二分決定図構築手順と、
前記二分決定図における各節点の確率を算出し、算出した確率を用いて、前記ネットワークにおける前記連結対象のノード間の連結確率を算出する確率算出手順と、
を順に有するネットワーク評価方法。
【請求項３】
請求項２に記載のハイパーグラフ生成手順、二分決定図構築手順及び確率算出手順をコンピュータに実行させることによって、前記ネットワーク評価装置を実現するネットワーク評価プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク評価装置、ネットワーク評価方法及びネットワーク評価プログラムに関する。
【背景技術】
【０００２】
通信ネットワークにおいて、ノード同士が通信できるためには、ノード間にパスが存在しており、連結されていなければならない。ノードやリンクの故障率が与えられると、パスが存在する確率を計算することができる。ネットワークの信頼性評価において、ノードの連結確率は重要な基礎データとなる。
【０００３】
たとえば、図１に示す辺連結度が１のネットワーク構成の場合、リンク故障率が１０％のとき、黒ノードの連結確率は０．９２＝８１％である（ここではノードは故障しないとする）。一方で、図２に示す辺連結度が２のネットワーク構成の場合、リンク故障率が２５％であれば、黒ノードの連結確率は１−（１−０．７５２）２＝８０．８５９３７５％である。
【０００４】
ネットワークの規模が大きくなるとノード間には膨大な数のパスが存在し、さらにそれらには依存関係があるため、連結確率の計算は容易ではない。非特許文献１は、リンク故障のみを対象とし、二分決定図（ＢＤＤ：ｂｉｎａｒｙ  ｄｅｃｉｓｉｏｎ  ｄｉａｇｒａｍ）を用いた効率的な計算手法を提案している。また、非特許文献２はノード故障を扱う方法を紹介している。
【０００５】
（非特許文献１の技術）
非特許文献１の概要を説明する。図３のネットワーク構成において、ノードｓとノードｔの連結確率を計算する。まず、ノードｓとノードｔが連結になるようなネットワーク状態をＢＤＤとして列挙する。
【０００６】
図３のネットワーク構成には５つのリンクがあるため、５つのバイナリ変数からなるベクトル（ｅ１，ｅ２，ｅ３，ｅ４，ｅ５）によってネットワーク状態を表現できる。図３に示すすべてのリンクが故障していればネットワーク状態は（０，０，０，０，０）であり、すべて稼働していればネットワーク状態は（１，１，１，１，１）である。以降、ネットワーク状態をベクトルで表す。ただし、連結状態に影響しないリンクの状態は＊で表す。たとえば、図３に示すリンクｅ１とリンクｅ２が故障していれば、他のリンクの状態にかかわらずノードｓとノードｔは非連結になる。この条件は（０，０，＊，＊，＊）と表される。
【０００７】
図４は、連結状態を表すＢＤＤの一例である。ＢＤＤはグラフであり、最上位の頂点（根節点）から最下位の頂点（終端節点）へのパスが個々のネットワーク状態を表す。終端節点が┬に到達するパスは連結状態を表し、┴に到達するパスは非連結状態を表す。根節点Ｖ−ｅ１はリンクｅ１の状態を表し、ｅ１＝０の０枝を示す点線をたどると故障、ｅ１＝１の１枝を示す実線をたどると稼働となる。たとえば、もっとも左のパスはｅ１＝０でありかつｅ２＝０であり、┴終端節点に到達している。つまり、図３において、リンクｅ１とリンクｅ２が故障すると、ノードｓとノードｔは非連結になることを表しており、（０，０，＊，＊，＊）ということである。もっとも右のパスは（１，１，＊，１，＊）であり、┬終端節点に到達していることから連結状態を表しているとわかる。
【０００８】
次に、構築した図４に示す連結状態を表すＢＤＤを用いて、連結確率を算出する。すべてのリンクの故障率を１０％とする。ＢＤＤの下から上に向かって確率を足し合わせていく。まず、┴終端節点の連結確率を０とし、┬終端節点の連結確率を１とする。ＢＤＤ節点では、０枝は０．１を掛け、１枝は０．９を掛け、両者の和をその節点の確率とする。この場合の各節点の確率を、図４の括弧内に示す。
【０００９】
まず、ｅ５節点を考えてみる。０枝は┴終端節点につながっており、┴終端節点の連結確率は０であるため、０×０．１＝０である。１枝は┬終端節点につながっており、┬終端節点の連結確率は１であるため、１×０．９＝０．９である。両方の和をとって、０．９がこの節点の確率となる。
【００１０】
次に、２つのｅ４のうちの右側のｅ４節点を考える。０枝は先ほどのｅ５節点につながっており、その節点の確率は０．９であったから、０．９×０．１＝０．０９となる。１枝は┬終端節点につながっているから０．９である。両者の和は０．９９である。このようにして、根節点となるリンクｅ１まで算出すると、ネットワーク全体の連結確率が得られる。
【００１１】
（非特許文献２の技術）
まずは非特許文献１と同様に、リンク故障のみを考慮して図４の連結状態を表すＢＤＤを構築する。次に、リンクｅｉが稼働しているときは、その両端ノードも稼働しているという条件を追加する。たとえば、リンクｅ１が稼働しているときは、その両端ノードであるノードｓとノードｖ１も稼働していなければいけないので、ｓ∧ｅ１∧ｖ１とする。このような条件付けは、ＢＤＤが提供するｃｏｍｐｏｓｉｔｉｏｎと呼ばれる演算によって行うことができる（ここではｂｌａｃｋｂｏｘとして扱ってよい）。すべての辺に対してｃｏｍｐｏｓｉｔｉｏｎを行い、ＢＤＤを変換する。例えば、リンクｅ１をｓ∧ｅ１∧ｖ１とし、リンクｅ２をｓ∧ｅ２∧ｖ２とし、リンクｅ３をｖ１∧ｅ３∧ｖ２とし、リンクｅ４をｖ１∧ｅ４∧ｔとし、リンクｅ５をｖ２∧ｅ５∧ｔとする。
【００１２】
図５に、ノード状態及び連結状態の両方を含むように変換されたＢＤＤを示す。たとえば、このＢＤＤのもっとも右のパスは、（ｓ，ｅ１，ｅ２，ｖ１，ｅ３，ｅ４，ｖ２，ｅ５，ｔ）＝（１，１，１，１，＊，１，＊，＊，１）というネットワーク状態を表し、┬終端節点に到達していることから連結であるとわかる。連結確率の算出手法は非特許文献１と同様である。図５に示す括弧内の数字は、すべてのリンクとノードの故障率を１０％としたときの各節点の確率の計算例を示してある。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】Ｇ．Ｈａｒｄｙ，Ｃ．Ｌｕｃｅｔ，ａｎｄ  Ｎ．Ｌｉｍｎｉｏｓ，“Ｋ−Ｔｅｒｍｉｎａｌ  Ｎｅｔｗｏｒｋ  Ｒｅｌｉａｂｉｌｉｔｙ  Ｍｅａｓｕｒｅｓ  Ｗｉｔｈ  Ｂｉｎａｒｙ  Ｄｅｃｉｓｉｏｎ  Ｄｉａｇｒａｍｓ”，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｒｅｌｉａｂｉｌｉｔｙ，ｖｏｌ．５６，ｎｏ．３，ｐｐ．５０６−５１５，Ｓｅｐｔ．２００７
【非特許文献２】Ｓ．Ｋｕｏ，Ｆ．Ｙｅｈ  ａｎｄ  Ｈ．Ｌｉｎ，“Ｅｆｆｉｃｉｅｎｔ  ａｎｄ  Ｅｘａｃｔ  Ｒｅｌｉａｂｉｌｉｔｙ  Ｅｖａｌｕａｔｉｏｎ  ｆｏｒ  Ｎｅｔｗｏｒｋｓ  Ｗｉｔｈ  Ｉｍｐｅｒｆｅｃｔ  Ｖｅｒｔｉｃｅｓ”，  ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｒｅｌｉａｂｉｌｉｔｙ，ｖｏｌ．５６，ｎｏ．２，ｐｐ．２８８−３００，Ｊｕｎｅ  ２００７
【発明の概要】
【発明が解決しようとする課題】
【００１４】
非特許文献２は、ノード状態を含むようにＢＤＤを変換するために、すべての辺に対してｃｏｍｐｏｓｉｔｉｏｎを行う必要があった。このため、計算コストが高いという問題がある。
【００１５】
ここで、連結確率の算出に必要な計算量を見積もる。ネットワークのノード数をｎ、リンク数をｍとする。ここでは疎なネットワークを考え、次数（ノードあたりのリンク数）を定数ｋで抑えられるとする。すると、ｍ≦ｋｎ／２であるから、ｍ＝Ｏ（ｎ）となる（密なネットワークではｍ＝Ｏ（ｎ２）とすればよい）。ＢＤＤの高さはｎ＋ｍ＝Ｏ（ｎ）である。ＢＤＤの各レベルでの節点数を「幅」と呼び、最大の幅をｗで表す。ＢＤＤの節点数は（ｎ＋ｍ）ｗ以下であり、Ｏ（ｎｗ）となる。
【００１６】
ＢＤＤ構築アルゴリズムとｃｏｍｐｏｓｉｔｉｏｎ演算、連結確率の計算量は、すべてＢＤＤの節点数に依存するため、Ｏ（ｎｗ）である。ＢＤＤ構築と確率計算は１回ずつ実行され、ｃｏｍｐｏｓｉｔｉｏｎはすべての辺に対して実行されるため、全体の計算量は（ｍ＋２）×Ｏ（ｎｗ）＝Ｏ（ｎ２ｗ）となる。つまり、ネットワークサイズｎの２乗に比例して計算コストが増加してしまう。
【００１７】
本発明は、リンク故障だけでなくノード故障も考慮しつつ、連結確率の計算コストを抑制することを目的とする。
【課題を解決するための手段】
【００１８】
本発明に係るネットワーク評価装置は、
複数のノードが複数のリンクで接続されたネットワークにおけるノード間の連結確率を、二分決定図を用いて算出するネットワーク評価装置であって、
ノードとリンクの接点を示す頂点を前記接点ごとに生成し、
共通のノードに接続される全てのリンクの前記頂点を包含するノード領域をノードごとに生成し、
共通のリンクに接続される全てのノードの前記頂点を包含するリンク領域をリンクごとに生成し、
前記ノード領域のうちの連結対象のノードのノード領域内に、連結対象のノードであることを示す頂点を生成する、ハイパーグラフ生成部と、
前記連結対象のノードのうちの一方を示す前記頂点の状態を根節点とし、
前記連結対象のノードのうちの他方を示す前記頂点に連結されるか否かを終端節点とし、
前記連結対象のノードのうちの一方から他方までの間に経由する前記ノード領域及び前記リンク領域の各状態を節点とする二分決定図を構築する、二分決定図構築部と、
前記二分決定図における各節点の確率を算出し、算出した確率を用いて、前記ネットワークにおける前記連結対象のノード間の連結確率を算出する、確率算出部と、
を備える。
【００１９】
本発明に係るネットワーク評価方法は、
複数のノードが複数のリンクで接続されたネットワークにおけるノード間の連結確率を、二分決定図を用いて算出するネットワーク評価装置が実行する方法であって、
ノードとリンクの接点を示す頂点を前記接点ごとに生成し、
共通のノードに接続される全てのリンクの前記頂点を包含するノード領域をノードごとに生成し、
共通のリンクに接続される全てのノードの前記頂点を包含するリンク領域をリンクごとに生成し、
前記ノード領域のうちの連結対象のノードのノード領域内に、連結対象のノードであることを示す頂点を生成する、ハイパーグラフ生成手順と、
前記連結対象のノードのうちの一方を示す前記頂点の状態を根節点とし、
前記連結対象のノードのうちの他方を示す前記頂点に連結されるか否かを終端節点とし、
前記連結対象のノードのうちの一方から他方までの間に経由する前記ノード領域及び前記リンク領域の各状態を節点とする二分決定図を構築する、二分決定図構築手順と、
前記二分決定図における各節点の確率を算出し、算出した確率を用いて、前記ネットワークにおける前記連結対象のノード間の連結確率を算出する確率算出手順と、
を順に有する。
【００２０】
本発明に係るネットワーク評価プログラムは、ハイパーグラフ生成手順、二分決定図構築手順及び確率算出手順をコンピュータに実行させることによって、本発明に係るネットワーク評価装置を実現する。
【発明の効果】
【００２１】
本発明によれば、リンク故障だけでなくノード故障も考慮した連結確率の計算コストを抑制することができる。
【図面の簡単な説明】
【００２２】
【図１】辺連結度が１のネットワーク構成の一例を示す。
【図２】辺連結度が２のネットワーク構成の一例を示す。
【図３】ノードｓとノードｔの間に５つのリンクを有するネットワーク構成の一例である。
【図４】連結状態を表すＢＤＤの一例である。
【図５】ノード状態及び連結状態を含むように変換されたＢＤＤの一例を示す。
【図６】本発明の実施形態に係るネットワーク評価装置の構成の一例を示す。
【図７】ハイパーグラフの一例を示す。
【図８】ハイパーグラフへの変換例を示す。
【図９】ハイパーグラフへの変換手順のフローチャートの一例を示す。
【図１０】本発明の実施形態におけるＢＤＤ構築過程の一例を示す。
【発明を実施するための形態】
【００２３】
以下、本発明の実施形態について、図面を参照しながら詳細に説明する。なお、本発明は、以下に示す実施形態に限定されるものではない。これらの実施の例は例示に過ぎず、本発明は当業者の知識に基づいて種々の変更、改良を施した形態で実施することができる。なお、本明細書及び図面において符号が同じ構成要素は、相互に同一のものを示すものとする。
【００２４】
本実施形態に係るネットワーク評価装置及びネットワーク評価方法は、ネットワーク構成をｈｙｐｅｒｇｒａｐｈ（以下、ハイパーグラフと称する。）として表現することで、ノードをリンクの一種であるｈｙｐｅｒｅｄｇｅ（以下、ハイパーエッジと称する。）として扱えるようにする。これによって、本実施形態に係る発明は、ｃｏｍｐｏｓｉｔｉｏｎを用いることなく、図５のようにノード状態及び連結状態をともに含むＢＤＤを構築する。
【００２５】
図６に、本実施形態に係るネットワーク評価装置の構成図を示す。本実施形態に係るネットワーク評価装置は、情報処理部及び記憶部を備える。情報処理部は、例えばＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）であり、ネットワーク情報入力部１１、ハイパーグラフ生成部１３、ＢＤＤ構築部１５及び確率算出部１７として機能する。記憶部は、例えばメモリであり、ネットワーク情報のデータベース１２、ハイパーグラフのデータベース１４、ＢＤＤのデータベース１６として機能する。
【００２６】
本実施形態に係るネットワーク評価は、ハイパーグラフ生成手順と、二分決定図構築手順と、確率算出手順と、を順に有する。
【００２７】
ネットワーク情報入力部１１は、ノードとリンク、それらの稼働率をネットワーク情報のＤＢ１２に保存する。
ハイパーグラフ生成手順では、ハイパーグラフ生成部１３が、図９のフローチャートに従って、ネットワークを図７に示すハイパーグラフに変換し、ハイパーグラフのＤＢ１４に保存する。
二分決定図構築手順では、ＢＤＤ構築部１５が、図１０のようにしてハイパーグラフからＢＤＤを構築し、ＢＤＤのＤＢ１６に保存する。
確率算出手順では、確率算出部１７が、ＢＤＤとネットワーク情報（ノードとリンクの稼働率）から、連結確率を算出する。
【００２８】
まず、ハイパーグラフについて説明する。通常のグラフにおける辺とは、２つの頂点の組合せである。ハイパーグラフでは、２つ以上の任意の数の頂点を組合せ、辺として扱う（一般化グラフとも呼ばれる）。このような辺をハイパーエッジと呼ぶ。ハイパーエッジを図で示すときは、任意の数の組合せを表現するために、直線ではなく「点を囲む領域」として表す。ハイパーグラフにおける頂点は、「ｈｙｐｅｒｖｅｒｔｅｘ」と呼ばれるが、本実施形態では簡単のため、「頂点」と記載する。
【００２９】
ネットワークからハイパーグラフへの変更方法を説明する。図７に、図３のネットワークから変換したハイパーグラフを示す。ノードとリンクの接点を、ハイパーグラフにおける頂点とする。元のリンクに加え、ノードｓ、ｖ１、ｖ２、ｔもハイパーエッジとして表されている。ノードｓ、ｔには、ノードとリンクの接点以外にも、頂点ｐｓ０及びｐｔ０を１つずつ追加しておく。
【００３０】
ハイパーグラフ生成部１３におけるハイパーグラフへの変換手順をまとめる。
ステップＳ１：元のネットワークにおけるノードとリンクの接点を頂点とする。例えば、ノードｓとリンクｅ１の接点を頂点ｐｓ１とする。接点とは図７及び図８に示す黒丸であり、例えば、ルータにおけるリンクを差し込むためのポートのような位置づけと考えることができる。この頂点を接点ごとに生成する。これによって、頂点ＰＳ１、ＰＳ２、Ｐ１１、Ｐ１３、Ｐ１４、Ｐ２２、Ｐ２３、Ｐ２５、Ｐｔ４、Ｐｔ５を生成する。
【００３１】
ステップＳ２：元のネットワークのノードをハイパーエッジとみなし、ノード領域を示すハイパーエッジをノードごとに生成する。図８では、ノードｓ、ｖ１、ｖ２、ｔがノード領域のハイパーエッジとなる。図示するときは、頂点を囲む領域で表す。ノード領域のハイパーエッジは、共通のノードに接続される全てのリンクの頂点を包含する。例えば、ノードｓのハイパーエッジは、頂点ｐｓ１及びｐｓ２を囲む領域となる。
【００３２】
また、図７に示すように、元のネットワークのリンクも、リンク領域を示すハイパーエッジとし、リンクごとに生成する。図８では、ｅ１、ｅ２、ｅ３、ｅ４、ｅ５がリンク用のハイパーエッジとなる。図示するときは、直線から、リンクを構成する接点を囲む楕円に書き換えておく。リンク領域のハイパーエッジは、共通のリンクに接続される全てのノードの頂点を包含する。例えば、リンクｅ１のリンク領域のハイパーエッジは、頂点ｐｓ１及びｐ１１を囲む領域となる。
【００３３】
ステップＳ３：連結対象ノードであるノードｓとノードｔを表すノード領域のハイパーエッジ内に、１つずつ連結対象のノードであることを示すｈｙｐｅｒｖｅｒｔｅｘである頂点を追加する。例えば、ノードｓのｈｙｐｅｒｖｅｒｔｅｘはノードｓのハイパーエッジで囲まれた頂点ｐｓ０であり、ノードｔのｈｙｐｅｒｖｅｒｔｅｘはノードｔのハイパーエッジで囲まれた頂点ｐｔ０である。
【００３４】
この手順の計算量を考える。ｈｙｐｅｒｖｅｒｔｅｘは各リンクの両端にあり、ノードｓとノードｔにひとつずつ追加されるため、２ｍ＋２個である。また、ハイパーエッジに変換されるノード数はｎである。これらに対して変換処理を行うため、ハイパーグラフに変換するための計算量は２ｍ＋ｎ＋２＝Ｏ（ｎ）である。
【００３５】
ハイパーグラフへの変換手順を表すフローチャートを図９に示す。ネットワーク情報としてノードとリンクが与えられると、まず、すべてのリンクに対して（Ｓ１０１）、ステップＳ１で説明したように、ノードとの接点をｈｙｐｅｒｖｅｒｔｅｘに変換する（Ｓ１０２）。また、ステップＳ２で説明したように、各リンクをハイパーエッジに変換しておく（Ｓ１０３）。
次に、すべてのノードに対して（Ｓ１０４）、ステップＳ２で説明したように、ハイパーエッジへの変換処理を行う（Ｓ１０５）。
最後に、ステップＳ３で説明したように、始端であるノードｓ及び終端であるノードｔを表すハイパーエッジに、ノードを示す頂点を追加する（Ｓ１０６）。例えば、図９に示す頂点ｐｓ０及び頂点ｐｔ０である。
【００３６】
この図９に示すようなハイパーグラフを用いて、連結状態を表すＢＤＤを構築し、連結確率を算出する。ハイパーグラフでは、頂点ｐｓ０及び頂点ｐｔ０の連結性を考える。頂点ｐｓ０及び頂点ｐｔ０を連結するためには、図３に示すノードｖ１，ｖ２とリンクｅ１〜ｅ５を通過しなければならない。そこで、元のネットワークと同様に連結状態を考え、各節点の確率を算出する。
【００３７】
ここで、非特許文献１のＢＤＤ構築アルゴリズムは、リンクに含まれるノード数を２つに限定していない。つまり、ネットワークをハイパーグラフに変換しても、既存のＢＤＤ構築アルゴリズムをそのまま適用することができる。また、ＢＤＤを構築してしまえば、元がネットワークであったかハイパーグラフであったかは関係なく、各節点の確率を算出することができる。
【００３８】
図１０を用いて、ＢＤＤ構築過程を説明する。本実施形態において構築するＢＤＤは、連結対象のノードｓからノードｔまでの間に経由するリンクｅ１、リンクｅ２、ノードｖ１、リンクｅ３、リンクｅ４、ノードｖ２、リンクｅ５の状態を節点とする。連結対象のノードのうちのノードｓを示す頂点ｐｓ０の状態を根節点とし、連結対象のノードのうちのノードｔを示す頂点ｐｔ０に連結されるか否かを終端節点とする。例えば、ノードｓがノードｔに連結されることを示す「┬」又はノードｓがノードｔに非連結状態であることを示す「┴」である。ハイパーエッジの順序をノードｓ、リンクｅ１、リンクｅ２、ノードｖ１、リンクｅ３、リンクｅ４、ノードｖ２、リンクｅ５、ノードｔとし、この順に従って状態を決定していく。
【００３９】
まず、ＢＤＤの根節点Ｖ−ｓを置く。根節点Ｖ−ｓは、連結対象のノードのうちの一方を示す頂点ｐｓ０の状態を示す。ＢＤＤ節点Ｖ−ｓ内に、ハイパーエッジの状態を図示する。破線のハイパーエッジは状態が未決定であり、実線は稼働状態に決定したことを表す。
【００４０】
ノードｓが故障していると（ｓ＝０）、他のハイパーエッジの状態にかかわらず頂点ｐｓ０及び頂点ｐｔ０は連結されないため、０枝を非連結状態を表す┴につなぐ。ノードｓが稼働しているときは（ｓ＝１）、次のハイパーエッジである節点Ｖ−ｅ１へと処理を継続する。
【００４１】
節点Ｖ−ｅ１は、ノードｓが稼働していることを示す。例えば、ノードｓのハイパーエッジ内を黒塗りにする。そして、次のハイパーエッジである節点Ｖ−ｅ２−１及び節点Ｖ−ｅ２−１へと処理を継続する。
【００４２】
節点Ｖ−ｅ２−１は、リンクｅ１が非連結状態である場合（ｅ１＝０）のハイパーエッジの状態を示す。リンクｅ１が非連結状態であるため、リンクｅ１を除去する。節点Ｖ−ｅ２−２は、リンクｅ１が連結状態である場合（ｅ１＝１）のハイパーエッジの状態を示す。リンクｅ１が連結状態であるため、リンクｅ１内を黒塗りにする。
【００４３】
このように、頂点ｐｓ０及び頂点ｐｔ０が非連結にならない限り、この手続きを繰り返しＢＤＤを上から下へと構築していく。これにより、ノード状態及び連結状態を含むＢＤＤを構築することができる。図１０はノードｖ２の途中まで構築した様子を表している。
【００４４】
ここで、「等価な」節点が現れたときは、節点Ｖ−ｖ２−１及び節点Ｖ−ｅ４−３のように、枝を合流させることができる。例えば、節点Ｖ−ｖ１−１、節点Ｖ−ｖ３−１及び節点Ｖ−ｅ３−１は、いずれも未処理部との接続関係が同じである。例えば、上からノードｓ、リンクｅ１、リンクｅ２、ノードｖ１、リンクｅ３、リンクｅ４の処理が終わり、未処理なのはノードｖ２、リンクｅ５、ノードｔである。未処理の３つの枝はいずれもリンクｅ２を経由してｖ２に接続している。しかし、ノードｖ２が存在せず、リンクｅ５は未定であるため，ノードｔには接続していない。また、リンクｅ５の両端であるノードｖ２とノードｔの状態が未定なため、リンクｅ５にもまだ接続していない。このため、節点Ｖ−ｖ１−１、節点Ｖ−ｖ３−１及び節点Ｖ−ｅ３−１は、ノードｖ２を経由してノードｔに到達するしか道はなく、残りのハイパーエッジ（ノードｖ２，リンクｅ５）を考えるときには区別しなくてよい。このため、節点Ｖ−ｖ１−１、節点Ｖ−ｖ３−１及び節点Ｖ−ｅ３−１の枝を合流させて縮退させ、節点Ｖ−ｖ２−１とする。このとき、灰色で示すリンクｅ１、ノードｖ１、リンクｅ３、リンクｅ４のハイパーエッジは、０又は１いずれの状態であってもよい。
【００４５】
節点Ｖ−ｅ４−３についても同様である。この時点では、上からノードｓ、リンクｅ１、リンクｅ２、ノードｖ１、リンクｅ３の処理が終わり、ノードｖ２、リンクｅ４、リンクｅ５、ノードｔが未処理である。節点Ｖ−ｅ４−３に合流している２つの枝は、リンクｅ１又はリンクｅ３を経由してノードｖ２に接続している。また、ノードｖ１を経由してリンクｅ４にも接続している。一方、リンクｅ５とノードｔについては未定である。この場合、節点Ｖ−ｅ４−３は、リンクｅ２とリンクｅ３の少なくともどちらかが稼働しており、ノードｖ１とノードｖ２のいずれもノードｔに到達する可能性を残している。
【００４６】
確率算出部１７は、図１０に示す各節点の確率を算出し、算出した確率を用いて、ノードｓからノードｔまでの連結確率を算出する。確率算出部１７における連結確率の計算は、例えば、非特許文献１と同様の手法を用いて行うことができる。例えば、節点Ｖ−ｖ２−１及び節点Ｖ−ｅ４−１の確率を用いて節点Ｖ−ｅ３−１の確率を求める。節点Ｖ−ｖ２−１の確率が０．７２９であり、節点Ｖ−ｅ４−１の確率が０．８０１９であり、すべてのリンクとノードの故障率を１０％とすると、節点Ｖ−ｅ３−１の確率は、０．７２９×０．１＋０．８０１９×０．９＝０．７９４６１となる。このように、本実施形態では、ノード状態及び連結状態の両方を用いて各接点の確率を求める。
【００４７】
非特許文献２の手法が図４を構築してからｃｏｍｐｏｓｉｔｉｏｎ演算によって図５へと変換したのに対し、本実施形態では、ノード状態及び連結状態を含むＢＤＤを直接構築することができる。
【００４８】
本実施形態における全体の計算量を考える。図７に示すハイパーグラフへの変換はＯ（ｎ）であった。従来技術で述べたように、ＢＤＤ構築と連結確率の計算量はＯ（ｎｗ）である。全体の計算量はＯ（ｎ）＋Ｏ（ｎｗ）＝Ｏ（ｎｗ）であり、非特許文献２のＯ（ｎ２ｗ）より小さい。
【００４９】
ここまで、２つのノードｓ及びノードｔの連結確率を考えてきたが、２つに限定される処理はない。既存のＢＤＤ構築アルゴリズムと確率計算も、２つに限定されない。よって、連結対象とするノード数が３以上になっても、同じ手法を適用することができる。
【００５０】
本実施形態は、計算コストの高いｃｏｍｐｏｓｉｔｉｏｎ演算を行うことなく、短時間で連結確率を算出することができる。ネットワークのノード数をｎ、構築されるＢＤＤの幅をｗとすると、計算量をＯ（ｎ２ｗ）からＯ（ｎｗ）に削減することができる。
【００５１】
本実施形態に係るネットワーク評価装置は、記憶部（不図示）に記憶されたコンピュータプログラムを実行することで、各構成を実現してもよい。このように、本実施形態に係るネットワーク評価装置は、コンピュータとプログラムによっても実現でき、プログラムを記録媒体に記録することも、ネットワークを通して提供することも可能である。
【産業上の利用可能性】
【００５２】
本発明は情報通信産業に適用することができる。
【符号の説明】
【００５３】
１１：ネットワーク情報入力部
１２：ネットワーク情報のデータベース
１３：ハイパーグラフ生成部
１４：ハイパーグラフのデータベース
１５：ＢＤＤ構築部
１６：ＢＤＤのデータベース
１７：確率算出部
【図１】
0006282606.tif 000002
【図２】
0006282606.tif 000003
【図３】
0006282606.tif 000004
【図４】
0006282606.tif 000005
【図５】
0006282606.tif 000006
【図６】
0006282606.tif 000007
【図７】
0006282606.tif 000008
【図８】
0006282606.tif 000009
【図９】
0006282606.tif 000010
【図１０】
0006282606.tif 000011