(57)【特許請求の範囲】
【請求項１】
実世界に存在するものの関係をノードとエッジで表現するデータ構造を有するグラフの直径をモニタリングするためのグラフの直径のモニタリング装置であって、
時刻毎に変化するノードを受信するデータ受信手段と、
受信したノード（追加ノード）及び、ノード間の距離が直径となる１時刻前の２つのノードの組である解ノードのペアと該ノード間の最大距離である直径を格納した記憶手段と、
ノード間の距離を計算する距離計算手段と、
前記記憶手段に格納されているノードからその他のノードまでの最大距離を前記距離計算手段により求め、直径になり得ないノードを枝刈りする枝刈り手段と、
前記記憶手段の直径となるノードのペアを、前記データ受信手段により追加されたノードからの距離に基づいて更新する更新手段と、
を有することを特徴とするグラフの直径のモニタリング装置。
【請求項２】
前記枝刈り手段は、
前記記憶手段に格納された前記追加ノード及び１時刻前の解ノードから最も次数の高いノードである参照ノードを選択し、前記距離計算手段を用いて、前記記憶手段の１時刻前の解ノードのペアから候補距離を計算し、該参照ノードの周辺ノードに対してその他のノードまでの距離の最大値を推定し、該最大値が該候補距離より小さければ該ノードを探索対象から除外する手段を含む
請求項１記載のグラフの直径のモニタリング装置。
【請求項３】
前記更新手段は、
前記データ受信手段により追加されたノードにより直径が大きくなる、または、小さくなる、変化しない、のいずれかに応じて、前記記憶手段の前記解ノードのペアと直径を更新する手段を含む
請求項１記載のグラフの直径のモニタリング装置。
【請求項４】
前記更新手段は、
前記最大距離が前記憶手段に格納されている１時刻前の直径よりも大きければ、該直径を該最大距離とし、該記憶手段の解ノードペアを更新し、該最大距離が１時刻前の直径と同じ長さのノードのペアがあれば、該追加ノードからの距離を用いて該記憶手段の解ノードのペアを更新し、１時刻前の直径と同じ距離のペアがなければ、前記距離計算手段により直径を求める手段、
を含む請求項１記載のグラフの直径モニタリング装置。
【請求項５】
実世界に存在するものの関係をノードとエッジで表現するデータ構造を有するグラフの直径をモニタリングするためのグラフの直径のモニタリング方法であって、
受信されたノード及びノード間の距離が直径となる１時刻前の２つのノードの組である解ノードのペアと該ノード間の最大距離である直径を格納した記憶手段と、データ受信手段、ノード間の距離を求める距離計算手段、枝刈り手段、更新手段を有する装置において、
前記データ受信手段が、時刻毎に変化するノードを受信するデータ受信ステップと、
前記枝刈り手段が、前記記憶手段に格納されているノードからその他のノードまでの最大距離を前記距離計算手段により求め、直径になり得ないノードを枝刈りする枝刈りステップと、
前記更新手段が、前記記憶手段の直径となるノードのペアを、前記データ受信手段により追加されたノードからの距離に基づいて更新する更新ステップと、
を行うことを特徴とするグラフの直径のモニタリング方法。
【請求項６】
前記枝刈りステップにおいて、
前記記憶手段に格納された前記追加ノード及び１時刻前の解ノードから最も次数の高いノードである参照ノードを選択し、前記距離計算手段を用いて、前記記憶手段の１時刻前の解ノードのペアから候補距離を計算し、該参照ノードの周辺ノードに対してその他のノードまでの距離の最大値を推定し、該最大値が該候補距離より小さければ該ノードを探索対象から除外する
請求項５記載のグラフの直径のモニタリング方法。
【請求項７】
前記更新ステップにおいて、
前記データ受信ステップにより追加されたノードにより直径が大きくなる、または、小さくなる、変化しない、のいずれかに応じて、前記記憶手段の前記解ノードのペアと直径を更新する
請求項５記載のグラフの直径のモニタリング方法。
【請求項８】
前記更新ステップにおいて、
前記最大距離が前記憶手段に格納されている１時刻前の直径よりも大きければ、該直径を該最大距離とし、該記憶手段の解ノードペアを更新し、該最大距離が１時刻前の直径と同じ長さのノードのペアがあれば、該追加ノードからの距離を用いて該記憶手段の解ノードのペアを更新し、１時刻前の直径と同じ距離のペアがなければ、前記距離計算手段により直径を求める、
請求項５記載のグラフの直径モニタリング方法。
【請求項９】
請求項１乃至４のいずれか１項に記載のグラフの直径モニタリング装置を構成する各手段としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グラフの直径のモニタリング装置及び方法及びプログラムに係り、特に、時々刻々と増大するグラフの直径をモニタリングするためのグラフの直径のモニタリング装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
グラフは実世界に存在するものとそれらの関係をノードとエッジという形で表現するデータ構造である。その直感的な表現方法によりグラフは数学やコンピュータ科学の分野において広く使われている。
【０００３】
グラフにおけるノード間の距離はグラフ理論の中で基本的な特徴量の一つである。グラフの直径とは、ノード間の距離に基づいた特徴量であり、グラフを解析する上で非常に重要である。しかし、従来のグラフ理論が対象としてきたグラフは静的であり、ノード及びエッジの数は変わらないという前提があった。
【０００４】
近年、時間と共にノード数が時々刻々と増大し、結果的にノード数が数十万以上になるグラフデータを扱うことが必要となってきた。これは巨大なデータベースとインターネットを用いる環境が整ってきた結果である。そして、近年の研究により時々刻々とノードの数を増やしながら成長し続けるグラフデータの特徴が明らかになりつつある（例えば、非特許文献１参照）。そのため時々刻々と成長し、結果的に非常に大きなサイズになるグラフを効率的に処理する需要が高まりつつある。
【０００５】
本発明では、時々刻々と成長し続けるグラフの中から直径を検出し続ける問題を扱う。
【０００６】
本明細書が対象とする問題の応用例としてP2P（ポイントツーポイント）ネットワークがあげられる。
【０００７】
近年、Gnutella(登録商標)、
【０００８】
【数１】
0005340232.tif 000002
OceanStore（登録商標）などP2Pサービスに対する注目が集まっている。P2Pは中心にサーバを置くのではなくネットワークを介して計算リソースを共有するところに大きな特徴がある（例えば、非特許文献２参照）。
【０００９】
P2Pを用いたアプリケーションの中でもインターネットを用いたコンテンツ配信は多くの研究者から注目される最も重要なもののひとつである。例えば、Kazaaとその亜種のネットワークは急激に成長していて、４５０万人以上のユーザが７ペタバイト以上のコンテンツを共有していることが知られている（例えば、非特許文献３参照）。これらアプリケーションにおいて各コンピュータはデータを互いに転送し合いコンテンツ配信を行っている。
【００１０】
各コンピュータが直接通信するコンピュータの数は、ネットワークで用いられるプロトコルによって制限される。ネットワークを設計するとき最も重要な問題として、各コンピュータが直接通信するコンピュータの数を何台とするかというものがある（例えば、非特許文献4参照）。この問題は2つの理由から重要である。1つ目の理由としてネットワークに接続するコンピュータの数は膨大であり直接通信するコンピュータの数は非常に大きくなりうることがあげられる。また、コンピュータ間のデータ転送はオーバヘッドであるため、効率的な配信のためには転送の数を減らすことが必要である。
【００１１】
ネットワークにおける直径は効率的なコンテンツ配信のための重要な指標である。それは直径がネットワークにおけるコンピュータ間の最大の転送回数と対応しているからである（例えば、非特許文献５参照）。直径が大きくなったときにのみ各コンピュータが直接通信するコンピュータを増やすことによって効率的なコンテンツ配信が可能になる。
【００１２】
上記以外にネットワークの頑健性の向上も重要なアプリケーションとしてあげられる。Koppulaらは動的に変化するグラフの直径をプロットすることにより、どのようにエッジを張り替えればネットワークの頑健性を向上できるかを示した（例えば、非特許文献６参照）。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】Newman, The Structure and Function of Complex Networks, SIREV: SIAM Review, 2003
【非特許文献２】Stephanos Androutsellis-Theotokis and Diomidis Spinellis, A survey of peer-to-peer content distribution technologies, ACM comput. Surv., 2004.
【非特許文献３】Mayank Bawa，  Brian F. Cooper，  Arturo Crespo，  Neil Daswani，  Prasanna Ganesan，  Hector Garcia-Molina, Sepandar D. Kamvar, Sergio Marti, Mario T. Schlosser, Qi Sun, Patrick Venograd and Beverly Yang, Peer-to-peer research at Stanford, SIGMOD Record, 2003.
【非特許文献４】Sylvia Ratnasamy, Ion Stoica and Scott Shenker, Routing Algorithms for DHTs: Some Open Questions, IPTPS, 2003.
【非特許文献５】AAbhishek Kumar, Shashidhar Merugu, Jun Xu and Xingxing Yu. Ulysses: A Robust, Low-Diameter, Low-Latency Peer-to-Peer Network, ICNP, 2003.
【非特許文献６】Hema Swetha Koppula, Kumar Puspesh and Nily Ganguly, Study and Improvement of Robustness of Overlay Networks, HiPC, 2007.
【発明の開示】
【発明が解決しようとする課題】
【００１４】
従来は、O(n2+nm)の計算時間（nとmはそれぞれノードとエッジ数）が必要であり、大規模なグラフの解析には実用的ではなかった。
【００１５】
本発明は、上記の点に鑑みなされたもので、グラフにおける直径を、従来より高速に求めることができ、また、元のグラフが時々刻々と成長しても効率的にグラフの近似を計算することが可能なグラフの直径のモニタリング装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１６】
上記の課題を解決するために、本発明（請求項１）は、実世界に存在するものの関係をノードとエッジで表現するデータ構造を有するグラフの直径をモニタリングするためのグラフの直径のモニタリング装置であって、
時刻毎に変化するノードを受信するデータ受信手段と、
受信したノード（追加ノード）及び、ノード間の距離が直径となる１時刻前の２つのノードの組である解ノードのペアと該ノード間の最大距離である直径を格納した記憶手段と、
ノード間の距離を計算する距離計算手段と、
前記記憶手段に格納されているノードからその他のノードまでの最大距離を前記距離計算手段により求め、直径になり得ないノードを枝刈りする枝刈り手段と、
前記記憶手段の直径となるノードのペアを、前記データ受信手段により追加されたノードからの距離に基づいて更新する更新手段と、を有する。
【００１７】
また、本発明（請求項２）は、前記枝刈り手段において、
前記記憶手段に格納された前記追加ノード及び１時刻前の解ノードから最も次数の高いノードである参照ノードを選択し、前記距離計算手段を用いて、前記記憶手段の１時刻前の解ノードのペアから候補距離を計算し、該参照ノードの周辺ノードに対してその他のノードまでの距離の最大値を推定し、該最大値が該候補距離より小さければ該ノードを探索対象から除外する手段を含む。
【００１８】
また、本発明（請求項３）は、前記更新手段において、
前記データ受信手段により追加されたノードにより直径が大きくなる、または、小さくなる、変化しない、のいずれかに応じて、前記記憶手段の前記解ノードのペアと直径を更新する手段を含む。
【００１９】
また、本発明（請求項４）は、前記更新手段において、
前記最大距離が前記憶手段に格納されている１時刻前の直径よりも大きければ、該直径を該最大距離とし、該記憶手段の解ノードペアを更新し、該最大距離が１時刻前の直径と同じ長さのノードのペアがあれば、該追加ノードからの距離を用いて該記憶手段の解ノードのペアを更新し、１時刻前の直径と同じ距離のペアがなければ、前記距離計算手段により直径を求める手段、を含む。
【００２０】
また、本発明（請求項５）は、実世界に存在するものの関係をノードとエッジで表現するデータ構造を有するグラフの直径をモニタリングするためのグラフの直径のモニタリング方法であって、
受信されたノード及びノード間の距離が直径となる１時刻前の２つのノードの組である解ノードのペアと該ノード間の最大距離である直径を格納した記憶手段と、データ受信手段、ノード間の距離を求める距離計算手段、枝刈り手段、更新手段を有する装置において、
前記データ受信手段が、時刻毎に変化するノードを受信するデータ受信ステップと、
前記枝刈り手段が、前記記憶手段に格納されているノードからその他のノードまでの最大距離を前記距離計算手段により求め、直径になり得ないノードを枝刈りする枝刈りステップと、
前記更新手段が、前記記憶手段の直径となるノードのペアを、前記データ受信手段により追加されたノードからの距離に基づいて更新する更新ステップと、を行う。
【００２１】
また、本発明（請求項６）は、前記枝刈りステップにおいて、
前記記憶手段に格納された前記追加ノード及び１時刻前の解ノードから最も次数の高いノードである参照ノードを選択し、前記距離計算手段を用いて、前記記憶手段の１時刻前の解ノードのペアから候補距離を計算し、該参照ノードの周辺ノードに対してその他のノードまでの距離の最大値を推定し、該最大値が該候補距離より小さければ該ノードを探索対象から除外する。
【００２２】
また、本発明（請求項７）は、前記更新ステップにおいて、
前記データ受信ステップにより追加されたノードにより直径が大きくなる、または、小さくなる、変化しない、のいずれかに応じて、前記記憶手段の前記解ノードのペアと直径を更新する法。
【００２３】
また、本発明（請求項８）は、前記更新ステップにおいて、
前記最大距離が前記憶手段に格納されている１時刻前の直径よりも大きければ、該直径を該最大距離とし、該記憶手段の解ノードペアを更新し、該最大距離が１時刻前の直径と同じ長さのノードのペアがあれば、該追加ノードからの距離を用いて該記憶手段の解ノードのペアを更新し、１時刻前の直径と同じ距離のペアがなければ、前記距離計算手段により直径を求める。
【００２４】
また、本発明（請求項９）は、請求項１乃至４のいずれか１項に記載のグラフの直径モニタリング装置を構成する各手段としてコンピュータを機能させるためのプログラムである。
【発明の効果】
【００２５】
上記のように、従来の技術は大規模なグラフの解析には実用的ではなかったが、本発明によれば、大幅に高速に直径を求めることができる。グラフの近似は元のグラフが時々刻々と成長しても効率的に計算することができる。
【００２６】
また、本発明によれば、近似よって解になり得ないノードを枝刈りするが、得られる解は正確である。
【００２７】
また、本発明によれば、自動的に必要となるパラメータを決定するため、ユーザはパラメータ調整する必要がない。
【図面の簡単な説明】
【００２８】
【図１】本発明の一実施の形態におけるモニタリング装置の構成図である。
【図２】本発明の一実施の形態における参照ノードの枝刈りのアルゴリズムである。
【図３】グラフの直径の変化である。
【図４】本発明の一実施の形態における逐次的更新のアルゴリズムである。
【発明を実施するための形態】
【００２９】
以下図面と共に、本発明の実施の形態を説明する。
【００３０】
本実施の形態では、以下の問題を対象とする。
【００３１】
＜問題＞
グラフにおける直径を求める：
Given:時刻tにおける重みなし無向グラフG[t] = (V,E)：
Find: G[t]における直径の値とそれを与えるノードのペア：
なお、ここで、VとEはそれぞれノードとエッジの集合とする。この問題は重みなし無向グラフを対象とするが、本発明は重みありグラフに対しても有向グラフに対しても適用することができる。
【００３２】
また、本発明はノードの追加のみでなく、エッジの追加に対してもノード／エッジの削除に対しても適用することができる。
【００３３】
図１は、本発明の一実施の形態におけるモニタリング装置の構成を示す。
【００３４】
同図に示すモニタリング装置は、データ受信部１０、距離計算部２０、データ記憶部３０、検出部４０から構成される。
【００３５】
データ受信部１０は、時刻毎に変化するノードを受信し、距離計算部２０及びデータ記憶部３０に転送する。距離計算部２０は、ノード間の距離を計算する。データ記憶部３０は、データ受信部１０から入力された追加ノード、及び、グラフ（ノード間の最大距離である直径）と１時刻前の解ノードのペアを格納する。検出部４０は、参照ノードの選択、及びグラフにおいて直径を計算する。
【００３６】
まず、本明細書で用いる記号を定義し、必要となる背景知識を説明する。
【００３７】
実世界のネットワークはグラフG = (V,E)として表現することができる。ここで、Vはノードの集合とし、Eはエッジの集合とする。また、nとｍはそれぞれノードとエッジの数とする。すなわち、n=｜V|であり、m=|E|である。
【００３８】
「ノードuからノードｖまでのパス」とは、ノードuから始まりノードｖで終わるエッジの並びである。パスの中に含まれるノードが最も少ないものは「最短パス」と呼ばれる。ノードuとノードｖの距離は最短パスに含まれるエッジ数の合計であり、
エッジ数の合計＝d(u,v)
と定義される。定義からノードu∈Vに対してd(u,u)＝０であり、ノードu,v∈Vに対して、d(u,v)=d(v,u)となる。
【００３９】
グラフの直径は以下のようにノード間の最大の距離として定義される。
【００４０】
[定義１]（直径）
グラフG = (V,E)において、ノード間の最大の距離をmax(d(u,v)|u,v∈V)としたとき、直径Dは以下のように定義される。
【００４１】
D=max(d(u,v)｜u,v∈V)                      （１）
本発明は、グラフの直径のみでなく、直径となるノードのペアの集合Dも計算する。Dは定式的に以下のように定義される。
【００４２】
[定義２]（解ノードのペア）
ノード間の距離が直径となるノードのペアDは以下のように定義される。
【００４３】
D={(u,v)|d(u,v)=D}                          （２）
正確にグラフの直径を計算するには、従来は幅優先探索が用いられていた。幅優先探索は、グラフの探索において広く使われている手法である。幅優先探索はグラフG = (V,E)が与えられたときに始点ノードuから到達可能な周辺のノードを辿りながら徐々に距離を計算していく。ノードuの中心性を計算するために既存の手法では、幅優先探索を用いてノードuからその他全てのノードまでの距離を計算し、距離の合計を計算する。
【００４４】
幅優先探索を用いて直径を計算するためにはO(n2+nm)の計算量が必要となる。これは全てのn個のノードに対してO(n+m)の計算量が必要になる幅優先探索を行うからである。そのためグラフが大規模になるとこの処理には莫大な計算量が必要となる。また、時々刻々と成長するグラフに対してはグラフが成長するためにこの処理を繰り返すこととなるために、幅優先探索により直径をノードから求めるのは現実的ではない。
【００４５】
これに対し、本発明は、検出部４０において、「参照ノードによる枝刈り」と、「逐次的更新」を行う。
【００４６】
（Ａ）参照ノードによる枝刈り：
この手法は、検出部４０において、高い計算時間を減らすために直径になりえないノードを高速に枝刈りするものである。
【００４７】
従来手法では、ｎ個のノード全てから幅優先探索を行うため非常に高い計算コストになる。
【００４８】
本発明では、全てのノードから距離を計算する代わりに、枝刈りされていないノードの中で最も次数の高いノード（以下、「参照ノード」と記す）を選択し、当該参照ノードからのみ距離を計算するというシンプルなものである。
【００４９】
検出部４０は、一つ一つ参照ノードを選択し、参照ノードからその他の枝刈り対象のノード間の距離に基づいて、その周辺のノードが解ノードのペアとなり得るかを推定する。すなわち、参照ノードによってその周辺のノードの枝刈りを行う。それぞれの周辺のノードに対して推定はO(1)の計算時間で行うことができる。そのため参照ノードの個数をｋ（ｋ≪ｎ）としたとき、O(kn + km)の計算時間で直径を求めることができる。
【００５０】
この手法は、２つの利点を有する。１つは、参照ノードからの距離が近い周辺のノードを推定値によって枝刈りするが、正確に直径を求められることがあげられる。すなわち、この手法は少ない計算時間で解になり得ないノードを安全に枝刈りできる。また、参照ノードの個数ｋは自動的に決定される。一般的にアルゴリズムのパラメータはその性能に大きく影響するためその決定は煩雑であるが、本発明は、パラメータを自動的に決定するためユーザに対してパラメータの決定を求めない。
【００５１】
（Ｂ）逐次的更新：
当該逐次的更新とは、時々刻々と成長するグラフにノードが追加された後、直径は大きくなるか、縮むか、変化しない、のいずれかである。ノードが追加された後に、直径を効率的に更新する処理であり、検出部４０で行われる。
【００５２】
参照ノードによる枝刈りによって高速に直径を求めることができるが、グラフが成長する場合はその度に参照ノードによる再計算が必要になる。本手法は、グラフが成長する度に参照ノードによる枝刈りを避けるためのものである。後に述べるように、もし直径がノードの追加によって縮まなければ、直径は追加されたノードからの距離だけで更新することができる。
【００５３】
この手法は特に時々刻々と成長するグラフに対して有効である。それは追加されるノードは元々存在するノードに比べて少ないため、追加の前後で大きくグラフは変化しないためである。
【００５４】
上記の（Ａ）の参照ノードによる枝刈りと（Ｂ）の逐次的更新について、以下に説明する。
【００５５】
まず、上記の（Ａ）の手法を詳細に説明する。
【００５６】
上記の（Ａ）の手法は、参照ノードを選択し、直径になり得ないノードを枝刈り（探索対象から除外）するものである。
【００５７】
参照ノードによる枝刈りは以下のように行う。
【００５８】
（１）距離計算部２０は、参照ノードからその他のノードまでの距離が長くなることが期待される候補距離を計算し、検出部４０に出力する。
【００５９】
（２）検出部４０は、その他のノードまでの距離が短くなることが期待される参照ノードを選択する。
【００６０】
（３）検出部４０は、データ記憶部３０に格納されている参照ノードの周辺ノードに対して、その他のノードまでの距離の最大値を推定する。
【００６１】
（４）検出部４０は、推定された最大値が候補距離より小さければそのノードを枝刈りする。
【００６２】
ここでは、まずノードに対して最大の距離を推定する方法について述べ、その推定値が最大の距離の上限値となることを示す。そして、検出部４０において参照ノードを選択する方法と距離計算部２０において候補距離を求める方法について述べる。
【００６３】
定式的に、グラフのある１つのノードｕからデータ記憶部３０内に格納されている他のノードまでの距離の最大値を以下のように定義する。
【００６４】
［定義３］（最大距離）
グラフGにおいてその他のノードまでの距離の最大値dmax（u）、を以下のように定義する。
【００６５】
dmax(u) = max(d(u,v)|v∈Ｖ)              （３）
最大距離の推定値は以下のように定義する。
【００６６】
［定義４］（推定値）
グラフGのｖノードに対して参照ノードをｕrとしたとき、最大距離の推定値
【００６７】
【数２】
0005340232.tif 000003
を以下のように定義する。
【００６８】
【数３】
0005340232.tif 000004
推定値は以下に述べるように、距離の最大値の上限値となる性質がある。
【００６９】
［補助定理１］（上限値）
グラフGの全てのノードに対して以下の性質が成り立つ。
【００７０】
【数４】
0005340232.tif 000005
証明）
ノードvからの距離がdmax (v)であるノードをｗとすると以下の式が成り立つ。
【００７１】
【数５】
0005340232.tif 000006
よって成り立つ。
【００７２】
本発明は後述するように、距離計算部２０は、この性質を用いて正確な直径を求めることができる。
【００７３】
もし、推定値が候補距離より短ければ、そのノードを枝刈りする。上記の定義４に見られるように、推定値はO(1)の計算時間で求めることができるため、効率的に直径を計算することができる。
【００７４】
もし、参照ノードの最大距離が長く、また、候補距離が短ければ効率的に枝刈りすることができない。そのため、効果的に枝刈りを行うためには参照ノードと候補距離の選択が重要である。本発明では、データ記憶部３０内の全てのノードのうち直径になる可能性のある枝刈りされていないノードの中で最も次数の高いノードを参照ノードとして選択する。これはそのようなノードの最大距離が小さいことが期待されるからである。
【００７５】
また、本発明では１時刻前の解ノードのペアから候補距離を計算する。これはノードが追加されてもグラフはほとんど変化しないため、これらのノードのペアは長い距離となることが期待されるからである。
【００７６】
図２のアルゴリズム１に、参照ノードによる枝刈りの手法を示す。
【００７７】
ここで、ノードｕの次数をdeg(u)とする。アルゴリズム１では、
１）データ記憶部３０のまず１時刻前の解のペアを用いて候補距離を計算する（１行目）。
【００７８】
２）そして次数に基づいて参照ノードを求める（５行目）。
【００７９】
３）もし参照ノードの最大距離が候補距離以上であれば、解ノードのペアを更新する（７〜１３行目）。
【００８０】
４）アルゴリズムは候補距離の枝刈りのために用いる。すなわち、もしあるノードにおける推定値が候補距離より小さければ、そのノードを枝刈りする（１５行目）。
【００８１】
これらの処理は全てのノードが処理されるまで繰り返される。このアルゴリズムにおいて参照ノードの数は自動的に決定される。
【００８２】
次に、上記（Ｂ）の逐次的更新の手法について説明する。
【００８３】
当該手法は、検出部４０において、直径を高速に検出するために解ノードのペアを逐次的に更新するものである。参照ノードによる枝刈りをグラフが成長する度に行う必要がなくなるため、より効率的な検出が可能になる。
【００８４】
まず、グラフが成長した後のノード間の距離の性質について述べる。そして、直径の（１）大きくなる、（２）縮む、（３）変化しない、必要充分条件を明らかにする。
【００８５】
ここでは、１時刻毎にデータ記憶部３０にノードuaが新たに加わるとする。
【００８６】
まず、ノードが追加された後は追加前に存在するノード間の距離は増えることが無いことを示す。
【００８７】
［補助定理２］（ノード追加後のノード間の距離）
時刻ｔにおけるノード間の距離は時刻ｔ−１におけるグラフGt-1におけるノード間の距離より長くなることはない。
【００８８】
証明）もし時刻ｔにおけるノードｕとｖの最短パスが追加ノードを通るとすると、時刻ｔ−１においてそれに対応するパスは存在しない。すなわち、時刻ｔ−１における最短パスは追加ノードによって短くなる。そうでなければ時刻ｔにおいて追加ノードを通らないノードｕとｖの最短パスが存在する。すなわち、時刻ｔ−１においても同じパスが存在する。結果ノードｕとｖの距離はノードの追加によって長くなることはない。
【００８９】
ノードが追加された後直径は変化するが、上記の性質を用いてグラフの直径が変化する条件を明らかにする。グラフの直径が変化する例を図３に示す。図３において、元から存在するノードは白い丸、新たに追加したノードは灰色の丸として表現する。
【００９０】
まず、グラフが大きくなる条件を述べる。
【００９１】
グラフが大きくなる必要充分条件は、追加したノードの最大距離が１時刻前の直径よりも大きいことである。
【００９２】
［補助定理３］（直径が大きくなる必要十分条件）
グラフの直径が大きくなる必要十分条件は以下のとおりである。
【００９３】
d max (ua )> Dt-1                    （７）
証明）もし、Dt > Dt-1であれば補助定理２より元から存在する全てのノードの最大距離はD t-1より長くなることはないため、ノードuaの最大距離が直径となる。また、もし、dmax (ua) > Dt-1であれば明らかにdmax (ua) = Dtであり、Dt ＞ Dt-1が成り立つ。
【００９４】
グラフの直径が縮むことの必要十分条件は、追加ノードの最大距離が１時刻前の直径より短くかつノードの追加によって１時刻前の全ての解ノードのペアの距離が短くなることである。
【００９５】
［補助定理４］（直径が縮む必要十分条件）
グラフの直径が縮むことの必要十分条件は以下のとおりである。
【００９６】
【数６】
0005340232.tif 000007
証明）もし、Dt < Dt-1であれば、定義２よりdmax (ua)< Dt-1でありかつ１時刻前の全ての解ノードのペアの距離がDt-1より短くなる。またもし式（１）と式（２）が成り立つのであれば定義２と補助定理２よりグラフの直径は時刻ｔで短くなる。
【００９７】
グラフの直径が変化しないことの必要十分条件は追加ノードの最大距離が１時刻前の直径と同じまたはノードの追加によって距離が縮まない１時刻前の解ノードのペアが存在することである。
【００９８】
［補助定理５］（直径が変化しない必要十分条件）
グラフの直径が変化しないことの必要十分条件は以下のとおりである。
【００９９】
【数７】
0005340232.tif 000008
証明）補助定理３と４より明らか。
【０１００】
逐次的に解ノードのペアを更新することにより効率的に直径を検出できる。まず、１時刻前の解ノードのペアの距離が短くなるのかの確認は追加ノードからの距離を用いて可能であることを示し、逐次的更新を用いた本発明の詳細について述べる。
【０１０１】
解ノードのペアを更新するため、本発明では、最短パスにおける以下の性質（例えば、文献「Ulrik Brandes, A Faster Algorithm for Betweenness Centrality, Journal of Mathematical Sociology, 2001」を用いる。
【０１０２】
［補助定理６］（Bellman criterion）
ノードｕがノードｖとｗの最短パス上にあることの必要十分条件は以下のとおりである。
【０１０３】
d(u,v) + d(u,w) = d(v,w)                    （１０）
定理６を用いてノードの追加によって１時刻前の解ノードのペアの距離が短くなるのかの確認ができる。
【０１０４】
［補助定理７］（距離の確認）
時々刻々と成長するグラフにおいてノードuaが１時刻前の解ノードのペア（v,w）の距離を縮めることの必要十分条件は以下のとおりである。
【０１０５】
d(v,ua) + d(w,ua) < Dt-1                        （１１）
証明）もし、ノードuaが距離を縮めるのであればノードuaはノードvとｗの最短パス上にある。そのため補助定理６より
Dt-1 > d(v,w)=d(ua,v) + d(ua,w)
が成り立つ。
【０１０６】
また、もし、
d(v,ua) + (d(w,ua) < Dt-1
であれば、追加ノードuaは
Dt-1 > d(ua,v) + d(uaw) ≧ d(v,w)
が成り立つため距離を縮める。
【０１０７】
定理７より、もしグラフの直径が大きくなるか変わらない場合は解ノードのペアを追加ノードの距離から逐次的に更新することができる。すなわち、検出部４０は、もし追加ノードが直径となるのであれば追加ノードからの距離を用いて解ノードのペアを更新する。また、もし追加ノードが１時間前の解ノードのペアの距離を縮めるのであれば、そのことを補助定理７を用いて効率的に求める。また、もし１時刻前の直径と同じ長さのノードのペアがなければ距離計算部２０において参照ノードによる枝刈りを用いて直径を求める。
【０１０８】
図４に、逐次的更新のアルゴリズムを示す。
【０１０９】
（１）まず、追加したノードの最大距離を求める（１行目）。
【０１１０】
（２）もしその最大距離が、データ記憶部３０に格納されている１時刻前の直径より大きければそれが新しい直径になるため（補助定理３）、直径と解ノードのペアを初期化してデータ記憶部３０に書き込む（３〜５行目）。
【０１１１】
（３）もし、求めた最大距離が１時刻前の直径と同じかまたは１時刻前の直径と同じ長さのノードのペアがあればノードが追加されても直径は変わらない（補助定理５）。そのため、当該手法では、追加ノードからの距離を用いて解ノードのペアを更新し、データ記憶部３０に書き込む。
【０１１２】
（４）また、もし１時刻前の直径と同じ距離のノードのペアがなければ直径は縮むため（補助定理４）、距離計算部２０にて、前述の図２のアルゴリズム１によって直径を求める（１５〜１７行目）。
【０１１３】
ノードの数を増やしながらグラフは成長していくが、簡単のため時刻ｔ＝１においてノードは一つあるとする。そのため時刻ｔ＝１において、Dt-1＝０でありDt-1≠０である。
【０１１４】
今まで一つのノードが追加されることを前提に議論を進めてきたが、本発明は複数のノードが追加されても対応することができる。また、もしエッジが追加されたらそのエッジに接続されたノードが追加されたものとして処理を行う。また、ノード／エッジが削除された場合は図２のアルゴリズム１によって直径を求める。
【０１１５】
次に、本発明が正確に直径を検出できることと、その計算量を示す。
【０１１６】
なお、参照ノードの数kとする。
【０１１７】
[1]  直径検出の正確さ
まず、本発明により正確に直径を検出できることを示す。
【０１１８】
[補助定理８]（正確な検出）
本発明は正確に直径を検出できる。
【０１１９】
証明）時刻t（≧１）で本発明が正確な検出を行うことができることを数学的帰納法を用いて証明する。
【０１２０】
まず、時刻t=1で正確な検出を行えることを示す。時刻t=1で正確な検出を行えることを示す。時刻t=1において、本発明はD１＝0でD１=(u１,u１)であることを
（１）Dt-1=0でDt-1≠０であり、
（２）dmax (u１)=0であるため求めることができる（図４のアルゴリズム２の８〜12行目参照）。
【０１２１】
また、時刻t=kにおいて正確な検出が行えるとした場合、時刻t=k+1でも正確な検出が行えることを示す。もし時刻t=k+1で直径が縮まなければ補助定理７を用いて、本発明は正確な検出を行うことができる。また、もしそうでなければ本発明は参照ノードによる枝刈りにより直径を求める。ここで推定値が候補距離より小さければノードが枝刈りされるが、推定値は上限値になる性質がある（補助定理１）。そのため、直径となるノードが枝刈りされることはあり得ない。よって成り立つ。
【０１２２】
[2]計算量
ここではまず従来手法の計算量について述べてから、本発明の計算量について述べる。
【０１２３】
[補助定理９]（従来手法）
従来手法で直径を求めるにはO(n+m)のメモリ量とO(n2+nm)の計算時間が必要である。
【０１２４】
証明）従来手法では隣接リスト表現でグラフを保持するためO(n+m)のメモリ量が必要である。また、n個の全てのノードから距離をそれぞれO(n+m)の計算時間が必要である。
【０１２５】
[補助定理１０]（本発明のメモリ量）
本発明は、O(n+m)のメモリ量が必要である。
【０１２６】
証明）本発明はグラフを保持するメモリ量と解ノードのペアを保持するメモリ量が必要であるが、解ノードのペアの数はノード／エッジ数に比例して非常に小さい。そのため、本発明は、O(n+m)のメモリ量が必要である。
【０１２７】
[補助定理１１]（本発明の計算時間）
本発明においては直径が縮まない場合O(n+m)の計算時間が必要であり、直径が縮む場合O(kn+km)の計算時間が必要である。
【０１２８】
証明）本発明はまず追加されたノードから距離を計算し、直径が縮むかの確認を行う。このために必要な計算時間はO(n+m)である。もし直径が縮む場合、本発明は参照ノードによる枝刈りによって直径を求めるがこの場合の計算時間はO(km+km)である。
【０１２９】
なお、本発明は、図１に示すモニタリング装置の構成要素の動作をプログラムとして構築し、モニタリング装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【０１３０】
また、構築されたプログラムをハードディスクやフレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【０１３１】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【０１３２】
１０  データ受信部
２０  距離計算部
３０  データ記憶部
４０  検出部
【図１】
0005340232.tif 000009
【図２】
0005340232.tif 000010
【図３】
0005340232.tif 000011
【図４】
0005340232.tif 000012