(57)【要約】【課題】ノード間の加速度計算に関して、ノードの更新座標を効率よく計算できるグラフ可視化技術を提供する。【解決手段】グラフ可視化座標計算装置１は、複数のノードとノード間をつなぐエッジとを備えるネットワークのノード間の接続状態を可視化したグラフ上のノードの座標を階層的独立固有時間刻み法を用いて計算するものであって、対象となるネットワークのノードの個数およびエッジの個数を入力する入力手段３と、初期配置部２１と、初期値導出部２２と、大局時間設定部２３と、予測子導出部２４と、同期ノード導出部２５と、加速度導出部２６と、座標更新処理部２７と、独立固有時間導出部２８と、エネルギ導出部２９と、計算終了条件判定部３０と、データ制御部３１と、ノードの座標およびエネルギ値を出力する出力手段５とを含んで構成される。【選択図】図１
2008287497.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードと前記ノード間をつなぐエッジとを備えるネットワークの前記ノード間の接続状態を可視化したグラフ上の前記ノードの座標を階層的独立固有時間刻み法を用いて計算するグラフ可視化座標計算装置であって、
対象となるネットワークのノードの個数およびエッジの個数を入力する入力手段と、
演算手段と、
演算結果を格納する記憶手段と、
演算結果を出力する出力手段と、を有し、
前記演算手段は、
前記各ノードにおける固有時間と、加速度の大きさに反比例した固有時間刻みとの和の最小値を導出し、その値を大局時間として設定する大局時間設定部と、
前記入力された全ノードに対して、対象とするノードの固有時間と異なる固有時間を有するノードの配置された座標を示す仮想ノード座標と前記対象とするノードとの相互作用を計算するために前記大局時間での予測子を導出する予測子導出部と、
前記入力された全ノードのうち、前記固有時間と前記固有時間刻みとの和の値が前記大局時間となるノードを示す同期ノードを求める同期ノード導出部と、
前記同期ノードに対して、前記導出された予測子を用いて前記大局時間における加速度を導出する加速度導出部と、
前記同期ノードに対して、前記導出された加速度と前記固有時間刻みとの積に、更新前の座標を加算することで、前記大局時間における座標を更新する座標更新処理部と、
前記同期ノードに対して、前記導出された加速度と、前記固有時間刻みを所定の離散値に制限する階層化の指標と、更新前の前記固有時間と、更新前の前記固有時間刻みとを用いて、前記固有時間と前記固有時間刻みとを更新する独立固有時間導出部と、
を備えることを特徴とするグラフ可視化座標計算装置。
【請求項２】
前記演算手段は、
前記同期ノードに対して、前記導出された加速度の勾配を示すポテンシャルエネルギを求め、求めたポテンシャルエネルギを全ノードに対して総計したエネルギを導出するエネルギ導出部をさらに備えることを特徴とする請求項１に記載のグラフ可視化座標計算装置。
【請求項３】
複数のノードと前記ノード間をつなぐエッジとを備えるネットワークの前記ノード間の接続状態を可視化したグラフ上の前記ノードの座標を階層的独立固有時間刻み法を用いて計算するグラフ可視化座標計算装置のグラフ可視化座標計算方法であって、
入力手段によって、対象となるネットワークのノードの個数およびエッジの個数を入力する入力ステップと、
大局時間設定部によって、前記各ノードにおける固有時間と、加速度の大きさに反比例した固有時間刻みとの和の最小値を導出し、その値を大局時間として設定する大局時間設定ステップと、
予測子導出部によって、前記入力された全ノードに対して、対象とするノードの固有時間と異なる固有時間を有するノードの配置された座標を示す仮想ノード座標と前記対象とするノードとの相互作用を計算するために前記大局時間での予測子を導出する予測子導出ステップと、
同期ノード導出部によって、前記入力された全ノードのうち、前記固有時間と前記固有時間刻みとの和の値が前記大局時間となるノードを示す同期ノードを求める同期ノード導出ステップと、
加速度導出部によって、前記同期ノードに対して、前記導出された予測子を用いて前記大局時間における加速度を導出する加速度導出ステップと、
座標更新処理部によって、前記同期ノードに対して、前記導出された加速度と、前記固有時間刻みと、更新前の座標とを用いて、前記大局時間における座標を更新する座標更新処理ステップと、
独立固有時間導出手段によって、前記同期ノードに対して、前記導出された加速度と、前記固有時間刻みを所定の離散値に制限する階層化の指標と、更新前の前記固有時間と、更新前の前記固有時間刻みとを用いて、前記固有時間と前記固有時間刻みとを更新する独立固有時間導出ステップと、
を有することを特徴とするグラフ可視化座標計算方法。
【請求項４】
エネルギ導出部によって、前記同期ノードに対して、前記導出された加速度の勾配を示すポテンシャルエネルギを求め、求めたポテンシャルエネルギを全ノードに対して総計したエネルギを導出するエネルギ導出ステップをさらに有することを特徴とする請求項３に記載のグラフ可視化座標計算方法。
【請求項５】
請求項３または請求項４に記載のグラフ可視化座標計算方法をコンピュータに実行させることを特徴とするグラフ可視化座標計算プログラム。
【請求項６】
請求項５に記載のグラフ可視化座標計算プログラムが記録されたことを特徴とするコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、インターネットやソーシャルネットワークのような関係性を有したデータファイルがリンクのあるネットワークとして表現されるときに、２次元のネットワークまたは３次元のネットワークをグラフとして可視化する技術に関し、特に、グラフとして可視化する点の位置座標を計算する技術に関する。
【背景技術】
【０００２】
ネットワークをグラフとして可視化する技術（単に、グラフ可視化技術という）は、一般に、データとデータとの関連性によってネットワークを形成したデータを可視化することを指す。このグラフ可視化技術では、個々のデータをノードと呼び、データ間のリンクをエッジと呼ぶ。ここで、“ノード”とはネットワークデータにおけるデータを意味し、“エッジ”とはデータ間に関係性があることを示す。例えば、インターネット上のハイパーリンクの張られたＷＥＢページであれば、各ＷＥＢページのことを“ノード”といい、ハイパーリンクのことを“エッジ”という。また、例えば、テキストのことを“ノード”といい、その関係性のことを“エッジ”といってもよい。さらに、例えば、ソーシャルネットワーク上の人間のことを“ノード”といい、友達や付き合いのことを“エッジ”といってもよい。
【０００３】
図１０は、ノードとエッジの模式図である。グラフ可視化技術においては、図１０に示すように、ネットワークの関連性を元に、２次元の仮想空間または３次元の仮想空間に、ノード１００１が「点」として、エッジ１００２が点と点とをつなぐ「辺」として投影されてグラフとして描画される。以下では、この描画された点および辺のことを、単にノードおよびエッジとも呼ぶ。グラフ可視化においては、一般に、関係性があるものは近くに描画し、また、なるべく重ならないように描画するように、グラフとして可視化する点の位置座標を計算する。
【０００４】
従来、グラフ可視化の研究分野では１９８０年代より様々な手法が考案されてきた。最も一般的な手法は、仮想空間上に配置されたノード間のグラフ距離や、ノードが本来持っている接続関係などに基づき、系に力学関係を与え、加速度方向に座標を更新してゆくことによって系の最小エネルギ状態を求める手法である。すなわち、ノード間は力学的ポテンシャルに従い、グラフのノード（例えばインターネットでいうリンクの張られたページのことを指す）を力の勾配のかかる方向に座標を更新してゆく方法である。この方法に従えば、各ノードはポテンシャルの深い場所に移動して行き、結果として系全体のエネルギが極小になるように更新されてゆく。グラフ可視化技術において、速度（熱力学でいう温度）という概念はなく、分子動力学に例えると、温度「０」の結晶構造を求めることに等しい。この手法はひとまとめに“Force-directed法”と呼ばれ、近年では、さまざまな手法も考案されている（非特許文献１〜３参照）。
【０００５】
非特許文献１に記載された技術は、グラフ可視化において最も良く知られている“Spring Embedder method”と呼ばれる手法の原型である。“Spring Embedder method”は、リンクのあるエッジにバネと同様な力学モデルを与え、系全体のエネルギが極小になるように加速度方向にノードの配置を更新してゆく手法である。
【０００６】
非特許文献２に記載された技術は、非特許文献１に記載された技術を基に提案された新たなspring methodである。著者名（Kamada and Kawai）にちなんで以下では、ＫＫ法という。ＫＫ法は、すべてのノード間に理想的なバネを仮定し、座標の更新手法を逐次的に１ノードずつ行うものである。具体的には、ｉ番目のノードとｊ番目のノードとの間のグラフ上での最短経路の距離をバネの自然長ｌij、ノード間のバネ定数をκij（＝κ／ｌij）、ノードの空間的な座標距離をｘijとするときに、ｉ番目のノードに加わる加速度は、式（１）で表される。なお、κは無次元量の規格化定数である。
【０００７】
【数１】
2008287497.tif 000003
【０００８】
ＫＫ法では、エネルギ準位が高いノードから逐次的に座標更新を行う。このとき、ＫＫ法では、ポテンシャル勾配の２次導関数を求め、Newton-Laphson法を用いて系全体のエネルギが減少する方向に座標更新を行う。言い換えると、このＫＫ法は、選択的にポテンシャル勾配の大きなものから座標更新を行う。このことから、座標更新が早く収束するという利点がある。
【０００９】
非特許文献３に記載された技術は、非特許文献１に記載された技術を基に提案された手法であり、全ノードの座標更新を同時に行うものである。著者名（Fruchterman and Reingold）にちなんで、以下では、ＦＲ法という。
【００１０】
ＦＲ法では、エッジ間に働く力を引力ａa、ノード間に働く力を斥力ａrとして、これら２つの力の和で、ノードにかかる力を与える。なお、グラフ可視化において「加速度」と「力」は実質的に同じことを意味する。従って、ｉ番目のノードの加速度は、式（５）〜式（７）に示すように表される。ここで、Ｋは、無次元量の距離であり、おおよそバネの自然長に相当する。
【００１１】
【数２】
2008287497.tif 000004
【００１２】
ＦＲ法では、式（５）で定義される加速度の方向に、全ノードを同時に座標更新してゆくときの座標更新式は、式（８）で与えられる。式（８）中のｔcool（ｔ）は、最大更新幅を制限するための冷却関数であり、式（９）で示される。式（９）中のＣは更新幅の初期値を示すパラメータであり、ＦＲ法ではＣ＝０．１としている。また、ＴENDは収束時間（最大更新幅を抑えるために収束させる時間）である。
【００１３】
【数３】
2008287497.tif 000005
【００１４】
ここで、ＦＲ法の座標更新の概念図を図１１（ａ）に示す。ＦＲ法の座標更新は、“Shared timestep”と呼ばれている。“Shared timestep”では、毎回全ノードの更新を行う。そのため、たとえ更新座標がほとんど変化しない（加速度がゼロに近い）場合であっても毎回ノードを更新し続ける。図１１（ａ）では、１１個のノード１００１がそれぞれ４回座標更新されていることを例示している。また、ＦＲ法で算出された座標値で作成した可視化グラフの一例を図１２に示す。図１２は、収束時間ＴENDを４通りに変えたときの様子をそれぞれ示している。
【００１５】
近年、グラフ可視化の手法では、加速度を与える側の近似手法は色々取り入れられてきたが、加速度を受ける側、つまり、更新する側の近似手法は考慮されていなかった。ところで、グラフ可視化の研究分野とは異なるが、天体力学のＮ体計算では、天体の星団や銀河団の計算のような密度の粗密の差が大きな粒子計算を扱う計算において、高精度かつ高速な計算のために階層的独立固有時間刻み法（Hierarchical Individual timestep method）という手法が開発されている（非特許文献４参照）。
【００１６】
階層的独立固有時間刻み法は、特に局所的に密集した領域を対象として精度よく計算する手法である。また、階層的独立固有時間刻み法は、全体を支配する大局的な時間とは別に、各天体に対して固有時刻と固有の時間更新幅とを設定することによって、高精度に、かつ効率よく座標更新を行う。階層的独立固有時間刻み法の粒子計算は、“Individual timestep”と呼ばれている。“Individual timestep”では、更新幅の短い（加速度の小さな）粒子については、更新間隔を長くする。ここで、仮に階層的独立固有時間刻み法の粒子を、グラフ可視化技術のノードとして図１１（ｂ）に示す。この図１１（ｂ）では、ハッチングされた丸印はノード１００１を表し、白い丸印は予測子を示す。図１１（ｂ）に示すように、例えば、更新幅の特に長い２個のノード１００１については、それぞれ４回座標更新されているが、更新幅の特に短い６個のノード１００１については、それぞれ１回だけ座標更新されている。つまり、“Individual timestep”は、毎回全粒子を更新するものではなく、大局的な時間に対しては、予測子で表される予測座標を用いて全体の加速度計算を行う。
【非特許文献１】P.Eades:A heuristic for graph drawing, Congressus Numerantium, 42:149-160,1984
【非特許文献２】T. Kamada and S. Kawai, An algorithm for drawing general undirected graphs, Information Processing Letters, 31(12), p7-15, April, 1989
【非特許文献３】T．Fruchterman and E. Reingold, Graph drawing by forcedirected placement, Software-Practice and Experience, 21(11), p.1129-1164, Novenber,1991
【非特許文献４】Makino,J, A Modified Aarseth Code for GRAPE and Vector Processors, Publications of the Astronomical Society of Japan, 43, 859-876, 1991
【発明の開示】
【発明が解決しようとする課題】
【００１７】
非特許文献２に開示されたＫＫ法では、ノード間の最短経路のデータを常に保持する必要があり、ノード数Ｎに対してＯ（Ｎ2）のメモリ領域が必要になる。それゆえ、例えば数ＧＢ（ギガバイト）のメモリを持つ汎用計算機を用いて、数万ノード程度の計算を行った場合にメモリ容量が足りなくなり、計算を行うことができなくなる。したがって、ＫＫ法は、数万ノード以上の大規模なネットワークを、グラフとして可視化する点の位置座標を計算することには適していないという問題がある。
【００１８】
また、非特許文献３に開示されたＦＲ法では、前記した式（９）で示される冷却関数に対し、最適な収束時間ＴENDの値を予め設定する必要がある。しかし、最適な収束時間ＴENDの値は自明ではない。このことは、大規模なネットワークの計算では特に問題となる。
【００１９】
グラフ可視化の分野において、ノード間の加速度計算に関して、これまでも様々な効率化手法が提案されてきたが、座標の更新手法は未だ改良の余地が残っている。そこで、非特許文献４に開示された天体力学における階層的独立固有時間刻み法を、グラフ可視化の研究分野に適用して、各ノードに固有の更新時間を持たせる手法が考えられる。天体力学に用いられる計算手法は、系の運動エネルギとポテンシャルエネルギとを保存させるために、計算誤差を減らして高精度に微分方程式を解く必要がある。しかしながら、グラフ可視化における座標更新では、系のポテンシャルエネルギを効率よく減少させる必要があり、天体力学で用いられている手法を直接利用することはできないという問題がある。
【００２０】
そこで、本発明は、以上のような問題点に鑑みてなされたものであり、ノード間の加速度計算に関して、ノードの更新座標を効率よく計算できるグラフ可視化技術を提供することを目的とする。
【課題を解決するための手段】
【００２１】
前記課題を解決するために、本発明のグラフ可視化座標計算装置は、複数のノードと前記ノード間をつなぐエッジとを備えるネットワークの前記ノード間の接続状態を可視化したグラフ上の前記ノードの座標を階層的独立固有時間刻み法を用いて計算するグラフ可視化座標計算装置であって、対象となるネットワークのノードの個数およびエッジの個数を入力する入力手段と、演算手段と、演算結果を格納する記憶手段と、演算結果を出力する出力手段と、を有し、前記演算手段が、前記各ノードにおける固有時間と、加速度の大きさに反比例した固有時間刻みとの和の最小値を導出し、その値を大局時間として設定する大局時間設定部と、前記入力された全ノードに対して、対象とするノードの固有時間と異なる固有時間を有するノードの配置された座標を示す仮想ノード座標と前記対象とするノードとの相互作用を計算するために前記大局時間での予測子を導出する予測子導出部と、前記入力された全ノードのうち、前記固有時間と前記固有時間刻みとの和の値が前記大局時間となるノードを示す同期ノードを求める同期ノード導出部と、前記同期ノードに対して、前記導出された予測子を用いて前記大局時間における加速度を導出する加速度導出部と、前記同期ノードに対して、前記導出された加速度と前記固有時間刻みとの積に、更新前の座標を加算することで、前記大局時間における座標を更新する座標更新処理部と、前記同期ノードに対して、前記導出された加速度と、前記固有時間刻みを所定の離散値に制限する階層化の指標と、更新前の前記固有時間と、更新前の前記固有時間刻みとを用いて、前記固有時間と前記固有時間刻みとを更新する独立固有時間導出部とを備えることを特徴とする。
【００２２】
また、前記課題を解決するために、本発明のグラフ可視化座標計算方法は、複数のノードと前記ノード間をつなぐエッジとを備えるネットワークの前記ノード間の接続状態を可視化したグラフ上の前記ノードの座標を階層的独立固有時間刻み法を用いて計算するグラフ可視化座標計算装置のグラフ可視化座標計算方法であって、入力手段によって、対象となるネットワークのノードの個数およびエッジの個数を入力する入力ステップと、大局時間設定部によって、前記各ノードにおける固有時間と、加速度の大きさに反比例した固有時間刻みとの和の最小値を導出し、その値を大局時間として設定する大局時間設定ステップと、予測子導出部によって、前記入力された全ノードに対して、対象とするノードの固有時間と異なる固有時間を有するノードの配置された座標を示す仮想ノード座標と前記対象とするノードとの相互作用を計算するために前記大局時間での予測子を導出する予測子導出ステップと、同期ノード導出部によって、前記入力された全ノードのうち、前記固有時間と前記固有時間刻みとの和の値が前記大局時間となるノードを示す同期ノードを求める同期ノード導出ステップと、加速度導出部によって、前記同期ノードに対して、前記導出された予測子を用いて前記大局時間における加速度を導出する加速度導出ステップと、座標更新処理部によって、前記同期ノードに対して、前記導出された加速度と、前記固有時間刻みと、更新前の座標とを用いて、前記大局時間における座標を更新する座標更新処理ステップと、独立固有時間導出手段によって、前記同期ノードに対して、前記導出された加速度と、前記固有時間刻みを所定の離散値に制限する階層化の指標と、更新前の前記固有時間と、更新前の前記固有時間刻みとを用いて、前記固有時間と前記固有時間刻みとを更新する独立固有時間導出ステップとを有することを特徴とする。
【００２３】
かかる構成のグラフ可視化座標計算装置、または、かかる手順のグラフ可視化座標計算方法によれば、グラフ可視化座標計算装置は、入力される個々のノードに固有時間を持たせ、固有時間刻みを所定の離散値に制限する階層化の指標を用いて、入力される全ノードのうちの一部のノード集合に時間同期を行った同期ノードを求めて、同期ノードごとに座標更新時間を変える。したがって、グラフ可視化座標計算装置は、固有時間の異なるノードからの相互作用を同期ノードごとに計算できるので、従来のように個々のノードに対して計算を行う場合と比べて計算コストを低減できる。そして、グラフ可視化座標計算装置は、ノード間相互作用を計算するために全ノードに対して予測子を求めるときに、大局的にノードの座標更新を行いながら、同期ノードに対して加速度の計算を行うことで局所的にノードの座標を求めて行くことができる。したがって、従来のように全ノードを同時に座標更新することがないので、効率よく座標更新を行うことが可能である。そして、グラフ可視化座標計算装置は、固有時間刻みを加速度の大きさに反比例したもので定義すると共に、座標更新式を加速度依存項と更新前の座標との和という簡易な構成で形成したので、従来の階層的独立固有時間刻み法に比べて微分方程式を容易に解くことができる。その結果、ノード間の加速度計算に関して、ノードの更新座標を効率よく計算できる。
【００２４】
また、本発明に係るグラフ可視化座標計算装置は、前記演算手段が、前記同期ノードに対して、前記導出された加速度の勾配を示すポテンシャルエネルギを求め、求めたポテンシャルエネルギを全ノードに対して総計したエネルギを導出するエネルギ導出部をさらに備えることが好ましい。
【００２５】
また、本発明に係るグラフ可視化座標計算方法は、エネルギ導出部によって、前記同期ノードに対して、前記導出された加速度の勾配を示すポテンシャルエネルギを求め、求めたポテンシャルエネルギを全ノードに対して総計したエネルギを導出するエネルギ導出ステップをさらに有することが好ましい。
【００２６】
かかる構成のグラフ可視化座標計算装置、または、かかる手順のグラフ可視化座標計算方法によれば、グラフ可視化座標計算装置は、系の運動エネルギとポテンシャルエネルギとの保存を考慮した高精度な微分方程式を解くことなく、加速度の勾配によって容易にポテンシャルエネルギを求めることができる。そして、グラフ可視化座標計算装置は、求めたポテンシャルエネルギを効率よく減少させることで、速やかに座標更新を収束させることができる。
【００２７】
また、本発明に係るグラフ可視化座標計算プログラムは、前記したグラフ可視化座標計算方法をコンピュータに実行させることを特徴とする。このように構成されることにより、このプログラムをインストールされたコンピュータは、このプログラムに基づいた各機能を実現することができる。
【００２８】
また、本発明に係るコンピュータ読み取り可能な記録媒体は、前記したグラフ可視化座標計算プログラムが記録されたことを特徴とする。このように構成されることにより、この記録媒体を装着されたコンピュータは、この記録媒体に記録されたプログラムに基づいた各機能を実現することができる。
【発明の効果】
【００２９】
本発明によれば、ノード間の加速度計算に関して、ノードの更新座標を効率よく計算できるグラフ可視化技術を提供することができる。したがって、与えられたネットワークデータが大規模である場合であっても、高速に座標計算を行うことができる。その結果、大規模なネットワークデータを高速かつ効率よく描画することが可能となる。
【発明を実施するための最良の形態】
【００３０】
以下、本発明のグラフ可視化座標計算装置およびグラフ可視化座標計算方法を実施するための最良の形態（以下「実施形態」という）について詳細に説明する。説明の都合上、本発明の概要を説明した上で、第１実施形態および第２実施形態について数式および図面を参照して説明する。
【００３１】
［本発明の概要］
本発明は、天体力学等の分野で知られる階層的独立固有時間刻み法と呼ばれる積分法を、ネットワークの階層的特性を活かしてグラフ可視化技術の“Force-directed法”に適用可能に組み込んだ手法である。本実施形態のグラフ可視化座標計算方法は、個々のノードに固有時間を持たせ、時間同期を行いつつ、ポテンシャル勾配の大きさによって更新時間を変えることを特徴とする。この方法は、大局的に座標更新を行いながら、局所的にも座標を求めて行くことができるという利点がある。
【００３２】
以下では、２つの従来の手法と対比させながら本発明の原理について説明する。
＜天体力学との対比＞
従来、天体力学では、天体の軌道進化を導出するために用いられ、軌道の更新式は空間座標の時間微分方捏式より式（１０）のように表すことができる。
【００３３】
【数４】
2008287497.tif 000006
【００３４】
式（１０）では、微分方程式を時間の４階微分まで表記した。これは、天体力学で広く用いられているルンゲクッタ法やエルミート法が４次精度のものが主流であるためである。天体力学では、座標と速度が決まれば、ニュートンの力学方程式より、加速度と加速度の（１階）時間微分を導出することができる。また、通常、加速度の２階時間微分を過去の状態から予測して導出する。
【００３５】
グラフ可視化技術において座標更新の計算では、エネルギの極小状態を求めることが天体力学と異なる点である。力学では、系のエネルギは、運動エネルギとポテンシャルエネルギとの和で定義される。そのため、天体力学では、運動エネルギとポテンシャルエネルギは、互いにエネルギを交換しながら、かつ、系全体のエネルギの和が保存されるように進化する。これに対して、グラフ可視化技術における座標更新の計算では、ポテンシャルエネルギのみが保存され、運動エネルギの定義が存在していない。これは、グラフ可視化の座標計算において、ノードが速度の概念を持たないためである。そのため、前記した式（１０）に示した天体軌道の微分方程式をグラフ可視化の座標計算に用いる場合には、速度を常に「０」として計算を行うために、式（１１）のように考えることとなる。
【００３６】
【数５】
2008287497.tif 000007
【００３７】
式（１１）は、摩擦係数が非常に大きい力学進化過程や、極低温まで冷却を行う分子動力学の世界を表す式に酷似している。このように速度を「０」とすることによって、結果として加速度の１階時間微分項および２階時間微分項も「０」とすることができるので、座標更新式は式（１２）で表せることとなる。
【００３８】
【数６】
2008287497.tif 000008
【００３９】
また、従来の天体力学の階層的独立時間刻み法で用いられる時間刻み幅の指標は、式（１３）で示される。
【００４０】
【数７】
2008287497.tif 000009
【００４１】
しかしながら、グラフ可視化技術では、加速度の１階時間微分項および２階時間微分項も「０」とすることができるので、式（１３）の右辺は、分母が「０」になってしまい定義することができない。そのため、グラフ可視化の座標更新で用いる時間刻み幅の指標として式（１３）をそのまま用いることはできない。ここで、グラフ可視化技術において、座標は無次元量であり、単位距離を「１」として考えても問題は無い。
【００４２】
ここで、さらに計算の効率を考慮に入れる。従来、グラフ可視化の座標更新の計算では、時間の進化を求めるのではなく、効率的に最終極小エネルギ状態を導出することが目的なので、“時間”という概念を力学的に厳密に考慮する必要が無い。時間進化を厳密に考え、次元を正確に合わせると、時間刻み幅の指標を式（１４）のように設定する必要がある。
【００４３】
【数８】
2008287497.tif 000010
【００４４】
しかしながら、式（１４）を計算するときに｜ａi（ｔi）｜の平方根を導出して時間刻み幅の指標を評価し、前記した式（１２）によって、この時間刻み幅の指標を二乗する計算を行うことは非効率である。そこで、本実施形態のグラフ可視化座標計算方法においては、系の時間を動力学的に厳密に用いずに、座標更新式を式（１５）のように近似することとする。
【００４５】
【数９】
2008287497.tif 000011
【００４６】
これにより、座標更新、および予測子の計算負荷も軽減させることができる。さらに、時間刻み幅の指標は、式（１６）のように近似することとする。これにより、平方根の計算も省略することができる。
【００４７】
【数１０】
2008287497.tif 000012
【００４８】
＜ＦＲ法との対比＞
グラフ可視化技術の“Force-directed法”の１つであるＦＲ法との対比について図１１を参照して説明する。ＦＲ法は、Shared timestepの座標更新手法を用いており、全ノードの更新を毎回行なうために、更新座標がほとんど変化しない（加速度がゼロに近い）場合でも毎回ノードを更新し続ける。一方、本実施形態のグラフ可視化座標計算方法は、Individual timestepの更新手法を用いており、全体を支配する大局的な時間とは別に、個々のノードに独立な更新時間を設定し、加速度の小さなノードに対しては更新のタイミングを長くすることにより、効率良く計算を高速化することができる。
【００４９】
しかし、Individual timestepによると、個々に独立な固有時間を持つノードは、更新時に他のノードから受ける力を計算するために、大局的な時間に従って他のノードの近以的な座標である予測子を計算しなければならない。ここで、各ノードが完全に独立な固有時間を持つと仮定すると、予測子の計算頻度が増し、莫大なコストがかかる。そこで、Individual timestepでは、計算コストを低減するために、複数のノードを時間同期させる。つまり、各ノードが持つ固有時間を階層化する。各ノードが持つ固有時間を階層化すると、予測子の計算量を軽減できるだけではなく、計算処理の並列性を高めることもできる。したがって、計算処理を一層効率化することが可能となる。
【００５０】
また、ＦＲ法では、式（９）に示す冷却関数中の収束時間ＴENDを予め設定する必要があった。しかしながら、本実施形態のグラフ可視化座標計算方法は、収束時間ＴENDを必ずしも設定する必要がない。これは、局所的にノードが密になり加速度が大きな領域では、大局的な領域と比べて精度よく座標を更新できるからである。
【００５１】
（第１実施形態）
図１は、本発明の第１実施形態に係るグラフ可視化座標計算装置の構成を示すブロック図である。グラフ可視化座標計算装置１は、複数のノードとノード間をつなぐエッジとを備えるネットワークのノード間の接続状態を可視化したグラフ上のノードの座標を階層的独立固有時間刻み法を用いて計算するものである。このグラフ可視化座標計算装置１は、図１に示すように、演算手段２と、入力手段３と、記憶手段４と、出力手段５とを備えており、各手段２〜５はバスライン６に接続されている。
【００５２】
演算手段２は、例えば、ＣＰＵ（Central Processing Unit）およびＲＡＭ（Random Access Memory）から構成される主制御装置である。この演算手段２は、図１に示すように、初期配置部２１と、初期値導出部２２と、大局時間設定部２３と、予測子導出部２４と、同期ノード導出部２５と、加速度導出部２６と、座標更新処理部２７と、独立固有時間導出部２８と、エネルギ導出部２９と、計算終了条件判定部３０と、データ制御部３１とを含んで構成される。
【００５３】
初期配置部２１は、入力された全ノードに対して、初期座標を設定するものである。本実施形態では、初期配置部２１は、乱数を発生し、発生した乱数を元に、各ノードにランダムな初期座標ｘiを与える。
初期値導出部２２は、入力された全ノードに対して、与えられた初期座標ｘiを元に、加速度ａi（０）、固有時間刻みΔｔi、全体のエネルギΨの各初期値を導出するものである。
【００５４】
大局時間設定部２３は、各ノードにおける固有時間と、加速度の大きさに反比例した固有時間刻みとの和の最小値を導出し、その値を大局時間ｔ（＝ｍｉｎ（ｔi＋Δｔi））として設定するものである。
予測子導出部２４は、入力された全ノードに対して、対象とするノードの固有時間と異なる固有時間を有するノードの配置された座標を示す仮想ノード座標と対象とするノードとの相互作用を計算するために大局時間ｔでの予測子ｘp,i（ｔ）を導出するものである。
同期ノード導出部２５は、入力された全ノードのうち、固有時間と固有時間刻みとの和の値が大局時間となるノードを示す同期ノードを求めるものである。同期ノード導出部２５は、求めた同期ノードの個数ｎs（ｔ）を導出する。
【００５５】
加速度導出部２６は、ｎs（ｔ）個の同期ノードに対して、予測子導出部２４で導出された予測子ｘp,i（ｔ）を用いて、大局時間設定部２３で設定された大局時間ｔにおける加速度ａi（ｔ）を導出するものである。
座標更新処理部２７は、同期ノードに対して、加速度導出部２６で導出された加速度と固有時間刻みとの積に、更新前の座標を加算することで、大局時間における座標を更新するものである。
【００５６】
独立固有時間導出部２８は、同期ノードに対して、加速度導出部２６で導出された加速度と、固有時間刻みを所定の離散値に制限する階層化の指標と、更新前の固有時間と、更新前の固有時間刻みとを用いて、固有時間と固有時間刻みとを更新するものである。
エネルギ導出部２９は、同期ノードに対して、加速度導出部２６で導出された加速度の勾配を示すポテンシャルエネルギを求め、求めたエネルギを全ノードに対して総計したエネルギを導出するものである。
【００５７】
計算終了条件判定部３０は、所定の計算終了条件を満たすか否かを判別するものである。データ制御部３１は、前記した初期配置部２１と、初期値導出部２２と、大局時間設定部２３と、予測子導出部２４と、同期ノード導出部２５と、加速度導出部２６と、座標更新処理部２７と、独立固有時間導出部２８と、エネルギ導出部２９と、計算終了条件判定部３０とを統括制御すると共に、演算処理データの記憶手段４への書き込み、読み出し等を行うものである。
【００５８】
入力手段３は、例えば、キーボード、マウス、ディスクドライブ装置などから構成される。この入力手段３は、例えば、データとして、対象となるネットワークのリンク情報（ノード数と、各ノードのリンク先）を入力し、記憶手段４に格納する。本実施形態では、入力手段３は、ノード数Ｎとエッジ数Ｅを入力する。
【００５９】
記憶手段４は、例えば、一般的なハードディスク装置などから構成され、演算手段２で用いられる各種プログラムや各種データ等を記憶する。演算手段２は、これらのプログラムを記憶手段４から読み込んでメモリに展開して実行することで、前記した初期配置部２１、初期値導出部２２、大局時間設定部２３、予測子導出部２４、同期ノード導出部２５、加速度導出部２６、座標更新処理部２７、独立固有時間導出部２８、エネルギ導出部２９、計算終了条件判定部３０およびデータ制御部３１の各機能を実現する。
【００６０】
出力手段５は、例えば、グラフィックボード（出力インタフェース）およびそれに接続されたモニタである。モニタは、例えば、液晶ディスプレイ等から構成され、演算処理結果（例えば、ネットワークの座標ｘi等）を表示する。
【００６１】
［演算手段の各部の詳細］
次に、演算手段２の各部の詳細について、本実施形態のグラフ可視化座標計算方法の詳細な原理と共に説明する。
＜固有時間刻みの制限＞
本実施形態のグラフ可視化座標計算方法では、座標の更新方法は、ＦＲ法と同様にForce-directed法を用いて、加速度方向に座標を更新する。具体的には、ｉ番目のノードには、それぞれ固有時間ｔi、固有時間刻みΔｔiを与えておき、座標更新処理部２７は、ｉ番目のノードについて、前記した式（１５）により、時刻がｔiになったときにおいてのみ、加速度方向へΔｔi倍だけ座標を更新する。ここで、各ノードに完全な固有時間を与えると、計算効率が低下するため、階層的で離散的な固有時間を与えて複数のノードを同期させる。そこで、固有時間刻みΔｔiを式（１７）で与える。
【００６２】
【数１１】
2008287497.tif 000013
【００６３】
ここで、ηは無次元定数で、数値計算の精度を決めると共に、各階層での最大時間更新幅を与えるものである。また、ｋは整数であって、固有時間刻みΔｔiを所定の離散値に制限する階層化の指標を示す。式（１７）のように固有時間刻みΔｔiを２のベキで与えることによって、同期ノード導出部２５は、数値計算上、複数ノードの時間同期を行うことができる。このように２のベキで与えられた固有時間刻みΔｔiのことを、時間更新幅または時間刻み幅ともいう。
【００６４】
＜更新タイミングの制限＞
次に、各ノードの更新タイミングに対し、制限を設ける。座標更新処理部２７は、全体の大局時間ｔに対して、式（１８）に示す条件を満たしたノードのみを更新する。
【００６５】
【数１２】
2008287497.tif 000014
【００６６】
この制限は、ノードの並び替えに要する数値計算を軽減させると共に、以下に述べるように固有時間刻みΔｔiの更新のタイミングに対しても制限を与える。初めにｉ番目のノードに対して、時間刻み幅の指標を、前記した式（１６）のように与える。固有時間刻みΔｔiの更新のタイミングが新しくなったときに、更新された新しい固有時間刻みΔｔnew,iは、そのときの階層化の指標ｋnewを用いると、式（１９）で表記できる。ここで、階層化の指標ｋnewは、式（２０）のように場合分けされる。
【００６７】
【数１３】
2008287497.tif 000015
【００６８】
【数１４】
2008287497.tif 000016
【００６９】
すなわち、前記した式（１６）の時間刻み幅の指標が２kより小さければ、無条件にｋ→ｋ−１とする。しかし、ｋ→ｋ＋１とする場合、つまり、Δｔi＝２k+1となる場合には、２k+1も前記した式（１８）を満たす必要がある。したがって、固有時間刻みが増加するタイミングの条件は、式（２１）で示されることとなる。
【００７０】
＜階層化の指標と大局時間との関係＞
ここで、階層化の指標ｋと大局時間ｔとの関係を模式的に図２に示す。図２は、階層的時間刻みを示す説明図であり、図２の横軸は時間、縦軸はｋをそれぞれ表している。図２においては、ｋ＝０からｋ＝−７までしか描画していないが、実際には、さらに深い階層まで時間刻みを取ることが可能であり、ｋ≧１とすることも可能である。前記した式（１７）で与えられるように、時間刻み幅は、２のｋ乗で与えられる。また、前記した式（１６）で与えられるように、加速度が大きくなる程、固有時間刻みΔｔiは小さくなり、ｋは負の絶対値が大きくなる（図２において“・”で表示した位置が下がる）。個々の独立した時間（固有時間ｔi）とは別に全体の大局的な時間ｔを設定し、個々の時間は、このｔと同期したときに更新されてゆく。つまり、図２は、各ノードが、式（１７）および式（１８）を満たす固有時間刻みΔｔiにより、図２において“・”で表示した位置の時間しか固有時間ｔiを選択することができないことを示している。
【００７１】
＜階層的固有時間刻み法の座標更新の具体例＞
階層的固有時間刻み法の座標更新について、式（２０）に示した階層化の指標ｋnewの場合分けに対応して、図３および図４を参照して説明する。図３は、ある時刻を始点とした更新時間の変更の説明図であり、図４は、他の時刻を始点とした更新時間の変更の説明図である。
【００７２】
≪ある時刻を始点とする場合≫
まず、図３を参照して説明する。図３は、例えば、図２においてｋ＝−３、かつ、ｔ＝２-3の位置に表示した“・”で示される位置に相当する位置の拡大図である。ここでは、“・”で示される位置に対応する更新時刻に存在する１つのノードに着目し、そのノード番号をｉとする。このノード番号ｉのノードは、更新前の時間更新幅が、Δｔi＝２kである。このとき、このノードは、階層化の指標ｋで示される階層（以下、単にｋの階層という）において、図３（ａ）に示す符号３０１で示す位置に存在するものとする。加速度導出部２６は、このノードの加速度を求め、独立固有時間導出部２８は、時間刻み幅の指標を前記した式（１６）より求める。座標更新処理部２７は、前記した式（２０）に従い、時間更新幅を求める。
【００７３】
前記した式（１６）の時間刻み幅の指標が２kより小さい場合には、このノードは、（ｋ−１）の階層、つまり、図３（ｂ）に符号３０２で示す位置に下がり、（ｋ−１）の階層における次の更新時刻には、符号３０３に示す位置まで移動する。
【００７４】
また、前記した式（１６）の時間刻み幅の指標が２k+1以上の場合には、このノードは、図３（ａ）に符号３０１で示す位置の時刻では、前記した式（２１）の条件を満たさない。そのため、（ｋ＋１）の階層に移動することができない。つまり、図３（ｃ）に符号３０４で示す位置に移動することができない。したがって、ｋの階層に留まり、ｋの階層における次の更新時刻には、図３（ｃ）に符号３０５で示す位置まで移動する。
【００７５】
さらに、前記した式（１７）の条件の場合には、図３（ａ）に符号３０１で示す位置の時刻では、時間更新幅は、そのままである。そのため、このノードは、ｋの階層に留まり、次の更新時刻には、図３（ｃ）に符号３０５で示す位置まで移動する。
【００７６】
≪他の時刻を始点とする場合≫
次に、図４を参照して説明する。図４は、例えば、図２においてｋ＝−３、かつ、ｔ＝２-2の位置に表示した“・”で示される位置に相当する位置の拡大図である。ここでは、“・”で示される位置に対応する更新時刻に存在する１つのノードに着目し、そのノード番号をあらためてｉとする。このノード番号ｉのノードは、更新前の時間更新幅が、Δｔi＝２kである。このとき、このノードは、ｋの階層において、図４（ａ）に示す符号４０１で示す位置に存在するものとする。加速度導出部２６、独立固有時間導出部２８、および、座標更新処理部２７は、それぞれ同様な処理を行う。
【００７７】
前記した式（１６）の時間刻み幅の指標が２kより小さい場合には、このノードは、（ｋ−１）の階層、つまり、図４（ｂ）に符号４０２で示す位置に下がり、（ｋ−１）の階層における次の更新時刻には、符号４０３に示す位置まで移動する。
【００７８】
また、前記した式（１６）の時間刻み幅の指標が２k+1以上の場合には、このノードは、図４（ａ）に符号４０１で示す位置の時刻では、前記した式（２１）の条件を満たす。そのため、（ｋ＋１）の階層に移動することができる。つまり、図４（ｃ）に符号４０４で示す位置に移動することができ、（ｋ＋１）の階層において、次の更新時刻には、図４（ｃ）に符号４０５で示す位置まで移動する。
【００７９】
さらに、前記した式（１７）の条件の場合には、図４（ａ）に符号４０１で示す位置の時刻では、時間更新幅は、そのままである。そのため、このノードは、ｋの階層に留まり、次の更新時刻には、図４（ｄ）に符号４０６で示す位置まで移動する。
【００８０】
＜時間刻み幅の上限および下限＞
本実施形態では、計算の更新条件として、時間刻み幅に上限値（Δｔmax）と下限値（Δｔmin）とが設定されている。更新時間幅に上限値を設けることにより、一定の間隔で全ノードの時間同期をさせて、定期的な座標データの保存やエネルギ評価を行うことができる。また、初期配置部２１は、初期配置を乱数で与えるため、何もしなければ、加速度導出部２６で算出される加速度が限りなく大きくなってしまう（発散してしまう）ことになる。また、下限値を設定しないと、初期配置から計算が進行しなくなってしまうことになる。そこで、Δｔi＝Δｔminとなったときには、前記した式（１６）の時間刻み幅の指標を用いて更新座標を式（２２）で与えることとする。つまり、本実施形態では、更新時間幅に下限値を設けることにより、熱力学における最大温度が予め設定されていることとなる。なお、本実施形態では、Δｔmax＝１、Δｔmin＝２-10とした。
【００８１】
【数１５】
2008287497.tif 000017
【００８２】
＜同期ノード＞
本実施形態では、入力された全ノードのうち、そのノードの固有時間ｔiが大局時間ｔと同期したノードの集合Γ（ｔ）のみが更新される。大局時間設定部２３は、式（２３）により、大局時間ｔを更新する。このときに同期しているノードの集合Γ（ｔ）は、式（２４）で定義される。同期ノード導出部２５は、ノードの集合Γ（ｔ）を求め、求めたノードの個数を式（２５）に示すようにｎs（ｔ）とする。
【００８３】
【数１６】
2008287497.tif 000018
【００８４】
通常、対象とするノードの固有時間と異なる固有時間を有するノードの配置された座標を示す仮想ノード座標と、対象とするノードとの相互作用を計算するための計算量は、入力された全ノード（ノード数Ｎ）に対して、時刻ｔにおいて、１ステップ当たりＯ（Ｎ2）だけ必要とする。しかしながら、本実施形態によれば、階層化された同期ノードを考慮するので、ノード間の相互作用の計算量は、入力された全ノード（ノード数Ｎ）に対して、時刻ｔにおいては１ステップ当たりＯ（ｎs（ｔ）×Ｎ）に軽減することができる。
【００８５】
＜予測子＞
一般に、階層的独立固有時間刻み法では、異なる固有時間を持つノードからの力を計算するために、予測子を用いて、仮想ノード座標からの相互作用を計算する。本実施形態では、時刻ｔにおける予測子ｘp,i（ｔ）は、固有時間との差分だけ座標更新させて、式（２６）で与える。予測子導出部２４は、式（２６）で示す予測子について、入力された全ノードで更新を行う。
【００８６】
【数１７】
2008287497.tif 000019
【００８７】
＜加速度の導出方法＞
加速度導出部２６は、前記した式（２６）の予測子を用いるが、入力された全ノードで更新を行うわけではなく、時間が同期しているｎs（ｔ）個のノード集合に対して、加速度ａi（ｔ）を計算する。本実施形態では、前記したＦＲ法の加速度公式である式（５）〜式（７）を用いて、加速度ａi（ｔ）を式（２７）で与える。ここで、ｘijは、前記した式（２）とは異なり、予測子を用いて式（２８）で定義される。また、εは、Softening parameterであり、式（２７）において、右辺第２項が｜ｘij｜→０で発散してしまうのを防ぐための補正項である。本実施形態では、例えば、ε＝０．０１、定数Ｋ＝１とすることができる。
【００８８】
【数１８】
2008287497.tif 000020
【００８９】
＜ポテンシャルエネルギΨの定義＞
グラフ可視化の座標計算においては、ノード間やエッジに力学方程式を与えれば、ｉ番目のノードについてのポテンシャルエネルギΦiと加速度ａiとの関係は、ポテンシャル勾配より式（２９）に示すように決定される。式（２９）中の∇はナブラである。
【００９０】
【数１９】
2008287497.tif 000021
【００９１】
前記した式（２７）〜式（２９）によれば、ｉ番目のノードについてのポテンシャルエネルギΦiは、式（３０）で表される。したがって、系全体（入力された全ノード）のポテンシャルエネルギΨは、式（３１）で与えられる。エネルギ導出部２９は、式（３０）および式（３１）を用いて、ポテンシャルエネルギΨを導出する。以下では、このΨを評価関数として扱う。
【００９２】
【数２０】
2008287497.tif 000022
【００９３】
＜平均ステップ数の定義＞
本実施形態では、エネルギ導出部２９は、式（３２）で定義される平均ステップ数ｎaveを算出することとした。ここで、平均ステップ数ｎaveは、対象とする大局時間ｔまでの同期ノードの個数ｎs（ｔ）の和をノード数Ｎで除した数値である。
【００９４】
【数２１】
2008287497.tif 000023
【００９５】
本実施形態では、式（３２）に示す平均ステップ数ｎaveを計算量に対してのエネルギ収束性評価のために用いた。この平均ステップ数ｎaveは、従来のＦＲ法の計算ステップ数に相当するものである。
【００９６】
なお、実際には、エッジ数Ｅも計算負荷に関わるが、本実施形態は、ネットワークデータとしてスパースデータ（sparse data）を扱うため、エッジ数Ｅは、ノード数の２乗（Ｎ2）に対して無視できる。つまり、Ｎ2≫Ｅを満たす。したがって、ノードに張られているエッジに関する加速度の計算にかかる負荷よりも、ノード間の加速度の計算にかかる負荷が高くなる。そのため、本実施形態において、計算量の評価は、式（３２）で定義される平均ステップ数ｎaveを用いる。
【００９７】
[グラフ可視化座標計算装置の動作]
図１に示したグラフ可視化座標計算装置１の動作について図５を参照（適宜図１参照）して説明する。図５は、図１に示したグラフ可視化座標計算装置の動作を示すフローチャートである。グラフ可視化座標計算装置１は、入力手段３によって、対象となるネットワークのノード数Ｎとエッジ数Ｅを入力し、記憶手段４に格納し（ステップＳ１）、初期配置部２１によって、入力された全ノードに対して、初期座標を設定する（ステップＳ２）。そして、グラフ可視化座標計算装置１は、初期値導出部２２によって、入力された全ノードに対して、加速度、固有時間刻み、エネルギの各初期値を導出する（ステップＳ３）。
【００９８】
次に、グラフ可視化座標計算装置１は、大局時間設定部２３によって、前記した式（２３）を用いて、各ノードにおける固有時間ｔiと固有時間刻みΔｔiとの和の最小値を導出し、その値を大局時間ｔとして設定（算出）する（ステップＳ４：大局時間設定ステップ）。そして、グラフ可視化座標計算装置１は、予測子導出部２４によって、入力された全ノードに対して、前記した式（２６）で示す予測子ｘp,iを導出する（ステップＳ５：予測子導出ステップ）。そして、グラフ可視化座標計算装置１は、同期ノード導出部２５によって、入力された全ノードのうち、同期ノード（ｔi＋Δｔi＝ｔとなるノード）を求め、その個数をｎs（ｔ）とする（ステップＳ６：同期ノード導出ステップ）。そして、グラフ可視化座標計算装置１は、加速度導出部２６によって、ｎs（ｔ）個の同期ノードに対して、ステップＳ５で導出された予測子を用いて、大局時間ｔにおける加速度ａi（ｔ）を前記した式（２７）を用いて導出する（ステップＳ７：加速度導出ステップ）。
【００９９】
次に、グラフ可視化座標計算装置１は、座標更新処理部２７によって、ｎs（ｔ）個の同期ノードに対して、前記した式（１５）に基づいて、ステップＳ７で導出された加速度と固有時間刻みとの積に、更新前の座標を加算することで、大局時間における座標ｘi（ｔ）を更新する（ステップＳ８：座標更新処理ステップ）。また、グラフ可視化座標計算装置１は、独立固有時間導出部２８によって、ｎs（ｔ）個の同期ノードに対して、ステップＳ７で導出された加速度と、固有時間刻みを所定の離散値に制限する階層化の指標ｋと、更新前の固有時間と、更新前の固有時間刻みとを用いて、固有時間ｔiと固有時間刻みΔｔiとを更新する（ステップＳ９：独立固有時間導出ステップ）。そして、グラフ可視化座標計算装置１は、エネルギ導出部２９によって、同期ノードに対して、ステップＳ７で導出された加速度の勾配を示すポテンシャルエネルギを求め、求めたエネルギを全ノードに対して総計したエネルギΨを導出する（ステップＳ１０：エネルギ導出ステップ）。
【０１００】
次に、グラフ可視化座標計算装置１は、計算終了条件判定部３０によって、計算終了条件を満たすか否かを判別する（ステップＳ１１）。計算終了条件を満たさない場合（ステップＳ１１：Ｎｏ）、グラフ可視化座標計算装置１は、ステップＳ４に戻る。一方、計算終了条件を満たす場合（ステップＳ１１：Ｙｅｓ）、グラフ可視化座標計算装置１は、出力手段５によって、対象となるネットワークの各ノードの座標と、総計したエネルギΨを出力し（ステップＳ１２）、処理を終了する。
【０１０１】
なお、グラフ可視化座標計算装置１は、一般的なコンピュータに、前記した各ステップを実行させるグラフ可視化座標計算プログラムを実行することで実現することもできる。このプログラムは、通信回線を介して配布することも可能であるし、ＣＤ−ＲＯＭ等の記録媒体に書き込んで配布することも可能である。
【０１０２】
第１実施形態によれば、例えば、ブログ、ウェブページ、ソーシャルネットワーク等をノードとし、それらの関係がネットワークとして表現されるデータが与えられたときに、与えられたデータが大規模である場合であっても、高速に座標計算を行うことができる。その結果、大規模なネットワークデータが与えられても高速かつ効率よくグラフを描画することができる。また、第１実施形態によれば、ネットワークの可視化において、従来天体力学において提案された階層的独立固有時間刻み法をネットワークの可視化に好適に利用することが可能である。そのため、高速に、かつ効率よく座標計算を行うことができる。
【０１０３】
（第２実施形態）
本発明のグラフ可視化座標計算方法が固有時間の階層化によって複数のノードを時間同期させることによって並列性を高めるものである。したがって、ＰＣクラスタ（コンピュータクラスタ）などの並列処理を有するコンピュータのシステム環境によって計算の高速化が可能である。一般に大規模ネットワークの計算においては、ノード間（個々の部分）の計算が全体の９９％以上を占める。そのため、ノード間の相互作用計算を高速化することは重要課題の一つである。そこで、第２実施形態のグラフ可視化座標計算装置は、ホストコンピュータと、ノード間の計算に対して使用される高速計算機ボードとを備える構成とした。
【０１０４】
[グラフ可視化座標計算装置の構成]
図６は、本発明の第２実施形態に係るグラフ可視化座標計算装置の構成を示すブロック図である。第２実施形態に係るグラフ可視化座標計算装置１Ａは、互いに接続されたホストコンピュータ１００と、高速計算機ボード２００とを備えている。
ホストコンピュータ１００は、Ｏ（Ｅ）またはＯ（Ｎ）の計算を行うものである。具体的には、ホストコンピュータ１００は、エッジに働く加速度の計算処理と、エッジに働くエネルギの計算処理と、座標更新の計算処理と、固有時間の更新の計算処理とを実行する。また、ホストコンピュータ１００は、座標更新の計算処理結果として座標情報を高速計算機ボード２００に出力する。
【０１０５】
高速計算機ボード２００は、Ｏ（Ｎ2）の計算を行うものである。具体的には、高速計算機ボード２００は、前記した式（２７）によってノード間に働く加速度の計算処理を実行すると共に、前記した式（３０）および式（３１）によってノード間に働くエネルギの計算処理を実行する。また、高速計算機ボード２００は、計算処理結果として、加速度情報とエネルギ情報とをホストコンピュータ１００に出力する。つまり、第２実施形態に係るグラフ可視化座標計算装置１Ａでは、高速計算機ボード２００が、図１に示した加速度導出部２６と、エネルギ導出部２９との機能を果たす構成とした。この高速計算機ボード２００は、例えば、粒子間相互作用専用計算機のMDGRPE-3から構成される。
【０１０６】
図７は、図６に示した高速計算機ボードの構成を示すブロック図である。高速計算機ボード２００は、座標情報（ｘj、ｙj）およびSoftening parameterであるε2をメモリ２１０に記憶しており、ホストコンピュータ１００から入力する座標情報（ｘi、ｙi）を用いて、前記した式（２７）によってノード間に働く加速度の計算処理を実行すると共に、前記した式（３０）および式（３１）によってノード間に働くエネルギの計算処理を実行する。高速計算機ボード２００は、スイッチＳＷを有しており、このスイッチＳＷを切り替えてpipe lineを入れ替えることによって、加速度導出部２６の機能により、加速度（force）を求め、エネルギ導出部２９の機能によって、エネルギ（energy）を求める。
【０１０７】
第２実施形態によれば、ホストコンピュータ１００と、ノード間の計算に対して使用される高速計算機ボード２００とを備える簡易な構成で、ノード間の相互作用を迅速に計算することが可能となる。これにより、汎用マシンよりもさらに高速に計算を行うことが可能である。
【０１０８】
以上、本発明の各実施形態について説明したが、本発明はこれらに限定されるものではなく、その趣旨を変えない範囲で実施することができる。例えば、グラフ可視化座標計算装置１の演算手段２を構成する各部は、１台に限定されることはなく、複数の装置に機能を分散配置してもよい。これにより、各装置への負荷が分散され、高速な処理が実現可能となる。また、第２実施形態のグラフ可視化座標計算装置１Ａでは、高速計算機ボード２００は、MDGRPE-3から構成されるものとしたが、これは一例であって、これに限定されるものではない。
【実施例】
【０１０９】
本発明の効果を確認するために、本実施形態に係るグラフ可視化座標計算装置１を用いて、前記した式（３１）で示すポテンシャルエネルギΨを評価関数として求めた。
【０１１０】
＜設定＞
実施例では、入力するネットワークデータ（グラフデータ）として、“Opte Project”のＩＰネットワークのデータを用いた。このデータは、サイト（Lyon, B, Opte as an Aesthetic Experience, The Opte Project(2005),http://www. opte. org/）からデータファイルをダウンロードすることが可能である。本実施例では、2005年１月に収集されたノード数Ｎ＝40027、エッジ数Ｅ＝47215のネットワークデータを用いた。
【０１１１】
＜エネルギΨの変化＞
評価関数として求めたエネルギΨの変化を図８に示す。本実施例との比較例として、ＦＲ法に対して、収束時間ＴEND＝100（太い実線）、収束時間ＴEND＝1000（短く細い破線）、収束時間ＴEND＝5000（長く細い破線）、収束時間ＴEND＝10000（細い実線）と変えてエネルギΨの計算を行なった。図８のグラフでは、縦軸はエネルギΨであり、横軸は、ＦＲ法に対しては、計算ステップ数「Ｔ」であり、実施例（Our method：長く太い破線）に対しては、平均ステップ数「ｎave」である。なお、横軸の指標の数値は同一である。
【０１１２】
この図８によれば、ＦＲ法では、収束時間ＴEND＝100、1000では、エネルギΨがまだ十分収束せず、エネルギΨを収束させるためには収束時間ＴEND≧5000とする必要があることが分かる。一方、本実施例（Our method）では、ＦＲ法よりも早期にエネルギΨが収束していることが分かる。
【０１１３】
＜可視化結果＞
図８に示したエネルギΨの変化に対応して、本実施例の可視化グラフ（可視化結果）を図９に示すと共に、比較例のＦＲ法の可視化グラフ（可視化結果）を図１２に示す。比較例のＦＲ法では、図１２（ｃ）に示すように、収束時間ＴEND≧5000としなければ、ネットワーク構造がまったく見えてこなかった。一方、実施例では、図９に示すように、初期の段階（例えば、平均ステップ数ｎave＝100、1000）からネットワークの全体的な構造が見え始める。これは、本実施形態に係るグラフ可視化座標計算方法がネットワーク構造を階層的に計算するために、クリーク（clique）性の高いサブネットワーク構造に対し、初期段階から優先的に計算を行うからである。図９により、本実施形態に係るグラフ可視化座標計算方法は、ノードの更新を階層的に設定することにより、ＦＲ法よりも早い段階でネットワーク全体の構造を与えることが示された。
【０１１４】
＜実装例＞
また、本実施形態に係るグラフ可視化座標計算装置１Ａにおいて、ホストコンピュータ１００をIntel Xeon 3.2GHzで構成すると共に、高速計算機ボード２００をMDGRPE-3で構成して計算処理時間を測定した。測定に際し、平均ステップ数ｎave＝59.16まで計算を行った。その結果、ホストコンピュータ１００のみ（グラフ可視化座標計算装置１）で行った場合には「219.5分」かかった計算が、MDGRPE-3を導入したグラフ可視化座標計算装置１Ａでは「28.4秒」で行うことができ、約450倍の高速化を可能とした。なお、MDGRPE-3 PCI-Xの仕様を表１に示す。
【０１１５】
【表１】
2008287497.tif 000024
【０１１６】
粒子間相互作用専用計算機MDGRPE-3 PCI-Xは、小規模応用／商用化目的を兼ねて理化学研究所で開発された、PCI-X準拠の専用計算ボードである。１ボードにつきMDGRPE-3のチップを２台搭載し、汎用Linuxマシンで使用可能である。１ボードあたり330ギガフロップス（3300億計算／秒）の性能を実現できる。MDGRPE-3は、2006年のIEEE Gordon Bell Prizeでは、ピーク性能部門（Honorable Mention）を受賞している。同システムは、３次元座標まで計算が可能で、ベクトル関数およびスカラー関数は、自由に設定することができる。
【０１１７】
なお、表１において、１フロップス（flops：Floating point number Operations Per Second）は、大規模なシミュレーションや科学技術計算に用いる大型コンピュータの性能指標としてよく用いられる、コンピュータの処理速度を表す単位の一つである。例えば、処理速度が１flopsのコンピュータは、１秒間に１回の浮動小数点数演算（実数計算）ができることを示す。
【図面の簡単な説明】
【０１１８】
【図１】本発明の第１実施形態に係るグラフ可視化座標計算装置の構成を示すブロック図である。
【図２】階層的時間刻みを示す説明図である。
【図３】ある時刻を始点とした更新時間の変更の説明図である。
【図４】他の時刻を始点とした更新時間の変更の説明図である。
【図５】図１に示したグラフ可視化座標計算装置の動作を示すフローチャートである。
【図６】本発明の第２実施形態に係るグラフ可視化座標計算装置の構成を示すブロック図である。
【図７】図６に示した高速計算機ボードの構成を示すブロック図である。
【図８】実施例で算出されたエネルギの時間変化を示すグラフである。
【図９】実施例で算出された座標値で作成した可視化グラフである。
【図１０】ノードとエッジの模式図である。
【図１１】座標更新を示す概念図であり、（ａ）はShared timestep、（ｂ）はIndividual timestepをそれぞれ示している。
【図１２】従来の座標更新方法で算出された座標値で作成した可視化グラフである。
【符号の説明】
【０１１９】
１（１Ａ）  グラフ可視化座標計算装置
２      演算手段
３      入力手段
４      記憶手段
５      出力手段
６      バスライン
２１    初期配置部
２２    初期値導出部
２３    大局時間設定部
２４    予測子導出部
２５    同期ノード導出部
２６    加速度導出部
２７    座標更新処理部
２８    独立固有時間導出部
２９    エネルギ導出部
３０    計算終了条件判定部
３１    データ制御部
１００  ホストコンピュータ
２００  高速計算機ボード
２１０  メモリ
ＳＷ    スイッチ
【図１】
2008287497.tif 000025
【図２】
2008287497.tif 000026
【図３】
2008287497.tif 000027
【図４】
2008287497.tif 000028
【図５】
2008287497.tif 000029
【図６】
2008287497.tif 000030
【図７】
2008287497.tif 000031
【図８】
2008287497.tif 000032
【図１０】
2008287497.tif 000033
【図１１】
2008287497.tif 000034
【図９】
2008287497.tif 000035
【図１２】
2008287497.tif 000036