(57)【特許請求の範囲】
【請求項１】
複数のノードと該ノード間をつなぐエッジで構成されるグラフデータを可視化するグラフ可視化表示装置であって、
複数のノードと該ノード間の関係性をエッジとして表現したグラフデータに基づいて、グラフ可視化イメージを生成する処理手段と、
前記処理手段において生成された前記グラフ可視化イメージを表示する表示手段と、を備え、
前記処理手段は、
前記表示手段に表示されるディスプレイ空間上にノードを追加する際には、追加される追加ノードと接続関係にある、既に配置されている既存配置ノード群の重心に前記追加ノードを配置した後に、所定の力学モデルに従って各ノードの位置を修正し、
複数の追加ノードを追加する際には、当該複数の追加ノードのいずれかのみと接続関係にある追加ノードよりも、いずれかの前記既存配置ノードと接続関係にある追加ノードから先に配置を行う、
ことを特徴とするグラフ可視化表示装置。
【請求項２】
前記処理手段は、
前記既存配置ノード群の重心に前記追加ノードを配置する際に、同じ接続情報を持つノードが存在する場合には、乱数を用いて微少に配置をずらして前記追加ノードを追加する
請求項１記載のグラフ可視化表示装置。
【請求項３】
前記処理手段は、
前記追加ノードが前記既存配置ノードとの接続関係が一つだけである場合は、接続関係にある該既存配置ノードの近傍に前記追加ノードを配置する
請求項１記載のグラフ可視化表示装置。
【請求項４】
前記処理手段は、
前記既存配置ノードとの接続関係がない前記追加ノードを、前記ディスプレイ空間上の任意の場所に配置する
請求項１記載のグラフ可視化表示装置。
【請求項５】
複数のノードと該ノード間をつなぐエッジで構成されるグラフデータを可視化するグラフ可視化表示方法であって、
複数のノードと該ノード間の関係性をエッジとして表現したグラフデータに基づいて、グラフ可視化イメージを生成する処理手段と、
前記処理手段において生成された前記グラフ可視化イメージを表示する表示手段と、を備える装置において、
前記処理手段が、
前記表示手段に表示されるディスプレイ空間上にノードを追加する際には、追加される追加ノードと接続関係にある、既に配置されている既存配置ノード群の重心に前記追加ノードを配置する配置ステップと、
前記配置ステップの後に、所定の力学モデルに従って各ノードの位置を修正する修正ステップと、
を行い、
前記配置するステップにおいて、複数の追加ノードを追加する際には、当該複数の追加ノードのいずれかのみと接続関係にある追加ノードよりも、いずれかの前記既存配置ノードと接続関係にある追加ノードから先に配置を行う、
ことを特徴とするグラフ可視化表示方法。
【請求項６】
前記配置ステップにおいて、
前記既存配置ノード群の重心に前記追加ノードを配置する際に、同じ接続情報を持つノードが存在する場合には、乱数を用いて微少に配置をずらして前記追加ノードを追加する
請求項５記載のグラフ可視化表示方法。
【請求項７】
前記配置ステップにおいて、
前記追加ノードが前記既存配置ノードとの接続関係が一つだけである場合は、接続関係にある該既存配置ノードの近傍に前記追加ノードを配置する
請求項５記載のグラフ可視化表示方法。
【請求項８】
前記配置ステップにおいて、
前記既存配置ノードとの接続関係がない前記追加ノードを、前記ディスプレイ空間上の任意の場所に配置する
請求項５記載のグラフ可視化表示方法。
【請求項９】
コンピュータを、
請求項１乃至４のいずれか１項に記載のグラフ可視化表示装置の各手段として機能させるためのグラフ可視化表示プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グラフデータ可視化表示装置及び方法及びプログラムに係り、特に、複数ノードと当該ノード間をつなぐエッジで構成されるグラフデータを可視化するためのグラフデータ可視化表示装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
ネットワークをグラフとして可視化する技術（以下、単に「可視化技術」と記す）は、一般にデータとデータとの関連性によってネットワークを形成したグラフデータを可視化することを指す。グラフデータでは、当該要素を示すノードとノード間を繋ぐエッジとで表すことにより視覚化することが可能である。例えば、インターネット上のハイパーリンクの張られたWEBページであれば、各WEBページをノードとして、ハイパーリンクをエッジとして表現することにより、グラフ可視化表示をすることが可能である。また、例えば、金融・通信・交通・社会組織・遺伝子情報などのネットワーク表示、化学・生物学・医学などのデータをグラフ化したものの表示、テキストデータや画像データを関連性をもとにグラフ化したものの表示、関連性のあるモジュール群の組み合わせ表示（例えば、ICチップのLSI設計図）、地図や参考書の図解表示に用いられるラベル表示などのように、種々の用途が考えられる。それゆえ、コンピュータによる力学的アルゴリズムを用いたグラフ可視化表示技術は、非常に幅広い分野での需要のある技術である。
【０００３】
＜条件＞
グラフ可視化表示技術における重要かつ最大の目的は、グラフ可視化表示装置上において、次の2つの条件を可能な限り満たすことが好ましいとされている。
【０００４】
[条件１]  ノード同士を重ならないように配置する。
【０００５】
[条件２]  関連性のあるノード同士はエッジを介して接続させ、近傍に配置する。
【０００６】
これらの条件を図1に示す。[条件1］は、異なるノード情報が重なって表示されることによる情報の誤読を防ぐためである。[条件２]は、関連性のあるノードを近傍に配置することにより視覚的な情報認識精度を向上させるためである。上記の２つの条件を満たすべく、ノードのグラフ可視化表示装置上での配置座標を求めることが必要である。
【０００７】
＜関連技術＞
[基本技術]
従来、上記の条件を満たすためのグラフ可視化表示技術には、一般的に力学モデルを用いた手法が広く利用されており、以下の２つが世界中で最も頻繁に利用されている。
【０００８】
・バネモデル法：全てのノード間に仮想的なバネを仮定し、座標の更新手法を1ノードずつ逐次的に行う手法である。一般的に、ノード間のグラフ上での最短経路パス数を、ノード間のバネの自然長として計算を行う（例えば、非特許文献1参照）。
【０００９】
・Force-directed法：全てのノード間で斥力を与え（例えば、分子間に働くクーロン斥力のように）、接続されているノード間（エッジ）には引力を与え、座標の更新をこの引力と斥力の総和を用いてまとめて更新していく（例えば、非特許文献２参照）。
【００１０】
上記の２つのいずれの手法においても、全てのノード間に反発する力が働き[条件１]で要求される、ノード同士の重なりの排除を実施することができる。また、接続するノード同士では引き合う力が働き、[条件２]で要求される、接続ノードを近傍に配置することを実施することができる。
【００１１】
また、上記の２つの手法においては、引力と斥力の関数が一意に決まると、最急降下法やニュートン法などの数値計算法を用いて、目的関数が収束する（最大エントロピーが求まる）ように座標を更新する。
【００１２】
上記の条件２に対して、「最適な配置を高速に求める」という技術に対するグラフ可視化表示技術に関しては、1980年代以降様々な手法が提案されてきた。最適な配置を高速に求めることに関する問題は、大きく分けて２つのアプローチがある。
【００１３】
[アプローチ１]効率的な初期配置を行い、数値計算の目的関数に対する収束を早めさせる。
【００１４】
[アプローチ２]最適配置のための数値計算を高速化する。
【００１５】
通常、演算の高速化に関して特に効果的なのは[アプローチ２]であり、いかに高速に処理を行うかが鍵となっている。しかしながら、本発明において、問題視している課題は「ノード数やエッジ数が変化するなど、データ構造が変化し続けるストリーミングデータ」に対して、リアルタイムにグラフ可視化表示を行う技術の要求である。そのため、[アプローチ１]で述べた「効率的な初期配置手法」が、特に大規模なストリーミングデータを扱うグラフ可視化表示に関して要求される。尚、[アプローチ２]では、特に近似手法を用いた高速化は幾つかの手法が提案されているが、本発明とは対立せず、両立可能な技術であるため、本発明の課題として含めない。
【００１６】
[アプローチ１]では、代表的な手法として、LGL法を用いたグラフ可視化計算手法がある（例えば、非特許文献３参照）。LGL法は、グラフデータ構造から最小全域木を作成し、作成された全域木の木構造を元に描画を行う。
【００１７】
また次数を考慮して次数の高いものから中心付近に配置して計算処理を行ってゆく方法が提案されている（例えば、特許文献1参照）。当該手法は、ターゲットとするグラフデータは数十〜数百ノード程度で、全てのノードが連結されている場合に非常に有効である。
【先行技術文献】
【特許文献】
【００１８】
【特許文献１】特開2002-312803号公報
【非特許文献】
【００１９】
【非特許文献１】Kamada, T., and Kawai, S.: An algorithm for drawing general undirected graphs, Information Processing Letters, 12, 31, 7-15 (1989).
【非特許文献２】Fruchterman, T. M. J., and Reingold, E. M.: Graph Drawing by Force-directed Placement, Software - Practice and Experience, 11, 21, 1129-1164 (1991).
【非特許文献３】Adai, LGL: creating a map of protein function with an algorithm for visualizing very large biological networks Lyon, B.: The Opte Project (2005). http://www.opte.org/
【発明の概要】
【発明が解決しようとする課題】
【００２０】
上述したグラフ可視化表示技術に対して、基本的に求められる要件は、「最適な配置を高速に求める」ことである。具体的には、パソコンのディスプレイ装置に表示されたウィンドウ内、もしくは印刷に耐えられる画像データのサイズ内に収まる程度（現実的には数百から数千ノード規模）のグラフデータをウィンドウ内であれば数秒程度で、印刷物としても数分以内に配置の計算を行う必要性がある。このとき、上記の２つの条件である「ノード同士が重ならず」かつ「関連性のあるものは近傍に配置」を満たすことが要求される。
【００２１】
また、近年では、Twitter(登録商標)やFacebook（登録商標）といった、SNS（Social Networking Service）を利用したマイクロブログが流行し、常にデータが増加し続ける。このWeb上で増え続けている大規模データ分析においては、データストリームをリアルタイムに処理し、同時に「可視化」することが要求されている。それゆえ、グラフ可視化技術においても、ノード数やエッジ数が変化するなど、データ構造が変化し続けるストリーミングデータの可視化技術が要求されている。
【００２２】
また、初期配置とストリーミング処理における[アプローチ１]における最小全域木を用いた手法では、接続関係を排除するという近似の影響が強く出てしまうため、エッジ接続を持ちながら、極端に離れたノードのペアが生じてしまうため、好ましくない結果が生じる。つまり、[条件1]を満たすことは可能であるが、[条件２]に関しては可読性を十分満たすことができない。
【００２３】
また、特許文献1の手法では、部分グラフから構成されているグラフデータや、特に大規模なグラフデータでは有効な手段ではない。
【００２４】
本発明は、上記の点に鑑みなされたもので、グラフ可視化表示技術において、ノード数やエッジ数が変化するなど、データ構造が変化し続けるストリーミングデータに対して、ノード同士が重ならず、かつ、関連性のあるものは近傍に配置、という２つの条件を満たし、リアルタイムに最適な配置を高速に求めることが可能なグラフデータ可視化表示装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００２５】
上記の課題を解決するため、本発明（請求項１）は、複数のノードと該ノード間をつなぐエッジで構成されるグラフデータを可視化するグラフ可視化表示装置であって、
複数のノードと該ノード間の関係性をエッジとして表現したグラフデータに基づいて、グラフ可視化イメージを生成する処理手段と、
前記処理手段において生成された前記グラフ可視化イメージを表示する表示手段と、を備え、
前記処理手段は、
前記表示手段に表示されるディスプレイ空間上にノードを追加する際には、追加される追加ノードと接続関係にある、既に配置されている既存配置ノード群の重心に前記追加ノードを配置した後に、所定の力学モデルに従って各ノードの位置を修正し、
複数の追加ノードを追加する際には、当該複数の追加ノードのいずれかのみと接続関係にある追加ノードよりも、いずれかの前記既存配置ノードと接続関係にある追加ノードから先に配置を行う。
【００２７】
また、本発明（請求項２）は、前記処理手段において、
前記既存配置ノード群の重心に前記追加ノードを配置する際に、同じ接続情報を持つノードが存在する場合には、乱数を用いて微少に配置をずらして前記追加ノードを追加する。
【００２８】
また、本発明（請求項３）は、前記処理手段において、
前記追加ノードが前記既存配置ノードとの接続関係が一つだけである場合は、接続関係にある該既存配置ノードの近傍に前記追加ノードを配置する。
【００２９】
また、本発明（請求項４）は、前記処理手段において、
前記既存配置ノードとの接続関係がない前記追加ノードを、前記ディスプレイ空間上の任意の場所に配置する。
【発明の効果】
【００３０】
上述のように、本発明によれば、ストリーミングデータや時系列グラフデータのように、グラフデータのノード情報に追加や削除が起きる場合、グラフ可視化表示における処理速度の向上を図り、追加ノード配置の効率化による品質の向上と高速な処理という要求を高度に両立させることが可能となる。
【図面の簡単な説明】
【００３１】
【図１】グラフ可視化表示技術に要求される条件を示す図である。
【図２】本発明の一実施の形態におけるグラフ可視化表示装置の構成図である。
【図３】本発明の一実施の形態における処理装置の動作のフローチャートである。
【図４】本発明の一実施の形態における追加ノード配置決定部の処理のフローチャートである。
【図５】本発明の一実施の形態における追加ノードの配置手法を示す図（その１）である。
【図６】本発明の一実施の形態における追加ノードの配置手法を示す図（その２）である。
【図７】本発明の一実施の形態における追加ノードの配置手法を示す図（その３）である。
【図８】本発明の一実施の形態における人物データを用いた共起グラフ可視化の例である。
【図９】本発明の一実施の形態におけるサンプルデータ（その１）である。
【図１０】本発明の一実施の形態におけるサンプルデータ（その２）である。
【図１１】従来技術と本発明の比較を示す図（その１）である。
【図１２】従来技術と本発明の比較を示す図（その２）である。
【発明を実施するための形態】
【００３２】
以下、図面と共に本発明の実施の形態を説明する。
【００３３】
図２は、本発明の一実施の形態におけるグラフデータ可視化表示装置の構成を示す。
【００３４】
同図に示すグラフ可視化表示装置１０は、処理対象であるグラフデータを格納した記憶装置１４、グラフ可視化表示処理をプログラム制御により実行する処理装置（CPU）１１、処理装置１１を制御するプログラムを格納した主メモリ１２、処理装置１１により生成されたグラフデータの可視化イメージを表示するディスプレイ装置１３から構成される。
【００３５】
なお、図２には、本実施の形態を実現するための構成のみを図示している。実際には、図２の構成の他に、各種の命令やデータを入力するためのキーボードやマウス等の入力装置、各種周辺機器、ネットワークに対するインタフェースなどが設けられていることを前提とする。
【００３６】
また、本実施の形態におけるグラフデータ可視化表示装置は、グラフデータに基づいて追加する追加ノード初期配置決定部２１と、削除ノード処理部２２と、所定の力学モデルに従い、ノード座標の最適化計算を行うノード配置座標最適化更新処理部２３と、を備え、各種構成要素は、主メモリ１２に保持されているコンピュータプログラムにより制御された処理装置１１において実現される仮想的なソフトウェアプログラムである。
【００３７】
図３は、本発明の一実施の形態における処理装置の動作のフローチャートである。
【００３８】
以下では、追加ノード初期配置決定部２１、削除ノード処理部２２及びノード配置座標最適化更新処理部２３による、追加ノードの配置、及び削除ノードの削除及び全体のノードの座標の最適化更新処理について説明する。
【００３９】
ステップ３０１）  記憶装置１４からグラフデータを取得する。
【００４０】
ステップ３０２）  処理装置１１は、各ノードに対して追加または削除を行うタイミングを決定する。当該タイミングは、Wikipedia（登録商標）の人物リストデータ（後述する図８〜図１２）を例にとると、誕生年と没年のデータを読み込み、時間窓を１年に設定し、誕生年にノード（この場合は人物）を追加するように、また、没年にノードを削除するように事前処理を行っておくことにより決定されるものとする。
【００４１】
ステップ３０３）  ノード情報を更新するタイミングであれば、ステップ３０４に移行し、そうでなければステップ３０６に移行する。
【００４２】
ステップ３０４）  追加ノード配置決定部２１において、追加ノードの座標を決定する。詳細な処理については図４で後述する。
【００４３】
ステップ３０５）  削除ノード処理部２２において、削除ノードを削除する。実際には、ノード更新時にリストに含まれない場合、更新のタイミングで排除している。
【００４４】
ステップ３０６）  ノード配置座標最適化更新処理部２３は、所定の力学モデルに従う運動方程式よりノードの最適な配置を算出して更新する。最適化としては、例えば、ニュートン法等を用いることができる。
【００４５】
ステップ３０７）  ノード配置座標最適化更新処理部２３は、全ノードの座標を更新する。
【００４６】
ステップ３０８）  停止条件を満たす場合は当該処理を終了し、満たさない場合はステップ３０３に移行する。
【００４７】
次に、上記のステップ３０４の処理について説明する。
【００４８】
図４は、本発明の一実施の形態における追加ノード配置決定部の処理のフローチャートである。
【００４９】
ステップ４０１）  追加ノード配置決定部２１は、記憶装置１４からグラフデータを取得する。
【００５０】
ステップ４０２）  グラフデータから追加するノードの接続エッジ情報を抽出する。
【００５１】
ステップ４０３）  新規追加ノードを任意に１つ選択する。
【００５２】
ステップ４０４）  選択した新規追加ノードにエッジ接続があるかを判定し、ある場合はステップ４０６に移行し、ない場合はステップ４０５に移行する。
【００５３】
ステップ４０５）  エッジ接続がない場合は、新規追加ノードの座標を乱数を用いて、当該追加ノード配置決定部２１内のメモリ上の描画領域内にランダムに配置し、ステップ４１１に移行する。
【００５４】
ステップ４０６）  エッジ接続がある場合は、当該エッジ接続先に既存の配置ノードがあるかを判定し、ある場合はステップ４０８に移行し、ない場合はステップ４０７に移行する。
【００５５】
ステップ４０７）  残る全ての新規ノードのエッジ接続先が新規ノードである場合はステップ４０５に移行し、そうでない場合は、ステップ４０３に移行する。
【００５６】
ステップ４０８）  エッジ接続先の既存の配置ノードは１つであるかを判定し、１つである場合はステップ４１０に移行し、そうでない場合はステップ４０９に移行する。
【００５７】
ステップ４０９）  エッジ接続先の既存配置ノードが複数ある場合は、接続先の既存配置ノード群の重心に新規追加ノードの座標を配置し、ステップ４１１に移行する。
【００５８】
ステップ４１０）  エッジの接続先の既存配置ノードが１つの場合は、接続先の既存配置ノードの近傍に配置し、ステップ４１１に移行する。
【００５９】
ステップ４１１）  接続エッジ情報にまだ追加ノードが残っている場合はステップ４０３に移行し、残っていない場合は当該処理を終了する。
【００６０】
以下に、上記の図４のフローチャートに示す処理についてノードを配置する４つのパターンを説明する。
【００６１】
＜ノード追加処理（１）＞
追加ノード配置決定部２１は、追加するノードについて、追加エッジを元に、接続関係にある既存配置ノードに対しての重心に配置を行っていく（ステップ４０９）。例えば、図５のように、（ａ）の既存配置ノードに対して、（ｂ）と（ｃ）で示されるノードとエッジの追加を行うとき、９番ノードは５番と８番の重心に、１０番ノードは１番と５番と４番の重心に、１１番ノードは２番と４番の重心に配置する。ノード配置座標最適化更新処理部２３は、追加配置した（ｄ）の座標を元に、所定の力学モデルに従って配置の最適化計算を行い、（ｅ）の配置を得る。
【００６２】
＜ノード追加処理（２）＞
追加された当該ノードが既存配置されているノードとの接続関係にあり、かつ、追加ノードとも接続関係にある場合（ステップ４０９）、追加ノード配置決定部２１は、既存配置ノードと接続関係にあるノードから先に追加を行い、逐次的にノードの追加を行うことによって、追加ノードを既存配置ノードの重心に配置していく。例えば、図６のように、（ａ）の既存配置ノードに対して、（ｂ）と（ｃ）で示されるノードとエッジの追加を行うとき、まずは、９番ノードを接続する５番と８番の重心に（ｄ）のように配置する。次に１０番ノードを９番と５番と４番の重心に（ｆ）のように配置する。次に１１番ノードを１０番と２番の重心に（ｈ）のように配置する。ノード配置座標最適化更新処理部２３は、（ｈ）の配置を元に所定の力学モデルに従って最適化計算を行い、（ｉ）の最適配置を得る。
【００６３】
＜ノード追加処理（３）＞
追加するノードが、接続関係にある既存配置ノードが一つの場合、追加ノード配置決定部２１は、重心ではなく既存配置ノードの近傍に配置を行う（ステップ４１０）。例えば、図７のように、（ａ）の配置済みノードに対して、（ｂ）と（ｃ）で示されるノードとエッジの追加を行うとき、９番ノードは５番の近傍に、１０番ノードは１番の近傍に、１１番ノードは４番の近傍に配置する。ノード配置座標最適化更新処理部２３は、追加配置した（ｄ）の座標を元に、所定の力学モデルに従って最適化計算を行い、（ｅ）の最適配置を得る。
【００６４】
＜ノード追加処理（４）＞
既に配置されているノードとの接続関係がないものは、ディスプレイ空間上の任意の場所に配置を行う（ステップ４０５）。
【００６５】
次に、上記の実施の形態の処理を具体的に説明する。
【００６６】
図８は、本発明の一実施の形態における人物データを用いた共起グラフ可視化の例である。用いたデータはWikipedia(登録商標)より、人物リストを収集し、Wikipedia(登録商標)の記事に出現する頻度を元に共起度の計算を行い、共起度を元にグラフデータを作成したものである。図８の（ａ）では、１６０年に生存していた人物の共起データを元に、所定の力学モデルに従い最適配置を行い表示した様子を示している。同図（ｂ）では、１６１年に生存していた人物の座標配置を行ったものであり、（ａ）の１６０年のデータと比べて新たに『劉備』が追加されたことがわかる。このとき、『劉備』は既存配置されていた『曹操』ら４人の人物と共起度が高く接続関係にあるため、４人の既存配置座標の重心に追加配置を行った。（ｂ）の配置座標を元に再び所定の力学モデルによる最適配置計算を行い、その結果得られた配置が（ｃ）となる。このグラフ可視化表示を実現するために用いたサンプルデータを図９、図１０に示す。
【００６７】
＜従来技術と本願発明の比較＞
本発明の効果を考察するために、前述したWikipedia(登録商標)の人物リストデータを用いて検証を行った。定量評価としては、所定の力学モデルを用いて、計算の最適化を行い、グラフデータのエッジ長の平均と分散で評価を行った。
【００６８】
まず、初めに１９７０年のデータを用いて、配置計算が十分収束するまでの所定の力学モデルによる最適配置計算を行い、１９７０年の配置座標を取得する。取得した１９７０年の座標を元に１９７１年のデータを追加し、本発明の方法を用いて追加配置の初期化を行った場合と、乱数を用いて追加配置の初期化を行った場合で比較を行った。図１１がその結果である。同図の（ａ）及び（ｂ）は、従来手法と本発明におけるエッジ長の平均値で、従来手法と比べて本発明の手法の方が早期に収束していることがわかる。また、初期値として同図（ａ）の従来手法の方が本発明の手法の倍近い値になるのは、非常に長いエッジが発生してしまうためである。
【００６９】
一方、（ｂ）の本発明の手法では、長いエッジの発生を抑えることができるため、平均値が初期から低く抑えることができている。この分散値は０に近ければ近いほどよく、しかしながら、次元圧縮の問題で、複雑なネットワークデータは２次元に完全に埋め込むことが物理上不可能であるため、０の値をとることは不可能であるが極力小さい値になるように計算を行う。
【００７０】
同図（ｃ）及び（ｄ）は、従来手法と本発明のエッジ長の分散値で、平均値と同様に従来手法と比べて本発明の手法が早期に収束していることがわかる。また、初期値として（ｃ）の従来手法が本発明の手法と比べて圧倒的に大きい値になるのも、前述したように非常に長いエッジが発生してしまうことが原因である。図１１の結果からわかることは、従来手法だと収束までに４０００回ほどの反復計算をするのに対して、本発明の手法だと１０００回にも満たず、１００回程度で殆ど収束してしまうことがわかる。
【００７１】
図１２は、前述したWikipedia(登録商標)のデータを、１３２年のデータから２０１０年までのデータを用いて配置計算を行った結果である。それぞれ各年代において、同一条件で１００回の、所定の力学モデルによる反復計算を行った。（ａ）及び（ｂ）は、従来手法及び本発明の手法のエッジ長の平均値で、従来手法がノードの増加に伴い収束できなくなっているのに対して、本発明の手法では、１００回程度の反復計算で精度を保って計算が進んでいることがわかる。図１２の中の図は図１２の１９００年から２０１０年を拡大したものである。本発明の手法では、ノード数の急激な増加（この場合、各年代に約１００人程増えている）にも耐えていることがわかる。
【００７２】
上記のように、ディスプレイ空間上にノードの追加を行う際に、グラフデータの接続関係に応じて、
１）  既に配置されているノード群の重心に配置する；
２）  既に配置されているノードとの接続関係が１つだけのものについては、接続関係にあるノード近傍に配置する；
３）  既に配置されているノードと接続関係がないものは、ディスプレイ空間上の任意の場所に配置する；
のいずれかを逐次的に行う。そして、追加したノードと、ディスプレイ空間上に既に配置されているノードとの間に所定の力学モデルを適用して各ノードの位置を修正する。
【００７３】
これにより、ノードやエッジが逐次追加、もしくは削除されているデータを可視化する際に、より高速に、かつ高精度に処理を行うことが可能となる。
【００７４】
また、本発明は、上記の実施の形態における図２に示す処理装置１１の動作をプログラムとして構築し、グラフ可視化表示装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００７５】
なお、本発明は、上記の実施の形態及び実施例に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００７６】
１０  グラフ可視化表示装置
１１  処理装置（CPU）
１２  主メモリ
１３  ディスプレイ装置
２１  追加ノード配置決定部
２２  削除ノード処理部
２３ノード配置座標最適化更新処理部
【図１】
0005700841.tif 000002
【図２】
0005700841.tif 000003
【図３】
0005700841.tif 000004
【図４】
0005700841.tif 000005
【図５】
0005700841.tif 000006
【図６】
0005700841.tif 000007
【図７】
0005700841.tif 000008
【図８】
0005700841.tif 000009
【図９】
0005700841.tif 000010
【図１０】
0005700841.tif 000011
【図１１】
0005700841.tif 000012
【図１２】
0005700841.tif 000013