JP5340232B2

JP5340232B2 - グラフの直径のモニタリング装置及び方法及びプログラム

Info

Publication number: JP5340232B2
Application number: JP2010165143A
Authority: JP
Inventors: 靖宏藤原
Original assignee: Nippon Telegraph and Telephone Corp; NTT Inc USA
Current assignee: NTT Inc; NTT Inc USA
Priority date: 2010-07-22
Filing date: 2010-07-22
Publication date: 2013-11-13
Anticipated expiration: 2030-07-22
Also published as: JP2012027654A

Description

本発明は、グラフの直径のモニタリング装置及び方法及びプログラムに係り、特に、時々刻々と増大するグラフの直径をモニタリングするためのグラフの直径のモニタリング装置及び方法及びプログラムに関する。

グラフは実世界に存在するものとそれらの関係をノードとエッジという形で表現するデータ構造である。その直感的な表現方法によりグラフは数学やコンピュータ科学の分野において広く使われている。

グラフにおけるノード間の距離はグラフ理論の中で基本的な特徴量の一つである。グラフの直径とは、ノード間の距離に基づいた特徴量であり、グラフを解析する上で非常に重要である。しかし、従来のグラフ理論が対象としてきたグラフは静的であり、ノード及びエッジの数は変わらないという前提があった。

近年、時間と共にノード数が時々刻々と増大し、結果的にノード数が数十万以上になるグラフデータを扱うことが必要となってきた。これは巨大なデータベースとインターネットを用いる環境が整ってきた結果である。そして、近年の研究により時々刻々とノードの数を増やしながら成長し続けるグラフデータの特徴が明らかになりつつある（例えば、非特許文献１参照）。そのため時々刻々と成長し、結果的に非常に大きなサイズになるグラフを効率的に処理する需要が高まりつつある。

本発明では、時々刻々と成長し続けるグラフの中から直径を検出し続ける問題を扱う。

本明細書が対象とする問題の応用例としてP2P（ポイントツーポイント）ネットワークがあげられる。

