ネットワーク構成装置、処理方法およびプログラム
【課題】通信ネットワークに適したグラフを構成するネットワーク構成装置、処理方法およびプログラムを提供する。
【解決手段】ネットワーク構成装置は、通信ネットワークがＶ個のノードとＥ本のリンクとで構成されるグラフＧにおいて、平方剰余（ｐ｜ｑ）＝１を満たす互いに異なる素数ｐおよび素数ｑについて、ノード数がｑ＋１であり、ノード次数がｐ＋１であるラマヌジャングラフを構成し、そのラマヌジャングラフから、単数または複数のノードを除去した場合にラマヌジャングラフが非連結にはならず、ノードが故障した前後で、ノード次数が４以上の偶数のまま不変であり、かつ、グラフＧの第２最小ラプラシアン固有値が、所定の関係式を満たす範囲内で可能な限り大きいグラフＧを構成する。
【解決手段】ネットワーク構成装置は、通信ネットワークがＶ個のノードとＥ本のリンクとで構成されるグラフＧにおいて、平方剰余（ｐ｜ｑ）＝１を満たす互いに異なる素数ｐおよび素数ｑについて、ノード数がｑ＋１であり、ノード次数がｐ＋１であるラマヌジャングラフを構成し、そのラマヌジャングラフから、単数または複数のノードを除去した場合にラマヌジャングラフが非連結にはならず、ノードが故障した前後で、ノード次数が４以上の偶数のまま不変であり、かつ、グラフＧの第２最小ラプラシアン固有値が、所定の関係式を満たす範囲内で可能な限り大きいグラフＧを構成する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク構成装置、処理方法およびプログラムに関し、特には、グラフ理論を用いて通信ネットワークおよびシステムを構成するネットワーク構成装置、処理方法およびプログラムに関する。
【背景技術】
【０００２】
ネットワークを含むシステムおよびネットワーク（以下、「ＮＷ」と記す。）のグラフ構造（以下、単に、「グラフ」とも言う）を構成するノードの通信端末は故障することがある。この場合、ノードの故障後に構成されるＮＷのグラフ構造では、元のＮＷのグラフ構造が有していた「通信ＮＷに適した３つの特性」が維持されることが、通信ＮＷの堅牢性を保つ上で重要である。
【０００３】
通信ＮＷに適した３つの特性とは、１）任意の２ノード間の通信時間が短いこと、２）任意の２ノード間に複数の経路があること、３）スケーラビリティーが高いこと、を意味する。これら３つの条件は、「通信ＮＷに適した特性」の十分条件ではないが、必要条件のうち特に重要な条件である。
【０００４】
上記の３つの条件について、それぞれに対応するグラフ上の条件（以下、「グラフ条件」と称する）が存在する（例えば、非特許文献１〜３参照）。
【０００５】
１）のグラフ条件は、非特許文献１に示されているとおり、グラフ上でのランダムウォークにおけるｆｉｒｓｔ ｐａｓｓａｇｅ ｔｉｍｅが短いグラフであること、および、非特許文献２に示されているとおり、グラフ直径が小さいこと、である。なお、ｆｉｒｓｔ ｐａｓｓａｇｅ ｔｉｍｅは、グラフの第２最小ラプラシアン固有値が大きいほど、短くなることが知られている（非特許文献１および３参照）。
【０００６】
２）のグラフ条件は、グラフが連結であり、かつ、非特許文献２に示されているとおり、拡大定数が大きいこと、である。
【０００７】
３）のグラフ条件は、グラフ構造を構成するリンクの数が、ノード数（ＮＷサイズ）の増加に伴い、線形に増加する、または、線形に増加する数以下で増加すること、である。なお、完全グラフは、１）および２）のグラフ条件を満たしているが、ノード数の増加に伴いリンク数が概ねノード数の２乗に比例して増加するため、３）のグラフ条件を満たしていない。
【０００８】
非特許文献２では、「通信ＮＷに適した３つの特性」を満たすグラフが、ラマヌジャングラフであることも記載されている。しかしながら、非特許文献２には、ノードが故障したときに再帰的にラマヌジャングラフを構成可能であるラマヌジャングラフの構造および条件については記載されていない。
【０００９】
また、非特許文献１および非特許文献４〜６には、Ｅｎｔａｎｇｌｅｄ ＮＷが、記載されている。これは、第２最小ラプラシアン固有値λ２と、最大ラプラシアン固有値λＮとの比（λＮ／λ２）を最小化するようなグラフである。このグラフは、１）のグラフ条件しか満たしていない。
【００１０】
なお、非特許文献７〜９では、Ｂｉｍｏｄａｌ ＮＷが、記載されており、このグラフでは、ノードまたはリンクを、ランダムまたは選択的に除去した場合でも、元のグラフの連結性が維持されることが定量的に示されている。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】Ｌｕｃａ Ｄｏｎｅｔｔｉ， Ｆｒａｎｃｏ Ｎｅｒｉ ａｎｄ Ｍｉｇｕｅｌ Ａ Ｍｕnｏｚ．“Ｏｐｔｉｍａｌ ｎｅｔｗｏｒｋ ｔｏｐｏｌｏｇｉｅｓ：ｅｘｐａｎｄｅｒｓ， ｃａｇｅｓ， Ｒａｍａｎｕｊａｎ ｇｒａｐｈｓ， ｅｎｔａｎｇｌｅｄ ｎｅｔｗｏｒｋｓ ａｎｄ ａｌｌ ｔｈａｔ，” Ｊｏｕｒｎａｌ ｏｆ Ｓｔａｔｉｓｔｉｃａｌ Ｍｅｃｈａｎｉｃｓ： Ｔｈｅｏｒｙ ａｎｄ Ｅｘｐｅｒｉｍｅｎｔ，Ｖｏｌｕｍｅ ２００６， Ａｕｇｕｓｔ ２００６．
【非特許文献２】平松豊一・知念宏司 共著．“有限数学入門 有限上半平面とラマヌジャングラフ”牧野出版（２００３年８月初版），ＩＳＢＮ４−４３４−０３４０７−３ Ｃ３０４１．
【非特許文献３】Ｐ Ｚｕｍｓｔｅｉｎ． “Ｃｏｍｐａｒｉｓｏｎ ｏｆ Ｓｐｅｃｔｒａｌ Ｍｅｔｈｏｄｓ Ｔｈｒｏｕｇｈ ｔｈｅ Ａｄｊａｃｅｎｃｙ Ｍａｔｒｉｘ ａｎｄ ｔｈｅ Ｌａｐｌａｃｉａｎ ｏｆ ａ Ｇｒａｐｈ，” ｓｕｂｍｉｔｔｅｄ ２８． Ｆｅｂｒｕａｒｙ ２００５ ａｔ ＥＴＨ Ｚｕｒｉｃｈ， ２００５．
【非特許文献４】Ｌ． Ｄｏｎｅｔｔｉ， Ｐ．Ｉ． Ｈｕｒｔａｄｏ， ａｎｄ Ｍ．Ａ． Ｍｕnｏｚ． “Ｅｎｔａｎｇｌｅｄ Ｎｅｔｗｏｒｋｓ， Ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ， ａｎｄ Ｏｐｔｉｍａｌ Ｎｅｔｗｏｒｋ Ｔｏｐｏｌｏｇｙ，” Ｐｈｙｓ． Ｒｅｖ． Ｌｅｔｔ． ９５， １８８７０１， ２００５．
【非特許文献５】Ｌ． Ｄｏｎｅｔｔｉ， Ｐ．Ｉ． Ｈｕｒｔａｄｏ， ａｎｄ Ｍ．Ａ． Ｍｕnｏｚ． “Ｅｎｔａｎｇｌｅｄ ｎｅｔｗｏｒｋｓ， ｓｕｐｅｒ−ｈｏｍｏｇｅｎｅｉｔｙ ａｎｄ ｏｐｔｉｍａｌ ｎｅｔｗｏｒｋ ｔｏｐｏｌｏｇｙ，” Ａｒｘｉｖ ｐｒｅｐｒｉｎｔ ｃｏｎｄ−ｍａｔ／０５０２２３０， ２００５．
【非特許文献６】Ｌ． Ｄｏｎｅｔｔｉ， Ｐ．Ｉ． Ｈｕｒｔａｄｏ， ａｎｄ Ｍ．Ａ． Ｍｕnｏｚ． “Ｎｅｔｗｏｒｋ ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ： ｏｐｔｉｍａｌ ａｎｄ ｐｅｓｓｉｍａｌ ｓｃａｌｅ−ｆｒｅｅ ｔｏｐｏｌｏｇｉｅｓ，” Ｊｏｕｒｎａｌ ｏｆ Ｐｈｙｓｉｃｓ Ａ： Ｍａｔｈｅｍａｔｉｃａｌ ａｎｄ Ｔｈｅｏｒｅｔｉｃａｌ， Ｖｏｌ． ４１， Ｎｏ． ２２， ２００８．
【非特許文献７】Ｇ． Ｐａｕｌ， Ｔ． Ｔａｎｉｚａｗａ， Ｓ． Ｈａｖｌｉｎ， ａｎｄ Ｈ． Ｅ． Ｓｔａｎｌｅｙ． “Ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ Ｒｏｂｕｓｔｎｅｓｓ ｏｆ Ｃｏｍｐｌｅｘ Ｎｅｔｗｏｒｋｓ，” ［Ｐｒｏｃ． ２００３ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｇｒｏｗｉｎｇ Ｎｅｔｗｏｒｋｓ ａｎｄ Ｇｒａｐｈｓ］， Ｅｕｒｏ． Ｐｈｙｓ． Ｊ． Ｂ ３８ ，ｐｐ―１８７−１９１， ２００４．
【非特許文献８】Ｔ Ｔａｎｉｚａｗａ， Ｇ Ｐａｕｌ ａｎｄ Ｒ Ｃｏｈｅｎ ｅｔ ａｌ． “Ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ｎｅｔｗｏｒｋ ｒｏｂｕｓｔｎｅｓｓ ｔｏ ｗａｖｅｓ ｏｆ ｔａｒｇｅｔｅｄ ａｎｄ ｒａｎｄｏｍ ａｔｔａｃｋｓ，” Ｐｈｙｓ． Ｒｅｖ． Ｅ． Ｖｏｌ．７１，Ｎｏ． ４，２００５．
【非特許文献９】Ｔ． Ｔａｎｉｚａｗａ，Ｇ．Ｐａｕｌ，Ｓ．Ｈａｖｌｉｎ，ａｎｄ Ｈ． Ｅ．Ｓｔａｎｌｅｙ． “Ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ｔｈｅ ｒｏｂｕｓｔｎｅｓｓ ｏｆ ｍｕｌｔｉｍｏｄａｌ ｎｅｔｗｏｒｋｓ，”Ｐｈｙｓ．Ｒｅｖ．Ｅ，Ｖｏｌ．７４，Ｎｏ．１，２００６．
【発明の概要】
【発明が解決しようとする課題】
【００１２】
ノードの故障後に構成される通信ＮＷのグラフでは、元のグラフが有していた「通信ＮＷに適した３つの特性」を維持することが、通信ＮＷの堅牢性を保つ上で重要である。
【００１３】
しかしながら、非特許文献１〜９では、上記のグラフの構成を実現するための具体的な記載がなく、通信ＮＷに適した３つの特性をノードの故障後にも維持できるグラフの構成手法が明らかにされていなかった。
【００１４】
本発明の目的は、上記した課題を解決するネットワーク構成装置、処理方法およびプログラムを提供することにある。
【課題を解決するための手段】
【００１５】
本発明のネットワーク構成装置は、通信ネットワークをＶ個のノードとＥ本のリンクとで構成するグラフＧを作成するネットワーク構成装置であって、前記グラフＧでは、平方剰余（ｐ｜ｑ）＝１を満たす互いに異なる素数ｐおよび素数ｑについて、ノード数がｑ＋１であり、ノード次数がｐ＋１である連結なラマヌジャングラフから、単数または複数の前記ノードを除去した場合に前記ラマヌジャングラフが非連結にはならず、前記ノードが故障した前後で、前記ノード次数が４以上の偶数のまま不変であり、かつ、前記グラフＧの第２最小ラプラシアン固有値が、以下の関係式を満たす範囲内で可能な限り大きい。
【００１６】
【数１】
【００１７】
ここで、ｋは、前記ノード次数であり、λＮ（Ｌ（Ｇ））は、上記を満たす前記グラフＧの最大ラプラシアン固有値であり、λ２（Ｌ（Ｇ））は、上記を満たす前記グラフＧの第２最小ラプラシアン固有値であり、λ２（Ｌ（Ｇ（Ｖ−１，Ｅ−ｋ／２）））は、上記を満たす前記グラフＧから、１個の前記ノードと、該ノードに接続されていた前記リンクのうちの（ｋ／２）本のリンクとが除去されたグラフの第２最小ラプラシアン固有値である。
【００１８】
また、本発明の処理方法は、ネットワーク構成装置が行う処理方法であって、通信ネットワークがＶ個のノードとＥ本のリンクとで構成されるグラフＧにおいて、平方剰余（ｐ｜ｑ）＝１を満たす互いに異なる素数ｐおよび素数ｑについて、ノード数がｑ＋１であり、ノード次数がｐ＋１である連結なラマヌジャングラフを構成する第１構成ステップと、前記ラマヌジャングラフから、単数または複数の前記ノードを除去した場合に前記ラマヌジャングラフが非連結にはならず、前記ノードが故障した前後で、前記ノード次数が４以上の偶数のまま不変であり、かつ、前記グラフＧの第２最小ラプラシアン固有値が以下の関係式を満たす範囲内で可能な限り大きい前記グラフＧを構成する第２構成ステップと、を含む処理方法。
【００１９】
【数２】
【００２０】
ここで、ｋは、前記ノード次数であり、λＮ（Ｌ（Ｇ））は、上記を満たす前記グラフＧの最大ラプラシアン固有値であり、λ２（Ｌ（Ｇ））は、上記を満たす前記グラフＧの第２最小ラプラシアン固有値であり、λ２（Ｌ（Ｇ（Ｖ−１，Ｅ−ｋ／２）））は、上記を満たす前記グラフＧから、１個の前記ノードと、該ノードに接続されていた前記リンクのうちの（ｋ／２）本のリンクとが除去されたグラフの第２最小ラプラシアン固有値である。
【００２１】
また、本発明のプログラムは、コンピュータに、通信ネットワークがＶ個のノードとＥ本のリンクとで構成されるグラフＧにおいて、平方剰余（ｐ｜ｑ）＝１を満たす互いに異なる素数ｐおよび素数ｑについて、ノード数がｑ＋１であり、ノード次数がｐ＋１である連結なラマヌジャングラフを構成する第１構成手順と、前記ラマヌジャングラフから、単数または複数の前記ノードを除去した場合に前記ラマヌジャングラフが非連結にはならず、前記ノードが故障した前後で、前記ノード次数が４以上の偶数のまま不変であり、かつ、前記グラフＧの第２最小ラプラシアン固有値が以下の関係式を満たす範囲内で可能な限り大きい前記グラフＧを構成する第２構成手順と、を実行させる。
【００２２】
【数３】
【００２３】
ここで、ｋは、前記ノード次数であり、λＮ（Ｌ（Ｇ））は、上記を満たす前記グラフＧの最大ラプラシアン固有値であり、λ２（Ｌ（Ｇ））は、上記を満たす前記グラフＧの第２最小ラプラシアン固有値であり、λ２（Ｌ（Ｇ（Ｖ−１，Ｅ−ｋ／２）））は、上記を満たす前記グラフＧから、１個の前記ノードと、該ノードに接続されていた前記リンクのうちの（ｋ／２）本のリンクとが除去されたグラフの第２最小ラプラシアン固有値である。
【発明の効果】
【００２４】
本発明によれば、通信ネットワークに適したグラフを構成することが可能になる。
【図面の簡単な説明】
【００２５】
【図１】本発明の第１実施形態におけるネットワーク構成装置を示すブロック図である。
【図２】ネットワーク構成装置が構成したネットワークを示す図である。
【図３】ネットワーク構成装置の処理方法を示すフローチャートである。
【図４】第２実施形態のネットワーク構成装置が構成したネットワークを示す図である。
【図５】ネットワーク構成装置の処理方法を示すフローチャートである。
【図６】ネットワーク内のノードに故障したときのネットワークを示す図である。
【図７】ノードが故障したときに行われる通信経路の再構築の一例を示す図である。
【図８】ネットワークの再構築方法を示すフローチャートである。
【図９】高速通信が可能なプロトコルを用いて通信を行うノードの動作を説明するための図である。
【図１０】第３実施形態の通信ネットワークを示す図である。
【図１１ａ】固有値計算用のサーバの動作を説明するためのフローチャートである。
【図１１ｂ】図１１ａに示したステップＡの処理を示すフローチャートである。
【図１１ｃ】図１１ｂに示したステップＢの処理を示すフローチャートである。
【図１２】固有値計算用のサーバの構成例を示すブロック図である。
【発明を実施するための形態】
【００２６】
以下、本発明の各実施形態について図面を参照して説明する。
【００２７】
図１は、本発明の第１実施形態におけるネットワーク構成装置を示すブロック図である。
【００２８】
ネットワーク構成装置１０は、通信ネットワークを含む通信システム、または、通信ネットワークを、Ｖ個のノードとＥ本のリンクとで構築されるグラフＧを用いて構成する。ネットワーク構成装置１０は、通信ネットワークに適した３つの特性に関するグラフ条件を満たすグラフＧを構成する。
【００２９】
ここで、ネットワーク構成装置１０で構成されるグラフＧについて説明する。
【００３０】
一般のグラフの最小ラプラシアン固有値には、明確な下限の値が存在しない。一方、ｋ−正則グラフの１つであるラマヌジャングラフの第２最小ラプラシアン固有値には下限がある（非特許文献１参照）。したがって、ノードの次数がｋであるｋ−正則グラフには、明確な下限を持つ固有値が存在するため、その下限の値以上の固有値が存在することが保証されている。
【００３１】
また、ｋ−正則グラフでは、グラフ内の任意の２ノード間のマルコフ連鎖に従うランダムウォークのｆｉｒｓｔ ｐａｓｓａｇｅ ｔｉｍｅ（非特許文献１参照）が最小となるグラフを構成することが可能である。
【００３２】
非特許文献１に記載されたｆｉｒｓｔ ｐａｓｓａｇｅ ｔｉｍｅを示す式は、非特許文献３に記載されている、規格化ラプラシアン固有値とラプラシアン固有値との関係を示した定理２．２０を用いて、下式のとおり、書き直される。
【００３３】
【数１】
【００３４】
ここで、Ｍは、ネットワーク内のリンクの総数であり、０＜λｖ（Ｌ）≦２は、ネットワークのラプラシアン行列の小さい方からｖ番目（ｖは２以上の自然数）の固有値であり、ｕ＿（ｌ，ｓ）は、ネットワークの規格化ラプラシアン行列の小さい方からｌ番目の固有値（ｌは２以上の自然数）に対する大きさが１の固有ベクトルの上からｔ行目の値である。
【００３５】
また、ｋ−正則グラフの１つであるラマヌジャングラフは、拡大定数を最大化するためにグラフの自明でない固有値の絶対値を最大化し、グラフ直径を最大化する。
【００３６】
また、ｋ−正則グラフのうち、完全グラフを除いたグラフは、一般に、ノード数が増加するにつれてリンク数が線形に増加する。
【００３７】
したがって、本実施形態では、「通信ＮＷに適した３つの特性」のグラフ条件を満たすグラフＧとして、「ラマヌジャングラフ」が用いられる。
【００３８】
このため、ネットワーク構成装置１０は、平方剰余（ｐ｜ｑ）＝１を満たす互いに異なる素数ｐおよび素数ｑについて、ノード数がｑ＋１であり、ノード次数がｐ＋１である連結なラマヌジャングラフＧ１を構成する。このラマヌジャングラフＧ１のノード次数は、４以上の偶数であり、かつ、ノードの除去前後で不変である。
【００３９】
ネットワーク構成装置１０は、そのラマヌジャングラフＧ１の第２最小ラプラシアン固有値が、式（２）の不等式および等式を満たす範囲内で可能な限り大きいグラフＧを構成する。
【００４０】
【数２】
【００４１】
ここで、ｋは、ノード次数であり、λＮ（Ｌ（Ｇ））は、上記を満たすグラフＧの最大ラプラシアン固有値であり、λ２（Ｌ（Ｇ））は、上記を満たすグラフＧの第２最小ラプラシアン固有値であり、λ２（Ｌ（Ｇ（Ｖ−１，Ｅ−ｋ／２）））は、上記を満たすグラフＧから、１個のノードと、そのノードに接続されていた前記リンクのうちの（ｋ／２）本のリンクと、が除去されたグラフの第２最小ラプラシアン固有値である。１個のノードと共に、そのノードに接続されていたリンクのうちのｋ／２本のリンクを除去するのは、グラフＧのノード次数が、ノードの除去後でも変わらないようにするためである。
【００４２】
図２は、ネットワーク構成装置１０が構成するネットワークの一例を示す図である。
【００４３】
ネットワークＮＷ１には、通信ネットワークを含むシステム、または、通信ネットワークが、複数のノードＮと複数のリンクＬとで構成されたグラフＧの構造が示されている。ネットワークＮＷ１は、ネットワークＮＷ１−ａと、ネットワークＮＷ１−ｂと、ネットワークＮＷ１−ｃと、ネットワークＮＷ１−ｄとで構成されている。
【００４４】
本実施形態では、ネットワーク構成装置１０は、ネットワークＮＷ１の設計段階に用いられる。ネットワーク構成装置１０は、通信部１１と、グラフ構成部１２と、グラフ決定部１３と、を備える。
【００４５】
通信部１１は、ネットワークＮＷ１内で許容可能なノードの最大ノード数Ｎ１と、許容可能なリンクの最大リンク数Ｅ１とを受け付ける。例えば、通信部１１は、ネットワーク管理者により入力された、最大ノード数Ｎ１と最大リンク数Ｅ１とを設計情報として、外部の通信装置から受信する。通信部１１は、その最大ノード数Ｎ１と最大リンク数Ｅ１とをグラフ構成部１２に供給する。
【００４６】
グラフ構成部１２は、最大ノード数Ｎ１と最大リンク数Ｅ１とを受け付けると、最大ノード数Ｎ１および最大リンク数Ｅ１を満たし、かつ、「通信ネットワークに適した３つの特性」に関するグラフ条件を実現可能な、ネットワークＮＷ１−ａの仮のグラフＧ１を作成（構築）する。例えば、グラフ構成部１２は、ネットワークＮＷ１−ａの仮のグラフＧ１を複数作成する。
【００４７】
グラフ構成部１２は、ネットワークＮＷ１−ａのグラフが、ラマヌジャングラフＧ１となるように、素数ｐ１および素数ｑ１を用いて、式（３）を満たすノード数｜Ｖ１｜と、式（４）を満たすノード次数ｋ1とを設定する。素数ｐ１および素数ｑ１は、平方剰余（ｐ１｜ｑ１）＝１を満たす互いに異なる素数である。
【００４８】
｜Ｖ１｜＝ ｑ１ ＋ １ ≦ Ｎ１ ・・・式（３）
ｋ1 ＝ ｐ１ ＋ １ ≦ Ｅ１ ・・・式（４）
すなわち、グラフ構成部１２は、最大ノード数Ｎ１と最大リンク数Ｅ１とを受け付けると、式（３）を満たすノード数｜Ｖ１｜と、式（４）を満たすノード次数ｋ1とで構成される、ラマヌジャングラフＧ１（Ｖ１,Ｅ１）を、物理的ネットワークまたは論理ネットワークとして構成する。ここで、Ｖ１は、ラマヌジャングラフＧ１内の全てのノードを表すノード集合であり、Ｅ１は、ラマヌジャングラフＧ１内の全てのリンクを表すリンク集合である。
【００４９】
グラフ決定部１３は、グラフ構成部１２で構成されたラマヌジャングラフＧ１と、そのラマヌジャングラフＧ１から、１個のノード、および、そのノードに接続されていたリンクのうちの（ｋ1／２）本のリンクを除去したラマヌジャングラフＧ１−ｖ１と、のそれぞれの第２最小ラプラシアン固有値が不変であるラマヌジャングラフＧを取る。このラマヌジャングラフＧは、ノードの除去の前後で、ノード次数ｋ1が４以上の偶数のまま不変であり、かつ、式（２）が成り立つことになる。
【００５０】
グラフ決定部１３は、行列計算部１３１と、固有値計算部１３２と、判定部１３３と、固有値選択部１３４と、を備える。
【００５１】
行列計算部１３１は、グラフ構成部１２にて構成されたラマヌジャングラフＧ１のラプラシアン行列を計算する。行列計算部１３１は、ラマヌジャングラフＧ１のラプラシアン行列を固有値計算部１３２に供給する。
【００５２】
固有値計算部１３２は、行列計算部１３１から、ラプラシアン行列を受け付けると、そのラプラシアン行列を用いて第２最小ラプラシアン固有値を計算する。固有値計算部１４は、その第２最小ラプラシアン固有値を判定部１３３に供給する。
【００５３】
判定部１３３は、固有値計算部１３２から、第２最小ラプラシアン固有値を受け付けると、グラフ構成部１２を制御して、ラマヌジャングラフＧ１から、ノード１個、および、そのノードに接続されているリンクのうちの（ｋ1／２）本のリンクを除去する。具体的には判定部１３３は、グラフ構成部１２で作成されたラマヌジャングラフＧ１から、１個のノードと、そのノードに接続されているリンクのうち（ｋ1／２）本のリンクを除去する旨を指示する除去指示信号をグラフ構成部１２に供給する。行列計算部１３１は、グラフ構成部１２でノードおよびリンクが除去されると、その除去された後のラマヌジャングラフＧ１−ｖ１のラプラシアン行列を計算する。そして固有値計算部１３２は、ラマヌジャングラフＧ１−ｖ１のラプラシアン行列の最小ラプラシアン固有値を計算して判定部１３３に供給する。
【００５４】
判定部１３３は、除去後のラマヌジャングラフＧ１−ｖ１と、元のラマヌジャングラフＧ１と、が式（２）を満たすか否かを判定する。すなわち、判定部１３３は、除去後のラマヌジャングラフＧ１−ｖ１の第２最小ラプラシアン固有値が、元のラマヌジャングラフＧ１の第２最小ラプラシアン固有値と同一であるか否かを判定する。
【００５５】
判定部１３３は、除去後のラマヌジャングラフＧ１−ｖ１と、元のラマヌジャングラフＧ１と、が式（２）を満たす場合、すなわち、ノードの除去の前後のそれぞれの第２最小ラプラシアン固有値が同一である場合には、その第２最小ラプラシアン固有値を、固有値選択部１３４に供給する。
【００５６】
例えば、判定部１３３は、ラマヌジャングラフＧ１内のノードを１個から所定の個数まで１個ずつ除去する。そして判定部１３３は、ラマヌジャングラフＧ１内のノードを１個ずつ除去するたびに、その除去後のラマヌジャングラフＧ１−ｖ１と、元のラマヌジャンクグラフＧ１と、が式（２）を満たすか否かを判定する。判定部１３３は、ラマヌジャングラフＧ１内のノードを１個から所定の個数まで１個ずつ除去した後、全ての判定で式（２）を満たした場合には、第２最小ラプラシアン固有値を固有値選択部１３４に供給する。
【００５７】
固有値選択部１３４は、判定部１３３から、式（２）を満たす範囲内での第２最小ラプラシアン固有値を受け付けると、第２最小ラプラシアン固有値の中から、最大の第２最小ラプラシアン固有値を選択する。または、固有値選択部１６は、第２最小ラプラシアン固有値の中から、可能な限り大きな値の第２最小ラプラシアン固有値を選択する。
【００５８】
また、固有値選択部１３４は、例えば、判定部１３３から第２最小ラプラシアン固有値を受け付け、その第２最小ラプラシアン固有値が、所定の固有値閾値よりも小さい場合には、グラフ構成部１２に新たなグラフの構築を指示してもよい。
【００５９】
固有値選択部１３４は、その選択した第２最小ラプラシアン固有値を用いて、ネットワークＮＷ１-ａのグラフＧ内のノード数と、リンク数と、ノードとリンクとの接続関係と、を含むグラフ構成情報を、通信部１１に供給する。通信部１１は、固有値選択部１３４からグラフ構成情報を受け付けると、そのグラフ構成情報を外部の装置に送信する。
【００６０】
図３は、ネットワーク構成装置１０の処理方法を示すフローチャートである。
【００６１】
まず、通信部１１は、例えばネットワーク管理者により入力された設計情報として、最大ノード数Ｎ１と最大リンク数Ｅ１とを受け付ける（ステップＳ１−１）。通信部１１は、その最大ノード数Ｎ１と最大リンク数Ｅ１とをグラフ構成部１２に供給する。
【００６２】
グラフ構成部１２は、最大ノード数Ｎ１と最大リンク数Ｅ１とを受け付けると、最大ノード数Ｎ１および最大リンク数Ｅ１を満たし、かつ、通信ネットワークに適した３つの特性に関するグラフ条件を実現可能な、ネットワークＮＷ１−ａのグラフを構築する（ステップＳ１−２）。
【００６３】
グラフ構成部１２は、ネットワークＮＷ１−ａのグラフが、式３を満たすノード数｜Ｖ１｜であり、かつ、式４を満たすノード次数ｋ1であるラマヌジャングラフＧ１（Ｖ１，Ｅ１）を構成する（ステップＳ１−３）。
【００６４】
グラフ決定部１３は、グラフ構成部１２で構成されたラマヌジャングラフＧ１と、そのラマヌジャングラフＧ１から、１個のノード、および、そのノードに接続されていたリンクのうちの（ｋ1／２）本のリンクを除去する（ステップＳ１−４）。
【００６５】
グラフ決定部１３は、その１個のノードおよび（ｋ1／２）本のリンクが除去されたラマヌジャングラフＧ１−ｖ１と元のラマヌジャングラフＧ１で、ノード次数ｋ1が４以上の偶数のまま不変であり、かつ、式（２）が成り立つことを確認する（ステップＳ１−５）。そしてノード次数ｋ1が４以上の偶数ではない場合、または、式（２）が成り立たない場合にはグラフ決定部１３は、ステップＳ１−２に戻る。
【００６６】
一方、グラフ決定部１３は、ノード次数ｋ1が４以上の偶数のまま不変であり、かつ、式（２）が成り立つ場合にはラマヌジャングラフＧ１から除去されたノードの数が所定数未満であるか否かを判断する（ステップＳ１−６）。そしてグラフ決定部１３は、除去されたノードの数が所定数未満である場合には、ステップＳ１−４に戻り、除去されたノードの数が所定数となるまで繰り返しステップＳ１−４および１−５の処理を行う。
【００６７】
グラフ決定部１３は、ラマヌジャングラフＧ１の式（２）を満たす範囲内で可能な限り大きな値の第２最小ラプラシア固有値を選択して（ステップＳ１−７）、ネットワーク構成装置１０の処理方法を終了する。
【００６８】
なお、ネットワークＮＷ１−ａだけでは、最大ノード数Ｎ１および最大リンク数Ｅ１の条件を満たさない場合には、ネットワーク構成装置１０は、図３で示した処理方法でネットワークＮＷ１−ｂ乃至ＮＷ１−ｃを構成し、これらを連結してもよい。
【００６９】
本実施形態によれば、ネットワーク構成装置１０は、通信ネットワークをＶ個のノードとＥ本のリンクとで構築されるグラフＧを構成する。ネットワーク構成装置１０は、平方剰余（ｐ｜ｑ）＝１を満たす互いに異なる素数ｐおよび素数ｑについて、ノード数がｑ＋１であり、かつ、ノード次数がｐ＋１である連結なラマヌジャングラフＧ１を構成し、ラマヌジャングラフＧ１から、単数または複数のノードを除去した場合にラマヌジャングラフＧ１−ｖ１が非連結にはならず、ノードが故障した前後で、ノード次数が４以上の偶数のまま不変であり、かつ、グラフＧの第２最小ラプラシアン固有値が、式（２）の関係式を満たす範囲内で可能な限り大きいグラフＧを構成する。
【００７０】
このため、ネットワーク構成装置１０は、通信ネットワークに適した３つの特性に関する１）から３）のグラフ条件を満たすグラフＧを作成することが可能となる。グラフＧは、連結なラマヌジャングラフに含まれてもよく、連結な２部グラフでないラマヌジャングラフに含まれてもよい。
【００７１】
次に、本発明の第２実施形態について説明する。第２実施形態では、既存のネットワークが存在する状況で、そのネットワーク上にネットワーク構成装置がグラフＧを構成する。なお、第２実施形態のネットワーク構成装置は、図１に示した構成と同様のものである。
【００７２】
図４は、第２実施形態のネットワーク構成装置１０が構成したネットワークを示す図である。
【００７３】
既存のネットワークＮＷ２には、図２と同様、通信ネットワークを含むシステム、または、通信ネットワークが、複数のノードＮと複数のリンクＬとで構成されたグラフＧの構造が示されている。ネットワークＮＷ２は、ネットワークＮＷ２−ａと、ネットワークＮＷ２−ｂと、ネットワークＮＷ２−ｃと、ネットワークＮＷ２−ｄと、で構成される。
【００７４】
図５は、第２実施形態の処理方法を示すフローチャートである。
【００７５】
まず、通信部１１は、設計情報として、ネットワークＮＷ２を指定する旨の指定情報と、ＮＷ２−ａ内の最大ノード数Ｎ２と、最大リンク数Ｅ２と、を受け付ける（ステップＳ２−１）。通信部１１は、その最大ノード数Ｎ１と最大リンク数Ｅ１とをグラフ構成部１２に供給する。
【００７６】
グラフ構成部１２は、最大ノード数Ｎ１と最大リンク数Ｅ１とを受け付けると、最大ノード数Ｎ１および最大リンク数Ｅ１を満たし、かつ、通信ネットワークに適した３つの特性に関するグラフ条件を実現可能な、ネットワークＮＷ２−ａのグラフを構築する（ステップＳ２−２）。
【００７７】
グラフ構成部１２は、ネットワークＮＷ２−ａのグラフが、式（５）を満たすノード数｜Ｖ２｜であり、式（６）を満たすノード次数ｋ2である連結なラマヌジャングラフＧ１（Ｖ２，Ｅ２）を構成する（ステップＳ２−３）。
【００７８】
｜Ｖ２｜＝ ｑ２ ＋ １ ≦ Ｎ２ ・・・式（５）
ｋ2 ＝ ｐ２ ＋ １ ≦ Ｅ２ ・・・式（６）
なお、ｑ２およびｐ２は、平方剰余（ｐ２｜ｑ２）＝１を満たす互いに異なる素数である。
【００７９】
グラフ決定部１３は、グラフ構成部１２で構成されたラマヌジャングラフＧ２と、そのラマヌジャングラフＧ１から、１個のノード、および、そのノードに接続されていたリンクのうちの（ｋ2／２）本のリンクを除去する（ステップＳ２−４）。
【００８０】
グラフ決定部１３は、１個のノードおよび（ｋ2／２）本のリンクが除去されたラマヌジャングラフＧ２−ｖ２と元のラマヌジャングラフＧ２とで、ノード次数ｋ2が４以上の偶数のまま不変であり、かつ、式（２）が成り立つことを確認する（ステップＳ２−５）。そしてノード次数ｋ2が４以上の偶数ではない場合、または、式（２）が成り立たない場合にはグラフ決定部１３は、ステップＳ２−２に戻る。
【００８１】
一方、グラフ決定部１３は、ノード次数ｋ2が４以上の偶数のまま不変であり、かつ、式（２）が成り立つ場合にはラマヌジャングラフＧ２から除去されたノードの数が所定数未満であるか否かを確認する（ステップＳ２−６）。そしてグラフ決定部１３は、除去されたノードの数が所定数未満である場合には、ステップＳ２−４に戻り、除去されたノードの数が所定数となるまで繰り返しステップＳ２−４およびＳ２−５の処理を行う。
【００８２】
グラフ決定部１３は、ラマヌジャングラフＧ２の式（２）を満たす範囲内で可能な限り大きな値の第２最小ラプラシア固有値を選択して（ステップＳ２−７）、ネットワーク構成装置１０の処理方法を終了する。
【００８３】
なお、ネットワークＮＷ２−ａのみでは、最大ノード数Ｎ２および最大リンク数Ｅ２の条件を満足しない場合には、ネットワーク構成装置１０は、新たにネットワークＮＷ２−ｂ乃至ＮＷ２−ｄを構成し、これらを連結してもよい。
【００８４】
次にネットワークＮＷ１またはＮＷ２が構成されている状態で、ネットワークＮＷ１またはＮＷ２内のノードが故障した場合に、その故障したノード以外のノードを経由する通信経路のうち、最短の通信経路を再構築するための手法について説明する。
【００８５】
図６は、ネットワーク構成装置１０が構成したネットワークＮＷ３を示す図である。
【００８６】
ネットワークＮＷ３は、ネットワークＮＷ３−ａと、ネットワークＮＷ３−ｂと、ネットワークＮＷ３−ｃと、ネットワークＮＷ３−ｄと、で構成されている。ここでは、ネットワークＮＷ３−ａでノードａが故障した場合を想定している。
【００８７】
図７は、ネットワークＮＷ３−ａで、ノードａが故障した場合に行われる通信経路の再構築の一例を示す図である。図７には、ネットワークＮＷ３−ａ（Ｖ３，Ｅ３）と、ノードａが故障してノードａが除去されたネットワークＮＷ３−ａ−ａ（Ｖ３−ａ，Ｅ３−ｋ3／２）とが示されている。
【００８８】
ネットワークＮＷ３−ａは、ノードａと直接接続されていない部分グラフＳと、ノードａと直接接続されている部分グラフＵとで構成されている。ネットワークＮＷ３−ａ−ａ内の部分グラフＵ’は、ノードａに接続されていたｋ3本のリンクのうちのｋ3／２本のリンクの接続先が、ノードａから別のノードに切り替えられた後の部分グラフである。
【００８９】
図８は、図７に示したネットワークＮＷ３−ａの再構築方法を示すフローチャートである。
【００９０】
まず、ネットワークＮＷ−３ａでノードａに故障が発生した場合（ステップＳ３−０）に、ノードａに隣接している全てのノードは、ノードａの故障情報をノードａ以外のノードに送信して故障情報をＮＷ３−ａ内の全てのノードに伝達する（ステップＳ３−１）。ネットワークＮＷ−３ａは、通信ネットワークに適した３つの特性を有しているため、任意の２ノード間の通信時間が短く、任意の２ノード間に複数の経路がある。このため、本実施形態のネットワークＮＷ３−ａでは、故障情報が、全てのノードに短い時間で到達されることになる。
【００９１】
なお、故障情報には、ノードａの識別情報と、ノードａに故障が発生した時刻と、ノードａの識別情報とが含まれる。故障情報は、一般的な経路制御プロトコルよりも高速通信が可能な通信プロトコルＰ２を用いてＮＷ３−ａ内の各経路に分散される。通信プロトコルとしては、例えば、フラッディングアルゴリズムに基づいて経路制御を行うプロトコルが用いられる。
【００９２】
ＮＷ３−ａ内の全てのノードに故障情報が伝達されると、ノードａが除去されてリンクの張り替えが行われる。このとき、ＮＷ３−ａの第２最小ラプラシアン固有値が、元のＮＷ３−ａ（Ｖ３，Ｅ３）と同じ値のＮＷ３−ａ−ａ（Ｖ３−ａ，Ｅ３−ｋ3／２）を再構築することが可能である。短時間で通信経路を変更する場合には、通信経路上のノードのうち、ノードａに接続されていた２ノード間を接続すればよい。
【００９３】
図９は、通信プロトコルＰ２を用いて通信を行う各ノードの動作を説明するためのフローチャートである。
【００９４】
まず、通信プロトコルを用いてリンクの張り替えが行われるネットワークＮＷａ−３では、全てのノードを根とする最短スパニング木が構成される（ステップＳ３−３）。
【００９５】
ネットワークＮＷ３−ａ内の各ノードは、ノードａの故障を検出した場合に、フラッディングアルゴリズムに従って、自身のノードを根とする最短スパニング木上の隣接ノードに、故障情報を伝達する（ステップＳ３−４）。
【００９６】
ネットワークＮＷ３−ａ内の各ノードは、故障情報を受信する（ステップＳ３−４−２）と、故障情報が１つの場合には、自身のノードを根とする最短スパニング木上の全ての隣接ノードに伝達する（ステップＳ３−４−３）。ネットワークＮＷ３−ａでは、全てのノードに伝達されるまで故障情報の送信が行われる。
【００９７】
ネットワークＮＷ３−ａ内の各ノードは、複数の故障情報を受信したとき（ステップＳ３−５）に、複数の故障情報に含まれている識別情報または発生時刻が互いに異なる場合（ステップＳ３−６）には、複数の故障情報のそれぞれを、自身のノードを根とする最短スパニング木上の隣接ノードに伝達する（ステップＳ３−６−１）。
【００９８】
一方、ネットワークＮＷ３−ａ内の各ノードは、複数の故障情報を受信したとき（ステップＳ３−５）に、複数の故障情報が同じ場合（ステップＳ３−６）には、複数の故障情報の中からいずれか１つを選択し、その故障情報を、自身のノードを根とする最短スパニング木上の隣接ノードに伝達する（ステップＳ３−６−２）。
【００９９】
次に本発明の第３実施形態として、既存の通信ネットワーク内の各ノードが自律的に通信経路を切り替えることで、通信ＮＷに適したネットワークＮＷ１またはＮＷ２を構成する手法について説明する。
【０１００】
図１０は、第３実施形態のネットワークＮＷ４を示す図である。ネットワークＮＷ４は、
既存の通信ネットワーク内の各ノードが自律的に通信経路を制御する自律機能を有する。
【０１０１】
ネットワークＮＷ４は、多数のノードＮおよび多数のリンクＬに加えて、通信ノードＣＮ、および、固有値計算用のサーバＣＳを備える。ネットワークＮＷ４は、ネットワークＮＷ４−ａと、ネットワークＮＷ４−ｂと、ネットワークＮＷ４−ｃと、ネットワークＮＷ４−ｄと、で構成される。
【０１０２】
図１１ａは、固有値計算用のサーバＣＳの動作を説明するためのフローチャートである。
【０１０３】
ネットワークＮＷ４−ａは、ノードに故障が発生した場合に、図８で述べた通信プロトコルＰ２を用いて故障情報を、ネットワークＮＷ４−ａ内の各ノードに伝達する機能を有する。ネットワークＮＷ４内のノードに接続されるサーバＣＳは、自律分散的な手法を用いてノードの接続先が決定される。自律分散的な手法としては、例えば、ＲＦＣ ２３２８ − ＯＳＰＦ Ｖｅｒｓｉｏｎ ２に記載のＤｅｓｉｇｎａｔｅｄ Ｒｏｕｔｅｒ選別方法が挙げられる。
【０１０４】
サーバＣＳは、ネットワーク管理者により入力された設定情報として、ノードが故障した時点から、ネットワークＮＷ４の制御を開始するまでの最大期間Ｔｍａｘを受け付ける。最大期間Ｔｍａｘは、故障情報を伝播させる時間の最大値である。
【０１０５】
サーバＣＳは、最大期間Ｔｍａｘを受け付けると、その最大期間Ｔｍａｘを、２ノード間で通信プロトコルＰ２を用いて通信するのに必要な所要時間ＴＰ２で除算し、最大期間Ｔｍａｘを所要時間ＴＰ２で除算した値を超えない最大の自然数Ｎｍａｘを算出する（ステップＳ４−２−３）。Ｎｍａｘは、通信プロトコルＰ２を使用して、ノード間の物理リンクを通じて故障情報を伝達できるノードの最大数を示す。
【０１０６】
サーバＣＳは、ネットワークＮＷ４内のノードの中から適当な通信ノードＮ０を選択し、その通信ノードＮ０から、物理リンクを辿って到達可能なＮｍａｘ番目のノードまでの全てのノードを集める（ステップＳ４−２−４）。ここでは、通信ノードＮ０からＮｍａｘ番目までの全てのノードの数をｎ個とする。
【０１０７】
サーバＣＳは、その特定されたｎ個のノードで構成される部分ネットワークを、故障情報を伝播させる仮のネットワーク範囲（以下「ＮＷ４−ａ」と称する。）に決定する（ステップＳ４−２−５）。
【０１０８】
サーバＣＳは、ＮＷ４−ａの隣接行列Ａ（ＮＷ４−ａ）とラプラシアン行列Ｌ（ＮＷ４−ａ）とを生成する（ステップＳ４−３）。隣接行列Ａおよびラプラシアン行列Ｌは、ＮＷ４−ａのノードの総数がｎであるため、ｎ行ｎ列の行列となる。
【０１０９】
サーバＣＳは、隣接行列Ａ（ＮＷ４−ａ）の最大固有値λＮと、ラプラシアン行列Ｌ（ＮＷ４−ａ）の第２最小ラプラシアン固有値λ２とを求める（ステップＳ４−４−１）。また、サーバＣＳは、ｖ＝２としたときの式（１）の算出結果である初到達時刻π（ＮＷ４−ａ）と、Ｎｍａｘとを比較し、式（７）を満たしている場合にはステップＡの処理に進む。式（７）満たしていない場合にはノード数を増加させる（ステップＳ４−４−４）。
【０１１０】
π（ＮＷ４−ａ） ＜ Ｎｍａｘ ・・・式（７）
図１１ｂは、図１１ａで示したステップＡの処理を示すフローチャートである。
【０１１１】
ステップＡの処理では、サーバＣＳは、式（８）を満たすノード数｜Ｖ４｜であり、式（９）を満たすノード次数ｋ4であるような連結なラマヌジャングラフＧ４を、物理的ＮＷまたは論理的ＮＷとして構成する（ステップＳ４−５−１）。ここで、Ｖ４は、ラマヌジャングラフＧ４のノード集合であり、Ｅ４は、ラマヌジャングラフＧ４のリンク集合である。
【０１１２】
｜Ｖ４｜＝ ｑ４ ＋ １ ≦ Ｎ４ ・・・式（８）
ｋ4 ＝ ｐ４ ＋ １ ≦ Ｅ４ ・・・式（９）
なお、素数ｐ４および素数ｑ４は、平方剰余（ｐ４｜ｑ４）＝１を満たす互いに異なる素数である。
【０１１３】
サーバＣＳは、ラマヌジャングラフＧ４と、そのラマヌジャングラフＧ４から、１個のノード、および、そのノードに接続されていたリンクのうちの（ｋ4／２）本のリンクを除去する（ステップＳ４−５−２）。
【０１１４】
サーバＣＳは、その１個のノードおよび（ｋ4／２）本のリンクが除去されたラマヌジャングラフＧ４−ｖ４と元のラマヌジャングラフＧ４とで、ノード次数ｋ4が４以上の偶数のまま不変であり、かつ、式（２）が成り立つことを確認する（ステップＳ４−５−３）。そしてノード次数ｋ2が４以上の偶数ではない場合、または、式（２）が成り立たない場合にはグラフ決定部１３は、ステップＳ４−５−１に戻る。
【０１１５】
サーバＣＳは、ノード次数ｋ2が４以上の偶数のまま不変であり、かつ、式（２）が成り立つ場合には、ラマヌジャングラフＧ２から除去されたノードの数が所定数未満であるか否かを確認する（ステップＳ４−６）。そしてサーバＣＳは、除去されたノードの数が所定数未満である場合には、ステップＳ４−５−２に戻り、除去されたノードの数が所定数となるまで繰り返しステップＳ４−５−２およびＳ４−５−３の処理を行う。
【０１１６】
サーバＣＳは、ラマヌジャングラフＧ４の式（２）を満たす範囲内で可能な限り大きな値の第２最小ラプラシア固有値を選択して（ステップＳ４−７）、ステップＢの処理に進む。
【０１１７】
図１１ｃは、図１１ｂで示したステップＢの処理を示すフローチャートである。
【０１１８】
ステップＢの処理では、サーバＣＳは、焼きなまし法（Ｓｉｍｕｌａｔｅｄ ａｎｎｅａｌｉｎｇ）という最適化アルゴリズムを用いて、ステップＳ４−５−１、Ｓ４−５−２、４−５−３、Ｓ４−６およびＳ４−７の一連の処理を繰り返し実行して、ＮＷ４−ａのグラフＧを構成する（ステップＳ４−８）。
【０１１９】
そしてサーバＣＳは、ステップＳ４−２−５で決定されたＮＷ４−ａに属する全てのノードに対し、通信ノードＣＮを介して、通信プロトコルＰ２を用いてＮＷ４−ａの構成情報を伝達する（ステップＳ４−９）。
【０１２０】
また、ネットワークＮＷ４からＮＷ４−ａを除いたネットワークについても、ステップＳ４−２−３からＳ４−９までの一連の処理手順を実行してＮＷ４−ｂ乃至４−ｄを構成し、サーバＣＳの処理方法が終了する。このため、ネットワークＮＷ４は、ＮＷ４−ａ乃至４−ｄによって分割された構成となる。
【０１２１】
図１２は、通信ノードＣＮおよびサーバＣＳの構成の一例を示すブロック図である。
【０１２２】
通信ノードＣＮは、ＮＷ４内のノードおよびリンクに関する構成情報を受信し、そのＮＷ４の構成情報のうち、ＮＷ４−＊（例えば、ＮＷ４−ａ）に関する構成情報をサーバＣＳに送信する。
【０１２３】
サーバＣＳは、通信部２１と、ラプラシアン行列計算部２２と、固有値λ２計算部２３と、隣接行列計算部２４と、固有値λＮ計算部２５と、初到達時刻π算出部２６と、比較部２７と、ＮＷ構成部２８と、を備える。なお、サーバＣＳは、一般的にネットワーク構成装置と呼ぶことができる。
【０１２４】
通信部２１は、通信ノードＣＮから、例えば、ＮＷ４−ａの構成情報を受信する。通信部２１は、そのＮＷ４−ａの構成情報を、ラプラシアン行列計算部２２と隣接行列計算部２４とに供給する。
【０１２５】
ラプラシアン行列計算部２２は、ＮＷ４−ａの構成情報を用いてラプラシアン行列Ｌを計算し、そのラプラシアン行列Ｌを、固有値λ２計算部２３に供給する。
【０１２６】
固有値λ２計算部２３は、ＮＷ４−ａのラプラシアン行列Ｌを受け付けると、そのラプラシアン行列の第２最小ラプラシアン固有値λ２を算出する。
【０１２７】
隣接行列計算部２４は、通信部２１から、ＮＷ４−ａの構成情報を受け付けると、そのＮＷ４−ａの隣接行列を計算し、その隣接行列を固有値λＮ計算部２５に供給する。
【０１２８】
固有値λＮ計算部２５は、ＮＷ４−ａの隣接行列を受け付けると、その隣接行列の最大ラプラシアン固有値λＮを計算し、その最大ラプラシアン固有値λＮを初到達時刻π算出部２６に供給する。
【０１２９】
初到達時刻π算出部２６は、ＮＷ４−ａの最大ラプラシアン固有値λＮを受け付けると、式（１）においてｖ＝２としたときの初到達時刻πを算出し、その初到達時刻πを比較部２７に供給する。
【０１３０】
比較部２７は、初到達時刻πを受け付けると、初到達時刻πが式（７）を満たしていることを確認する。比較部２７は、初到達時刻πが式（７）を満たしている場合には、ＮＷ４−ａの構成情報をＮＷ構成部２８に供給する。
【０１３１】
ＮＷ構成部２８は、ＮＷ４−ａの構成情報にて特定されるグラフを、ラマヌジャングラフＧ４となるように構成する。具体的にはＮＷ構成部２８は、式（８）を満たすノード数｜Ｖ４｜であり、式（４）を満たすノード次数ｋ4あるラマヌジャングラフＧ４（Ｖ４,Ｅ４）を、物理的ネットワークまたは論理ネットワークとして構成する。
【０１３２】
ＮＷ構成部２８は、ラマヌジャングラフＧ４と、そのラマヌジャングラフＧ４から、１個のノード、および、そのノードに接続されていたリンクのうちの（ｋ1／２）本のリンクを除去したラマヌジャングラフＧ４−ｖ４とで、第２最小ラプラシアン固有値が不変であるラマヌジャングラフＧを取る。このラマヌジャングラフＧは、ノードの故障の前後で、ノード次数ｋ4が４以上の偶数のまま不変であり、かつ、式（２）が成り立つことになる。ＮＷ構成部２８は、ＮＷ４−ａのラマヌジャングラフＧを示すＮＷ構成情報を生成し、そのＮＷ４−ａのＮＷ構成情報を通信部２１に供給する。
【０１３３】
通信部２１は、ＮＷ構成部２８からＮＷ４−ａのＮＷ構成情報を受け付けると、通信ノードＣＮを介して、ＮＷ４−ａのノードに対し、通信プロトコルＰ２を用いてＮＷ４−ａのＮＷ構成情報を伝達する。このため、ＮＷ４−ａのノードは、ＮＷ４−ａ内の通信経路を自律的に切り替えることが可能となる。
【０１３４】
第３実施形態によれば、ＮＷ４−ａのラマヌジャングラフＧ４は、通信ネットワークの通信経路を自律的に制御する単数または複数のノードで構成される。このため、通信ノードＣＮおよびサーバＣＳは、１）から３）のグラフ条件を満足する通信ネットワークＮＷ４−ａを構成することが可能となる。
【０１３５】
以上説明した各実施形態において、図示した構成は単なる一例であって、本発明はその構成に限定されるものではない。
【符号の説明】
【０１３６】
１０ ネットワーク構成装置
１１ 通信部
１２ グラフ構成部
１３ グラフ決定部
１３１ 行列計算部
１３２ 固有値計算部
１３３ 判定部
１３４ 固有値選択部
【技術分野】
【０００１】
本発明は、ネットワーク構成装置、処理方法およびプログラムに関し、特には、グラフ理論を用いて通信ネットワークおよびシステムを構成するネットワーク構成装置、処理方法およびプログラムに関する。
【背景技術】
【０００２】
ネットワークを含むシステムおよびネットワーク（以下、「ＮＷ」と記す。）のグラフ構造（以下、単に、「グラフ」とも言う）を構成するノードの通信端末は故障することがある。この場合、ノードの故障後に構成されるＮＷのグラフ構造では、元のＮＷのグラフ構造が有していた「通信ＮＷに適した３つの特性」が維持されることが、通信ＮＷの堅牢性を保つ上で重要である。
【０００３】
通信ＮＷに適した３つの特性とは、１）任意の２ノード間の通信時間が短いこと、２）任意の２ノード間に複数の経路があること、３）スケーラビリティーが高いこと、を意味する。これら３つの条件は、「通信ＮＷに適した特性」の十分条件ではないが、必要条件のうち特に重要な条件である。
【０００４】
上記の３つの条件について、それぞれに対応するグラフ上の条件（以下、「グラフ条件」と称する）が存在する（例えば、非特許文献１〜３参照）。
【０００５】
１）のグラフ条件は、非特許文献１に示されているとおり、グラフ上でのランダムウォークにおけるｆｉｒｓｔ ｐａｓｓａｇｅ ｔｉｍｅが短いグラフであること、および、非特許文献２に示されているとおり、グラフ直径が小さいこと、である。なお、ｆｉｒｓｔ ｐａｓｓａｇｅ ｔｉｍｅは、グラフの第２最小ラプラシアン固有値が大きいほど、短くなることが知られている（非特許文献１および３参照）。
【０００６】
２）のグラフ条件は、グラフが連結であり、かつ、非特許文献２に示されているとおり、拡大定数が大きいこと、である。
【０００７】
３）のグラフ条件は、グラフ構造を構成するリンクの数が、ノード数（ＮＷサイズ）の増加に伴い、線形に増加する、または、線形に増加する数以下で増加すること、である。なお、完全グラフは、１）および２）のグラフ条件を満たしているが、ノード数の増加に伴いリンク数が概ねノード数の２乗に比例して増加するため、３）のグラフ条件を満たしていない。
【０００８】
非特許文献２では、「通信ＮＷに適した３つの特性」を満たすグラフが、ラマヌジャングラフであることも記載されている。しかしながら、非特許文献２には、ノードが故障したときに再帰的にラマヌジャングラフを構成可能であるラマヌジャングラフの構造および条件については記載されていない。
【０００９】
また、非特許文献１および非特許文献４〜６には、Ｅｎｔａｎｇｌｅｄ ＮＷが、記載されている。これは、第２最小ラプラシアン固有値λ２と、最大ラプラシアン固有値λＮとの比（λＮ／λ２）を最小化するようなグラフである。このグラフは、１）のグラフ条件しか満たしていない。
【００１０】
なお、非特許文献７〜９では、Ｂｉｍｏｄａｌ ＮＷが、記載されており、このグラフでは、ノードまたはリンクを、ランダムまたは選択的に除去した場合でも、元のグラフの連結性が維持されることが定量的に示されている。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】Ｌｕｃａ Ｄｏｎｅｔｔｉ， Ｆｒａｎｃｏ Ｎｅｒｉ ａｎｄ Ｍｉｇｕｅｌ Ａ Ｍｕnｏｚ．“Ｏｐｔｉｍａｌ ｎｅｔｗｏｒｋ ｔｏｐｏｌｏｇｉｅｓ：ｅｘｐａｎｄｅｒｓ， ｃａｇｅｓ， Ｒａｍａｎｕｊａｎ ｇｒａｐｈｓ， ｅｎｔａｎｇｌｅｄ ｎｅｔｗｏｒｋｓ ａｎｄ ａｌｌ ｔｈａｔ，” Ｊｏｕｒｎａｌ ｏｆ Ｓｔａｔｉｓｔｉｃａｌ Ｍｅｃｈａｎｉｃｓ： Ｔｈｅｏｒｙ ａｎｄ Ｅｘｐｅｒｉｍｅｎｔ，Ｖｏｌｕｍｅ ２００６， Ａｕｇｕｓｔ ２００６．
【非特許文献２】平松豊一・知念宏司 共著．“有限数学入門 有限上半平面とラマヌジャングラフ”牧野出版（２００３年８月初版），ＩＳＢＮ４−４３４−０３４０７−３ Ｃ３０４１．
【非特許文献３】Ｐ Ｚｕｍｓｔｅｉｎ． “Ｃｏｍｐａｒｉｓｏｎ ｏｆ Ｓｐｅｃｔｒａｌ Ｍｅｔｈｏｄｓ Ｔｈｒｏｕｇｈ ｔｈｅ Ａｄｊａｃｅｎｃｙ Ｍａｔｒｉｘ ａｎｄ ｔｈｅ Ｌａｐｌａｃｉａｎ ｏｆ ａ Ｇｒａｐｈ，” ｓｕｂｍｉｔｔｅｄ ２８． Ｆｅｂｒｕａｒｙ ２００５ ａｔ ＥＴＨ Ｚｕｒｉｃｈ， ２００５．
【非特許文献４】Ｌ． Ｄｏｎｅｔｔｉ， Ｐ．Ｉ． Ｈｕｒｔａｄｏ， ａｎｄ Ｍ．Ａ． Ｍｕnｏｚ． “Ｅｎｔａｎｇｌｅｄ Ｎｅｔｗｏｒｋｓ， Ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ， ａｎｄ Ｏｐｔｉｍａｌ Ｎｅｔｗｏｒｋ Ｔｏｐｏｌｏｇｙ，” Ｐｈｙｓ． Ｒｅｖ． Ｌｅｔｔ． ９５， １８８７０１， ２００５．
【非特許文献５】Ｌ． Ｄｏｎｅｔｔｉ， Ｐ．Ｉ． Ｈｕｒｔａｄｏ， ａｎｄ Ｍ．Ａ． Ｍｕnｏｚ． “Ｅｎｔａｎｇｌｅｄ ｎｅｔｗｏｒｋｓ， ｓｕｐｅｒ−ｈｏｍｏｇｅｎｅｉｔｙ ａｎｄ ｏｐｔｉｍａｌ ｎｅｔｗｏｒｋ ｔｏｐｏｌｏｇｙ，” Ａｒｘｉｖ ｐｒｅｐｒｉｎｔ ｃｏｎｄ−ｍａｔ／０５０２２３０， ２００５．
【非特許文献６】Ｌ． Ｄｏｎｅｔｔｉ， Ｐ．Ｉ． Ｈｕｒｔａｄｏ， ａｎｄ Ｍ．Ａ． Ｍｕnｏｚ． “Ｎｅｔｗｏｒｋ ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ： ｏｐｔｉｍａｌ ａｎｄ ｐｅｓｓｉｍａｌ ｓｃａｌｅ−ｆｒｅｅ ｔｏｐｏｌｏｇｉｅｓ，” Ｊｏｕｒｎａｌ ｏｆ Ｐｈｙｓｉｃｓ Ａ： Ｍａｔｈｅｍａｔｉｃａｌ ａｎｄ Ｔｈｅｏｒｅｔｉｃａｌ， Ｖｏｌ． ４１， Ｎｏ． ２２， ２００８．
【非特許文献７】Ｇ． Ｐａｕｌ， Ｔ． Ｔａｎｉｚａｗａ， Ｓ． Ｈａｖｌｉｎ， ａｎｄ Ｈ． Ｅ． Ｓｔａｎｌｅｙ． “Ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ Ｒｏｂｕｓｔｎｅｓｓ ｏｆ Ｃｏｍｐｌｅｘ Ｎｅｔｗｏｒｋｓ，” ［Ｐｒｏｃ． ２００３ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｇｒｏｗｉｎｇ Ｎｅｔｗｏｒｋｓ ａｎｄ Ｇｒａｐｈｓ］， Ｅｕｒｏ． Ｐｈｙｓ． Ｊ． Ｂ ３８ ，ｐｐ―１８７−１９１， ２００４．
【非特許文献８】Ｔ Ｔａｎｉｚａｗａ， Ｇ Ｐａｕｌ ａｎｄ Ｒ Ｃｏｈｅｎ ｅｔ ａｌ． “Ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ｎｅｔｗｏｒｋ ｒｏｂｕｓｔｎｅｓｓ ｔｏ ｗａｖｅｓ ｏｆ ｔａｒｇｅｔｅｄ ａｎｄ ｒａｎｄｏｍ ａｔｔａｃｋｓ，” Ｐｈｙｓ． Ｒｅｖ． Ｅ． Ｖｏｌ．７１，Ｎｏ． ４，２００５．
【非特許文献９】Ｔ． Ｔａｎｉｚａｗａ，Ｇ．Ｐａｕｌ，Ｓ．Ｈａｖｌｉｎ，ａｎｄ Ｈ． Ｅ．Ｓｔａｎｌｅｙ． “Ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ｔｈｅ ｒｏｂｕｓｔｎｅｓｓ ｏｆ ｍｕｌｔｉｍｏｄａｌ ｎｅｔｗｏｒｋｓ，”Ｐｈｙｓ．Ｒｅｖ．Ｅ，Ｖｏｌ．７４，Ｎｏ．１，２００６．
【発明の概要】
【発明が解決しようとする課題】
【００１２】
ノードの故障後に構成される通信ＮＷのグラフでは、元のグラフが有していた「通信ＮＷに適した３つの特性」を維持することが、通信ＮＷの堅牢性を保つ上で重要である。
【００１３】
しかしながら、非特許文献１〜９では、上記のグラフの構成を実現するための具体的な記載がなく、通信ＮＷに適した３つの特性をノードの故障後にも維持できるグラフの構成手法が明らかにされていなかった。
【００１４】
本発明の目的は、上記した課題を解決するネットワーク構成装置、処理方法およびプログラムを提供することにある。
【課題を解決するための手段】
【００１５】
本発明のネットワーク構成装置は、通信ネットワークをＶ個のノードとＥ本のリンクとで構成するグラフＧを作成するネットワーク構成装置であって、前記グラフＧでは、平方剰余（ｐ｜ｑ）＝１を満たす互いに異なる素数ｐおよび素数ｑについて、ノード数がｑ＋１であり、ノード次数がｐ＋１である連結なラマヌジャングラフから、単数または複数の前記ノードを除去した場合に前記ラマヌジャングラフが非連結にはならず、前記ノードが故障した前後で、前記ノード次数が４以上の偶数のまま不変であり、かつ、前記グラフＧの第２最小ラプラシアン固有値が、以下の関係式を満たす範囲内で可能な限り大きい。
【００１６】
【数１】
【００１７】
ここで、ｋは、前記ノード次数であり、λＮ（Ｌ（Ｇ））は、上記を満たす前記グラフＧの最大ラプラシアン固有値であり、λ２（Ｌ（Ｇ））は、上記を満たす前記グラフＧの第２最小ラプラシアン固有値であり、λ２（Ｌ（Ｇ（Ｖ−１，Ｅ−ｋ／２）））は、上記を満たす前記グラフＧから、１個の前記ノードと、該ノードに接続されていた前記リンクのうちの（ｋ／２）本のリンクとが除去されたグラフの第２最小ラプラシアン固有値である。
【００１８】
また、本発明の処理方法は、ネットワーク構成装置が行う処理方法であって、通信ネットワークがＶ個のノードとＥ本のリンクとで構成されるグラフＧにおいて、平方剰余（ｐ｜ｑ）＝１を満たす互いに異なる素数ｐおよび素数ｑについて、ノード数がｑ＋１であり、ノード次数がｐ＋１である連結なラマヌジャングラフを構成する第１構成ステップと、前記ラマヌジャングラフから、単数または複数の前記ノードを除去した場合に前記ラマヌジャングラフが非連結にはならず、前記ノードが故障した前後で、前記ノード次数が４以上の偶数のまま不変であり、かつ、前記グラフＧの第２最小ラプラシアン固有値が以下の関係式を満たす範囲内で可能な限り大きい前記グラフＧを構成する第２構成ステップと、を含む処理方法。
【００１９】
【数２】
【００２０】
ここで、ｋは、前記ノード次数であり、λＮ（Ｌ（Ｇ））は、上記を満たす前記グラフＧの最大ラプラシアン固有値であり、λ２（Ｌ（Ｇ））は、上記を満たす前記グラフＧの第２最小ラプラシアン固有値であり、λ２（Ｌ（Ｇ（Ｖ−１，Ｅ−ｋ／２）））は、上記を満たす前記グラフＧから、１個の前記ノードと、該ノードに接続されていた前記リンクのうちの（ｋ／２）本のリンクとが除去されたグラフの第２最小ラプラシアン固有値である。
【００２１】
また、本発明のプログラムは、コンピュータに、通信ネットワークがＶ個のノードとＥ本のリンクとで構成されるグラフＧにおいて、平方剰余（ｐ｜ｑ）＝１を満たす互いに異なる素数ｐおよび素数ｑについて、ノード数がｑ＋１であり、ノード次数がｐ＋１である連結なラマヌジャングラフを構成する第１構成手順と、前記ラマヌジャングラフから、単数または複数の前記ノードを除去した場合に前記ラマヌジャングラフが非連結にはならず、前記ノードが故障した前後で、前記ノード次数が４以上の偶数のまま不変であり、かつ、前記グラフＧの第２最小ラプラシアン固有値が以下の関係式を満たす範囲内で可能な限り大きい前記グラフＧを構成する第２構成手順と、を実行させる。
【００２２】
【数３】
【００２３】
ここで、ｋは、前記ノード次数であり、λＮ（Ｌ（Ｇ））は、上記を満たす前記グラフＧの最大ラプラシアン固有値であり、λ２（Ｌ（Ｇ））は、上記を満たす前記グラフＧの第２最小ラプラシアン固有値であり、λ２（Ｌ（Ｇ（Ｖ−１，Ｅ−ｋ／２）））は、上記を満たす前記グラフＧから、１個の前記ノードと、該ノードに接続されていた前記リンクのうちの（ｋ／２）本のリンクとが除去されたグラフの第２最小ラプラシアン固有値である。
【発明の効果】
【００２４】
本発明によれば、通信ネットワークに適したグラフを構成することが可能になる。
【図面の簡単な説明】
【００２５】
【図１】本発明の第１実施形態におけるネットワーク構成装置を示すブロック図である。
【図２】ネットワーク構成装置が構成したネットワークを示す図である。
【図３】ネットワーク構成装置の処理方法を示すフローチャートである。
【図４】第２実施形態のネットワーク構成装置が構成したネットワークを示す図である。
【図５】ネットワーク構成装置の処理方法を示すフローチャートである。
【図６】ネットワーク内のノードに故障したときのネットワークを示す図である。
【図７】ノードが故障したときに行われる通信経路の再構築の一例を示す図である。
【図８】ネットワークの再構築方法を示すフローチャートである。
【図９】高速通信が可能なプロトコルを用いて通信を行うノードの動作を説明するための図である。
【図１０】第３実施形態の通信ネットワークを示す図である。
【図１１ａ】固有値計算用のサーバの動作を説明するためのフローチャートである。
【図１１ｂ】図１１ａに示したステップＡの処理を示すフローチャートである。
【図１１ｃ】図１１ｂに示したステップＢの処理を示すフローチャートである。
【図１２】固有値計算用のサーバの構成例を示すブロック図である。
【発明を実施するための形態】
【００２６】
以下、本発明の各実施形態について図面を参照して説明する。
【００２７】
図１は、本発明の第１実施形態におけるネットワーク構成装置を示すブロック図である。
【００２８】
ネットワーク構成装置１０は、通信ネットワークを含む通信システム、または、通信ネットワークを、Ｖ個のノードとＥ本のリンクとで構築されるグラフＧを用いて構成する。ネットワーク構成装置１０は、通信ネットワークに適した３つの特性に関するグラフ条件を満たすグラフＧを構成する。
【００２９】
ここで、ネットワーク構成装置１０で構成されるグラフＧについて説明する。
【００３０】
一般のグラフの最小ラプラシアン固有値には、明確な下限の値が存在しない。一方、ｋ−正則グラフの１つであるラマヌジャングラフの第２最小ラプラシアン固有値には下限がある（非特許文献１参照）。したがって、ノードの次数がｋであるｋ−正則グラフには、明確な下限を持つ固有値が存在するため、その下限の値以上の固有値が存在することが保証されている。
【００３１】
また、ｋ−正則グラフでは、グラフ内の任意の２ノード間のマルコフ連鎖に従うランダムウォークのｆｉｒｓｔ ｐａｓｓａｇｅ ｔｉｍｅ（非特許文献１参照）が最小となるグラフを構成することが可能である。
【００３２】
非特許文献１に記載されたｆｉｒｓｔ ｐａｓｓａｇｅ ｔｉｍｅを示す式は、非特許文献３に記載されている、規格化ラプラシアン固有値とラプラシアン固有値との関係を示した定理２．２０を用いて、下式のとおり、書き直される。
【００３３】
【数１】
【００３４】
ここで、Ｍは、ネットワーク内のリンクの総数であり、０＜λｖ（Ｌ）≦２は、ネットワークのラプラシアン行列の小さい方からｖ番目（ｖは２以上の自然数）の固有値であり、ｕ＿（ｌ，ｓ）は、ネットワークの規格化ラプラシアン行列の小さい方からｌ番目の固有値（ｌは２以上の自然数）に対する大きさが１の固有ベクトルの上からｔ行目の値である。
【００３５】
また、ｋ−正則グラフの１つであるラマヌジャングラフは、拡大定数を最大化するためにグラフの自明でない固有値の絶対値を最大化し、グラフ直径を最大化する。
【００３６】
また、ｋ−正則グラフのうち、完全グラフを除いたグラフは、一般に、ノード数が増加するにつれてリンク数が線形に増加する。
【００３７】
したがって、本実施形態では、「通信ＮＷに適した３つの特性」のグラフ条件を満たすグラフＧとして、「ラマヌジャングラフ」が用いられる。
【００３８】
このため、ネットワーク構成装置１０は、平方剰余（ｐ｜ｑ）＝１を満たす互いに異なる素数ｐおよび素数ｑについて、ノード数がｑ＋１であり、ノード次数がｐ＋１である連結なラマヌジャングラフＧ１を構成する。このラマヌジャングラフＧ１のノード次数は、４以上の偶数であり、かつ、ノードの除去前後で不変である。
【００３９】
ネットワーク構成装置１０は、そのラマヌジャングラフＧ１の第２最小ラプラシアン固有値が、式（２）の不等式および等式を満たす範囲内で可能な限り大きいグラフＧを構成する。
【００４０】
【数２】
【００４１】
ここで、ｋは、ノード次数であり、λＮ（Ｌ（Ｇ））は、上記を満たすグラフＧの最大ラプラシアン固有値であり、λ２（Ｌ（Ｇ））は、上記を満たすグラフＧの第２最小ラプラシアン固有値であり、λ２（Ｌ（Ｇ（Ｖ−１，Ｅ−ｋ／２）））は、上記を満たすグラフＧから、１個のノードと、そのノードに接続されていた前記リンクのうちの（ｋ／２）本のリンクと、が除去されたグラフの第２最小ラプラシアン固有値である。１個のノードと共に、そのノードに接続されていたリンクのうちのｋ／２本のリンクを除去するのは、グラフＧのノード次数が、ノードの除去後でも変わらないようにするためである。
【００４２】
図２は、ネットワーク構成装置１０が構成するネットワークの一例を示す図である。
【００４３】
ネットワークＮＷ１には、通信ネットワークを含むシステム、または、通信ネットワークが、複数のノードＮと複数のリンクＬとで構成されたグラフＧの構造が示されている。ネットワークＮＷ１は、ネットワークＮＷ１−ａと、ネットワークＮＷ１−ｂと、ネットワークＮＷ１−ｃと、ネットワークＮＷ１−ｄとで構成されている。
【００４４】
本実施形態では、ネットワーク構成装置１０は、ネットワークＮＷ１の設計段階に用いられる。ネットワーク構成装置１０は、通信部１１と、グラフ構成部１２と、グラフ決定部１３と、を備える。
【００４５】
通信部１１は、ネットワークＮＷ１内で許容可能なノードの最大ノード数Ｎ１と、許容可能なリンクの最大リンク数Ｅ１とを受け付ける。例えば、通信部１１は、ネットワーク管理者により入力された、最大ノード数Ｎ１と最大リンク数Ｅ１とを設計情報として、外部の通信装置から受信する。通信部１１は、その最大ノード数Ｎ１と最大リンク数Ｅ１とをグラフ構成部１２に供給する。
【００４６】
グラフ構成部１２は、最大ノード数Ｎ１と最大リンク数Ｅ１とを受け付けると、最大ノード数Ｎ１および最大リンク数Ｅ１を満たし、かつ、「通信ネットワークに適した３つの特性」に関するグラフ条件を実現可能な、ネットワークＮＷ１−ａの仮のグラフＧ１を作成（構築）する。例えば、グラフ構成部１２は、ネットワークＮＷ１−ａの仮のグラフＧ１を複数作成する。
【００４７】
グラフ構成部１２は、ネットワークＮＷ１−ａのグラフが、ラマヌジャングラフＧ１となるように、素数ｐ１および素数ｑ１を用いて、式（３）を満たすノード数｜Ｖ１｜と、式（４）を満たすノード次数ｋ1とを設定する。素数ｐ１および素数ｑ１は、平方剰余（ｐ１｜ｑ１）＝１を満たす互いに異なる素数である。
【００４８】
｜Ｖ１｜＝ ｑ１ ＋ １ ≦ Ｎ１ ・・・式（３）
ｋ1 ＝ ｐ１ ＋ １ ≦ Ｅ１ ・・・式（４）
すなわち、グラフ構成部１２は、最大ノード数Ｎ１と最大リンク数Ｅ１とを受け付けると、式（３）を満たすノード数｜Ｖ１｜と、式（４）を満たすノード次数ｋ1とで構成される、ラマヌジャングラフＧ１（Ｖ１,Ｅ１）を、物理的ネットワークまたは論理ネットワークとして構成する。ここで、Ｖ１は、ラマヌジャングラフＧ１内の全てのノードを表すノード集合であり、Ｅ１は、ラマヌジャングラフＧ１内の全てのリンクを表すリンク集合である。
【００４９】
グラフ決定部１３は、グラフ構成部１２で構成されたラマヌジャングラフＧ１と、そのラマヌジャングラフＧ１から、１個のノード、および、そのノードに接続されていたリンクのうちの（ｋ1／２）本のリンクを除去したラマヌジャングラフＧ１−ｖ１と、のそれぞれの第２最小ラプラシアン固有値が不変であるラマヌジャングラフＧを取る。このラマヌジャングラフＧは、ノードの除去の前後で、ノード次数ｋ1が４以上の偶数のまま不変であり、かつ、式（２）が成り立つことになる。
【００５０】
グラフ決定部１３は、行列計算部１３１と、固有値計算部１３２と、判定部１３３と、固有値選択部１３４と、を備える。
【００５１】
行列計算部１３１は、グラフ構成部１２にて構成されたラマヌジャングラフＧ１のラプラシアン行列を計算する。行列計算部１３１は、ラマヌジャングラフＧ１のラプラシアン行列を固有値計算部１３２に供給する。
【００５２】
固有値計算部１３２は、行列計算部１３１から、ラプラシアン行列を受け付けると、そのラプラシアン行列を用いて第２最小ラプラシアン固有値を計算する。固有値計算部１４は、その第２最小ラプラシアン固有値を判定部１３３に供給する。
【００５３】
判定部１３３は、固有値計算部１３２から、第２最小ラプラシアン固有値を受け付けると、グラフ構成部１２を制御して、ラマヌジャングラフＧ１から、ノード１個、および、そのノードに接続されているリンクのうちの（ｋ1／２）本のリンクを除去する。具体的には判定部１３３は、グラフ構成部１２で作成されたラマヌジャングラフＧ１から、１個のノードと、そのノードに接続されているリンクのうち（ｋ1／２）本のリンクを除去する旨を指示する除去指示信号をグラフ構成部１２に供給する。行列計算部１３１は、グラフ構成部１２でノードおよびリンクが除去されると、その除去された後のラマヌジャングラフＧ１−ｖ１のラプラシアン行列を計算する。そして固有値計算部１３２は、ラマヌジャングラフＧ１−ｖ１のラプラシアン行列の最小ラプラシアン固有値を計算して判定部１３３に供給する。
【００５４】
判定部１３３は、除去後のラマヌジャングラフＧ１−ｖ１と、元のラマヌジャングラフＧ１と、が式（２）を満たすか否かを判定する。すなわち、判定部１３３は、除去後のラマヌジャングラフＧ１−ｖ１の第２最小ラプラシアン固有値が、元のラマヌジャングラフＧ１の第２最小ラプラシアン固有値と同一であるか否かを判定する。
【００５５】
判定部１３３は、除去後のラマヌジャングラフＧ１−ｖ１と、元のラマヌジャングラフＧ１と、が式（２）を満たす場合、すなわち、ノードの除去の前後のそれぞれの第２最小ラプラシアン固有値が同一である場合には、その第２最小ラプラシアン固有値を、固有値選択部１３４に供給する。
【００５６】
例えば、判定部１３３は、ラマヌジャングラフＧ１内のノードを１個から所定の個数まで１個ずつ除去する。そして判定部１３３は、ラマヌジャングラフＧ１内のノードを１個ずつ除去するたびに、その除去後のラマヌジャングラフＧ１−ｖ１と、元のラマヌジャンクグラフＧ１と、が式（２）を満たすか否かを判定する。判定部１３３は、ラマヌジャングラフＧ１内のノードを１個から所定の個数まで１個ずつ除去した後、全ての判定で式（２）を満たした場合には、第２最小ラプラシアン固有値を固有値選択部１３４に供給する。
【００５７】
固有値選択部１３４は、判定部１３３から、式（２）を満たす範囲内での第２最小ラプラシアン固有値を受け付けると、第２最小ラプラシアン固有値の中から、最大の第２最小ラプラシアン固有値を選択する。または、固有値選択部１６は、第２最小ラプラシアン固有値の中から、可能な限り大きな値の第２最小ラプラシアン固有値を選択する。
【００５８】
また、固有値選択部１３４は、例えば、判定部１３３から第２最小ラプラシアン固有値を受け付け、その第２最小ラプラシアン固有値が、所定の固有値閾値よりも小さい場合には、グラフ構成部１２に新たなグラフの構築を指示してもよい。
【００５９】
固有値選択部１３４は、その選択した第２最小ラプラシアン固有値を用いて、ネットワークＮＷ１-ａのグラフＧ内のノード数と、リンク数と、ノードとリンクとの接続関係と、を含むグラフ構成情報を、通信部１１に供給する。通信部１１は、固有値選択部１３４からグラフ構成情報を受け付けると、そのグラフ構成情報を外部の装置に送信する。
【００６０】
図３は、ネットワーク構成装置１０の処理方法を示すフローチャートである。
【００６１】
まず、通信部１１は、例えばネットワーク管理者により入力された設計情報として、最大ノード数Ｎ１と最大リンク数Ｅ１とを受け付ける（ステップＳ１−１）。通信部１１は、その最大ノード数Ｎ１と最大リンク数Ｅ１とをグラフ構成部１２に供給する。
【００６２】
グラフ構成部１２は、最大ノード数Ｎ１と最大リンク数Ｅ１とを受け付けると、最大ノード数Ｎ１および最大リンク数Ｅ１を満たし、かつ、通信ネットワークに適した３つの特性に関するグラフ条件を実現可能な、ネットワークＮＷ１−ａのグラフを構築する（ステップＳ１−２）。
【００６３】
グラフ構成部１２は、ネットワークＮＷ１−ａのグラフが、式３を満たすノード数｜Ｖ１｜であり、かつ、式４を満たすノード次数ｋ1であるラマヌジャングラフＧ１（Ｖ１，Ｅ１）を構成する（ステップＳ１−３）。
【００６４】
グラフ決定部１３は、グラフ構成部１２で構成されたラマヌジャングラフＧ１と、そのラマヌジャングラフＧ１から、１個のノード、および、そのノードに接続されていたリンクのうちの（ｋ1／２）本のリンクを除去する（ステップＳ１−４）。
【００６５】
グラフ決定部１３は、その１個のノードおよび（ｋ1／２）本のリンクが除去されたラマヌジャングラフＧ１−ｖ１と元のラマヌジャングラフＧ１で、ノード次数ｋ1が４以上の偶数のまま不変であり、かつ、式（２）が成り立つことを確認する（ステップＳ１−５）。そしてノード次数ｋ1が４以上の偶数ではない場合、または、式（２）が成り立たない場合にはグラフ決定部１３は、ステップＳ１−２に戻る。
【００６６】
一方、グラフ決定部１３は、ノード次数ｋ1が４以上の偶数のまま不変であり、かつ、式（２）が成り立つ場合にはラマヌジャングラフＧ１から除去されたノードの数が所定数未満であるか否かを判断する（ステップＳ１−６）。そしてグラフ決定部１３は、除去されたノードの数が所定数未満である場合には、ステップＳ１−４に戻り、除去されたノードの数が所定数となるまで繰り返しステップＳ１−４および１−５の処理を行う。
【００６７】
グラフ決定部１３は、ラマヌジャングラフＧ１の式（２）を満たす範囲内で可能な限り大きな値の第２最小ラプラシア固有値を選択して（ステップＳ１−７）、ネットワーク構成装置１０の処理方法を終了する。
【００６８】
なお、ネットワークＮＷ１−ａだけでは、最大ノード数Ｎ１および最大リンク数Ｅ１の条件を満たさない場合には、ネットワーク構成装置１０は、図３で示した処理方法でネットワークＮＷ１−ｂ乃至ＮＷ１−ｃを構成し、これらを連結してもよい。
【００６９】
本実施形態によれば、ネットワーク構成装置１０は、通信ネットワークをＶ個のノードとＥ本のリンクとで構築されるグラフＧを構成する。ネットワーク構成装置１０は、平方剰余（ｐ｜ｑ）＝１を満たす互いに異なる素数ｐおよび素数ｑについて、ノード数がｑ＋１であり、かつ、ノード次数がｐ＋１である連結なラマヌジャングラフＧ１を構成し、ラマヌジャングラフＧ１から、単数または複数のノードを除去した場合にラマヌジャングラフＧ１−ｖ１が非連結にはならず、ノードが故障した前後で、ノード次数が４以上の偶数のまま不変であり、かつ、グラフＧの第２最小ラプラシアン固有値が、式（２）の関係式を満たす範囲内で可能な限り大きいグラフＧを構成する。
【００７０】
このため、ネットワーク構成装置１０は、通信ネットワークに適した３つの特性に関する１）から３）のグラフ条件を満たすグラフＧを作成することが可能となる。グラフＧは、連結なラマヌジャングラフに含まれてもよく、連結な２部グラフでないラマヌジャングラフに含まれてもよい。
【００７１】
次に、本発明の第２実施形態について説明する。第２実施形態では、既存のネットワークが存在する状況で、そのネットワーク上にネットワーク構成装置がグラフＧを構成する。なお、第２実施形態のネットワーク構成装置は、図１に示した構成と同様のものである。
【００７２】
図４は、第２実施形態のネットワーク構成装置１０が構成したネットワークを示す図である。
【００７３】
既存のネットワークＮＷ２には、図２と同様、通信ネットワークを含むシステム、または、通信ネットワークが、複数のノードＮと複数のリンクＬとで構成されたグラフＧの構造が示されている。ネットワークＮＷ２は、ネットワークＮＷ２−ａと、ネットワークＮＷ２−ｂと、ネットワークＮＷ２−ｃと、ネットワークＮＷ２−ｄと、で構成される。
【００７４】
図５は、第２実施形態の処理方法を示すフローチャートである。
【００７５】
まず、通信部１１は、設計情報として、ネットワークＮＷ２を指定する旨の指定情報と、ＮＷ２−ａ内の最大ノード数Ｎ２と、最大リンク数Ｅ２と、を受け付ける（ステップＳ２−１）。通信部１１は、その最大ノード数Ｎ１と最大リンク数Ｅ１とをグラフ構成部１２に供給する。
【００７６】
グラフ構成部１２は、最大ノード数Ｎ１と最大リンク数Ｅ１とを受け付けると、最大ノード数Ｎ１および最大リンク数Ｅ１を満たし、かつ、通信ネットワークに適した３つの特性に関するグラフ条件を実現可能な、ネットワークＮＷ２−ａのグラフを構築する（ステップＳ２−２）。
【００７７】
グラフ構成部１２は、ネットワークＮＷ２−ａのグラフが、式（５）を満たすノード数｜Ｖ２｜であり、式（６）を満たすノード次数ｋ2である連結なラマヌジャングラフＧ１（Ｖ２，Ｅ２）を構成する（ステップＳ２−３）。
【００７８】
｜Ｖ２｜＝ ｑ２ ＋ １ ≦ Ｎ２ ・・・式（５）
ｋ2 ＝ ｐ２ ＋ １ ≦ Ｅ２ ・・・式（６）
なお、ｑ２およびｐ２は、平方剰余（ｐ２｜ｑ２）＝１を満たす互いに異なる素数である。
【００７９】
グラフ決定部１３は、グラフ構成部１２で構成されたラマヌジャングラフＧ２と、そのラマヌジャングラフＧ１から、１個のノード、および、そのノードに接続されていたリンクのうちの（ｋ2／２）本のリンクを除去する（ステップＳ２−４）。
【００８０】
グラフ決定部１３は、１個のノードおよび（ｋ2／２）本のリンクが除去されたラマヌジャングラフＧ２−ｖ２と元のラマヌジャングラフＧ２とで、ノード次数ｋ2が４以上の偶数のまま不変であり、かつ、式（２）が成り立つことを確認する（ステップＳ２−５）。そしてノード次数ｋ2が４以上の偶数ではない場合、または、式（２）が成り立たない場合にはグラフ決定部１３は、ステップＳ２−２に戻る。
【００８１】
一方、グラフ決定部１３は、ノード次数ｋ2が４以上の偶数のまま不変であり、かつ、式（２）が成り立つ場合にはラマヌジャングラフＧ２から除去されたノードの数が所定数未満であるか否かを確認する（ステップＳ２−６）。そしてグラフ決定部１３は、除去されたノードの数が所定数未満である場合には、ステップＳ２−４に戻り、除去されたノードの数が所定数となるまで繰り返しステップＳ２−４およびＳ２−５の処理を行う。
【００８２】
グラフ決定部１３は、ラマヌジャングラフＧ２の式（２）を満たす範囲内で可能な限り大きな値の第２最小ラプラシア固有値を選択して（ステップＳ２−７）、ネットワーク構成装置１０の処理方法を終了する。
【００８３】
なお、ネットワークＮＷ２−ａのみでは、最大ノード数Ｎ２および最大リンク数Ｅ２の条件を満足しない場合には、ネットワーク構成装置１０は、新たにネットワークＮＷ２−ｂ乃至ＮＷ２−ｄを構成し、これらを連結してもよい。
【００８４】
次にネットワークＮＷ１またはＮＷ２が構成されている状態で、ネットワークＮＷ１またはＮＷ２内のノードが故障した場合に、その故障したノード以外のノードを経由する通信経路のうち、最短の通信経路を再構築するための手法について説明する。
【００８５】
図６は、ネットワーク構成装置１０が構成したネットワークＮＷ３を示す図である。
【００８６】
ネットワークＮＷ３は、ネットワークＮＷ３−ａと、ネットワークＮＷ３−ｂと、ネットワークＮＷ３−ｃと、ネットワークＮＷ３−ｄと、で構成されている。ここでは、ネットワークＮＷ３−ａでノードａが故障した場合を想定している。
【００８７】
図７は、ネットワークＮＷ３−ａで、ノードａが故障した場合に行われる通信経路の再構築の一例を示す図である。図７には、ネットワークＮＷ３−ａ（Ｖ３，Ｅ３）と、ノードａが故障してノードａが除去されたネットワークＮＷ３−ａ−ａ（Ｖ３−ａ，Ｅ３−ｋ3／２）とが示されている。
【００８８】
ネットワークＮＷ３−ａは、ノードａと直接接続されていない部分グラフＳと、ノードａと直接接続されている部分グラフＵとで構成されている。ネットワークＮＷ３−ａ−ａ内の部分グラフＵ’は、ノードａに接続されていたｋ3本のリンクのうちのｋ3／２本のリンクの接続先が、ノードａから別のノードに切り替えられた後の部分グラフである。
【００８９】
図８は、図７に示したネットワークＮＷ３−ａの再構築方法を示すフローチャートである。
【００９０】
まず、ネットワークＮＷ−３ａでノードａに故障が発生した場合（ステップＳ３−０）に、ノードａに隣接している全てのノードは、ノードａの故障情報をノードａ以外のノードに送信して故障情報をＮＷ３−ａ内の全てのノードに伝達する（ステップＳ３−１）。ネットワークＮＷ−３ａは、通信ネットワークに適した３つの特性を有しているため、任意の２ノード間の通信時間が短く、任意の２ノード間に複数の経路がある。このため、本実施形態のネットワークＮＷ３−ａでは、故障情報が、全てのノードに短い時間で到達されることになる。
【００９１】
なお、故障情報には、ノードａの識別情報と、ノードａに故障が発生した時刻と、ノードａの識別情報とが含まれる。故障情報は、一般的な経路制御プロトコルよりも高速通信が可能な通信プロトコルＰ２を用いてＮＷ３−ａ内の各経路に分散される。通信プロトコルとしては、例えば、フラッディングアルゴリズムに基づいて経路制御を行うプロトコルが用いられる。
【００９２】
ＮＷ３−ａ内の全てのノードに故障情報が伝達されると、ノードａが除去されてリンクの張り替えが行われる。このとき、ＮＷ３−ａの第２最小ラプラシアン固有値が、元のＮＷ３−ａ（Ｖ３，Ｅ３）と同じ値のＮＷ３−ａ−ａ（Ｖ３−ａ，Ｅ３−ｋ3／２）を再構築することが可能である。短時間で通信経路を変更する場合には、通信経路上のノードのうち、ノードａに接続されていた２ノード間を接続すればよい。
【００９３】
図９は、通信プロトコルＰ２を用いて通信を行う各ノードの動作を説明するためのフローチャートである。
【００９４】
まず、通信プロトコルを用いてリンクの張り替えが行われるネットワークＮＷａ−３では、全てのノードを根とする最短スパニング木が構成される（ステップＳ３−３）。
【００９５】
ネットワークＮＷ３−ａ内の各ノードは、ノードａの故障を検出した場合に、フラッディングアルゴリズムに従って、自身のノードを根とする最短スパニング木上の隣接ノードに、故障情報を伝達する（ステップＳ３−４）。
【００９６】
ネットワークＮＷ３−ａ内の各ノードは、故障情報を受信する（ステップＳ３−４−２）と、故障情報が１つの場合には、自身のノードを根とする最短スパニング木上の全ての隣接ノードに伝達する（ステップＳ３−４−３）。ネットワークＮＷ３−ａでは、全てのノードに伝達されるまで故障情報の送信が行われる。
【００９７】
ネットワークＮＷ３−ａ内の各ノードは、複数の故障情報を受信したとき（ステップＳ３−５）に、複数の故障情報に含まれている識別情報または発生時刻が互いに異なる場合（ステップＳ３−６）には、複数の故障情報のそれぞれを、自身のノードを根とする最短スパニング木上の隣接ノードに伝達する（ステップＳ３−６−１）。
【００９８】
一方、ネットワークＮＷ３−ａ内の各ノードは、複数の故障情報を受信したとき（ステップＳ３−５）に、複数の故障情報が同じ場合（ステップＳ３−６）には、複数の故障情報の中からいずれか１つを選択し、その故障情報を、自身のノードを根とする最短スパニング木上の隣接ノードに伝達する（ステップＳ３−６−２）。
【００９９】
次に本発明の第３実施形態として、既存の通信ネットワーク内の各ノードが自律的に通信経路を切り替えることで、通信ＮＷに適したネットワークＮＷ１またはＮＷ２を構成する手法について説明する。
【０１００】
図１０は、第３実施形態のネットワークＮＷ４を示す図である。ネットワークＮＷ４は、
既存の通信ネットワーク内の各ノードが自律的に通信経路を制御する自律機能を有する。
【０１０１】
ネットワークＮＷ４は、多数のノードＮおよび多数のリンクＬに加えて、通信ノードＣＮ、および、固有値計算用のサーバＣＳを備える。ネットワークＮＷ４は、ネットワークＮＷ４−ａと、ネットワークＮＷ４−ｂと、ネットワークＮＷ４−ｃと、ネットワークＮＷ４−ｄと、で構成される。
【０１０２】
図１１ａは、固有値計算用のサーバＣＳの動作を説明するためのフローチャートである。
【０１０３】
ネットワークＮＷ４−ａは、ノードに故障が発生した場合に、図８で述べた通信プロトコルＰ２を用いて故障情報を、ネットワークＮＷ４−ａ内の各ノードに伝達する機能を有する。ネットワークＮＷ４内のノードに接続されるサーバＣＳは、自律分散的な手法を用いてノードの接続先が決定される。自律分散的な手法としては、例えば、ＲＦＣ ２３２８ − ＯＳＰＦ Ｖｅｒｓｉｏｎ ２に記載のＤｅｓｉｇｎａｔｅｄ Ｒｏｕｔｅｒ選別方法が挙げられる。
【０１０４】
サーバＣＳは、ネットワーク管理者により入力された設定情報として、ノードが故障した時点から、ネットワークＮＷ４の制御を開始するまでの最大期間Ｔｍａｘを受け付ける。最大期間Ｔｍａｘは、故障情報を伝播させる時間の最大値である。
【０１０５】
サーバＣＳは、最大期間Ｔｍａｘを受け付けると、その最大期間Ｔｍａｘを、２ノード間で通信プロトコルＰ２を用いて通信するのに必要な所要時間ＴＰ２で除算し、最大期間Ｔｍａｘを所要時間ＴＰ２で除算した値を超えない最大の自然数Ｎｍａｘを算出する（ステップＳ４−２−３）。Ｎｍａｘは、通信プロトコルＰ２を使用して、ノード間の物理リンクを通じて故障情報を伝達できるノードの最大数を示す。
【０１０６】
サーバＣＳは、ネットワークＮＷ４内のノードの中から適当な通信ノードＮ０を選択し、その通信ノードＮ０から、物理リンクを辿って到達可能なＮｍａｘ番目のノードまでの全てのノードを集める（ステップＳ４−２−４）。ここでは、通信ノードＮ０からＮｍａｘ番目までの全てのノードの数をｎ個とする。
【０１０７】
サーバＣＳは、その特定されたｎ個のノードで構成される部分ネットワークを、故障情報を伝播させる仮のネットワーク範囲（以下「ＮＷ４−ａ」と称する。）に決定する（ステップＳ４−２−５）。
【０１０８】
サーバＣＳは、ＮＷ４−ａの隣接行列Ａ（ＮＷ４−ａ）とラプラシアン行列Ｌ（ＮＷ４−ａ）とを生成する（ステップＳ４−３）。隣接行列Ａおよびラプラシアン行列Ｌは、ＮＷ４−ａのノードの総数がｎであるため、ｎ行ｎ列の行列となる。
【０１０９】
サーバＣＳは、隣接行列Ａ（ＮＷ４−ａ）の最大固有値λＮと、ラプラシアン行列Ｌ（ＮＷ４−ａ）の第２最小ラプラシアン固有値λ２とを求める（ステップＳ４−４−１）。また、サーバＣＳは、ｖ＝２としたときの式（１）の算出結果である初到達時刻π（ＮＷ４−ａ）と、Ｎｍａｘとを比較し、式（７）を満たしている場合にはステップＡの処理に進む。式（７）満たしていない場合にはノード数を増加させる（ステップＳ４−４−４）。
【０１１０】
π（ＮＷ４−ａ） ＜ Ｎｍａｘ ・・・式（７）
図１１ｂは、図１１ａで示したステップＡの処理を示すフローチャートである。
【０１１１】
ステップＡの処理では、サーバＣＳは、式（８）を満たすノード数｜Ｖ４｜であり、式（９）を満たすノード次数ｋ4であるような連結なラマヌジャングラフＧ４を、物理的ＮＷまたは論理的ＮＷとして構成する（ステップＳ４−５−１）。ここで、Ｖ４は、ラマヌジャングラフＧ４のノード集合であり、Ｅ４は、ラマヌジャングラフＧ４のリンク集合である。
【０１１２】
｜Ｖ４｜＝ ｑ４ ＋ １ ≦ Ｎ４ ・・・式（８）
ｋ4 ＝ ｐ４ ＋ １ ≦ Ｅ４ ・・・式（９）
なお、素数ｐ４および素数ｑ４は、平方剰余（ｐ４｜ｑ４）＝１を満たす互いに異なる素数である。
【０１１３】
サーバＣＳは、ラマヌジャングラフＧ４と、そのラマヌジャングラフＧ４から、１個のノード、および、そのノードに接続されていたリンクのうちの（ｋ4／２）本のリンクを除去する（ステップＳ４−５−２）。
【０１１４】
サーバＣＳは、その１個のノードおよび（ｋ4／２）本のリンクが除去されたラマヌジャングラフＧ４−ｖ４と元のラマヌジャングラフＧ４とで、ノード次数ｋ4が４以上の偶数のまま不変であり、かつ、式（２）が成り立つことを確認する（ステップＳ４−５−３）。そしてノード次数ｋ2が４以上の偶数ではない場合、または、式（２）が成り立たない場合にはグラフ決定部１３は、ステップＳ４−５−１に戻る。
【０１１５】
サーバＣＳは、ノード次数ｋ2が４以上の偶数のまま不変であり、かつ、式（２）が成り立つ場合には、ラマヌジャングラフＧ２から除去されたノードの数が所定数未満であるか否かを確認する（ステップＳ４−６）。そしてサーバＣＳは、除去されたノードの数が所定数未満である場合には、ステップＳ４−５−２に戻り、除去されたノードの数が所定数となるまで繰り返しステップＳ４−５−２およびＳ４−５−３の処理を行う。
【０１１６】
サーバＣＳは、ラマヌジャングラフＧ４の式（２）を満たす範囲内で可能な限り大きな値の第２最小ラプラシア固有値を選択して（ステップＳ４−７）、ステップＢの処理に進む。
【０１１７】
図１１ｃは、図１１ｂで示したステップＢの処理を示すフローチャートである。
【０１１８】
ステップＢの処理では、サーバＣＳは、焼きなまし法（Ｓｉｍｕｌａｔｅｄ ａｎｎｅａｌｉｎｇ）という最適化アルゴリズムを用いて、ステップＳ４−５−１、Ｓ４−５−２、４−５−３、Ｓ４−６およびＳ４−７の一連の処理を繰り返し実行して、ＮＷ４−ａのグラフＧを構成する（ステップＳ４−８）。
【０１１９】
そしてサーバＣＳは、ステップＳ４−２−５で決定されたＮＷ４−ａに属する全てのノードに対し、通信ノードＣＮを介して、通信プロトコルＰ２を用いてＮＷ４−ａの構成情報を伝達する（ステップＳ４−９）。
【０１２０】
また、ネットワークＮＷ４からＮＷ４−ａを除いたネットワークについても、ステップＳ４−２−３からＳ４−９までの一連の処理手順を実行してＮＷ４−ｂ乃至４−ｄを構成し、サーバＣＳの処理方法が終了する。このため、ネットワークＮＷ４は、ＮＷ４−ａ乃至４−ｄによって分割された構成となる。
【０１２１】
図１２は、通信ノードＣＮおよびサーバＣＳの構成の一例を示すブロック図である。
【０１２２】
通信ノードＣＮは、ＮＷ４内のノードおよびリンクに関する構成情報を受信し、そのＮＷ４の構成情報のうち、ＮＷ４−＊（例えば、ＮＷ４−ａ）に関する構成情報をサーバＣＳに送信する。
【０１２３】
サーバＣＳは、通信部２１と、ラプラシアン行列計算部２２と、固有値λ２計算部２３と、隣接行列計算部２４と、固有値λＮ計算部２５と、初到達時刻π算出部２６と、比較部２７と、ＮＷ構成部２８と、を備える。なお、サーバＣＳは、一般的にネットワーク構成装置と呼ぶことができる。
【０１２４】
通信部２１は、通信ノードＣＮから、例えば、ＮＷ４−ａの構成情報を受信する。通信部２１は、そのＮＷ４−ａの構成情報を、ラプラシアン行列計算部２２と隣接行列計算部２４とに供給する。
【０１２５】
ラプラシアン行列計算部２２は、ＮＷ４−ａの構成情報を用いてラプラシアン行列Ｌを計算し、そのラプラシアン行列Ｌを、固有値λ２計算部２３に供給する。
【０１２６】
固有値λ２計算部２３は、ＮＷ４−ａのラプラシアン行列Ｌを受け付けると、そのラプラシアン行列の第２最小ラプラシアン固有値λ２を算出する。
【０１２７】
隣接行列計算部２４は、通信部２１から、ＮＷ４−ａの構成情報を受け付けると、そのＮＷ４−ａの隣接行列を計算し、その隣接行列を固有値λＮ計算部２５に供給する。
【０１２８】
固有値λＮ計算部２５は、ＮＷ４−ａの隣接行列を受け付けると、その隣接行列の最大ラプラシアン固有値λＮを計算し、その最大ラプラシアン固有値λＮを初到達時刻π算出部２６に供給する。
【０１２９】
初到達時刻π算出部２６は、ＮＷ４−ａの最大ラプラシアン固有値λＮを受け付けると、式（１）においてｖ＝２としたときの初到達時刻πを算出し、その初到達時刻πを比較部２７に供給する。
【０１３０】
比較部２７は、初到達時刻πを受け付けると、初到達時刻πが式（７）を満たしていることを確認する。比較部２７は、初到達時刻πが式（７）を満たしている場合には、ＮＷ４−ａの構成情報をＮＷ構成部２８に供給する。
【０１３１】
ＮＷ構成部２８は、ＮＷ４−ａの構成情報にて特定されるグラフを、ラマヌジャングラフＧ４となるように構成する。具体的にはＮＷ構成部２８は、式（８）を満たすノード数｜Ｖ４｜であり、式（４）を満たすノード次数ｋ4あるラマヌジャングラフＧ４（Ｖ４,Ｅ４）を、物理的ネットワークまたは論理ネットワークとして構成する。
【０１３２】
ＮＷ構成部２８は、ラマヌジャングラフＧ４と、そのラマヌジャングラフＧ４から、１個のノード、および、そのノードに接続されていたリンクのうちの（ｋ1／２）本のリンクを除去したラマヌジャングラフＧ４−ｖ４とで、第２最小ラプラシアン固有値が不変であるラマヌジャングラフＧを取る。このラマヌジャングラフＧは、ノードの故障の前後で、ノード次数ｋ4が４以上の偶数のまま不変であり、かつ、式（２）が成り立つことになる。ＮＷ構成部２８は、ＮＷ４−ａのラマヌジャングラフＧを示すＮＷ構成情報を生成し、そのＮＷ４−ａのＮＷ構成情報を通信部２１に供給する。
【０１３３】
通信部２１は、ＮＷ構成部２８からＮＷ４−ａのＮＷ構成情報を受け付けると、通信ノードＣＮを介して、ＮＷ４−ａのノードに対し、通信プロトコルＰ２を用いてＮＷ４−ａのＮＷ構成情報を伝達する。このため、ＮＷ４−ａのノードは、ＮＷ４−ａ内の通信経路を自律的に切り替えることが可能となる。
【０１３４】
第３実施形態によれば、ＮＷ４−ａのラマヌジャングラフＧ４は、通信ネットワークの通信経路を自律的に制御する単数または複数のノードで構成される。このため、通信ノードＣＮおよびサーバＣＳは、１）から３）のグラフ条件を満足する通信ネットワークＮＷ４−ａを構成することが可能となる。
【０１３５】
以上説明した各実施形態において、図示した構成は単なる一例であって、本発明はその構成に限定されるものではない。
【符号の説明】
【０１３６】
１０ ネットワーク構成装置
１１ 通信部
１２ グラフ構成部
１３ グラフ決定部
１３１ 行列計算部
１３２ 固有値計算部
１３３ 判定部
１３４ 固有値選択部
【特許請求の範囲】
【請求項１】
通信ネットワークをＶ個のノードとＥ本のリンクとで構成するグラフＧを作成するネットワーク構成装置であって、
前記グラフＧでは、平方剰余（ｐ｜ｑ）＝１を満たす互いに異なる素数ｐおよび素数ｑについて、ノード数がｑ＋１であり、ノード次数がｐ＋１である連結なラマヌジャングラフから、単数または複数の前記ノードを除去した場合に前記ラマヌジャングラフが非連結にはならず、前記ノードが故障した前後で、前記ノード次数が４以上の偶数のまま不変であり、かつ、前記グラフＧの第２最小ラプラシアン固有値が、以下の関係式を満たす範囲内で可能な限り大きい、ネットワーク構成装置。
【数１】
ここで、ｋは、前記ノード次数であり、λＮ（Ｌ（Ｇ））は、上記を満たす前記グラフＧの最大ラプラシアン固有値であり、λ２（Ｌ（Ｇ））は、上記を満たす前記グラフＧの第２最小ラプラシアン固有値であり、λ２（Ｌ（Ｇ（Ｖ−１，Ｅ−ｋ／２）））は、上記を満たす前記グラフＧから、１個の前記ノードと、該ノードに接続されていた前記リンクのうちの（ｋ／２）本のリンクとが除去されたグラフの第２最小ラプラシアン固有値である。
【請求項２】
請求項１に記載のネットワーク構成装置において、
前記グラフＧは、連結なラマヌジャングラフに含まれる、ネットワーク構成装置。
【請求項３】
請求項１または２に記載のネットワーク構成装置において、
前記グラフＧは、連結な２部グラフでないラマヌジャングラフに含まれる、ネットワーク構成装置。
【請求項４】
請求項１から３のいずれか１項に記載のネットワーク構成装置において、
前記グラフＧは、前記通信ネットワークの通信経路を自律的に制御する単数または複数のノードで構成される、ネットワーク構成装置。
【請求項５】
ネットワーク構成装置が行う処理方法であって、
通信ネットワークがＶ個のノードとＥ本のリンクとで構成されるグラフＧにおいて、平方剰余（ｐ｜ｑ）＝１を満たす互いに異なる素数ｐおよび素数ｑについて、ノード数がｑ＋１であり、ノード次数がｐ＋１である連結なラマヌジャングラフを構成する第１構成ステップと、
前記ラマヌジャングラフから、単数または複数の前記ノードを除去した場合に前記ラマヌジャングラフが非連結にはならず、前記ノードが故障した前後で、前記ノード次数が４以上の偶数のまま不変であり、かつ、前記グラフＧの第２最小ラプラシアン固有値が以下の関係式を満たす範囲内で可能な限り大きい前記グラフＧを構成する第２構成ステップと、を含む処理方法。
【数２】
ここで、ｋは、前記ノード次数であり、λＮ（Ｌ（Ｇ））は、上記を満たす前記グラフＧの最大ラプラシアン固有値であり、λ２（Ｌ（Ｇ））は、上記を満たす前記グラフＧの第２最小ラプラシアン固有値であり、λ２（Ｌ（Ｇ（Ｖ−１，Ｅ−ｋ／２）））は、上記を満たす前記グラフＧから、１個の前記ノードと、該ノードに接続されていた前記リンクのうちの（ｋ／２）本のリンクとが除去されたグラフの第２最小ラプラシアン固有値である。
【請求項６】
コンピュータに、
通信ネットワークがＶ個のノードとＥ本のリンクとで構成されるグラフＧにおいて、平方剰余（ｐ｜ｑ）＝１を満たす互いに異なる素数ｐおよび素数ｑについて、ノード数がｑ＋１であり、ノード次数がｐ＋１である連結なラマヌジャングラフを構成する第１構成手順と、
前記ラマヌジャングラフから、単数または複数の前記ノードを除去した場合に前記ラマヌジャングラフが非連結にはならず、前記ノードが故障した前後で、前記ノード次数が４以上の偶数のまま不変であり、かつ、前記グラフＧの第２最小ラプラシアン固有値が以下の関係式を満たす範囲内で可能な限り大きい前記グラフＧを構成する第２構成手順と、を実行させるためのプログラム。
【数３】
ここで、ｋは、前記ノード次数であり、λＮ（Ｌ（Ｇ））は、上記を満たす前記グラフＧの最大ラプラシアン固有値であり、λ２（Ｌ（Ｇ））は、上記を満たす前記グラフＧの第２最小ラプラシアン固有値であり、λ２（Ｌ（Ｇ（Ｖ−１，Ｅ−ｋ／２）））は、上記を満たす前記グラフＧから、１個の前記ノードと、該ノードに接続されていた前記リンクのうちの（ｋ／２）本のリンクとが除去されたグラフの第２最小ラプラシアン固有値である。
【請求項１】
通信ネットワークをＶ個のノードとＥ本のリンクとで構成するグラフＧを作成するネットワーク構成装置であって、
前記グラフＧでは、平方剰余（ｐ｜ｑ）＝１を満たす互いに異なる素数ｐおよび素数ｑについて、ノード数がｑ＋１であり、ノード次数がｐ＋１である連結なラマヌジャングラフから、単数または複数の前記ノードを除去した場合に前記ラマヌジャングラフが非連結にはならず、前記ノードが故障した前後で、前記ノード次数が４以上の偶数のまま不変であり、かつ、前記グラフＧの第２最小ラプラシアン固有値が、以下の関係式を満たす範囲内で可能な限り大きい、ネットワーク構成装置。
【数１】
ここで、ｋは、前記ノード次数であり、λＮ（Ｌ（Ｇ））は、上記を満たす前記グラフＧの最大ラプラシアン固有値であり、λ２（Ｌ（Ｇ））は、上記を満たす前記グラフＧの第２最小ラプラシアン固有値であり、λ２（Ｌ（Ｇ（Ｖ−１，Ｅ−ｋ／２）））は、上記を満たす前記グラフＧから、１個の前記ノードと、該ノードに接続されていた前記リンクのうちの（ｋ／２）本のリンクとが除去されたグラフの第２最小ラプラシアン固有値である。
【請求項２】
請求項１に記載のネットワーク構成装置において、
前記グラフＧは、連結なラマヌジャングラフに含まれる、ネットワーク構成装置。
【請求項３】
請求項１または２に記載のネットワーク構成装置において、
前記グラフＧは、連結な２部グラフでないラマヌジャングラフに含まれる、ネットワーク構成装置。
【請求項４】
請求項１から３のいずれか１項に記載のネットワーク構成装置において、
前記グラフＧは、前記通信ネットワークの通信経路を自律的に制御する単数または複数のノードで構成される、ネットワーク構成装置。
【請求項５】
ネットワーク構成装置が行う処理方法であって、
通信ネットワークがＶ個のノードとＥ本のリンクとで構成されるグラフＧにおいて、平方剰余（ｐ｜ｑ）＝１を満たす互いに異なる素数ｐおよび素数ｑについて、ノード数がｑ＋１であり、ノード次数がｐ＋１である連結なラマヌジャングラフを構成する第１構成ステップと、
前記ラマヌジャングラフから、単数または複数の前記ノードを除去した場合に前記ラマヌジャングラフが非連結にはならず、前記ノードが故障した前後で、前記ノード次数が４以上の偶数のまま不変であり、かつ、前記グラフＧの第２最小ラプラシアン固有値が以下の関係式を満たす範囲内で可能な限り大きい前記グラフＧを構成する第２構成ステップと、を含む処理方法。
【数２】
ここで、ｋは、前記ノード次数であり、λＮ（Ｌ（Ｇ））は、上記を満たす前記グラフＧの最大ラプラシアン固有値であり、λ２（Ｌ（Ｇ））は、上記を満たす前記グラフＧの第２最小ラプラシアン固有値であり、λ２（Ｌ（Ｇ（Ｖ−１，Ｅ−ｋ／２）））は、上記を満たす前記グラフＧから、１個の前記ノードと、該ノードに接続されていた前記リンクのうちの（ｋ／２）本のリンクとが除去されたグラフの第２最小ラプラシアン固有値である。
【請求項６】
コンピュータに、
通信ネットワークがＶ個のノードとＥ本のリンクとで構成されるグラフＧにおいて、平方剰余（ｐ｜ｑ）＝１を満たす互いに異なる素数ｐおよび素数ｑについて、ノード数がｑ＋１であり、ノード次数がｐ＋１である連結なラマヌジャングラフを構成する第１構成手順と、
前記ラマヌジャングラフから、単数または複数の前記ノードを除去した場合に前記ラマヌジャングラフが非連結にはならず、前記ノードが故障した前後で、前記ノード次数が４以上の偶数のまま不変であり、かつ、前記グラフＧの第２最小ラプラシアン固有値が以下の関係式を満たす範囲内で可能な限り大きい前記グラフＧを構成する第２構成手順と、を実行させるためのプログラム。
【数３】
ここで、ｋは、前記ノード次数であり、λＮ（Ｌ（Ｇ））は、上記を満たす前記グラフＧの最大ラプラシアン固有値であり、λ２（Ｌ（Ｇ））は、上記を満たす前記グラフＧの第２最小ラプラシアン固有値であり、λ２（Ｌ（Ｇ（Ｖ−１，Ｅ−ｋ／２）））は、上記を満たす前記グラフＧから、１個の前記ノードと、該ノードに接続されていた前記リンクのうちの（ｋ／２）本のリンクとが除去されたグラフの第２最小ラプラシアン固有値である。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１ａ】
【図１１ｂ】
【図１１ｃ】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１ａ】
【図１１ｂ】
【図１１ｃ】
【図１２】
【公開番号】特開２０１３−７０３００（Ｐ２０１３−７０３００Ａ）
【公開日】平成２５年４月１８日（２０１３．４．１８）
【国際特許分類】
【出願番号】特願２０１１−２０８４６９（Ｐ２０１１−２０８４６９）
【出願日】平成２３年９月２６日（２０１１．９．２６）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
【公開日】平成２５年４月１８日（２０１３．４．１８）
【国際特許分類】
【出願日】平成２３年９月２６日（２０１１．９．２６）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
[ Back to top ]