(57)【要約】【課題】  時々刻々と増大するグラフの中から最も中心性の高いノードを効率的に、かつ、正確に求める。【解決手段】  本発明は、受信したグラフ及び近似グラフを格納する記憶手段を有するコンピュータにおいて、グラフとして時刻毎に変動するノードまたはエッジを受信し、憶手段に格納し、受信した元のグラフの近似をとり、近似の中心性によりノードを枝刈りしてノードを集約し、近似グラフを計算し、該近似グラフを記憶手段に格納し、記憶手段から元のグラフと前記近似グラフを読み出して、不必要な距離計算を打ち止めすることにより中心性の低いノードを効率的に枝刈りし、グラフにおいて最も中心性の高いノードを計算する。【選択図】  図１
2011150539.tif 000002
【特許請求の範囲】
【請求項１】
時々刻々と増大するグラフの中から、グラフ理論において適切さを測る尺度である中心性が最も高いノードを求めるモニタリング装置であって、
グラフとして時刻毎に変動するノードまたはエッジを受信するデータ受信手段と、
前記データ受信手段で受信した元のグラフのノードを近似の中心性により枝刈りし、近似グラフを計算する集約手段と、
前記データ受信手段で受信した前記元のグラフと前記集約手段で計算された前記近似グラフを格納するデータ保持手段と、
前記データ保持手段から前記元のグラフと前記近似グラフを読み出して、グラフにおいて最も中心性の高いノードを計算する検出手段と、
を有することを特徴とするモニタリング装置。
【請求項２】
前記集約手段は、
前記データ受信手段で受信した元のノード集合のうち、ノード間の距離総和の逆数を求め、該逆数の値が近似するノード同士を纏めて近似グラフとして前記データ保持手段に格納する手段を含み、
前記検出手段は、
前記データ保持手段から前記元のグラフと前記近似グラフを読み出して、始点ノードから他のすべてのノードまでの距離を幅優先探索により求め、あるノードの中心性の上限値が該近似グラフの中心性より小さければ探索を終了する手段を含む
請求項１記載のモニタリング装置。
【請求項３】
時々刻々と増大するグラフの中から、グラフ理論において適切さを測る尺度である中心性が最も高いノードを求めるモニタリング方法であって、
受信したグラフ及び近似グラフを格納する記憶手段を有するコンピュータにおいて、
グラフとして時刻毎に変動するノードまたはエッジを受信し、前記記憶手段に格納するデータ受信ステップと、
前記データ受信ステップで受信した元のグラフのノードを近似の中心性により枝刈りし、近似グラフを計算し、該近似グラフを前記記憶手段に格納する集約ステップと、
前記記憶手段から前記元のグラフと前記近似グラフを読み出して、グラフにおいて最も中心性の高いノードを計算する検出ステップと、
を行うことを特徴とするモニタリング方法。
【請求項４】
前記集約ステップにおいて、
前記データ受信ステップで受信した元のノード集合のうち、ノード間の距離総和の逆数を求め、該逆数の値が近似するノード同士を纏めて近似グラフとして前記記憶手段に格納し、
前記検出ステップにおいて、
前記記憶手段から前記元のグラフと前記近似グラフを読み出して、始点ノードから他のすべてのノードまでの距離を幅優先探索により求め、あるノードの中心性の上限値が該近似グラフの中心性より小さければ探索を終了する
請求項３記載のモニタリング方法。
【請求項５】
請求項１または２に記載のモニタリング装置を構成する各手段としてコンピュータを機能させるためのモニタリングプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グラフの中心性のモニタリング装置及び方法及びプログラムに係り、特に、時々刻々と増大するグラフの中心性をモニタリングするためのグラフの中心性のモニタリング装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
グラフは実世界に存在するものとそれらの関係をノードとエッジという形で表現するデータ構造である。その直感的な表現方法により、グラフデータは数学やコンピュータ科学の分野において広く使われているデータ構造である。
【０００３】
グラフデータを扱うグラフ理論において、与えられたノードの中から適切なノードを求める施設配置問題は非常に重要な問題の１つである。この問題においては、他のノードからの距離の合計が短いノードの方がより適切だと考えられている。これは、その他のノードからの移動コストが小さいことが期待されるためである。
【０００４】
グラフ理論において、この適切さを測る尺度として「中心性」が用いられている。この「中心性」は他のノードまでの距離の和の逆数から計算され、中心性が高いノードがより適切であるとされる。施設配置問題は最適化問題の典型的なものであり、経済や産業などの広い分野に応用が可能である。この問題は、例えば輸送・通信・伝送システムなどにおいて、その効率性を解析するために用いられている（例えば、非特許文献１参照）。しかし、従来よりグラフ理論が対象としていた問題にはグラフは静的であり、ノード数は変化しないという大きな前提があった。
【０００５】
しかし近年、時間と共にノード数が時々刻々と増大し、結果的にノード数が数十万以上になるグラフデータを扱うことが必要となってきた。これは巨大なデータベースとインターネットを用いる環境が整ってきた結果である。近年の研究により時々刻々と増大し続けるグラフデータの特徴が明らかになりつつある（例えば、非特許文献２参照）。そのため、時々刻々と増大し、結果的に非常に大きなサイズになるグラフを効率的に処理する需要が高まりつつある。
【０００６】
本明細書では、時々刻々と増大し続けるグラフの中から最も高い中心性を有するノードを検出し続ける問題を扱う。
【０００７】
本明細書が対象とする問題の応用例としてソーシャルネットの解析があげられる。
【０００８】
社会科学者達によって様々な相互関係のネットワークについての研究が長い間行われてきた。これらのネットワークにおいてノードは人物や組織に対応し、エッジは社会的な関係に対応している。今までの研究において、「ネットワークにおいてどのノードが最も重要であるか？」という問題は彼らの大きな関心を集めてきた。
【０００９】
直感的にはノードが多くのエッジと繋がっているということは、関心や人気をそのネットワークにおいて集めているということである。この考えの重要な具体例としてあげられるのは科学分野における出版のネットワークである。ノードはこの場合、論文や本やジャーナルを表し、エッジは参照を表す。論文や本が多くの参照を集めるほど、他の多くの研究者から有用であると判断されたほどである。そのため、そのような論文などを重要と考えるのは素直な発想である。この考えに基づき、Garfieldは、ジャーナルに対する重要度の尺度としてインパクトファクタを提案した。インパクトファクタは、出版毎の参照の数から定義される。基本的にインパクトファクタはグラフにおける次数に対応するシンプルな尺度である。
【００１０】
しかし、このような尺度はグラフ全体から見れば局所的な尺度である。それは次数がノードの隣接ノードの個数から決定されるからである。そのため、次数が高いノードであっても、もしグラフ内の孤立したコミュニティに属するのであれば、そのノード全体に対する影響は大きいとは限らなくなる。
【００１１】
中心性の値は他のノードまでの距離の和の逆数から計算されるため、局所的な尺度ではない。そのため、中心性によってノードの重要性を測るのは次数より適切な尺度と考えられる。時系列的に最も重要なノードは、中心性に基づき時々刻々と増大するグラフをモニタリングすることで検出できる。例えば、Nascimentoらはデータベースにおける著名な国際会議であるSIGMODの共著者関係のグラフを1975年から2002年まで解析した（例えば、非特許文献３参照）。そして彼らは、L. A. RoweとM. StonebrakerとM. J. Careyがそれぞれ1986年から1988年、1989年から1992年、1992年から2002年まで最も影響力のある研究者であることを検出することに成功した。これら３人の研究者は、データベースコミュニティにおいて非常に著名な研究者として知られている。なお、最も共著関係にある著者（最も次数が高いノード）は必ずしも最も中心性の高かったわけではなかったことは、情報検索の分野の国際会議の共著関係を解析した結果から示されている（例えば、非特許文献４参照）。
【００１２】
この学術的なネットワークは非常に高い速度で増大することが知られている。例えば、データベース分野の共著関係のネットワークは数万以上の研究者で構成され、また、研究者の数は年々数千以上増加していることが知られている（例えば、非特許文献５参照）。そのため、成長し続けるネットワークのために用いる高速な解析方法に対する需要が高まっている。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】Ulrik Brandes, and Thomas Erlebach, Network Analysis: Methodological Foundations, Springer, 2008.
【非特許文献２】Jure Leskovec, Jon M. Kleinberg, and Christos Faloutsos, Graph evolution: Densification and shrinking diameters, TKDD, 2007.
【非特許文献３】Mario A. Nascimento, Jorg Sander, and Jeffrey Pound, Analysis of SIGMOD's co-authorship graph, SIGMOD Record, 2003.
【非特許文献４】Djoerd Hiemstra, Claudia Hauff, Franciska de Jong, and Wessel Kraaij, SIGIR's 30th anniversary: an analysis of trends in IR research and the topology of its community, SIGIR forum, 2007.
【非特許文献５】Ergin Elmacioglu, and Dongwon Lee On six degrees of separation in DBLP-DB and more, SIGMOD Record, 2005.
【発明の概要】
【発明が解決しようとする課題】
【００１４】
定式的に述べると本明細書では以下の問題を対象とする。
【００１５】
対象とする問題を「中心性のモニタリング」とし、時刻ｔにおける重み無し無向グラフＧ［ｔ］=（Ｖ，Ｅ）が与えられ、中心性の値が最も高くなるノードを見つける場合について説明する。なお、ここで、ＶとＥは、それぞれノードとエッジの集合とする。ノードの中心性は幅優先探索により計算することができる（例えば、Ulrik Brandes, A Faster Algorithm for Betweenness Centrality, Journal of Mathematical Sociology, 2001）。幅優先探索は、グラフの探索において広く使われる手法である。幅優先探索は、グラフＧ（Ｖ，Ｅ）が与えられたとき始点ノードｕから到達可能な周辺のノードを辿りながら徐々に距離を計算していく。ノードｕの中心性を計算するために既存の手法では、幅優先探索を用いてノードｕからその他すべてのノードまでの距離を計算し、距離の合計を計算する。
【００１６】
幅優先探索を用いて最も中心性ノードを計算するためには、Ｏ（ｎ２＋ｎｍ）の計算量が必要となる。これはすべてのｎ個のノードに対してＯ（ｎ＋ｍ）の計算量が必要になる幅優先探索を行うからである（例えば、Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, The MIT Press, 2009参照.)。グラフが大規模になると、この処理には莫大な計算量が必要となる。また、時々刻々と成長するグラフに対してはグラフが成長するためにこの処理を繰り返すこととなるために、幅優先探索により最も中心性の高いノードを求めるのは現実的ではない。
【００１７】
本発明は、上記の点に鑑みなされたもので、時々刻々と増大するグラフの中から最も中心性の高いノードを効率的に、かつ、正確に求めることが可能なグラフの中心性のモニタリング装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１８】
図１は、本発明の原理構成図である。
【００１９】
本発明（請求項１）は、時々刻々と増大するグラフの中から、グラフ理論において適切さを測る尺度である中心性が最も高いノードを求めるモニタリング装置であって、
グラフとして時刻毎に変動するノードまたはエッジを受信するデータ受信手段１１０と、
データ受信手段１１０で受信した元のグラフのノードを近似の中心性により枝刈りし、近似グラフを計算する集約手段１２０と、
データ受信手段１１０で受信した元のグラフと集約手段１２０で計算された近似グラフを格納するデータ保持手段１３０と、
データ保持手段１３０から元のグラフと近似グラフを読み出して、グラフにおいて最も中心性の高いノードを計算する検出手段１４０と、を有する。
【００２０】
また、本発明（請求項２）は、請求項１のモニタリング装置において、集約手段１２０は、データ受信手段で受信した元のノード集合のうち、ノード間の距離総和の逆数を求め、該逆数の値が近似するノード同士を纏めて近似グラフとしてデータ保持手段１３０に格納する手段を含み、
検出手段１４０は、データ保持手段１３０から元のグラフと近似グラフを読み出して、始点ノードから他のすべてのノードまでの距離を幅優先探索により求め、あるノードの中心性の上限値が該近似グラフの中心性より小さければ探索を終了する手段を含む。
【００２１】
図２は、本発明の原理を説明するための図である。
【００２２】
本発明（請求項３）は、時々刻々と増大するグラフの中から、グラフ理論において適切さを測る尺度である中心性が最も高いノードを求めるモニタリング方法であって、
受信したグラフ及び近似グラフを格納する記憶手段を有するコンピュータにおいて、
グラフとして時刻毎に変動するノードまたはエッジを受信し、前記記憶手段に格納するデータ受信ステップ（ステップ１）と、
前記データ受信ステップで受信した元のグラフのノードを近似の中心性により枝刈りし、近似グラフを計算し、該近似グラフを前記記憶手段に格納する集約ステップ（ステップ２）と、
前記記憶手段から前記元のグラフと前記近似グラフを読み出して、グラフにおいて最も中心性の高いノードを計算する検出ステップ（ステップ３）と、を行う。
【００２３】
また、本発明（請求項４）は、請求項３のモニタリング方法において、
集約ステップでは、データ受信ステップで受信した元のノード集合のうち、ノード間の距離総和の逆数を求め、該逆数の値が近似するノード同士を纏めて近似グラフとして前記記憶手段に格納し、
検出ステップでは、記憶手段から元のグラフと近似グラフを読み出して、始点ノードから他のすべてのノードまでの距離を幅優先探索により求め、あるノードの中心性の上限値が該近似グラフの中心性より小さければ探索を終了する。
【００２４】
本発明（請求項５）は、請求項１または２に記載のモニタリング装置を構成する各手段としてコンピュータを機能させるためのモニタリングプログラムである。
【発明の効果】
【００２５】
上記のように本発明によれば、以下のような効果を奏する。
【００２６】
・効率的：
既存の手法は大規模なグラフに対して莫大な計算量が必要であったが、本発明によれば、近似の中心性を用いることにより、高速に中心性の最も高いノードを検出することができる。グラフの近似は元のグラフが時々刻々と成長しても効率的に計算することができる。
【００２７】
・正確：
本発明によれば、ノードを枝刈りするために近似計算を用いるが、検出結果は正確であることが保証される。すなわち、検出結果に検出漏れなどは一切発生しない。
【００２８】
・省メモリ：
本発明によれば、近似したグラフを保持するためにメモリ量は必要になるが、そのメモリ量は少ない。高々元のグラフを保障するのと同じメモリ量しか必要にならない。
【図面の簡単な説明】
【００２９】
【図１】本発明の原理構成図である。
【図２】本発明の原理を説明するための図である。
【図３】本発明の一実施の形態におけるモニタリング装置の構成図である。
【図４】本発明の一実施の形態におけるグラフの例である。
【図５】本発明の一実施の形態におけるノード集約の例である。
【図６】本発明の一実施の形態における探索の枝刈りを説明するための図である。
【図７】本発明の一実施の形態における中心性の計算のアルゴリズムの例である。
【図８】本発明の一実施の形態における中心性のモニタリングのアルゴリズムの例である。
【図９】実験によるＰ２Ｐデータの処理時間を示す図である。
【図１０】実験によるＷＷＷデータの処理時間を示す図である。
【図１１】実験によるＤＢＬＰデータの処理時間を示す図である。
【発明を実施するための形態】
【００３０】
以下、図面と共に本発明の実施の形態を説明する。
【００３１】
図３は、本発明の一実施の形態におけるモニタリング装置の構成を示す。
【００３２】
同図に示すモニタリング装置１００は、データ受信部１１０、集約部１２０、データ保持部１３０、検出部１４０から構成される。
【００３３】
データ受信部１１０は、時刻毎に変動するグラフ（ノードまたはエッジ）を受信し、集約部１２０に渡すと共に、受信したグラフのノードとエッジをデータ保持部１３０に送る。
【００３４】
集約部１２０は、内部にメモリ（図示せず）を有し、受信した元のグラフのノードを集約し、近似グラフを計算する。
【００３５】
データ保持部１３０は、ディスク装置やメモリ等の記憶媒体であり、データ受信部１１０から渡された元のグラフと集約部１２０で計算された近似グラフを保持する。
【００３６】
検出部１４０は、データ保持部１３０から元のグラフと近似グラフを読み出して、これらのグラフにおいて最も中心性の高いノードを計算する。
【００３７】
まず、本明細書で用いる記号を定義し、必要となる背景知識を説明する。
【００３８】
主な記号とその定義を以下に示す。
【００３９】
【表１】
2011150539.tif 000003
実世界のネットワークは、グラフＧ＝（Ｖ，Ｅ）として表現することができる。ここで、Ｖは、ノードの集合とし、Ｅはエッジの集合とする。また、ｎとｍはそれぞれノードとエッジの数とする。すなわち、ノードの数ｎ＝│Ｖ│であり、エッジの数ｍ=│Ｅ│である。
【００４０】
「ノードｕからノードｖまでのパス」とは、ノードｕから始まりノードｖで終わるエッジの並びである。パスの中に含まれるノードが最も少ないものは「最短パス」と呼ばれる。
【００４１】
「ノードｕとノードｖの距離」は、最短パスに含まれるエッジの数の合計であり、ｄ（ｕ，ｖ）と定義される。当該定義からノードｕ∈Ｖに対してｄ（ｕ，ｕ）＝０であり、ノードｕ，ｖ∈Ｖに対してｄ（ｕ，ｖ）＝ｄ（ｖ，ｕ）となる。
【００４２】
「ノードの中心性」はその他のノードまでの距離の和の逆数であり、以下のように定義される。
【００４３】
＜定義１＞ノードの中心性：
グラフＧ＝（Ｖ，Ｅ）において、その他のノードまでの距離和
【００４４】
【数１】
2011150539.tif 000004
としたとき、ノードｕの中心性Ｃｕは以下のように定義される。
【００４５】
【数２】
2011150539.tif 000005
図４は、本発明の一実施の形態におけるグラフの例である。
【００４６】
同図において、ノードｕ１の中心性は１／１１となる。これは、それぞれの距離が、
ｄ（ｕ１，ｕ１）＝０，
ｄ（ｕ１，ｕ２）＝１，
ｄ（ｕ１，ｕ３）＝２，
ｄ（ｕ１，ｕ４）＝２，
ｄ（ｕ１，ｕ５）＝３，
ｄ（ｕ１，ｕ６）＝３
となるからである。
【００４７】
本発明は、時々刻々と成長するグラフに対して高速かつ正確に中心性の最も高いノードを求めることに大きな特徴がある。まず、２つの手法の概要を説明してからそれぞれの手法の詳細な説明を行う。
【００４８】
本発明の手法は、以下の２つの手法で構成される。
【００４９】
＜ノードの集約＞
従来の手法における莫大な計算量を削減するために、本発明では、集約部１２０において近似計算を行う。すべてのノードに対して正確な中心性を計算する代わりに、高速に近似の中心性を計算し、中心性の低いノードを効率的に枝刈りする。
【００５０】
図５にノードの集約の例を示す。
【００５１】
集約部１２０では、最初に、グラフのサイズを小さくする。データ受信部１１０から受信した元のノードがｎ個でエッジがｍ個のグラフが与えられると、当該グラフに対して、似たノード同士を纏めることにより、ノードがn'個でエッジがｍ'個（ｎ'≪ｎ，ｍ'≪ｍ）であるようなグラフを新たに計算する。この近似のグラフにおいて近似の中心性を計算するコストはＯ（ｎ'+ｍ'）である。これは元のグラフにおける中心性の計算量Ｏ（ｎ＋ｍ）と比較すると大きな削減である。
【００５２】
元のグラフにおいて似たノードを計算するためには、Jaccard係数を用いる。本発明において、受信した元のグラフを纏めることを「集約」と呼ぶこととする。
【００５３】
上記の手法には、２つの優位性がある。１つ目の優位性として、近似の中心性によってノードの枝刈りを行っても最も中心性の高いノードを枝刈りすることはないことが挙げられる。これは近似の中心性の値が正確な中心性の値よりも小さくなることがないためである。この手法により正確になり得ないノードを効率的に枝刈りすることができる。
【００５４】
２つ目の優位性は、近似の計算を行うノードの数は、受信した元のグラフのノードの数と比較して大きく減少することがあげられる。このため、グラフが大規模になっても効率的な処理が可能となる。
【００５５】
＜探索の枝刈り＞
上記の集約部１２０の処理により、ノードを集約するアプローチにより低い中心性を持つノードの大部分を枝刈りすることができるが、検索結果が正確になるためには正確な中心性の計算を行う必要がある。以下では、この計算量を削減するためのものである。図６の枝刈りの例を示す。
【００５６】
正確な中心性を計算するためには始点ノードからその他のすべてのノードまでの距離を計算する必要がある。この距離は、幅優先探索により求めることができるが、すべてのノードを探索するのはグラフが大規模になることを考えると好ましくない。そのため、本発明の検出部１４０では、始点ノードが最も高い中心性になり得なくなった時点で距離の計算を打ち切る。
【００５７】
データ保持部１３０は、検出結果を出力する前に、高い中心性を持つ解候補のノードを保持しており、検出部１４０は、あるノードの中心性を計算する途中で、データ保持部１３０に保持されている探索していないノードの距離を推定することにより、そのノードの中心性の上限値を計算する。検出部１４０の検出処理において、もし、あるノードの中心性の上限値が解候補の中心性より小さければ、そのノードは解になることはない。そのため、不必要な距離の計算を打ち切る。
【００５８】
上記のように、検出部１４０において、中心性の推定を行うことにより、幅優先探索においてグラフ全体の探索を行う必要が無くなるため、結果的に効率的な処理が可能となる。
【００５９】
上記の処理は、正確な中心性の計算のみでなく、近似の中心性の計算においても適用することができる。
【００６０】
次に、上記のノードの集約処理について詳細に説明する。
【００６１】
集約部１２０は、データ受信部１１０から元のグラフ（ｎ個のノードとｍ個のエッジを持つグラフＧからｎ'個のノードとｍ個のエッジを持つグラフＧ）を取得する。そして、元のグラフＧを集約して近似の中心性を高速に計算するために、ｎ個のノードとｍ個のエッジを持つグラフＧからｎ'個のノードとｍ'個のエッジを持つグラフＧ'を計算する。すなわち、この処理によって、グラフＧ＝（Ｖ，Ｅ）は、近似グラフＧ'（Ｖ'，Ｅ'）に集約され、データ保持部１３０に格納される。
【００６２】
ここでは、まず、近似グラフにおけるエッジの計算方法を述べ、それから元のグラフのノードを集約する方法について述べる。
【００６３】
元のグラフにおいて集約されているノードがエッジを持つときのみ、近似グラフにおいてノードｕ'とｖ'は、エッジ｛ｕ'，ｖ'｝∈Ｅを持つとする。また、近似グラフは輪(self-loop)となるエッジは持たないものとする。これらの定義は後に述べるように、中心性の上限値を計算するために必要なものである。形式的には近似グラフがエッジを持つため必要十分条件は以下の通りである。
【００６４】
＜定義２＞ノードの集約：
近似グラフＧ"において、ノードｕ'とノードｖ'は以下の条件を満たすときのみエッジを持つものとする。
【００６５】
（１）ｕ'≠ｖ'
（２）∃｛ｕ，ｖ｝，ｕ∈ｕ'∩ｖ∈ｖ'                      （２）
ここで、ｕ∈ｕ'は、集約ノードｕ'が元のノードｕを含むことを示す。
【００６６】
図４において、ｕ１，ｕ２，ｕ３，ｕ４，ｕ５をデータ受信部１１０から取得した元のノードとする。図５に示すとおり、集約部１２０において、ノードｕ１，ｕ２，ｕ３をノードｕ'１とし、ノードｕ５，ｕ６をノードｕ'３に集約するものとする。ノードｕ'２はノードｕ４に対応する。元のグラフはエッジ｛ｕ２，ｕ４｝と｛ｕ４，ｕ５｝を持つため、近似グラフはエッジ｛ｕ'１，ｕ'２｝と｛ｕ'２，ｕ'３｝を持つ。
【００６７】
集約部１２０は、グラフを近似したときの誤差を減らすために元のグラフにおいて似たノード同士を集約する。既に述べたとおり、集約ノード同士は少なくとも元のノードが一つでもエッジを持つときにのみエッジを持つ。そのため、元のノードの隣接ノードの集合が似ているほど、一つのノードに集約したときの誤差が小さくなる。本発明では、集合の類似性の評価基準としてよく用いられるJaccard係数を用いて類似のノードを集約する。
【００６８】
ＮｕとＮｖをそれぞれノードｖとノードｕの隣接ノードの集合とする。すると、Jaccard係数は、
│Ｎｕ∩Ｎｖ│／│Ｎｕ∪Ｎｖ│
として計算することができる。これは共通する隣接ノードの数を共有する隣接ノードの数で割ったものである。ここで、「隣接ノード」とは、図４のグラフにおいて、ノードｕ２の隣接ノードはｕ１，ｕ３，ｕ４になり、また、ノードｕ３の隣接ノードはｕ２，ｕ４になる。「共通するノード」とは、隣接ノードのＡＮＤ集合のことであり、ノードｕ２とｕ３の場合はｕ４になる。また、「共有する隣接ノード」とは、隣接ノードのＯＲ集合のことであり、ノードｕ２とノードｕ３の場合は、ｕ１，ｕ２，ｕ３，ｕ４になる。
【００６９】
この例においては、集約部１２０は、ノードｕに対してノードｖが最も似ているとき、それらのノードを集約する。但し、似ていないノードを集約しないために、もし共通するノードの数が共有するノードの半分より少ない場合はノードを集約しない。
【００７０】
本発明では、中心性の近似値を計算するが、その近似値は元の中心性の値より小さくなることはない。まず、近似値を計算する方法を述べる。それから近似グラフにおけるノード間の距離はそれに対応する元のグラフにおける距離より長くなることはないことを述べた上で、この特性によって近似グラフから中心性の上限値を求めることができることを示す。
【００７１】
検出部１４０は、データ保持部１３０から近似グラフを取得すると、中心性の近似値を以下のように求める。
【００７２】
＜定義３＞中心性の近似値；
検出部１４０は、近似グラフにおけるノードｕ'の中心性の近似値を以下のように計算する。
【００７３】
【数３】
2011150539.tif 000006
ここで、│ｖ'│は集約ノードｖ'に含まれる元のグラフにおけるノードの数とする。
【００７４】
例として、図５の近似グラフにおいて、ノードｕ'１の中心性の近似値は１／５となる。これは、
ｄ（ｕ'１，ｕ'２）＝１，
ｄ（ｕ'１，ｕ'３）＝２，
│ｕ'２│＝１、
│ｕ'３│＝２
だからである。なお、この近似値は元のグラフにおける中心性の値より大きくなっている。
【００７５】
中心性の近似値が元の中心性の上限値となる性質を示すために、以下の補助定理を示す。
【００７６】
＜補助定理１＞ショートカット：
近似グラフのすべてのノードに対して以下の不等式が成立する。
【００７７】
ｄ（ｕ'，ｖ'）≦ｄ（ｕ，ｖ）            （４）
［証明］
元のグラフのノードｕとｖの間の最短パスをｕ→ｖとする。また、その最短パスの一部分をｗｉ→ｗｊとする。もし最短パスにおけるすべてのノードが異なる集約ノードに集約されたとすると、その最短パスの長さと近似グラフで対応するパスの長さは等しくなる。これは近似グラフ上におけるパスｕ'→ｗ'ｉ→ｗ'ｊ→ｖ'は、元のグラフにおける最短パスｕ→ｗｉ→ｗｊ→ｖと完全に一致するからである。もしそうでなければ最短パスにおいて少なくとも２つ以上のノードが１つの集約ノードに集約されていることとなる。すなわち、元のグラフのノードｗｉとｗｊがノードｗ'に集約されていることとなる。そのため元のグラフにおける最短パスｕ→ｗｉ→ｗｊ→ｖは近似グラフにおいてパスｕ'→ｗ'→ｖ'に短縮される。結果としてｄ（ｕ'，ｖ'）≦ｄ（ｕ，ｖ）となる。
【００７８】
補助定理１から中心性の近似について以下の定理を示すことができる。
【００７９】
＜定理１＞（中心性の近似値）：
近似グラフのすべてのノードについて以下の不等式が成り立つ。
【００８０】
Ｃｕ'≧Ｃｕ                              （５）
［証明］
すべての集約ノードについて補助定理１から以下の不等式が成り立つ。
【００８１】
【数４】
2011150539.tif 000007
そのため以下の不等式が成り立つ。
【００８２】
【数５】
2011150539.tif 000008
よって定理は成り立つ。
【００８３】
上記の定理１を用いることで検出結果が正確であることを保証している。この証明は後述する。
【００８４】
次に、検出部１４０における、元のグラフの中心性を高速に計算するための手法を述べる。この手法は、もし、あるノードの中心性が候補ノードの中心性より小さくなった段階で幅優先探索を打ち切る。この処理は、幅優先探索で探索を行っていない未探索ノードの距離を推定することで行う。
【００８５】
ここでは、まずノードの中心性を推定する式を定義する。そして幅優先探索で未探索ノードの距離の性質を示した後に、定義した推定式が中心性の上限値なることを示す。
【００８６】
本例においては、幅優先探索においてノードｕの中心性を以下の式によって推定する。
【００８７】
＜定義４＞中心性の推定：
検出部１４０は、幅優先探索において計算を打ち切るために、元のグラフにおいて、ノードｕの中心性の推定値Ｃ*ｕを以下のように推定する。
【００８８】
【数６】
2011150539.tif 000009
ここで、Ｖexを幅優先探索で探索を行ったノードの集合、
【００８９】
【数７】
2011150539.tif 000010
を未探索のノードの個数、dmaxを以下に定義されるように探索を行ったノードの中で最も大きな距離とする。
【００９０】
【数８】
2011150539.tif 000011
もし、すべてのノードを探索した場合、この推定値は正確な中心性の値と同じになる。距離の推定値の性質を示すために、未探索ノードにおいて成り立つ性質を以下に示す。ここで、「未探索ノード」とは、あるノードを始点に幅優先探索を行う過程で距離を計算してないノードを指す。例えば、図４のグラフにおいて、始点ノードをｕ１としたときに幅優先探索は距離が短い順番にｕ２，ｕ３，ｕ４，ｕ５，ｕ６とノードを辿っていく。ノードｕ２まで探索が行われているとき未探索ノードはｕ３，ｕ４，ｕ５，ｕ６であり、ノードｕ４まで探索が行われているとき未探索ノードはｕ５，ｕ６となる。
【００９１】
＜補助定理２＞未探索ノード；
未探索ノードの距離は探索を行ったどのノードの距離より短くなることはない。
【００９２】
［証明］
幅優先探索においてノードの距離は、すでに探索を行ったノードから距離を用いて計算する。このため未探索ノードの距離は幅優先探索の処理を進めていく過程で単調増加となる。
【００９３】
この定理から未探索ノードの距離の下限値を計算できる。中心性の値は距離の和の逆数であるため、結果として中心性の上限値を求めることができる。
【００９４】
＜定理２＞中心性の推定：
元のグラフにおいて、幅優先探索を行う過程で以下の不等式が成り立つ。
【００９５】
【数９】
2011150539.tif 000012
［証明］
上記の補助定理２から幅優先探索において未探索ノードの距離は探索を行ったノードの距離より短くなることはない。そのため以下の不等式が成り立つ。
【００９６】
【数１０】
2011150539.tif 000013
この定理から当該方法による検出結果が正確になることが示されるが、その証明は後述する。
【００９７】
図７に示す「アルゴリズム１」は、検出部１４０における中心性の計算を示す。ここで、候補ノードの正確な中心性の値をθとする。この「アルゴリズム１」では解になり得ないノードを解候補のノードの正確な中心性θを用いて枝刈りする。もし、中心性の推定値がθよりも小さければ、そのノードは最も高い中心性の値を持つことはない。そのため、幅優先探索の途中であっても安全に枝刈りすることができる（図７の６〜8行目）。この推定値はすべてのノードを探索した場合は正確な中心性の値となるため、アルゴリズムの最後でノードuの中心性の推定値Ｃ*ｕを返す（図７の10行目）。なお、正確な中心性の値θは、解候補の正確な中心性の値を用いるが、解候補の選び方については後に詳述する。
【００９８】
具体的には、図４のグラフにおいて、ノードｕ１を始点ノード、また、θ＝１／６とする。検出部１４０は、ノードｕ２における推定値は１／５であり、当該候補ノードの中心性の値θ＝１／６より大きいので、このノードからノードｕ３とｕ４を探索する。しかし、ノードｕ３とｕ４における推定値は１／９であり、θ＝１／６より小さいため、これらのノードからは探索を行わず計算を打ち切る。
【００９９】
ここでは、元のグラフにおいて幅優先探索を打ち切る方法について述べたが、同様の議論は、集約部１２０の近似グラフにおいても適用することができる。
【０１００】
時々刻々と増大し続けるグラフに対して中心性の高いノードを検出し続ける方法について述べる。本実施例では、１時刻毎に１つのノードが新たにグラフに追加されるものとする。
【０１０１】
最も中心性の高いノードを検出する主な手法は前述したとおりである。すなわち、検出部１４０は、集約部１２０で求められた近似グラフで中心性の低いノードを枝刈りし、元のグラフにおいて探索の打ち切りを行いながら正確に最も中心性の高いノードを求める。しかし、時々刻々と増大するグラフを対象としたときには、以下の２つの課題がある。
【０１０２】
（１）時々刻々と増大するグラフの近似グラフを計算するために、どのようにして最も似ているノードを計算するのか。
【０１０３】
（２）中心性の低いノードを効率的に枝刈りするために、時々刻々と増大するグラフの中からどのようにして候補のノードを選択するのか。
【０１０４】
これらの問題を解決するために、時々刻々と増大するグラフに対する以下の知見を示す。
【０１０５】
ノードが加わった前後においてグラフに大きな違いはない。
【０１０６】
時々刻々と増大するグラフにおいては、少数のノードが既に存在する多数のノードから構成されるグラフに加わる。そのため、次々と新しいノードがグラフに加わることがあっても、ノードが加わる前後においてグラフに対する変化は小さなものである。以下の手法はこの知見に基づいたものである。
【０１０７】
上記の（１）の問題に対する解決策は、データ受信部１１０で受信し、グラフに新たに加わったノードの周辺のノードのみに類似性を計算するというものである。最も似ているノードを求めるために素朴な方法は新たに加わったノードとすべてのノードの組み合わせに対して類似性を計算するというものである。
【０１０８】
しかし、当該方法では高速に最も似ているノードを更新するために以下の補助定理を用いる。
【０１０９】
＜補助定理３＞類似ノード：
あるノードに対して最も似ているノードまでの距離は２より大きくなることはない。
【０１１０】
［証明］
共通する隣接ノードを持たない２つのノードのJaccard係数はその定義より０である。共通する隣接ノードを介した長さの２のパスが存在するため、Jaccard係数が正になるノードまでの距離はせいぜい２である。
【０１１１】
具体的には、図４のグラフにおいて、ノードｕ１とｕ５のJaccard係数はｄ（ｕ１，ｕ５）＞２であるため０である。同様の理由からノードｕ１とｕ６はノードｕ１に対して最も似ているノードにはなり得ない。
【０１１２】
データ保持部１３０に追加されたノードに対して補助定理３から以下の定理が成り立つ。
【０１１３】
＜定理３＞Update the most similar nodes（最も類似するノードの更新）：
追加されたノードに対して最も似ているノードまでの距離はせいぜい２である。
【０１１４】
［証明］
補助定理３より明らか。
【０１１５】
最も似ているノードを高速に更新するために、定理３を用いる。すなわち、集約部１２０では、追加されたノードからの距離が２以下であるノードだけに対してJaccard係数を計算する。
【０１１６】
上記では、はじめに述べたとおり、１つのノードのみが追加される場合について述べたが、定理３はノードが削除された場合についても適応することができる。また、もし複数のノードが追加されたら上記の処理を複数回行うことで対応することができる。また、１つのエッジが追加／削除された場合は、エッジの片方のノードを削除してから再度そのノードを追加することで対応することができる。
【０１１７】
２つ目の問題の解決策として、本実施例では、検出部１４０は、１時刻前の最も高い中心性の値を持つノードを解候補のノードとして選択する。もし解候補のノードの中心性が低ければ、多くのノードを枝刈りすることはできない。しかし、先に示した知見から１時刻前の最も高い中心性を持つノードは再度最も高い中心性の値を持つことが期待される。そのために、ノードの正確な中心性を計算し、候補ノードの中心性の値θとする。
【０１１８】
図８に示す「アルゴリズム２」に最も中心性が高いノードを検出するアルゴリズムを示す。
【０１１９】
ここで、ｕbest[t]を最も中心性の高いノード、ｕbest[t-1]を１時刻前の最も中心性の高いノード、ｕaddを新たに加わったノードとする。また、Ｖexactは正確な中心性の値を計算するノードの集合とする。
【０１２０】
「アルゴリズム２」は、更新と検出の２つの段階に分けることができる。更新段階においては、集約部１２０が、最も似ているノードを計算してから近似グラフを求める（図７の２〜５行目）。検出段階において、検出部１４０は、まず１時刻前の最も中心性の高いノードを用いて候補ノードの中心性の値θを計算する（図８の８行目）。もし中心性の近似値がθより小さくなれば、その集約ノードに集約されるノードは解にはなり得ない。そのため、その集約ノードを枝刈りする。近似値がθより小さくなればVexactに集約されているノードに加える（図８の１１〜１５行目）。その集約ノードに集約されるノードは解になりえるからである。検出部１４０は、Ｖexactに含まれるノードの正確な中心性の値を計算し、解であるかを確認する（図８の１７〜２３行目）。
【０１２１】
以下では、上記の手法における検出結果の正確性及び計算量についての理論的な解析を行う。計算量の観点から以下の２つについて述べる。
【０１２２】
（１）正確に最も中心性の高いノードを検出する。
【０１２３】
（２）メモリ量及び計算時間は既存の手法と同等である。
【０１２４】
なお、ｎはノードの数であり、また、ｍはエッジの数である。
【０１２５】
以下に示すとおり、本発明では、正確に最も中心性の高いノードを検出することを示す。
【０１２６】
＜定理４＞正確な検出：
正確に最も中心性の高いノードを検出することを保証する。
【０１２７】
［証明］
ｕbestを元のグラフにおいて最も中心性の高いノードとし、θmaxをノードｕbestの正確な中心性の値とする。また、θを解候補の正確な中心性の値とする。
【０１２８】
近似グラフにおいてθmax＞θであるため、ノードｕbestの近似の中心性の値はθより小さくなることはない（定理１）。同様に元のグラフにおいてノードｕbestの中心性の推定値はθより小さくなることはない（定理２）。検出部１４０の検出処理において、ノードが枝刈りされるのは、近似の中心性の値または中心性の推定値がθより小さくなる場合のみである。そのため、ノードｕbestが枝刈りされることはあり得ない。
【０１２９】
まずは、幅優先探索を用いる既存の手法について述べる。
【０１３０】
＜補助定理４＞（既存手法）グラフが与えられたとき、既存の手法は最も中心性の高いノードを求めるためにＯ（ｎ＋ｍ）のメモリ量とＯ（ｎ２＋ｎｍ）の計算時間が必要である。
【０１３１】
［証明］
最も中心性の高いノードを求めるために既存の手法は隣接リスト表現によってグラフを保持する。隣接リスト表現においてはＯ（ｎ＋ｍ）のメモリ量が必要になる。また、グラフのあるノードの中心性の値を求めるためには幅優先探索を行うことが必要なため、Ｏ（ｎ＋ｍ）の計算時間が必要である。既存手法ではすべてのノードの中心性のある値を求める必要があるため、Ｏ（ｎ２＋ｎｍ）の計算時間が必要となる。
【０１３２】
＜補助定理５＞本発明のメモリ量：
本発明は最も中心性の高いノードを求めるためにＯ（ｎ＋ｍ）のメモリ量が必要である。
【０１３３】
［証明］
本発明は、受信した元のグラフと集約部１２０から得られた近似グラフをデータ保持部１３０で保持する。近似グラフにおいてノードとエッジの数はそれぞれ元のグラフのノードとエッジの数を超えることはない。そのため、近似グラフを保持するために必要となるメモリ量はＯ（ｎ＋ｍ）である。また、データ保持部１３０は、元のグラフを保持するためのメモリ量はＯ（ｎ＋ｍ）であるため、本発明が必要とするメモリ量はＯ（ｎ＋ｍ）である。
【０１３４】
＜補助定理６＞本発明の計算時間：
本発明は、最も中心性の高いノードを求めるためにＯ（ｎ２＋ｎｍ）の計算時間が必要である。
【０１３５】
［証明］
最も中心性の高いノードを求めるため、本発明は近似グラフを求めてから近似グラフと元のグラフでノードの枝刈りを行う。近似グラフを求めるには、Ｏ（ｎｍ）の計算時間が必要である。これは、Jaccard係数を計算する計算時間がＯ（ｍ）であり、また新たに加わったノードと他のすべてのノードとJaccard係数を計算する必要があり得るからである。また、近似グラフと元のグラフのノードとエッジの数はそれぞれせいぜいｎとｍであるため、ノードを枝刈りするための計算時間はＯ（ｎ２＋ｎｍ）となる。結果、本発明の計算時間はＯ（ｎ２＋ｎｍ）となる。
【０１３６】
メモリ量と計算時間についての補助定理から本発明について以下の性質を示すことができる。
【０１３７】
＜定理５＞計算量の同等性：
本発明のメモリ量及び計算時間はそれぞれ既存手法と同等である。
【０１３８】
［証明］
補助定理４から補助定理６より明らか。
【０１３９】
●実験：
本発明の有効性を調べるために実験を行った。
【０１４０】
実験では、既存の幅優先探索に基づく手法と比較を行った。実験では公開されている実データＰ２Ｐ(Point to Point)，ＷＷＷ(World Wide Web)，ＤＢＬＰを用いた。これらはそれぞれ大学のＰ２Ｐネットワークのデータ、「nd,edu」ドメイン内のウェブデータ、コンピュータ科学の文献参照ネットワークのデータである。実験では、ネットワークから最も大きな連結成分を抜き出し、ひとつひとつノードを加えていった。
【０１４１】
実験は、ＣＰＵがIntel Xeon Quad-Core 3.33GHz、メモリが32GBのLinuxサーバで行った。また、すべてのアルゴリズムはＧＣＣで実装した。
【０１４２】
本発明と既存手法の処理時間を比較した。実験では処理時間に大きな影響があるノードの数を変化させた。
【０１４３】
図９，１０、１１に処理時間とノードの数の関係を示す。なお、ここで処理時間とは更新段階と検出段階の両方を含むトータルの時間である。本発明が既存手法と比較して９６０倍以上高速であることが確認された。
【０１４４】
既存手法がノードあたりの中心性の計算時間がＯ（ｎ＋ｍ）であるのに対して、本発明は、Ｏ（ｎ'＋ｍ'）の計算時間で近似の中心性を計算できる。本発明ではすべてのノードに対して近似の中心性を計算するが、この計算は効果的に打ち止めされるので処理時間に大きな影響はない。また、もし近似の中心性でノードが枝刈りできなければ、本発明では正確な中心性を計算する。しかし、近似の中心性により殆どのノードが枝刈りされるので、処理時間に大きな影響は見られなかった。
【０１４５】
なお、上記のモニタリング装置のデータ受信部、集約部、検出部の動作をプログラムとして構築し、モニタリング装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【０１４６】
また、構築されたプログラムをハードディスクや、フレキシブルディスク・ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【０１４７】
なお、本発明は、上記の実施の形態及び実施例に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【０１４８】
本発明は、ソーシャルネットの解析に適用可能である。
【符号の説明】
【０１４９】
１００  モニタリング装置
１１０  データ受信手段、データ受信部
１２０  集約手段、集約部
１３０  データ保持手段、データ保持部
１４０  検出手段、検出部
【図１】
2011150539.tif 000014
【図２】
2011150539.tif 000015
【図３】
2011150539.tif 000016
【図４】
2011150539.tif 000017
【図５】
2011150539.tif 000018
【図６】
2011150539.tif 000019
【図７】
2011150539.tif 000020
【図８】
2011150539.tif 000021
【図９】
2011150539.tif 000022
【図１０】
2011150539.tif 000023
【図１１】
2011150539.tif 000024