近年、Gnutella(登録商標)、

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(n²+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(n²+nm)の計算量が必要となる。これは全てのn個のノードに対してO(n+m)の計算量が必要になる幅優先探索を行うからである。そのためグラフが大規模になるとこの処理には莫大な計算量が必要となる。また、時々刻々と成長するグラフに対してはグラフが成長するためにこの処理を繰り返すこととなるために、幅優先探索により直径をノードから求めるのは現実的ではない。

これに対し、本発明は、検出部４０において、「参照ノードによる枝刈り」と、「逐次的更新」を行う。

（Ａ）参照ノードによる枝刈り：
この手法は、検出部４０において、高い計算時間を減らすために直径になりえないノードを高速に枝刈りするものである。

従来手法では、ｎ個のノード全てから幅優先探索を行うため非常に高い計算コストになる。

本発明では、全てのノードから距離を計算する代わりに、枝刈りされていないノードの中で最も次数の高いノード（以下、「参照ノード」と記す）を選択し、当該参照ノードからのみ距離を計算するというシンプルなものである。

検出部４０は、一つ一つ参照ノードを選択し、参照ノードからその他の枝刈り対象のノード間の距離に基づいて、その周辺のノードが解ノードのペアとなり得るかを推定する。すなわち、参照ノードによってその周辺のノードの枝刈りを行う。それぞれの周辺のノードに対して推定はO(1)の計算時間で行うことができる。そのため参照ノードの個数をｋ（ｋ≪ｎ）としたとき、O(kn + km)の計算時間で直径を求めることができる。

この手法は、２つの利点を有する。１つは、参照ノードからの距離が近い周辺のノードを推定値によって枝刈りするが、正確に直径を求められることがあげられる。すなわち、この手法は少ない計算時間で解になり得ないノードを安全に枝刈りできる。また、参照ノードの個数ｋは自動的に決定される。一般的にアルゴリズムのパラメータはその性能に大きく影響するためその決定は煩雑であるが、本発明は、パラメータを自動的に決定するためユーザに対してパラメータの決定を求めない。

（Ｂ）逐次的更新：
当該逐次的更新とは、時々刻々と成長するグラフにノードが追加された後、直径は大きくなるか、縮むか、変化しない、のいずれかである。ノードが追加された後に、直径を効率的に更新する処理であり、検出部４０で行われる。

参照ノードによる枝刈りによって高速に直径を求めることができるが、グラフが成長する場合はその度に参照ノードによる再計算が必要になる。本手法は、グラフが成長する度に参照ノードによる枝刈りを避けるためのものである。後に述べるように、もし直径がノードの追加によって縮まなければ、直径は追加されたノードからの距離だけで更新することができる。

この手法は特に時々刻々と成長するグラフに対して有効である。それは追加されるノードは元々存在するノードに比べて少ないため、追加の前後で大きくグラフは変化しないためである。

上記の（Ａ）の参照ノードによる枝刈りと（Ｂ）の逐次的更新について、以下に説明する。

まず、上記の（Ａ）の手法を詳細に説明する。

上記の（Ａ）の手法は、参照ノードを選択し、直径になり得ないノードを枝刈り（探索対象から除外）するものである。

参照ノードによる枝刈りは以下のように行う。

（１）距離計算部２０は、参照ノードからその他のノードまでの距離が長くなることが期待される候補距離を計算し、検出部４０に出力する。

（２）検出部４０は、その他のノードまでの距離が短くなることが期待される参照ノードを選択する。

（３）検出部４０は、データ記憶部３０に格納されている参照ノードの周辺ノードに対して、その他のノードまでの距離の最大値を推定する。

（４）検出部４０は、推定された最大値が候補距離より小さければそのノードを枝刈りする。

ここでは、まずノードに対して最大の距離を推定する方法について述べ、その推定値が最大の距離の上限値となることを示す。そして、検出部４０において参照ノードを選択する方法と距離計算部２０において候補距離を求める方法について述べる。

定式的に、グラフのある１つのノードｕからデータ記憶部３０内に格納されている他のノードまでの距離の最大値を以下のように定義する。

［定義３］（最大距離）
グラフGにおいてその他のノードまでの距離の最大値d_max（u）、を以下のように定義する。

d_max(u) = max(d(u,v)|v∈Ｖ) （３）
最大距離の推定値は以下のように定義する。

［定義４］（推定値）
グラフGのｖノードに対して参照ノードをｕ_rとしたとき、最大距離の推定値

を以下のように定義する。

推定値は以下に述べるように、距離の最大値の上限値となる性質がある。

［補助定理１］（上限値）
グラフGの全てのノードに対して以下の性質が成り立つ。

証明）
ノードvからの距離がd_max (v)であるノードをｗとすると以下の式が成り立つ。

よって成り立つ。

本発明は後述するように、距離計算部２０は、この性質を用いて正確な直径を求めることができる。

もし、推定値が候補距離より短ければ、そのノードを枝刈りする。上記の定義４に見られるように、推定値はO(1)の計算時間で求めることができるため、効率的に直径を計算することができる。

もし、参照ノードの最大距離が長く、また、候補距離が短ければ効率的に枝刈りすることができない。そのため、効果的に枝刈りを行うためには参照ノードと候補距離の選択が重要である。本発明では、データ記憶部３０内の全てのノードのうち直径になる可能性のある枝刈りされていないノードの中で最も次数の高いノードを参照ノードとして選択する。これはそのようなノードの最大距離が小さいことが期待されるからである。

また、本発明では１時刻前の解ノードのペアから候補距離を計算する。これはノードが追加されてもグラフはほとんど変化しないため、これらのノードのペアは長い距離となることが期待されるからである。

図２のアルゴリズム１に、参照ノードによる枝刈りの手法を示す。

ここで、ノードｕの次数をdeg(u)とする。アルゴリズム１では、
１）データ記憶部３０のまず１時刻前の解のペアを用いて候補距離を計算する（１行目）。

２）そして次数に基づいて参照ノードを求める（５行目）。

３）もし参照ノードの最大距離が候補距離以上であれば、解ノードのペアを更新する（７〜１３行目）。

４）アルゴリズムは候補距離の枝刈りのために用いる。すなわち、もしあるノードにおける推定値が候補距離より小さければ、そのノードを枝刈りする（１５行目）。

これらの処理は全てのノードが処理されるまで繰り返される。このアルゴリズムにおいて参照ノードの数は自動的に決定される。

次に、上記（Ｂ）の逐次的更新の手法について説明する。

当該手法は、検出部４０において、直径を高速に検出するために解ノードのペアを逐次的に更新するものである。参照ノードによる枝刈りをグラフが成長する度に行う必要がなくなるため、より効率的な検出が可能になる。

まず、グラフが成長した後のノード間の距離の性質について述べる。そして、直径の（１）大きくなる、（２）縮む、（３）変化しない、必要充分条件を明らかにする。

ここでは、１時刻毎にデータ記憶部３０にノードu_aが新たに加わるとする。

まず、ノードが追加された後は追加前に存在するノード間の距離は増えることが無いことを示す。

［補助定理２］（ノード追加後のノード間の距離）
時刻ｔにおけるノード間の距離は時刻ｔ−１におけるグラフG_t-1におけるノード間の距離より長くなることはない。

証明）もし時刻ｔにおけるノードｕとｖの最短パスが追加ノードを通るとすると、時刻ｔ−１においてそれに対応するパスは存在しない。すなわち、時刻ｔ−１における最短パスは追加ノードによって短くなる。そうでなければ時刻ｔにおいて追加ノードを通らないノードｕとｖの最短パスが存在する。すなわち、時刻ｔ−１においても同じパスが存在する。結果ノードｕとｖの距離はノードの追加によって長くなることはない。

ノードが追加された後直径は変化するが、上記の性質を用いてグラフの直径が変化する条件を明らかにする。グラフの直径が変化する例を図３に示す。図３において、元から存在するノードは白い丸、新たに追加したノードは灰色の丸として表現する。

まず、グラフが大きくなる条件を述べる。

グラフが大きくなる必要充分条件は、追加したノードの最大距離が１時刻前の直径よりも大きいことである。

［補助定理３］（直径が大きくなる必要十分条件）
グラフの直径が大きくなる必要十分条件は以下のとおりである。

d_max (u_a)> D_t-1 （７）
証明）もし、D_t > D_t-1であれば補助定理２より元から存在する全てのノードの最大距離はD_t-1より長くなることはないため、ノードu_aの最大距離が直径となる。また、もし、d_max (u_a) > D_t-1であれば明らかにd_max (u_a) = D_tであり、D_t ＞ D_t-1が成り立つ。

グラフの直径が縮むことの必要十分条件は、追加ノードの最大距離が１時刻前の直径より短くかつノードの追加によって１時刻前の全ての解ノードのペアの距離が短くなることである。

［補助定理４］（直径が縮む必要十分条件）
グラフの直径が縮むことの必要十分条件は以下のとおりである。

証明）もし、D_t < D_t-1であれば、定義２よりd_max (u_a)< D_t-1でありかつ１時刻前の全ての解ノードのペアの距離がD_t-1より短くなる。またもし式（１）と式（２）が成り立つのであれば定義２と補助定理２よりグラフの直径は時刻ｔで短くなる。

グラフの直径が変化しないことの必要十分条件は追加ノードの最大距離が１時刻前の直径と同じまたはノードの追加によって距離が縮まない１時刻前の解ノードのペアが存在することである。

［補助定理５］（直径が変化しない必要十分条件）
グラフの直径が変化しないことの必要十分条件は以下のとおりである。

証明）補助定理３と４より明らか。

逐次的に解ノードのペアを更新することにより効率的に直径を検出できる。まず、１時刻前の解ノードのペアの距離が短くなるのかの確認は追加ノードからの距離を用いて可能であることを示し、逐次的更新を用いた本発明の詳細について述べる。

解ノードのペアを更新するため、本発明では、最短パスにおける以下の性質（例えば、文献「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,u_a) + d(w,u_a) < D_t-1 （１１）
証明）もし、ノードu_aが距離を縮めるのであればノードu_aはノードvとｗの最短パス上にある。そのため補助定理６より
D_t-1 > d(v,w)=d(u_a,v) + d(u_a,w)
が成り立つ。

