単純な無向グラフの故障分布関数を計算するための漸化式を導出

【背景・経緯】

　道路網、送電網、通信網など世の中のインフラ構造は、数学的には「グラフ」で表現されます。ここでグラフとは、送電網を例にすると発電所や電気を消費する施設は「点」で表現され、施設間を結ぶ電線は「辺」で表現されます。そのため、インフラの構造的な強さ（ロバスト性）を評価するひとつの方法として、グラフの故障分布関数（ある時刻までに故障する確率を表す関数）を導出することが考えられます。しかし、大規模なグラフになると故障分布関数を実際に導出することは、一般的に困難です。そこで、故障分布関数の一般式をパラメータが含まれる形で表現し、そのパラメータの値を比較的な容易な方法で算出するアプローチを提案しました。

 

【成果】

　最も基本的なグラフである、単純（２点間を直接繋ぐ辺は高々１本）な無向（辺に向きを持たない）グラフを対象とし、辺のみが時刻に依存するある一定の確率で外的要因（自然災害や攻撃）によって故障する状況下で、グラフが連結（任意の２点間が辺をたどって行き来可能）ではなくなることを故障と見なし、その故障分布関数を計算するための漸化式を導出しました。具体的には、あるグラフに辺が１本追加された場合には、頂点数が変化しないケースと、頂点数が１個増えるケースしかないことに着目し、それぞれのケースについてあるグラフに辺が１本追加されたときの故障分布関数のパラメータを、辺が追加される前のグラフの故障分布関数のパラメータで表現する漸化式を導出しました。さらに、導出した漸化式を用いて、簡単なグラフである閉路グラフ（環状グラフ）や木（連結で閉路をもたないグラフ）や、単純な例について、具体的に故障分布関数を導出しました。

※ H. Mohri and J. Takeshita*, Graph reliability evaluation via random K-out-of-N systems, International Journal of Reliability,  Commun. Stat. Theory Methods (to appear).
 

図　グラフHに辺が１本追加された場合に、(i)頂点数が変化しないときと、(ii) 頂点数が１つ増えるときの例

 

【成果の意義・今後の展開】

　グラフの故障分布関数のパラメータに関する漸化式を導出した結果、大規模なグラフでも比較的簡単に故障分布関数を具体的に導出することが可能となりました。2頂点間に１辺のみを有する最も単純なグラフの故障分布関数は簡単に導出できるため、その結果に今回得られた漸化式を繰り返し適用することで、任意の単純な無向グラフについてその故障分布関数が得られます。今後はより現実的な現象をモデル化できる、より複雑なグラフも研究対象にしていきたいと考えています。

 

2023年08月02日