(57)【要約】【課題】  一般的なグラフに加えて、２部グラフなどの特殊な構造を持ったグラフを解析しやすいように可視化し、そのグラフの構造やノードやリンクの関係の分布なども解析しやすくなるように支援することを課題とする。【解決手段】  演算装置１と入力装置２と記憶装置３と表示装置４とを含んで構成される可視化装置が、利用者から与えられたノードとリンクからなるグラフに対して、初期設定決定部５がノードの座標を初期化し、最適配置推定部６がノードを最適な座標に移動し、可視化部７が表示装置４で表示可能な画像データを生成し、各ノードを円周上又は球面上に表示させることを特徴とする。【選択図】      図１
2006092354.tif 000002
【特許請求の範囲】
【請求項１】
ノードがリンクでつながれたグラフの可視化において、
各ノードが決められた半径の円周上又は球面上に配置されるという制約のもとで可視化装置を用いて前記グラフを可視化する方法であって、
前記可視化装置は、
各ノードを配置する半径、及び、リンクの関係の重要度を初期設定決定部が決定するステップと、
前記決定した値をもとに、関連するノード群を、円又は球の中心から見て同方向にクラスタリングされるように各ノードの配置を最適配置推定部が推定するステップと、
前記配置したノードとリンクを可視化部が外部出力するステップと
を実行することを特徴とする可視化方法。
【請求項２】
ノードの類似度によって関連付けられたノードの可視化において、
各ノードが決められた半径の円周上又は球面上に配置されるという制約のもとで可視化装置を用いて前記ノードを可視化する方法であって、
前記可視化装置は、
各ノードを配置する半径、及び、ノードの類似度を初期設定決定部が決定するステップと、
前記決定した値をもとに、前記ノードの類似度に応じて分布するように各ノードの配置を最適配置推定部が推定するステップと、
前記配置したノードを可視化部が外部出力するステップと
を実行することを特徴とする可視化方法。
【請求項３】
前記ノードの配置を最適配置推定部が推定するステップについて、
ノードを順次１つ選定し、他のノードの座標を固定して、
選定したノードの座標の更新を繰り返すオンライン学習法により、
前記ノードの最適座標を推定すること
を特徴とする請求項１又は請求項２に記載の可視化方法。
【請求項４】
２つのノード部分集合からなり、異なる部分集合のノード間にのみリンクが存在する２部グラフの可視化において、
前記ノード部分集合であって、同一のノード部分集合に属するノードを同一の半径の円周上又は球面上に配置すること
を特徴とする請求項１乃至請求項３のいずれか１項に記載の可視化方法。
【請求項５】
ノードがリンクでつながれたグラフの可視化において、
各ノードが決められた半径の円周上又は球面上に配置されるという制約のもとで可視化装置を用いて前記グラフを可視化する可視化装置であって、
各ノードを配置する半径、及び、リンクの関係の重要度を決定する初期設定決定部と、
前記決定した値をもとに、関連するノード群を、円又は球の中心から見て同方向にクラスタリングされるように各ノードの配置を推定する最適配置推定部と、
前記配置したノードとリンクを外部出力する可視化部と
を備えたことを特徴とする可視化装置。
【請求項６】
ノードの類似度によって関連付けられたノードの可視化において、
各ノードが決められた半径の円周上又は球面上に配置されるという制約のもとで可視化装置を用いて前記ノードを可視化する可視化装置であって、
各ノードを配置する半径、及び、ノードの類似度を決定する初期設定決定部と、
前記決定した値をもとに、前記ノードの類似度に応じて分布するように各ノードの配置を推定する最適配置推定部と、
前記配置したノードを外部出力する可視化部が外部出力と
を備えたことを特徴とする可視化装置。
【請求項７】
請求項１乃至請求項４のいずれか１項に記載の可視化方法をコンピュータで実行するための可視化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グラフの可視化に関する。特に、決められた半径の円周または球面上に各ノードが配置されるという制約の下でのグラフの可視化に関する。
【背景技術】
【０００２】
ノードとリンクの集まりによって表現されたグラフの構造を直感的に理解し解析する基本的手段の一つとして可視化が挙げられる。グラフの可視化の手法は、既に多く提案されている。無向グラフの可視化の手法のうちで代表的なものとしては、Ｋａｍａｄａ−Ｋａｗａｉバネモデル（非特許文献１参照）が挙げられる。この手法では、ノード間のリンクをあたかもバネであるかのように扱うことで、ノードとリンクをバランスよく配置してグラフを可視化することができる。しかしながら、２部グラフなどは特殊な構造を持っているため、これらの一般的な可視化手法ではその特徴が捉えにくい。２部グラフは２つのノード部分集合から成り、異なる部分集合のノード間にのみにリンクが存在するグラフである。人とコミュニティ、単語と文書、Ｗｅｂページのａｕｔｈｏｒｉｔｙ（コンテンツのページ）とｈｕｂ（リンクを集めたページ）など、２部グラフとして記述できるネットワークは数多く存在する。近年、２部グラフの重要性が再認識されて、２部グラフのクラスタリングなどの解析手法も提案されている。
【０００３】
また、２部グラフ以外のグラフでも、何らかの既知の性質を有している場合があり、その構造を可視化に組み込むことによって、与えられたグラフの特徴をより多くの観点から理解することが可能となる。
【０００４】
特許文献１は、Ｗｅｂのアクセスにおける構造などに関するグラフ構造を可視化する手法について記述しているが、これは、必ずしも２部グラフなどの特殊な構造を持ったグラフの解析を意図したものではない。
【特許文献１】特許２８６１９０８号明細書（段落００１７〜００２８、図１〜図３）
【非特許文献１】T. Kamada and S. Kawai, "An algorithm for drawing general undirected graph", Information Processing Letters, vol.32, pp.7−15(1989).
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明では、一般的なグラフに加えて、２部グラフなどの特殊な構造を持ったグラフを解析しやすいように可視化し、そのグラフの構造やノードやリンクの関係の分布なども解析しやすくなるように支援することを課題とする。
【課題を解決するための手段】
【０００６】
前記の課題を解決するため、本発明では、ノードがリンクでつながれたグラフの可視化において、各ノードが決められた半径の円周上又は球面上に配置されるという制約のもとで可視化装置を用いて前記グラフを可視化する方法であって、前記可視化装置は、各ノードを配置する半径、及び、リンクの関係の重要度を初期設定決定部が決定するステップと、前記決定した値（半径及び重要度）をもとに、関連するノード群を、円又は球の中心から見て同方向にクラスタリングされるように各ノードの配置を最適配置推定部が推定するステップと、前記配置したノードとリンクを可視化部が外部出力するステップとを実行する。
【０００７】
この方法によれば、ノードとリンクとからなるグラフを分かり易く可視化することができる。
【０００８】
また、本発明（請求項２）では、ノードの類似度によって関連付けられたノードの可視化において、各ノードが決められた半径の円周上又は球面上に配置されるという制約のもとで可視化装置を用いて前記ノードを可視化する方法であって、前記可視化装置は、各ノードを配置する半径、及び、ノードの類似度を初期設定決定部が決定するステップと、前記決定した値（半径及び類似度）をもとに、前記ノードの類似度に応じて分布するように各ノードの配置を最適配置推定部が推定するステップと、前記配置したノードを可視化部が外部出力するステップとを実行する。
【０００９】
この方法によれば、ノードを類似度に応じて分かり易く可視化することができる。
【００１０】
本発明（請求項３）では、前記ノードの配置を最適配置推定部が推定するステップについて、ノードを順次１つ選定し、他のノードの座標を固定して、選定したノードの座標の更新を繰り返すオンライン学習法により、前記ノードの最適座標を推定する。
【００１１】
これによれば、リンクの少ないときに高速に可視化を行うことができる。
【００１２】
本発明（請求項４）では、２つのノード部分集合からなり、異なる部分集合のノード間にのみリンクが存在する２部グラフの可視化において、前記ノード部分集合であって、同一のノード部分集合に属するノードを同一の半径の円周上又は球面上に配置する。
【００１３】
この配置によれば、２部グラフを見易く可視化できる。
【００１４】
本発明（請求項５）では、ノードがリンクでつながれたグラフの可視化において、各ノードが決められた半径の円周上又は球面上に配置されるという制約のもとで可視化装置を用いて前記グラフを可視化する可視化装置であって、各ノードを配置する半径、及び、リンクの関係の重要度を決定する初期設定決定部と、前記決定した値（半径及び重要度）をもとに、関連するノード群を、円又は球の中心から見て同方向にクラスタリングされるように各ノードの配置を推定する最適配置推定部と、前記配置したノードとリンクを外部出力する可視化部とを備える。
【００１５】
これによれば、ノードとリンクからなるグラフを分かり易く可視化する装置を構成できる。
【００１６】
本発明（請求項６）では、ノードの類似度によって関連付けられたノードの可視化において、各ノードが決められた半径の円周上又は球面上に配置されるという制約のもとで可視化装置を用いて前記ノードを可視化する可視化装置であって、各ノードを配置する半径、及び、ノードの類似度を決定する初期設定決定部と、前記決定した値（半径及び類似度）をもとに、前記ノードの類似度に応じて分布するように各ノードの配置を推定する最適配置推定部と、前記配置したノードを外部出力する可視化部が外部出力とを備える。
【００１７】
これによれば、ノードを類似度に応じて分かり易く可視化する装置を構成できる。
【発明の効果】
【００１８】
本発明によれば、グラフの構造やデータの性質を容易に理解できるように円周上又は球面上にノードを配置した表示ができる。
【発明を実施するための最良の形態】
【００１９】
［可視化装置の構成］
次に、前記した原理を踏まえて、与えられたグラフをコンピュータにより可視化する可視化装置を具体的に説明する。図1は、本発明の一実施形態の可視化装置の構成図である。図1に示すように、可視化装置は、演算装置１、入力装置２、記憶装置３及び表示装置４がバスライン１１に接続された構成をしている。
【００２０】
［演算装置］
演算装置１は、ハードウェア的には、演算手段としてのＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ、図示せず）や情報を記憶するメモリ８（ＲＡＭ、Ｒａｍｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙの略称）から構成されている。演算装置１は、バスライン１１を介して入力装置２、記憶装置３及び表示装置４と接続されている。この演算装置１は、初期設定決定部５、最適配置推定部６及び可視化部７を備えている。そして、記憶装置３は初期設定決定部５、最適配置推定部６及び可視化部７を構成するためのプログラムを記憶している。このプログラムは記憶装置３以外にも情報記憶媒体から読み出すことが可能である。
【００２１】
［入力装置］
入力装置２は、キーボードやフロッピー（登録商標）ディスクドライブなどの各種ディスクドライブ装置などから構成される入力手段であり、バスライン１１を介して演算装置１、記憶装置３及び表示装置４と接続されている。本実施形態では、グラフのノード間の接続関係を表現した隣接行列Ａ、各ノードの半径の集合Ｒ、重みの集合Ｗ、可視化次元（当面は、２次元又は３次元を選択）を可視化装置に入力するために用いられる（Ａ，Ｒ，Ｗは図２参照）。なお、入力装置２がフロッピー（登録商標）ディスクドライブなどのキーボード以外の入力手段を持っている場合は、隣接行列Ａ、各ノードの半径の集合Ｒ、重みの集合Ｗなどをこの入力手段から入力することもできる。
【００２２】
［記憶装置］
記憶装置３は、ハードディスク装置などから構成される記憶手段である。本実施形態では、入力装置２から入力された各種データは、必要に応じて記憶装置３に記憶されるものとする。また、記憶装置３は、初期設定決定部５、最適配置推定部６及び可視化部７を構成するためのプログラムを記憶しているものとする。
【００２３】
[表示装置]
表示装置４は、例えばグラフィックボード及びそれに接続されたモニタであり、可視化部７により可視化されたデータを視覚的に表示する。表示装置４は２次元的又は３次元的な表示機能を持つものであれば、たとえばプロジェクタのようなものであってもよい。ただし、この場合には後記する可視化部７がその装置に対応したものであることが必要となる。
【００２４】
[初期設定決定部]
図２は、初期設定決定部５の構成を示す。初期設定決定部５は、ノード座標発生手段５１、ノード座標情報テーブル５２、半径情報テーブル５３、隣接行列テーブル５４及び重み情報テーブル５５を含んでなる。ノード座標情報テーブル５２は後記する集合Ｘのデータを持ち、半径情報テーブル５３は後記する半径の集合Ｒ、隣接行列テーブル５４は後記する隣接行列Ａ、そして、重み情報テーブル５５は重み情報の集合Ｗを持っている。初期設定決定部５は、初期設定を決定するために、メモリ８との間でノード座標情報テーブル５２、半径情報テーブル５３、隣接行列テーブル５４及び重み情報テーブル５５の情報を双方向に読み書きする作業を行う。
【００２５】
初期設定決定部５は、可視化装置が利用するパラメータの初期状態を決定する。初期状態を決定する対象となるパラメータには、まず、隣接行列Ａがある。
【数１】
2006092354.tif 000003
隣接行列Ａにおける各成分は、ノード間のリンクの有無に対応する。たとえば、隣接行列Ａの（２，１）成分ａ2,1は、ノード１とノード２の間のリンクの有無を表している。もし、リンクがある場合は、ａ2,1＝1とし、リンクがない場合は、ａ2,1＝−１とする。同様に全ての成分に１と−１を割り当てておいて、必要に応じて参照できるようにする。なお、本実施形態においては、Ａを隣接行列としているが、リンクデータを集合として保持する形でも同様の機能を実現できる。
【００２６】
次に、初期状態を決定する対象となるパラメータには、可視化の対象となるノードの座標がある。初期設定決定部５は、この可視化の対象となるノードの座標を初期化する機能を持つ。このとき、設定する座標について一定の制約を満たすようにする。たとえば、設定する座標は、２次元の場合なら表示に対応した円周上になるように、３次元の場合なら表示に対応した球面上になるようにする。これにより初期化した後は、各ノードを適切な座標へと再配置ができるようになる。このままの状態での座標に基づいて可視化部７で表示した例が図１３に示されているが、この例のように円周上にノードが配置されるという基本的な制約を満たすようにランダムに配置されているに過ぎず、この段階では有効な可視化が実現されていない。ノードの座標情報は、行列を利用したベクトルの表現と同様に表現することとする。２次元の場合は、
【数２】
2006092354.tif 000004
という形で表現される。なお、ｖiTは、ｖiを転置したものである。
同様に３次元での場合は、
【数３】
2006092354.tif 000005
という形で表現される。より多次元の場合も同様の表現であり、転置も同様に行われる。座標の集合Ｘは、
Ｘ＝｛ｖ1，ｖ2，…，ｖN｝
と表現できる。ただし、Ｎはノードの総数を表す。
【００２７】
また、各ノードは、座標が円周上又は球面上に配置されるが、このときのノードｉが配置される円周又は球面の半径はｒiであり、この半径の集合をＲとする。
Ｒ＝｛ｒ1，ｒ2，…，ｒN｝
このｒiを用いてノードｉが満たすべき制約を記述すると、
ｖiTｖi＝ｒi2
となる。また、ノードｉとノードｊの関係の重要度を規定する重みをｗi,jとし、このｗi,jの集合Ｗを
Ｗ＝｛ｗ1,1，ｗ1,2，…，ｗ2,1，ｗ2,2，…，ｗN,N｝
とする。なお、Ｗについても、隣接行列Ａと同様に行列として保持することもできるが、単なる集合として保持しても本実施形態における可視化方法の実施には差し支えない。この初期設定決定部５では、これらのＡ，Ｘ，Ｒ、Ｗ及び表示を行う次元について、必要に応じて入力装置２を用いて利用者の入力を促し、初期値を決定する。
【００２８】
［最適配置推定部］
図３は最適配置推定部６の構成を示す。最適配置推定部６は、ｇ計算部６１、ｇs計算部６２、Ｈ計算部６３、Ｈs計算部６４、Ｅs最小化部６５、ノード座標情報テーブル６６、半径情報テーブル６７、隣接行列テーブル６８及び重み情報テーブル６９を含んで構成される。そして、各種テーブルの情報については、メモリ８との間で情報を双方向に読み書きする作業を行う。
【００２９】
そして、最適配置推定部６は、配置されたノードの表示座標を順次１つずつ変更していく機能を持つ。この機能では、他のノードの座標は固定したままで、対象となる座標についてたとえば以下のような目的関数Ｅを最小にする座標を求めることで最適な配置を決定する。
【数４】
2006092354.tif 000006
なお、本可視化装置においては、本実施形態で適用される前記の目的関数Ｅに限定されるものではなく、目的関数の与え方で多様な表示が可能になる。前記目的関数Ｅは、ある２つのノードがリンクでつながれていれば中心から見て同方向に、リンクでつながれていなければ逆方向に、ノードが配置されたとき、最小値をとる。また、半径が大きいノードほど目的関数に与える影響が大きくなる。従って、前記目的関数Ｅを最小化すれば、関連するノード群を、円の中心から放射状にクラスタリングされるような可視化が達成される。
【００３０】
本実施形態では、ノード間にリンクが有るか無いかで重み付けを行い、ａi,j＝１すなわちノードｉとノードｊの間にリンクがある場合は、ｗi,j＝１＋ｗ、そうでない場合は、ｗi,j＝１とする。ただし、ｗは正の定数である。
【００３１】
前記した目的関数Ｅの最小化を行うには、最適解を求める方法と近似解を求める方法とがある。本実施形態では、ノードを順次1つ選定し、他のノードを固定して、選定したノードの座標を繰り返し更新していくオンライン型学習法を採用し、近似解を求める。
【００３２】
ここで、ノードｓが選定されたとして、ｖsの出現に留意して前記目的関数Ｅを整理すると、
Ｅs＝０．５ｖsT  Ｈs  ｖs  −  ｒsｖsTｇs
となる。これは、ｖsについて２次の式になっている。故に、Ｅsが減少するようにｖsを求めれば、目的関数Ｅsを確実に減少させることができる。
【００３３】
一方、Ｅsを求めるために必要なＨsとｇs、及びそのＨsとｇsを求めるために必要なＨとｇは以下の式を用いて求めることができる。
【数５】
2006092354.tif 000007
これらのうち、全ノードで共通なＨとｇについては、あらかじめ計算しておけば、ｖsを更新するのに必要な主たる計算をノードｓのリンク数（次数）に比例するオーダで実現できる。その結果、総リンク数の少ないスパースなグラフに対しての座標の更新が効率よく行える。これを一般的なグラフの可視化方法の効率と比べると、リンク数が少ないときは有利であり、リンク数が多くなってもせいぜい同等で不利になることはない。
【００３４】
なお、前記のＥsを最小化するには、ｖsTｖs＝ｒs2の制約を考慮して、Ｌａｇｒａｎｇｅ未定乗数法から導かれるｓｅｑｕｌａｒ  ｅｑｕａｔｉｏｎをニュートン法で解けば、最適解が得られる（G. Goulb and C. Van Loan ， “Matrix Computation”  ， Johns Hopkins刊、(1996)参照）。
【００３５】
［可視化部］
図４は可視化部７の構成を示す。可視化部７は、ノード表示位置計算部７１、ノード座標情報テーブル７２、リンク表示位置計算部７３及び隣接行列テーブル７４を含んで構成される。このうち、ノード座標情報テーブル７２及び隣接行列テーブル７４については、メモリ８との間で情報を相互にやり取りを行い、表示に必要な情報については、表示装置４に送る。
【００３６】
［可視化装置の動作］
図５は可視化装置の全体動作を示す。可視化装置は、記憶装置３または情報記憶媒体に書き込まれている可視化プログラムをメモリ中に読み出して（Ｓ１０１）稼動可能な状態になる。その後、入力装置２から利用者によって与えられた隣接行列Ａなどのデータを読み込み、初期設定決定部５において、ノードの座標の初期化などの初期化処理を行う（Ｓ１０２）。この後、各ノードについて、最適配置推定部６において、最適配置推定処理を繰り返して（Ｓ１０３）、ノードを配置する座標を決定する。この結果を受けて、可視化部７で可視化結果の表示処理を行い、表示装置４に出力する（Ｓ１０４）。
【００３７】
［記憶装置の動作］
記憶装置３は、可視化装置のための演算装置１などを稼動させるためのプログラムを記録している。可視化装置が稼動する際には、記憶装置３は可視化方法についてのプログラムをメモリ８に転送し、装置が稼動可能な状態にする。他にも必要に応じて、可視化処理に必要な情報を演算装置１に対して転送する。
【００３８】
［入力装置の動作］
入力装置２は、利用者からの入力を受け取り、演算装置１に転送する。本実施形態では、グラフのノード間の接続関係を表現した隣接行列Ａ、各ノードの半径の集合Ｒ、重みの集合Ｗ、可視化次元（当面は、２次元又は３次元を選択）を可視化装置に入力するために用いられる。
【００３９】
［初期設定決定部の動作］
初期設定決定部５は、前記入力装置２の動作によって得た必要な情報を半径情報テーブル５３、隣接行列テーブル５４及び重み情報テーブル５５に読み取り（図２参照）、可視化装置で利用可能な状態にする。そして、ノード座標発生手段５１及びノード座標情報テーブル５２を用いて、ノードを配置する座標を初期化する。この初期化においては、ノード座標発生手段５１が、そのノードが位置するように指定されている円周上または球面上にランダムにノードを配置するように座標を決定していく。このとき、ノード座標発生手段５１は標準的な乱数発生方法を用いて、２次元なら２つの乱数、３次元なら３つの乱数を発生させて、制約を満たすように適宜決めた方法で座標を変換すればよい。本実施形態では、仮にこの初期配置されたノードの座標が完全に均一に分布していなくても、後記する最適配置推定部６の動作には差しさわりはない。
【００４０】
［最適配置推定部の動作］
図６は、最適配置推定部６の全体としての動作を示す。図６の各ステップの動作についてはさらに詳細な動作を説明するために別途図を参照して個別に説明する。
【００４１】
まず、最初に入力装置２または記憶装置３から必要なノードの座標情報のＸ、隣接行列Ａ、半径の情報Ｒ及びリンクの重みの情報Ｗを取り出して、後の計算に必要なＨとｇを計算する（Ｓ２０１）。そして、収束しているか否かを判定する際のために、その時点での全てのノードの座標の情報ＸをＸ’にコピーして保存しておく（Ｓ２０２）。そして、ループカウンタｓを１に初期化して、後記する繰り返し処理を行えるようにする（Ｓ２０３）。そして、ｖsを１つずつを順次とりだして、これに対応して、Ｈを用いてＨsを計算し、同様にｇを用いてｇsを計算した上で、これに加えて、全てのノード座標情報Ｘ、重み情報Ｗ、リンク情報を含む隣接行列Ａ、半径の情報Ｒを参照して計算する目的関数Ｅが最小になるようにｖsの座標を決定する（Ｓ２０４）。その後、ループカウンタｓを１つ増加させて（Ｓ２０５）、ループカウンタｓがノードの総数Ｎ以下の場合（Ｓ２０６のＹｅｓ）、すなわち、まだノードの再配置が一巡していない場合は別のｖsの再配置（Ｓ２０４）を繰り返す。ループカウンタｓがノードの総数Ｎより大きい場合（Ｓ２０６のＮｏ）、すなわち、ちょうどｖsの再配置が一巡した場合には、ｖsの更新の繰り返しによってＸが変化したか否かをＳ２０２で保存しておいたＸ’と比較して判定する（Ｓ２０７）。ＸがＸ’と同じ場合（Ｓ２０７のＹｅｓ）、全てのノードの座標が収束した状態であるので、これを可視化部７に出力して（Ｓ２０８）、終了する。ＸがＸ’と異なる場合（Ｓ２０７のＮｏ）、最初（Ｓ２０１）から再度全てのｖsの再配置を繰り返す。
【００４２】
図７は、図６におけるｖsの再配置（Ｓ２０４）で用いられるＥsが計算されるまでの流れの概略を示したものである。図７に示すように、Ｅsを計算する（Ｓ３０５）には、ｇsの計算（Ｓ３０２）とＨsの計算（Ｓ３０４）が必要である。さらに、ｇsを計算するにはｇの計算（Ｓ３０１）が必要となり、Ｈsを計算するにはＨの計算（Ｓ３０３）が必要となる。従って、まず、ｇ計算部６１及びＨ計算部６３で計算を行って、その後、ｇs計算部６２及びＨs計算部６４で計算を行い、最後にＥs最小化部６５で計算を行う流れとなる。以下に、ｇ計算部６１、Ｈ計算部６３、ｇs計算部６２、Ｈs計算部６４及びＥs最小化部６５の動作についてそれぞれ説明する。
【００４３】
［ｇ計算部の動作］
図８は、ｇ計算部６１の動作を示す図である。ｇは、ノードの座標情報Ｘと半径の情報Ｒを用いて、計算する。ここでは、説明のために２次元の例を取り上げているが、３次元以上でも次元が増える以外は同様に行えばよい。まず、最初にループカウンタｓを１に初期化し（Ｓ４０１）、同様にｇも全ての成分を０に初期化する（Ｓ４０２）。そして、各ノードが配置されるべき円周（３次元の場合は球面）の半径とそのノードの座標を表すベクトルを用いて、
ｇ＝ｇ＋ｒsｖs
という式に従ってｇを計算していく（Ｓ４０３）。そして、ループカウンタｓを１進めて（Ｓ４０４）、そのループカウンタｓをノードの個数Ｎと比較する（Ｓ４０５）。そして、ｓがＮ以下のとき（Ｓ４０５のＹｅｓ）、まだ全てのノードに一巡していないので、Ｓ４０３から同様の計算を繰り返す。ｓがＮより大きいとき（Ｓ４０５のＮｏ）、ｇの値を出力して（Ｓ４０６）、終了する。
【００４４】
［ｇs計算部の動作］
図９は、ｇs計算部６２の動作を示す図である。ｇsは、ノード座標情報テーブル６６の座標情報Ｘとｇ計算部６１で計算したｇを用いて計算する。ｇsの計算における初期値は、ｇと違って全ての成分を０としたものではなく、ｇs＝ｖs−ｇであるとする（Ｓ５０１）。そして、その時に計算の対象となっているノードｓと直接リンクで接続されているノードｊのリストを作る（Ｓ５０２）。そして、ｇの計算とは異なり、全てのノードを対象とするのではなく、ノードｓと直接リンクで接続されているノードｊだけを対象として、繰り返し処理を行う。次に、Ｓ５０２で作成したノードｊのリストにノードｊがあるか否かを調べて（Ｓ５０３）、Ｙｅｓであれば（ノードｊがあれば）、リストの中から選んだノードｊに対して、Ｓ５０５以降のｇsの計算のための繰り返し処理を続行する。Ｓ５０３で調べた結果がＮｏであれば（ノードｊが残っていなければ）、その時点でのｇsを出力して（Ｓ５０４）、終了する。Ｓ５０５では、リストの中から選んだノードｊに対して、以下の計算を行ってｇsの計算を進行させる。
ｇs＝ｇs＋（２＋ｗ）ｖj
この計算が終了した後は、その計算に用いたノードｊをリストから取り除き、Ｓ５０３から繰り返し処理を続行する。そして、リスト中の全てのノードｊを処理し終えて、前記したＳ５０３でＮｏの判定が出た時点で処理が終了する。
【００４５】
［Ｈ計算部の動作］
図１０は、Ｈ計算部６３の動作を示す図である。ここでは、説明のために２次元の例を取り上げているが、３次元以上でも次元が変わる以外は同様に行えばよい。まず、Ｈを計算するために、ループカウンタｓを１に初期化し（Ｓ６０１）、Ｈの全ての成分を０に初期化する（Ｓ６０２）。そして、各ノードの座標を表すベクトルｖsを用いて、以下の式に従ってＨの値を計算していく（Ｓ６０３）。
Ｈ＝Ｈ＋ｖsｖsT
その後、ループカウンタｓを１増加させて（Ｓ６０４）、そのループカウンタｓをノードの個数Ｎと比較する（Ｓ６０５）。そして、ｓがＮ以下のとき（Ｓ６０５のＹｅｓ）、まだ全てのノードに一巡していないので、Ｓ６０３から同様の計算を繰り返す。ｓがＮより大きいとき（Ｓ６０５のＮｏ）、Ｈの値を出力して（Ｓ６０６）、終了する。
【００４６】
［Ｈs計算部の動作］
図１１は、Ｈs計算部６４の動作を示す図である。Ｈsは、ノード座標情報テーブル６６の座標情報ＸとＨ計算部６３で計算したＨを用いて計算する。Ｈsの計算における初期値は、Ｈs＝Ｈ−ｖsｖsTであるとする（Ｓ７０１）。そして、その時に計算の対象となっているノードｓに対して、直接リンクでつながっているノードを全て集めてリストを作る（Ｓ７０２）。そして、Ｈの計算とは異なり、全てのノードを対象とするのではなく、ノードｓに対して直接リンクでつながっているノードｊだけを対象として、繰り返し処理を行う。次に、Ｓ７０２で作成したノードｊのリストにノードｊがあるか否かを調べて（Ｓ７０３）、ノードｊがあれば（Ｓ７０３のＹｅｓ）、リストの中から選んだノードｊに対して、Ｓ７０５以降のｇsの計算のための繰り返し処理を続行する。ノードｊが残っていなければ（Ｓ７０３のＮｏ）、その時点でのＨsを出力して（Ｓ７０４）終了する。Ｓ７０５では、リストの中から選んだノードｊに対して、以下の計算を行ってＨsの計算を進行させる。
Ｈs＝Ｈs＋ｗｖjｖjT
この計算が終了した後は、その計算に用いたノードｊをリストから取り除き、Ｓ７０３から繰り返し処理を続行する。そして、リスト中の全てのノードｊを処理し終えて、前記したＳ７０３でＮｏの判定が出た時点で処理が終わる。
【００４７】
［Ｅs最小化部の動作］
図１２は、Ｅs最小化部６５の動作を示す図である。Ｅs最小化部６５では、その時点でのｖsと共にＨsとｇsとを用いて、ｖsの座標を更新する計算をする。なお、ここでの計算はいわゆるニュートン法による近似解の探索を行っているだけである。まず、そのために既に計算したＨsとｇsとを取り出しておく（Ｓ８０１）。そして、まず最初にその時点でのｖsに対する目的関数Ｅsを以下の式に従って計算し、これをＥs’に保存しておく（Ｓ８０２）。
Ｅs＝０．５ｖsTＨsｖs−ｒsｖsTｇs
なお、この式において、Ｈsとｇsとは、ｖsを変化させると共に値が変わるものであるが、ここでは、Ｈsとｇsとを定数と見做して近似的に計算している。そして、この近似による誤差は最終的にｖsが収束するときには、問題にならない程度に収まる。
【００４８】
次に、ｖsをランダムに少し変化させて（Ｓ８０３）、前記Ｅsを求める計算式でＥsを求める（Ｓ８０４）。そして、ここで求めたＥsとＥs’との大小関係を比較する（Ｓ８０５）。この比較の結果、新たに計算したＥsがＥs’よりも大きい場合（Ｓ８０５のＮｏの場合）は、ｖsをＳ８０３で変化させたのとは逆の方向に少し変化させて（Ｓ８０９）、再度Ｓ８０４のＥsを計算からやり直す。このやり直しの結果でも値が小さくならない場合は、変化させる量をより小さくするなどの対応を取る。Ｓ８０５での比較の結果、新たに計算したＥsがＥs’よりも小さいか等しい場合（Ｓ８０５のＹｅｓの場合）、さらに収束したか否かを判定する（Ｓ８０６）。この判定は、ＥsとＥs’が等しいか、充分に差が小さければ、Ｙｅｓと判定し、そうでないときにはＮｏと判定する。Ｙｅｓと判定された場合は、Ｅsが収束したことになるので、このときのＥsの値を出力して（Ｓ８０７）、終了する。Ｎｏと判定された場合は、ここで計算したＥsをＥs’に保存した上で（Ｓ８０８）、さらにＳ８０３からＥs最小化の繰り返し処理を継続する。
【００４９】
既に最適配置推定部６の動作の説明で述べたように、Ｅsを最小化するようにして座標を再配置したｖsが、全て変化しなくなって収束したときには、この座標のデータを可視化部７に送る。
【００５０】
［可視化部の動作］
図４を参照して、可視化部７の動作を説明する。可視化部７は、最適配置推定部６において決定されたノードの座標の集合Ｘを含むノード座標情報テーブル７２とノード間のリンクの情報である隣接行列Ａの情報を含む隣接行列テーブル７４を利用して、ノード表示位置計算部７１及びリンク表示位置計算部７３によって、表示装置４で表示が可能な形に可視化された画像データを生成する。その際に、ノード表示位置計算部７１及びリンク表示位置計算部７３では、入力装置２によって利用者が与えた表示の次元に応じて、描画すべきノードやリンクの表示方法を決め、ノードの座標を画面上の表示位置に変換する。さらにユーザからの指示があった場合には、ある特定のノードの集合に含まれるノードから直接リンクで接続されているノードを特定の色で表示するなどの着色処理を行う。また、表示装置４が２次元で、ノードの座標の集合Ｘを含むノード座標情報テーブル７２に含まれるデータが３次元である場合には、３次元から２次元に射影する変換も必要になり、この処理もノード表示位置計算部７１及びリンク表示位置計算部７３が行う。なお、ノード表示位置計算部７１及びリンク表示位置計算部７３が行うべき処理の内容は、用いる表示装置４や次元に応じて変更する必要がある。
【００５１】
［表示装置の動作］
表示装置４は、可視化部７によって作成された表示可能な画像データを受け取り、それを表示する。ただし、表示装置４の仕様によっては、送られてきた色彩に関する情報や表示位置に関するデータ変換が必要になる場合もある。
【実施例１】
【００５２】
次に、本発明の効果を確認した実施例について説明する。実施例１では、頭痛合併症関係の２次元での可視化を行った。具体的には、疾患と患者の関係のデータ（H. Masuzawa, J.Sato, S.Kaida, H.Miyake, T.Kubo, H.Tsumura, M.Higashida and T.Wasano, 「医療知識ベースの利用による医療診断システム（ＤＯＣＴＯＲＳ）の臨床評価）」、第４回医療情報学連合大会参照）を対象として２部グラフの可視化を行った。
【００５３】
用いた２部グラフは、頭痛を起こす２３の疾患を選び、患者３９８人の診断結果をもとに、患者と疾患とをノードとして、患者とその患者がかかっている疾患をリンクで接続したものである。本実施例で対象として選んだ２３の疾患は、頭蓋頚椎移行部病変、群発性頭痛、古典的片頭痛、普通型片頭痛、小児血管性頭痛、後頭神経痛、緊張性頭痛、心因性頭痛、慢性副鼻腔炎、筋収縮性頭痛、慢性硬膜下血腫、頸性頭痛、脳腫瘍、脳動脈瘤破裂、中耳炎、ヘルぺス、急性副鼻腔炎、眼精疲労、混合性頭痛、頭部打撲、頭蓋底腫瘍、頚部捻挫、その他である。
【００５４】
図１３及び図１４は、実施例１に関する表示装置４の出力例である。このうち、図１３は、患者のノードは半径２の円周上に、疾患のノードは半径１の円周上に配置するようにして、可視化のためのノードの最適配置を行う前のランダムな配置のノードとリンクをそのまま出力したものである。この出力から２部グラフの構造を理解することは明らかに容易ではない。
【００５５】
それに対して、図１４は、ノードの最適配置を行った結果を出力したものである。図１４に示す実施例１では、同様に円周上に配置する制約下で、重荷ｗ＝１として可視化を行ったものである。この出力結果では、同じノードに対してリンクが張られているノードは比較的近くに配置されており、合併症の可能性の高い疾患がより近くに配置されるようになっている。このようにしてある種の類似度に基づく構造が具現されている。
【００５６】
また、２３の疾患のうち、血管性頭痛として分類できる疾患は普通型片頭痛、古典型片頭痛、小児血管性頭痛、群発頭痛であるが、全て円の下部に配置されており、患者データから得られた情報をもとに疾患分類が可能であることも確認できる。
【実施例２】
【００５７】
実施例２は、Ｗｅｂページとそこに出現する単語群についての関係を表したグラフを３次元で可視化したものである。本実施例では、各ノードがそれぞれ異なる半径の球面上に配置されるという制約を持たせた場合の可視化の例である。用いたデータは、ポータルサイトｇｏｏ（登録商標、http://www.goo.ne.jp/）のなかのグルメディレクトリに含まれる１９８５のＷｅｂページとその中で使用頻度が高い８６９単語とをノードとし、ページｉが単語ｊを含んでいれば、そのノード間にリンクを張ることによって可視化の対象となるグラフを作成した。ノードを配置する球面の半径は、Ｗｅｂページの場合と単語の場合でそれぞれ基準を設けて、その大小を決定した。ノードがＷｅｂページの場合には、そのページに含まれている単語が多いものは半径を小さくし、そのページに含まれている単語が少ないものは半径を大きくした。また、ノードが単語の場合には、単語が含まれるページ数が多いものは半径を小さくし、ページ数が少ないものは半径を大きくした。すなわち、多くのページで使われる一般的な単語は中心に配置され、少数のページでしか使われない特徴的な単語は周辺部に配置される。このことにより、単語の使われ方の類似度は角度によって、また単語の一般性は半径によって理解することが可能になる。図１５は本発明により前記単語群を可視化した結果であり、前記のように，「ホームページ」や「メニュー」、「料理」といった一般的な単語は中心付近に配置されていることが確認できる。
【実施例３】
【００５８】
実施例３は、類似度が高い文書は同方向に配置されるように文書群を可視化した例である。ここでいう文書の類似度とは、基本的には、同じようなトピックを持っているかどうかの尺度であり、トピックの同異は文書中に出現する単語の出現頻度が類似しているかどうかで判断する。本実施例では、文書中に出現する単語の出現頻度の代わりに文書群の単語頻度ベクトルを主成分分析にかけた結果得られた主成分で類似度を規定する。
【００５９】
本実施例で用いたデータは、１９９３年から２００２年までの１０年間のある新聞における国際面の記事である。本実施例では、このデータに対して、各記事をその記事に出現した単語の頻度のベクトルで表し、その単語頻度ベクトルを主成分分析にかけた。そして、通常の主成分分析と同様に１０次元に次元圧縮を行い、単語頻度ベクトル群の分散が最大になるように線形射影する。この結果、各記事は１０次元の主成分で表されるが、本実施例においては、その１０次元の主成分が似ているもの（主成分をベクトルで表したものの相互間の距離が短いもの）を類似度が高いとして記事の類似度を判断する。
【００６０】
本実施例では、まず記事を主成分分析により第１０成分まで抽出し、成分の似ている記事を同方向に配置するように最適配置を設定した。ここで、第一成分などの寄与率の高い成分をもつ記事は円周上に配置されるように半径ｒiを定めている。本実施例では、このような半径の取り方の制約に加えて、目的関数Ｅを以下に示すような形にして記事と記事の中に出現する単語頻度を表すベクトルによって可視化を行う。
Ｅ＝（ｙiTｙj  −  ｘiTｘi）2
ここで、ｘiはi番目の文書が埋め込まれる座標、ｙiはi番目の文書の単語頻度のベクトルである。本実施例では、ｙiは、文書の単語頻度のベクトルに代えて主成分分析により抽出した第１０成分までを代用する。
【００６１】
図１６は、前記記事群を前記目的関数Ｅによって可視化した結果を示す図であり、関連の近い記事は近くに配置されている。また、それぞれのトピックにおいて典型的な記事は周辺部に表示されている。図１６では、元々トピックごとにノードがそれぞれの色で彩色されており、この色の違いによってトピックごとの分類結果がわかるようになっていた。ここで示す図１６では、図１６の原画像を変換し、それぞれの色ごとにノードの模様を変えることによって示している。図１６で示されているノードはそれぞれ１つの記事に対応するものであるが、これらのノードがトピックごとにクラスタリングされているのがわかる。このように目的関数を選択することで、可視化による分類を支援する機能をも持たせることができる。
【００６２】
ここまで、本発明の最良の実施形態及び実施例について述べてきた。このような構成によれば、グラフ化された様々な事柄の関係を表す情報を分かり易く表示することができる。とりわけ、２部グラフによって表現される情報については、２部グラフであるという特徴を理解しやすくするにとどまらず、そのノード間における接続関係に基づく類似関係の存在及びその類似度の分布をも理解しやすくするという利点が得られる。なお、これらの利点は、２部グラフだけでなく、グラフ一般に対して本発明を実施したときにも得られる。また、一般的なグラフ表示方法と比べて、リンクが少ないグラフに対しては、より高速で処理できるという利点もある。なお、これらの可視化の方法は、演算手段により実現されている。
【図面の簡単な説明】
【００６３】
【図１】本発明における可視化装置の構成を示す図である。
【図２】図１の初期設定決定部の構成を示す図である。
【図３】図１の最適配置推定部の構成を示す図である。
【図４】図１の可視化部の構成を示す図である。
【図５】最適配置推定部の全体の動作を示す図である。
【図６】最適配置推定部の動作の概略を示す図である。
【図７】最適配置推定部の動作の概略を示す図である。
【図８】ｇ計算部の動作を示す図である。
【図９】ｇs計算部の動作を示す図である。
【図１０】Ｈ計算部の動作を示す図である。
【図１１】Ｈs計算部の動作を示す図である。
【図１２】Ｅs最小化部の動作を示す図である。
【図１３】実施例１における最適配置前の状態を示す図である。
【図１４】実施例１において最適配置を行った結果を示す図である。
【図１５】実施例２において最適配置を行った結果を示す図である。
【図１６】実施例３において最適配置を行った結果を示す図である。
【符号の説明】
【００６４】
１      演算装置
２      入力装置
３      記憶装置
４      表示装置
５      初期設定決定部
６      最適配置推定部
７      可視化部
８      メモリ
１１    バスライン
【図１】
2006092354.tif 000008
【図２】
2006092354.tif 000009
【図３】
2006092354.tif 000010
【図４】
2006092354.tif 000011
【図５】
2006092354.tif 000012
【図６】
2006092354.tif 000013
【図７】
2006092354.tif 000014
【図８】
2006092354.tif 000015
【図９】
2006092354.tif 000016
【図１０】
2006092354.tif 000017
【図１１】
2006092354.tif 000018
【図１２】
2006092354.tif 000019
【図１３】
2006092354.tif 000020
【図１４】
2006092354.tif 000021
【図１５】
2006092354.tif 000022
【図１６】
2006092354.tif 000023