また、もし、
d(v,u_a) + (d(w,u_a) < D_t-1
であれば、追加ノードu_aは
D_t-1 > d(u_a,v) + d(u_aw) ≧ d(v,w)
が成り立つため距離を縮める。

定理７より、もしグラフの直径が大きくなるか変わらない場合は解ノードのペアを追加ノードの距離から逐次的に更新することができる。すなわち、検出部４０は、もし追加ノードが直径となるのであれば追加ノードからの距離を用いて解ノードのペアを更新する。また、もし追加ノードが１時間前の解ノードのペアの距離を縮めるのであれば、そのことを補助定理７を用いて効率的に求める。また、もし１時刻前の直径と同じ長さのノードのペアがなければ距離計算部２０において参照ノードによる枝刈りを用いて直径を求める。

図４に、逐次的更新のアルゴリズムを示す。

（１）まず、追加したノードの最大距離を求める（１行目）。

（２）もしその最大距離が、データ記憶部３０に格納されている１時刻前の直径より大きければそれが新しい直径になるため（補助定理３）、直径と解ノードのペアを初期化してデータ記憶部３０に書き込む（３〜５行目）。

（３）もし、求めた最大距離が１時刻前の直径と同じかまたは１時刻前の直径と同じ長さのノードのペアがあればノードが追加されても直径は変わらない（補助定理５）。そのため、当該手法では、追加ノードからの距離を用いて解ノードのペアを更新し、データ記憶部３０に書き込む。

（４）また、もし１時刻前の直径と同じ距離のノードのペアがなければ直径は縮むため（補助定理４）、距離計算部２０にて、前述の図２のアルゴリズム１によって直径を求める（１５〜１７行目）。

ノードの数を増やしながらグラフは成長していくが、簡単のため時刻ｔ＝１においてノードは一つあるとする。そのため時刻ｔ＝１において、D_t-1＝０でありD_t-1≠０である。

今まで一つのノードが追加されることを前提に議論を進めてきたが、本発明は複数のノードが追加されても対応することができる。また、もしエッジが追加されたらそのエッジに接続されたノードが追加されたものとして処理を行う。また、ノード／エッジが削除された場合は図２のアルゴリズム１によって直径を求める。

次に、本発明が正確に直径を検出できることと、その計算量を示す。

なお、参照ノードの数kとする。

[1] 直径検出の正確さ
まず、本発明により正確に直径を検出できることを示す。

[補助定理８]（正確な検出）
本発明は正確に直径を検出できる。

証明）時刻t（≧１）で本発明が正確な検出を行うことができることを数学的帰納法を用いて証明する。

まず、時刻t=1で正確な検出を行えることを示す。時刻t=1で正確な検出を行えることを示す。時刻t=1において、本発明はD_１＝0でD_１=(u_１,u_１)であることを
（１）D_t-1=0でD_t-1≠０であり、
（２）d_max (u_１)=0であるため求めることができる（図４のアルゴリズム２の８〜12行目参照）。

また、時刻t=kにおいて正確な検出が行えるとした場合、時刻t=k+1でも正確な検出が行えることを示す。もし時刻t=k+1で直径が縮まなければ補助定理７を用いて、本発明は正確な検出を行うことができる。また、もしそうでなければ本発明は参照ノードによる枝刈りにより直径を求める。ここで推定値が候補距離より小さければノードが枝刈りされるが、推定値は上限値になる性質がある（補助定理１）。そのため、直径となるノードが枝刈りされることはあり得ない。よって成り立つ。

[2]計算量
ここではまず従来手法の計算量について述べてから、本発明の計算量について述べる。

[補助定理９]（従来手法）
従来手法で直径を求めるにはO(n+m)のメモリ量とO(n²+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)である。

なお、本発明は、図１に示すモニタリング装置の構成要素の動作をプログラムとして構築し、モニタリング装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。

また、構築されたプログラムをハードディスクやフレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。

なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。

１０データ受信部
２０距離計算部
３０データ記憶部
４０検出部

Claims

実世界に存在するものの関係をノードとエッジで表現するデータ構造を有するグラフの直径をモニタリングするためのグラフの直径のモニタリング装置であって、
時刻毎に変化するノードを受信するデータ受信手段と、
受信したノード（追加ノード）及び、ノード間の距離が直径となる１時刻前の２つのノードの組である解ノードのペアと該ノード間の最大距離である直径を格納した記憶手段と、
ノード間の距離を計算する距離計算手段と、
前記記憶手段に格納されているノードからその他のノードまでの最大距離を前記距離計算手段により求め、直径になり得ないノードを枝刈りする枝刈り手段と、
前記記憶手段の直径となるノードのペアを、前記データ受信手段により追加されたノードからの距離に基づいて更新する更新手段と、
を有することを特徴とするグラフの直径のモニタリング装置。
前記枝刈り手段は、
前記記憶手段に格納された前記追加ノード及び１時刻前の解ノードから最も次数の高いノードである参照ノードを選択し、前記距離計算手段を用いて、前記記憶手段の１時刻前の解ノードのペアから候補距離を計算し、該参照ノードの周辺ノードに対してその他のノードまでの距離の最大値を推定し、該最大値が該候補距離より小さければ該ノードを探索対象から除外する手段を含む
請求項１記載のグラフの直径のモニタリング装置。
前記更新手段は、
前記データ受信手段により追加されたノードにより直径が大きくなる、または、小さくなる、変化しない、のいずれかに応じて、前記記憶手段の前記解ノードのペアと直径を更新する手段を含む
請求項１記載のグラフの直径のモニタリング装置。
前記更新手段は、
前記最大距離が前記憶手段に格納されている１時刻前の直径よりも大きければ、該直径を該最大距離とし、該記憶手段の解ノードペアを更新し、該最大距離が１時刻前の直径と同じ長さのノードのペアがあれば、該追加ノードからの距離を用いて該記憶手段の解ノードのペアを更新し、１時刻前の直径と同じ距離のペアがなければ、前記距離計算手段により直径を求める手段、
を含む請求項１記載のグラフの直径モニタリング装置。
実世界に存在するものの関係をノードとエッジで表現するデータ構造を有するグラフの直径をモニタリングするためのグラフの直径のモニタリング方法であって、
受信されたノード及びノード間の距離が直径となる１時刻前の２つのノードの組である解ノードのペアと該ノード間の最大距離である直径を格納した記憶手段と、データ受信手段、ノード間の距離を求める距離計算手段、枝刈り手段、更新手段を有する装置において、
前記データ受信手段が、時刻毎に変化するノードを受信するデータ受信ステップと、
前記枝刈り手段が、前記記憶手段に格納されているノードからその他のノードまでの最大距離を前記距離計算手段により求め、直径になり得ないノードを枝刈りする枝刈りステップと、
前記更新手段が、前記記憶手段の直径となるノードのペアを、前記データ受信手段により追加されたノードからの距離に基づいて更新する更新ステップと、
を行うことを特徴とするグラフの直径のモニタリング方法。
前記枝刈りステップにおいて、
前記記憶手段に格納された前記追加ノード及び１時刻前の解ノードから最も次数の高いノードである参照ノードを選択し、前記距離計算手段を用いて、前記記憶手段の１時刻前の解ノードのペアから候補距離を計算し、該参照ノードの周辺ノードに対してその他のノードまでの距離の最大値を推定し、該最大値が該候補距離より小さければ該ノードを探索対象から除外する
請求項５記載のグラフの直径のモニタリング方法。
前記更新ステップにおいて、
前記データ受信ステップにより追加されたノードにより直径が大きくなる、または、小さくなる、変化しない、のいずれかに応じて、前記記憶手段の前記解ノードのペアと直径を更新する
請求項５記載のグラフの直径のモニタリング方法。
前記更新ステップにおいて、
前記最大距離が前記憶手段に格納されている１時刻前の直径よりも大きければ、該直径を該最大距離とし、該記憶手段の解ノードペアを更新し、該最大距離が１時刻前の直径と同じ長さのノードのペアがあれば、該追加ノードからの距離を用いて該記憶手段の解ノードのペアを更新し、１時刻前の直径と同じ距離のペアがなければ、前記距離計算手段により直径を求める、
請求項５記載のグラフの直径モニタリング方法。
請求項１乃至４のいずれか１項に記載のグラフの直径モニタリング装置を構成する各手段としてコンピュータを機能させるためのプログラム。