(57)【特許請求の範囲】
【請求項１】
大きさを有する複数のノード、および、前記ノード間をつなぐ複数のエッジ、を備えるネットワークをグラフとして可視化するグラフ可視化座標計算装置であって、
対象となるネットワークのノードの個数、各ノードの空間軸方向ごとのサイズ、エッジ情報を入力する入力手段と、
演算を行う演算手段と、
計算結果を記憶する記憶手段と、
前記計算結果を出力する出力手段と、を有し、
前記演算手段は、
すべての前記ノードの初期座標を設定する初期配置部と、
すべての前記ノード間に所定の斥力が働いて斥力エネルギーが発生し、前記エッジでつながれた前記ノード間にそのノード間の距離に応じた所定の引力が働いて引力エネルギーが発生し、前記ノードごとに、そのノードの空間軸方向ごとのサイズに基づいてエネルギーのポテンシャルが設定され、少なくとも前記斥力エネルギーは前記ポテンシャルに依存して発生するというモデルの下、前記ノードごとに、発生する前記斥力エネルギーと前記引力エネルギーとの総和をそのノードのポテンシャルエネルギーとして算出するエネルギー導出部と、
前記ノードごとに、前記算出したそのノードのポテンシャルエネルギーに基づいてポテンシャルエネルギー勾配を算出するポテンシャル勾配導出部と、
前記算出したノードごとのポテンシャルエネルギー勾配に基づいて、すべての前記ノードの座標更新を行う座標更新処理部と、
所定の計算終了条件に基づいて、計算を終了するか否かを判定する計算終了条件判定部と、
前記計算を終了すると判定された場合、すべての前記ノードの座標を含む計算結果を前記記憶手段および前記出力手段の少なくとも一方に与えるデータ制御部と、
を備えることを特徴とするグラフ可視化座標計算装置。
【請求項２】
前記ポテンシャルは、楕円曲線関数に基づいて設定されていることを特徴とする請求項１に記載のグラフ可視化座標計算装置。
【請求項３】
前記斥力エネルギーは、前記ポテンシャルに依存して発生する第１のエネルギーと、前記ポテンシャルに依存せず前記ノード間の距離に依存して発生する第２のエネルギーと、の和として算出され、前記ノード間の距離が大きいほど、前記第１のエネルギーが前記第２のエネルギーと比べて小さな割合になるように設定されている
ことを特徴とする請求項１または請求項２に記載のグラフ可視化座標計算装置。
【請求項４】
前記モデルの下で、すべての前記ノード間のエネルギーの総和Ψは、右辺第１項が前記引力エネルギーを表し、右辺第２項が前記斥力エネルギーを表す次の式によって与えられるものとし、
【数１】
0004939486.tif 000020
ただし、
【数２】
0004939486.tif 000021
前記ポテンシャル勾配導出部は、前記ノードごとのポテンシャルエネルギー勾配を、前記すべてのノード間のエネルギーの総和Ψを前記ノードごとに偏微分した次の式に基づいて算出する
【数３】
0004939486.tif 000022
ことを特徴とする請求項１に記載のグラフ可視化座標計算装置。
ただし、ｘｊ，ｙｊはｊ番目のノードのｘ座標、ｙ座標、ｘｉ，ｙｉはｉ番目のノードのｘ座標、ｙ座標、Ａｊ，Ｂｊはｊ番目のノードのｘ軸方向、ｙ軸方向のサイズ、α，ｋ，ｋαは無次元量の定数、Ｅはエッジの総数、Ｅｉはｉ番目のノードにつながっているエッジの数、Ｎはノードの総数とする。
【請求項５】
前記モデルの下で、すべての前記ノード間のエネルギーの総和Ψは、右辺第１項が前記引力エネルギーを表し、右辺第２項が前記斥力エネルギーを表す次の式によって与えられるものとし、
【数４】
0004939486.tif 000023
ただし、
【数５】
0004939486.tif 000024
前記ポテンシャル勾配導出部は、前記ノードごとのポテンシャルエネルギー勾配を、前記すべてのノード間のエネルギーの総和Ψを前記ノードごとに偏微分した次の式に基づいて算出する
【数６】
0004939486.tif 000025
ことを特徴とする請求項１に記載のグラフ可視化座標計算装置。
ただし、ｘｊ，ｙｊはｊ番目のノードのｘ座標、ｙ座標、ｘｉ，ｙｉはｉ番目のノードのｘ座標、ｙ座標、Ａｉ，Ｂｉはｉ番目のノードのｘ軸方向、ｙ軸方向のサイズ、Ａｊ，Ｂｊはｊ番目のノードのｘ軸方向、ｙ軸方向のサイズ、α，ｋ，ｋαは無次元量の定数、ｑｉはｉ番目のノードの反発係数、ｑｊはｊ番目のノードの反発係数、Ｅはエッジの総数、Ｅｉはｉ番目のノードにつながっているエッジの数、Ｎはノードの総数とする。
【請求項６】
大きさを有する複数のノード、および、前記ノード間をつなぐ複数のエッジ、を備えるネットワークをグラフとして可視化するグラフ可視化座標計算装置によるグラフ可視化座標計算方法であって、
前記グラフ可視化座標計算装置は、
対象となるネットワークのノードの個数、各ノードの空間軸方向ごとのサイズ、エッジ情報を入力する入力手段と、
演算を行う演算手段と、
計算結果を記憶する記憶手段と、
前記計算結果を出力する出力手段と、を有し、
前記演算手段において、
初期配置部が、すべての前記ノードの初期座標を設定するステップを行い、
その後、
エネルギー導出部が、すべての前記ノード間に所定の斥力が働いて斥力エネルギーが発生し、前記エッジでつながれた前記ノード間にそのノード間の距離に応じた所定の引力が働いて引力エネルギーが発生し、前記ノードごとに、そのノードの空間軸方向ごとのサイズに基づいてエネルギーのポテンシャルが設定され、少なくとも前記斥力エネルギーは前記ポテンシャルに依存して発生するというモデルの下、前記ノードごとに、発生する前記斥力エネルギーと前記引力エネルギーとの総和をそのノードのポテンシャルエネルギーとして算出するステップと、
ポテンシャル勾配導出部が、前記ノードごとに、前記算出したそのノードのポテンシャルエネルギーに基づいてポテンシャルエネルギー勾配を算出するステップと、
座標更新処理部が、前記算出したノードごとのポテンシャルエネルギー勾配に基づいて、すべての前記ノードの座標更新を行うステップと、を、所定の計算終了条件が満たされるまで繰り返し、
所定の計算終了条件が満たされた場合、データ制御部が、すべての前記ノードの座標を含む計算結果を前記記憶手段および前記出力手段の少なくとも一方に与えるステップを行う
ことを特徴とするグラフ可視化座標計算方法。
【請求項７】
請求項６に記載のグラフ可視化座標計算方法をコンピュータに実行させることを特徴とするグラフ可視化座標計算プログラム。
【請求項８】
請求項７に記載のグラフ可視化座標計算プログラムが記録されたことを特徴とするコンピュータに読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＩＰ（Internet Protocol）ネットワーク、ハイパーリンクで接続されているインターネット、ソーシャルネットワークなどのように関係性を有したデータファイルがリンクのあるネットワークとして表現されるときに、２次元のネットワークまたは３次元のネットワークをグラフとして可視化する技術に関し、特に、グラフにおける各ノードが大きさのない点ではなく大きさのあるラベルとして表現されるときに、各ラベルの位置座標を適切に計算する技術に関する。
【背景技術】
【０００２】
ネットワークをグラフとして可視化する技術（以下、「グラフ可視化技術」という。）は、一般に、データとデータとの関連性によってネットワークを形成したデータを可視化することを指す。このグラフ可視化技術では、個々のデータをノードと呼び、データ間のリンクをエッジと呼ぶ。つまり、“ノード”はネットワークデータにおけるデータを意味し、“エッジ”はデータ間の有関係性を示す。
【０００３】
例えば、インターネット上のハイパーリンクの張られたＷＥＢページであれば、各ＷＥＢページのことを“ノード”といい、ハイパーリンクのことを“エッジ”という。また、例えば、テキストのことを“ノード”といい、その関係性のことを“エッジ”といってもよい。さらに、例えば、ソーシャルネットワーク上の人間のことを“ノード”といい、友達や付き合いのことを“エッジ”といってもよい。
【０００４】
図２は、ノード（点）とエッジの模式図である。一般的なグラフ可視化技術においては、図２に示すように、ネットワークの関連性を基に、２次元の仮想空間または３次元の仮想空間にノードが「点」（図２では５つ）として、エッジが点と点を繋ぐ「辺」（図２では５本）として投影されてグラフとして描画される。しかし、各ノードが固有情報を持っている場合、ノード（文字列）とエッジの模式図である図３に示すように、各ノード（５つ）は、文字列であったり、またソーシャルネットワークでは個々の縮小版画像ファイルであったりする。その場合、ノードは「点」ではなく、「ラベル」として描画される。
【０００５】
従来、グラフ可視化技術の研究分野では、１９８０年代から様々な手法が考案されてきた。最も一般的な手法は、仮想空間上に配置されたノード間のグラフ距離や、ノードが本来持っている接続関係などに基づき、系に力学関係を与え、加速度（ポテンシャル勾配（ポテンシャルエネルギー勾配））方向に座標を更新していくことによって系の最小エネルギー状態を求める手法である。すなわち、ノード間は力学的ポテンシャルに従い、グラフのノード（例えばインターネットでいうリンクの張られたページ）を力のかかる方向に座標を更新していく方法である。
【０００６】
この方法に従えば、各ノードはポテンシャルの深い場所に移動していき、結果として系全体のエネルギーが極小となるように更新されていく。グラフ可視化技術において、速度（熱力学で言うところの温度）という概念は無く、分子動力学に例えると、温度「０」の結晶構造を求めることに等しい。この方法はひとまとめに“Force-directed法”と呼ばれ、近年では様々な手法も考案されている。
【０００７】
一般的なラベル付きグラフの表示手法としては、主に、非特許文献１のバネモデル法（以下、提案者２名のイニシャルをとって「ＫＫ法」ともいう。）や、非特許文献２のForce-directed法（以下、提案者２名のイニシャルをとって「ＦＲ法」ともいう。）を基にしたグラフ描画アルゴリズムを用いて座標計算を行い、得られた座標を基点としてラベルの表示を行う方法が広く用いられている。このような座標計算結果を基にグラフ描画を行うソフトウェアとして、世界中で最も利用されているものにGraphvizがある。このソフトウェアでは、座標計算アルゴリズムにＫＫ法やＦＲ法を用いている。また、同様に、世界中で広く利用されているソフトウェアにPajekがある。このPajekの描画アルゴリズムもＫＫ法である。
以下、グラフ可視化技術における座標計算手法として広く用いられている上記二つの手法について説明する。
【０００８】
＜ＫＫ法（非特許文献１のバネモデル法）＞
ＫＫ法では、全てのノード間に仮想的なバネを仮定し、座標の更新手法を１ノードずつ逐次的に行う。ｉ番目とｊ番目のグラフ上での最短経路数を、ノード間のバネの自然長（ｌｉｊ）として与え、全体のエネルギーが極小となるように座標を更新していく。この際、ノード間のバネ定数をｋｉｊ、ノードの空間的な座標をｘｉとし、グラフの総ノード数をＮとしたとき、系の総エネルギー（バネエネルギーの総和）は次の式（１）で定義される。なお、ｘｉｊ＝ｘｊ−ｘｉであり、ｘｉｊの大きさは式（２）で定義される。ここで、ｘｉはｉ番目のノードの位相空間上の、原点を基点とした座標ベクトルであり、２次元であれば式（３）で定義され、３次元であれば式（４）で定義される。また、ＫＫ法ではバネ定数をｋｉｊ＝ｋ／ｌ２ｉｊとする。ここで、ｋは無次元量の規格化定数である。
【０００９】
【数７】
0004939486.tif 000002
【００１０】
＜ＦＲ法（非特許文献２のForce-directed法）＞
ＦＲ法では、連結するノード間（エッジ）に働く力を引力として与え、さらにノード間に斥力（反発力）を与え、二つの力の和を与えることによりノードの座標更新を行う。ここで、系の総エネルギーは例えば次の式（５）として定義される。
【００１１】
【数８】
0004939486.tif 000003
ここで、ｋは無次元量の定数であり、Ｅは接続関係を意味するエッジの総数である。また、右辺第１項がエッジとしての引力項（引力エネルギーを表す項）を示し、右辺第２項が各ノード間の斥力項（斥力エネルギーを表す項）を示す。
【００１２】
そして、ＫＫ法およびＦＲ法に示される従来の可視化座標計算アルゴリズムでは、ノードは「点」、エッジは「辺」で表現することを前提として計算が行われるため、ラベル同士が重なり合い、ラベル表示が見難くなってしまう場合があるという問題がある。ここで、図４は、従来の可視化手法による、各ノードのポテンシャルの模式図であり、同心円の大きさがポテンシャルの大きさを表す。
【００１３】
そして、例えば、図５のように、ラベルの大きさが全て等しい場合は、座標のスケールを変えたり、全てのラベルの大きさの尺度を変えたりすることによって、ラベル同士の重なり合いを解消することができる。ここで、図５は、従来の可視化手法による、大きさの等しいラベルの可視化例であり、座標値は図４の場合と同様である。
【００１４】
しかし、例えば、図６に示すように、ＩＰアドレス（ＵＲＬ（Uniform Resource Locator））のように横に長い文字列の表示や、人名の様に様々な長さのラベルを表示させる場合は、従来の手法では限界がある。また、図７に示すように、大きさの異なるラベルを表示する（貼りつける）場合にも、従来の手法ではラベル同士が重なってしまうなどの問題が起こりえる。ここで、図６は、ラベルとして長い文字列を張りつけた場合の可視化例であり、座標値は図４の場合と同様である。また、図７は、大きさの異なるラベルを張りつけた場合の表示例（可視化例）であり、座標値は図４の場合と同様である。
【００１５】
また、与えられた座標を基点として、周囲にラベルが重ならないように表示する方法として、Force-scan（非特許文献３）やSlide model（非特許文献４）も提案されている。これらの方法は、与えられた座標値を基にラベル同士が重ならないようにずらして表示を行う方法である。また、これらの方法は、路線図上や地図上に駅名や地名を表示させる場合に有用な方法として用いられている。
また、リンクが密に結合している領域では、ノード同士の斥力（反発力）を強めあって、ノードの重なりを回避する方法として、Andreas(2004)の手法（非特許文献５）も提案されている。
【非特許文献１】T. Kamada, and S. Kawai: An algorithm for drawing general undirected graphs, Information Processing Letters, Vol. 31, No. 1, p.7-15, 12 April (1989)
【非特許文献２】T. M. J. Fruchterman, and E. M. Reingold: Graph Drawing by Force-directed Placement, Software - Practice and Experience, Vol. 21(11), p.1129-1164 (1991)
【非特許文献３】K. Misue, P. Eades, W. Lai, and K. Sugiyama: Layout Adjustment and the Mental Map, Journal of Visual Languages and Computing, Vol. 6, No. 2, p.183-210, (1995)
【非特許文献４】D. Ebner, G. W. Klau and R. Weiskircher: Label Number Maximization in the Slider Model, Proceedings Graph Drawing, New York, p.144-154 (2004)
【非特許文献５】Andreas N.: Visual clustering of graphs with nonuniform degrees, Technical Report 02/04, BTU Cottbus, (2004)
【発明の開示】
【発明が解決しようとする課題】
【００１６】
しかしながら、非特許文献３，４の手法を用いれば、与えられた座標値からラベルが重ならないように配置を変えることはある程度可能であるものの、ノードが密集した領域や、サイズの異なるラベルについてのグラフ可視化には適用が困難である（ラベル同士の重なりが生じてしまうことがある）という問題があった。さらに、座標軸を計算した後に、再度局所的に座標計算を行う必要もあり、ノードとリンクの数が大規模になると、計算量が莫大になるという問題があった。また、非特許文献５の手法を用いれば、ノードが密集した領域ではラベル同士の重なりをある程度回避できるものの、ノードの反発力が可視化結果に大きく影響を与えてしまい、全体の可視化結果が従来方法により算出される形状とは全く変わってしまうという問題があった。
【００１７】
そこで、本発明は、前記した問題点に鑑みてなされたものであり、全体の可視化結果が従来方法により算出される形状とそれほど変わらずに、ノードが密集した領域や、サイズの異なるノード（ラベル）についても、重なりが無いようにノード（ラベル）を配置することができ、計算量を軽減するグラフ可視化技術を提供することを課題とする。
【課題を解決するための手段】
【００１８】
前記課題を解決するために、本発明のグラフ可視化座標計算装置は、大きさを有する複数のノード、および、前記ノード間をつなぐ複数のエッジ、を備えるネットワークをグラフとして可視化するグラフ可視化座標計算装置であって、対象となるネットワークのノードの個数、各ノードの空間軸方向ごとのサイズ、エッジ情報を入力する入力手段と、演算を行う演算手段と、計算結果を記憶する記憶手段と、前記計算結果を出力する出力手段と、を有し、前記演算手段は、すべての前記ノードの初期座標を設定する初期配置部と、すべての前記ノード間に所定の斥力が働いて斥力エネルギーが発生し、前記エッジでつながれた前記ノード間にそのノード間の距離に応じた所定の引力が働いて引力エネルギーが発生し、前記ノードごとに、そのノードの空間軸方向ごとのサイズに基づいてエネルギーのポテンシャルが設定され、少なくとも前記斥力エネルギーは前記ポテンシャルに依存して発生するというモデルの下、前記ノードごとに、発生する前記斥力エネルギーと前記引力エネルギーとの総和をそのノードのポテンシャルエネルギーとして算出するエネルギー導出部と、前記ノードごとに、前記算出したそのノードのポテンシャルエネルギーに基づいてポテンシャルエネルギー勾配を算出するポテンシャル勾配導出部と、前記算出したノードごとのポテンシャルエネルギー勾配に基づいて、すべての前記ノードの座標更新を行う座標更新処理部と、所定の計算終了条件に基づいて、計算を終了するか否かを判定する計算終了条件判定部と、前記計算を終了すると判定された場合、すべての前記ノードの座標を含む計算結果を前記記憶手段および前記出力手段の少なくとも一方に与えるデータ制御部と、を備えることを特徴とする。グラフ可視化座標計算方法についても同様である。
【００１９】
かかる構成のグラフ可視化座標計算装置および方法によれば、ノードごとに、そのノードの空間軸方向ごとのサイズに基づいてエネルギーのポテンシャルが設定され、少なくとも前記斥力エネルギーは前記ポテンシャルに依存して発生するというモデルの下、ノードごとにポテンシャルエネルギー勾配を算出し、そのポテンシャルエネルギー勾配に基づいてすべてのノードの座標更新を行うので、ノードが密集した領域や、サイズの異なるノードについても、重なりが無いようにノードを配置することができる。
【００２０】
また、本発明に係るグラフ可視化座標計算装置は、ポテンシャルが楕円曲線関数に基づいて設定されていることが好ましい。
【００２１】
かかる構成のグラフ可視化座標計算装置によれば、楕円曲線関数が使用されていることで、他の関数を使用した場合に比べて計算量が少なくて済む。
【００２２】
また、本発明に係るグラフ可視化座標計算装置は、前記斥力エネルギーは、前記ポテンシャルに依存して発生する第１のエネルギーと、前記ポテンシャルに依存せず前記ノード間の距離に依存して発生する第２のエネルギーと、の和として算出され、前記ノード間の距離が大きいほど、前記第１のエネルギーが前記第２のエネルギーと比べて小さな割合になるように設定されていることが好ましい。
【００２３】
かかる構成のグラフ可視化座標計算装置によれば、各ノードにおいて、そのノードの近傍ではラベルの大きさに依存した反発力が与えられ、遠方では近似的にユークリッド距離のみに依存した反発力が与えられることになる。したがって、Tree-codeのようなポテンシャルの重ね合わせによる近似計算を適用することができ、ノードの数が数万あるいは数十万といった多い場合でも、比較的短い時間で計算を完了することができる。
【００２４】
また、本発明に係るグラフ可視化座標計算プログラムは、前記したグラフ可視化座標計算装置によるグラフ可視化座標計算方法をコンピュータに実行させることを特徴とする。このように構成されることにより、このプログラムをインストールされたコンピュータは、このプログラムに基づいた各機能を実現することができる。
【００２５】
また、本発明に係るコンピュータに読み取り可能な記録媒体は、前記したグラフ可視化座標計算プログラムが記録されたことを特徴とする。このように構成されることにより、この記録媒体を装着されたコンピュータは、この記録媒体に記録されたプログラムに基づいた各機能を実現することができる。
【発明の効果】
【００２６】
本発明によれば、ノードが密集した領域や、サイズの異なるノード（ラベル）についても、重なりが無いようにノード（ラベル）を配置することができる。また、全体の可視化結果が従来方法により算出される形状とそれほど変わらずに、計算の収束性を向上させ、計算量を軽減させることができる。
【発明を実施するための最良の形態】
【００２７】
以下、本発明のグラフ可視化座標計算装置およびグラフ可視化座標計算方法を実施すための最良の形態（以下、「実施形態」という。）について、図面を参照しながら説明する。なお、説明の都合上、まず、第１実施形態の概要を説明し、その後、第１実施形態の詳細について数式及び図面を参照して説明する。なお、以下、「加速度」とは、「ポテンシャル勾配（ポテンシャルエネルギー勾配）」またはその大きさを意味する。
【００２８】
［第１実施形態の概要］
従来の手法において、グラフ可視化の座標値計算では、ノード間の力学方程式を位相空間上での座標間距離に依存した関数系で与える。つまり、ＫＫ法やＦＲ法ではｉ番目とｊ番目のノードに関わる加速度公式はユークリッド距離｜ｘｉｊ｜に依存した関数で与えられ、その加速度の方向ベクトルはｘｉｊと平行である。
【００２９】
ここで、第１実施形態では、非軸対称ポテンシャルを用いて、各ノードに対して異なる形状の斥力（反発力）を与えることによって、個々のラベルの大きさを考慮した最適配置を求める手法を提案する。なお、「非軸対称」とは、２次元においては、ｘ軸方向とｙ軸方向にスケーリングが異なっていること、具体的な図形としては「正円以外」を意味する。また、引力に関しては従来通りの軸対称ポテンシャルを使用する。「軸対称」とは、２次元においては、ｘ軸方向とｙ軸方向にスケーリングが同じであること、具体的な図形としては「正円」を意味する。
【００３０】
第１実施形態の手法では、ｉ番目のノードに対してｘ軸方向、ｙ軸方向、ｚ軸方向にＡｉ，Ｂｉ，Ｃｉという大きさを持つラベルつきのグラフに対して、斥力のポテンシャルを設定する。従来では、ｘ軸方向、ｙ軸方向、ｚ軸方向に無次元量の同じスケール尺度を用いていたが、第１実施形態の手法では、ラベルの大きさを非軸対称ポテンシャルで与える。例えば、楕円形のポテンシャルとして、単位円（３次元では単位球）を、ｘ軸方向、ｙ軸方向、ｚ軸方向に、それぞれＡ，Ｂ，Ｃだけ延ばしたポテンシャル形状を与える。以下、ｉ番目のノードに対してはＡｉ，Ｂｉ，Ｃｉとする。
【００３１】
このとき、斥力ポテンシャル（以下、単に「ポテンシャル」ともいう。）をΦｉ（ｘ）とすると、この斥力ポテンシャルを、２次元の計算であれば式（６）に示す関数形で与え、３次元の計算であれば式（７）に示す関数形で与えることによって、非軸対称なポテンシャルを設定することができる。
【数９】
0004939486.tif 000004
【００３２】
ラベルが、例えば、図７のように互いに重なり合っていたとしても、第１実施形態のグラフ可視化座標計算技術において、図８のように固有の楕円ポテンシャルを与え、各ノードが系の総エネルギーを最小とするような配置を探せば、その結果、図９のようにラベルが重なり合わない座標を求めることができる。ここで、図７は、大きさの異なるラベルの表示例であり、座標値は図４の場合と同様である。また、図８は、非軸対称ポテンシャルを利用した、各ノードのポテンシャルの模式図であり、同心楕円の大きさがポテンシャルの大きさを表す。さらに、図９は、大きさの異なるラベルの表示例であり、図７の各ラベルの配置を変えることで重なりを無くした様子を示している。
【００３３】
[第１実施形態における計算例]
第１実施形態における計算例として、ＦＲ法の関数に対しての具体例を示す。第１実施形態では、系の総エネルギーを、前記した式（５）の代わりに、次の式（５ａ）、式（５ｂ）として定義する。
【００３４】
【数１０】
0004939486.tif 000005
【数１１】
0004939486.tif 000006
ここで、α，ｋ，ｋαは無次元量の定数であり、Ｅはエッジの総数、Ｎはノードの総数である。また、式（５）の場合と同様、右辺第１項が引力項を示し、右辺第２項がの斥力項を示す。
なお、先に述べたようにｋとｋαは定数なので、式（５ａ）と式（５ｂ）は実質等価である。
【００３５】
また、非軸対称なポテンシャルを設定するために、前記した式（２）で定義した｜ｘｉｊ｜の代わりに｜ｘ〜ｉｊ｜（本明細書において、記号「〜（チルダ）」はその直前の文字の上に付される記号であるものとする）を与える。その場合、｜ｘ〜ｉｊ｜を、２次元では式（８）のように定義し、３次元では式（９）のように定義する。また、その｜ｘ〜ｉｊ｜におけるポテンシャルΦｊの勾配を用いることで、ｉ番目のノードに対する加速度ａｉは式（１０）で表すことができる。
【００３６】
【数１２】
0004939486.tif 000007
【００３７】
ここで、さらに式（５ｂ）も考慮して、２次元の場合は、ｉ番目のノードに対する加速度ａｉのｘ成分ａｘ，ｉ、ｙ成分ａy，ｉはそれぞれ式（１１）、式（１２）のようになる。ここで、Ｅｉは、ｉ番目のノードの持つ総リンク（エッジ）数である。
【数１３】
0004939486.tif 000008
【００３８】
この加速度の表式を用いることで、ポテンシャルの形状、つまり、ラベルのサイズや形状に適した目的関数の算出式を設定することができる。
以下、２次元に絞って話を進める。
【００３９】
なお、第１実施形態では、このように、斥力項を｜ｘｉｊ｜と｜ｘ〜ｉｊ｜の両方を使って表すことで、高精度のラベル配置を実現している。つまり、非軸対称なポテンシャルに対応した加速度の表式を単純にＦＲ法に適用しただけ（以下、「ＦＲ法への単純適用」という。）では（つまり、式（５ｂ）の斥力項に｜ｘｉｊ｜の項がない場合）、横に長い（以下、「偏平」という。）、例えば文字列のようなラベルを扱う場合は、全体のポテンシャルが偏平になり過ぎてしまい、可視化計算の結果に影響を与える場合がある。
【００４０】
ＦＲ法への単純適用でも、例えば、図６のように、互いに重なり合っていたラベルを、ラベルの文字列の長さを考慮することによって、図１０のようにポテンシャルを与え、図１１のようにラベルが重なり合わない座標を求めることができる。ここで、図６は、ラベルが長い文字列の場合の可視化表示例であり、座標値は図４の場合と同様である。また、図１０は、非軸対称ポテンシャルを利用した、各ノードのポテンシャルの模式図（その２）であり、同心楕円の大きさがポテンシャルの大きさを表している。さらに、図１１は、図６の各ラベルの配置を変えることで重なりを無くした様子を示している。しかし、図１１に示すように、全てのノードが長い文字列の場合、全てのノードのポテンシャルが扁平であることにより、可視化結果が全体的に扁平になり、あまり好ましくない。これは、表示手段（モニタ）の画面と縦横比が大きく異なると表示しにくい、などの問題のためである。
【００４１】
また、ＦＲ法への単純適用では、非軸対称なポテンシャルを個々のノードに与えることによって、Tree-codeのようなポテンシャルの重ね合わせによる近似計算が適用できなくなる。Tree-codeとは、あるノードに対して遠方のノードの集団の一部ずつを近似的にひとまとまりに扱って計算する手法である。このTree-codeが使用できないことは、大規模計算（特に数十万ノードを超えるような計算）には致命的である。
しかしながら、この問題は、第１実施形態では、前記した式（５ｂ）のように、ポテンシャル関数を２重に与えることにより、回避している。
【００４２】
第１実施形態では、前記のように斥力項のポテンシャルを２重に設定することにより、ポテンシャルを遠方で点対称で与え、Tree-codeのような既存の近似手法を用いることができるようにしている。さらに、この手法では、遠方での斥力（反発力）を残しつつ、近傍の斥力を強くすることができる利点があり、近傍での斥力を強くすることにより、ラベル同士が重ならないという制限を強くすることができる。つまり、全てのノードが長い文字列の場合でも、可視化結果を、全体的があまり扁平でないようにすることができる。
【００４３】
例えば、ＦＲ法への単純適用では、斥力項は距離（または距離の２乗など）に反比例した大きさで定義される。このような力学関数では、遠方まで反発力の効果が続く反面、近傍での反発力はさほど強くならない。しかし、式（５ｂ）に示すように、斥力項を｜ｘｉｊ｜と｜ｘ〜ｉｊ｜の両方を使って表すことで、近傍でのラベルサイズに依存した反発力を強くすることができる。
【００４４】
ここで重要なのは、ノード間の距離が大きいほど、｜ｘ〜ｉｊ｜に依存して発生する第１のエネルギー（斥力ポテンシャルに依存する項）が、｜ｘｉｊ｜に依存して発生する第２のエネルギー（ユークリッド距離に依存する項）と比べて小さな割合になるように設定されていることである。その条件を満たす限り、斥力項は自由に設定できるものとする。
【００４５】
ここで、実際の計算結果例を図１２に示す。図１２において、（ａ）は式（５ｂ）の右辺第２項中の右項成分、（ｂ）は式（５ｂ）の右辺第２項中の左項成分、（ｃ）は（ａ）と（ｂ）の和を示したものである。このように、非軸対称の関数（式（５ｂ）の右辺第２項中の右項：第１のエネルギー）と、軸対称の関数（式（５ｂ）の右辺第２項中の左項：第２のエネルギー）の二つの関数を重ね合わせることによって、近傍ではラベルの大きさに依存した反発力を与え、遠方では近似的にユークリッド距離のみに依存した反発力を与えることができる。
【００４６】
（座標更新手法）
ここで、座標更新について説明する。座標更新は従来手法と同様に行う。つまり、第１実施形態のグラフ可視化座標計算方法は、ＫＫ法およびＦＲ法との相違点が目的関数のみであるため、エネルギー最小化問題に関しては同様の処理を行うことができる。以下、ここではＦＲ法をベースとした座標更新手法について述べる。
【００４７】
各ノードの初期配置を乱数で与え、各ノードに座標ｘｉ（０）を設定する。そして、全ノードの配置から各ノードの加速度（ポテンシャル勾配）を、式（５ｂ）を用いて算出し、ｉ番目のノードの更新式は次の式（１３）で与えられる。ここで、ｔは更新回数である。一般に、ＦＲ法では更新座標の発散を防ぐために冷却関数ｔｃｏｏｌ（ｔ）を用いて更新上限幅を押さえ込む。この冷却関数は、次の式（１４）で与えられる。なお、Ｃは無次元量の定数、ＴＥＮＤはあらかじめ設定された更新回数である。ＣおよびＴＥＮＤは自由に設定することができる。
【００４８】
【数１４】
0004939486.tif 000009
【００４９】
（ハードウェア構成など）
次に、第１実施形態のグラフ可視化座標計算装置のハードウェア構成などについて説明する。図１は、第１実施形態のグラフ可視化座標計算装置の構成図である。グラフ可視化座標計算装置１は、複数のノード、ノード間をつなぐ複数のエッジ、各ノードのラベルサイズなどの情報を有するネットワークにおける各ノードの座標を、各ノードが重ならないように、非軸対称ポテンシャルに基づいて計算し、グラフとして可視化するものである。このグラフ可視化座標計算装置１は、図１に示すように、演算手段２と、入力手段３と、記憶手段４と、出力手段５とを備えており、それらの各手段がバスライン６に接続されている。
【００５０】
演算手段２は、例えば、ＣＰＵ(Central Processing Unit)およびＲＡＭ(Random Access Memory)（メモリ）から構成される主制御装置である。この演算手段２は、図１に示すように、初期配置部２１と、加速度導出部２２（ポテンシャル勾配導出部）と、座標更新処理部２３と、エネルギー導出部２４と、計算終了条件判定部２５と、データ制御部２６とを含んで構成される（詳細は後記）。
【００５１】
入力手段３は、例えば、キーボードやマウスなどから構成される。この入力手段３は、例えば、データとして、対象となるネットワークのリンク情報（ノード数と、各ノードのリンク先）を入力し、記憶手段４に格納する。第１実施形態では、入力手段３は、ノード数Ｎ、各ノードのサイズ、および、エッジ数Ｅを入力する。
【００５２】
記憶手段４は、例えば、一般的なハードディスク装置などから構成され、演算手段２で用いられる各種プログラムや各種データなどを記憶する。演算手段２は、これらのプログラムを記憶手段４から読み込んでメモリに展開して実行することで、演算手段２の各機能を実現する。
【００５３】
出力手段５は、例えば、グラフィックボード（出力インタフェース）およびそれに接続されたモニタである。モニタは、例えば、液晶ディスプレイなどから構成され、演算処理結果（例えば、各ノードの座標など）を表示する。
【００５４】
図１３は、グラフ可視化座標計算装置１による処理の流れを示すフローチャートである。
まず、ユーザが入力手段３から入力した、対象となるネットワークのノード数Ｎ、各ノードのサイズ（Ａｉ，Ｂｉ）、エッジ数Ｅ（エッジ両端のノード情報も含む）を初期配置部２１が受け付け（ステップＳ１）、初期情報として記憶手段４（あるいはメモリ）に記憶する。
【００５５】
次に、初期配置部２１は、乱数を発生し、発生した乱数を基に、全ノードに対して、ランダムな初期座標を設定する（ステップＳ２）。
続いて、エネルギー導出部２４は、与えられた初期座標配置を基に全ノードのそれぞれのエネルギーの初期値として、式（５ｂ）を使用して初期エネルギーΦ０を算出（導出）する（ステップＳ３）。つまり、ノードごとに、斥力エネルギーと引力エネルギーとの総和をそのノードのポテンシャルエネルギーとして算出する。
【００５６】
次に、加速度導出部２２は、与えられた初期座標配置を基に全ノードに対して加速度（ポテンシャルエネルギー勾配）を算出（導出）する（ステップＳ４）。具体的には、式（１０）を使用して加速度を算出する。ＦＲ法に適用した場合は、加速度のｘ成分およびｙ成分はそれぞれ式（１１）および式（１２）に相当する。つまり、ノードごとに、そのノードのポテンシャルエネルギーに基づいてポテンシャルエネルギー勾配を算出する。
【００５７】
続いて、ステップＳ４で求めた加速度（ポテンシャルエネルギー勾配）を基に、座標更新処理部２３は、座標の更新を行う、つまり、更新座標ｘｉ（ｔ＋１）を計算する（ステップＳ５）。具体的には、ＦＲ法に適用した場合は、式（１３）を使用して更新座標を計算する。また、ＫＫ法などの他の既存手法に適用するときは適宜それらの手法に合わせて計算すればよい。
【００５８】
次に、エネルギー導出部２４は、各ノードの最新座標を基に、式（５ｂ）を使用して全ノードのそれぞれのエネルギーΦを算出（導出）する（ステップＳ６）。つまり、ノードごとに、斥力エネルギーと引力エネルギーとの総和をそのノードのポテンシャルエネルギーとして算出する。
【００５９】
続いて、計算終了条件判定部２５は、計算の終了条件を満たすか否か判定する（ステップＳ７）。ＦＲ法に適用した場合、例えば、式（１３）にあるようにあらかじめ計算の更新回数をＴＥＮＤとして設定するする必要があり、ｔ＝ＴＥＮＤが計算終了条件となる。また、ＫＫ法では、新しく得られたエネルギーΦ（ｔ＋１）と、更新前のエネルギーΦ（ｔ）との差分△Φ＝Φ（ｔ＋１）−Φ（ｔ）を求め、これが充分小さくなった時に計算を終了する。
【００６０】
計算終了条件を満たさない場合（ステップＳ７でＮｏ）、ステップＳ４に戻って処理を繰り返す。
一方、計算終了条件を満たす場合（ステップＳ７でＹｅｓ）、データ制御部２６は、対象となるネットワークの各ノードの座標とエネルギー（総エネルギー、各ノードのポテンシャルエネルギーのいずれかあるいは両方）などを、バスライン６を通じて出力手段５に送信する。これを受けて、出力手段５は、対象となるネットワークの各ノードの座標とエネルギーなどの計算結果を出力する。
【００６１】
このように、第１実施形態のグラフ可視化座標計算装置１によれば、ノードが密集した領域や、サイズの異なるラベルについても、重なりが無いようにラベルを配置することができる。
【００６２】
なお、対象となるラベルは、長方形（または直方体）や文字列のラベルに限るものではなく、多角形や様々な形状とすることができる。つまり、第１実施形態は、非軸対称ポテンシャルを用いる手法であるので、ラベルに対する外接長方形など使用することで、様々な形状のラベルを対象とすることができる。
【００６３】
図１４は、第１実施形態において長方形以外のラベルを対象とする場合の説明図である。
図１４において、（ａ）はラベル形状が三角形の場合、（ｂ）はラベル形状が五角形の場合、（ｃ）はラベル形状が六角形の場合、（ｄ）はラベル形状が自由形状の場合、をそれぞれ示している。
【００６４】
いずれの場合も、ラベルの“スケール（サイズ）”という考えを用いて、近似的に外接長方形（または直方体）を定義し、縦横のラベルサイズとして、Ａ，Ｂを定義する。このようにラベルサイズを定義することによって、原理的に、多角形や自由形状の場合でもラベルを重ならずに配置させることが可能である。
【００６５】
（第１実施形態における実験例）
次に、図１５Ａ〜１５Ｃを参照しながら、第１実施形態のグラフ可視化座標計算装置１による実験例について説明する。図１５Ａは、ラベルのサイズおよびエッジに関する情報の一覧表である。図１５Ｂは、図１５Ａに示すラベルに関するＦＲ法による可視化の計算結果を示す図である。図１５Ｃは、図１５Ａに示すラベルに関する第１実施形態の手法による可視化の計算結果を示す図である。
【００６６】
図１５Ａに示すように、６２個のラベル（「Ｂｅａｋ」以下）に関して、ラベルサイズ（Ａｉ，Ｂｉ）とエッジ数（Ｅｉ）が与えられている。なお、各ノードに関するエッジの相手ノードの情報などについては記載を省略している。図１５Ｂに示すように、ＦＲ法による可視化では、特にラベルが密集している箇所でラベル同士が重なり合っていることがわかる。
【００６７】
一方、第１実施形態の手法による可視化では、ラベル同士がほとんど重なり合っておらず、ＦＲ法（図１５Ｂ）と比べて、劇的に改善したことがわかる。
【００６８】
以上説明したように、第１実施形態のグラフ可視化座標計算装置１によれば、ノードが密集した領域や、サイズの異なるラベルについても、重なりが無いようにラベルを配置することができる。
【００６９】
また、第１実施形態では、非軸対称ポテンシャルが、シンプルな楕円曲線を表す関数に基づいて設定されていることで、計算量が少なくて済む。つまり、ポテンシャル形状を楕円にすることにより、加速度として定義されるポテンシャル勾配を非常にシンプルな関数として求めることができ、実アプリケーションヘの実装が容易となる利点がある。なお、ポテンシャル形状を多角形にした場合、ポテンシャル勾配の導出が複雑になり、さらに多角形の角の部分など、特異点などが存在し、条件分岐による処理が複雑化する。
【００７０】
さらに、第１実施形態では、非軸対称ポテンシャルが、非軸対称な関数と軸対称な関数との和の関数に基づいて設定されており、ノード間の距離が大きいほど非軸対称な関数の値が軸対称な関数の値に対して小さな割合になるように設定されている。これにより、各ノードにおいて、近傍ではラベルの大きさに依存した反発力を与え、遠方では近似的にユークリッド距離のみに依存した反発力を与えることができる。したがって、Tree-codeのようなポテンシャルの重ね合わせによる近似計算を適用することができ、ノードの数が数万あるいは数十万といった大きな場合でも、比較的短い時間で計算を完了することができる。
【００７１】
また、グラフ可視化座標計算装置１における各処理は、コンピュータのＣＰＵがプログラムを実行することで、実現することができる。また、コンピュータに読み取り可能な記録媒体に、そのプログラムを記録することもできる。
【００７２】
[第２実施形態における計算例]
第２実施形態では、系のエネルギーを、前記した式（５ｂ）、式（８）、式（１１）、式（１２）の代わりに、次の式（１５）、式（１６）、式（１７）、式（１８）として定義する。
【数１５】
0004939486.tif 000010
【００７３】
【数１６】
0004939486.tif 000011
【００７４】
【数１７】
0004939486.tif 000012
【００７５】
ここで、ｘｊ，ｙｊはｊ番目のノードのｘ座標、ｙ座標、ｘｉ，ｙｉはｉ番目のノードのｘ座標、ｙ座標、Ａｉ，Ｂｉはｉ番目のノードのｘ軸方向、ｙ軸方向のサイズ、Ａｊ，Ｂｊはｊ番目のノードのｘ軸方向、ｙ軸方向のサイズ、α，ｋ，ｋαは無次元量の定数、ｑｉはｉ番目のノードの反発係数、ｑｊはｊ番目のノードの反発係数、Ｅはエッジの総数、Ｅｉはｉ番目のノードにつながっているエッジの数、Ｎはノードの総数である。
【００７６】
式（５ｂ）と式（１５）とにおける違いは、式（１５）には反発係数ｑｉ，ｑｊがある点である。反発係数ｑｉ，ｑｊは、非特許文献５に記載されているAndreas(2004)の手法に用いられているもので、Andreas(2004)の手法で用いられている系のエネルギーは、次の式（１９）として定義されている。
【００７７】
【数１８】
0004939486.tif 000013
【００７８】
ちなみに、Andreas(2004)の手法では、ノードの反発係数ｑｉ，ｑｊが可視化結果に大きく影響を与えてしまい、全体の可視化結果が、ＦＲ法において算出された形状と全く変わってしまう。
それに対して、式（１５）では、ノードの反発係数ｑｉ，ｑｊは、固有楕円ポテンシャルの成分にしかかからない。そのため、遠距離力は、第２項が強く効くことになり、全体の可視化結果の形状に大きな影響を与えずに、かつ、近傍では、密にリンク結合している領域での重なりを回避することができる。
【００７９】
さらに、第２実施形態において、反発係数ｑｉは、ｉ番目のノードにつながっているエッジの数を重みとして与え、次の式（２０）として定義する。
【００８０】
【数１９】
0004939486.tif 000014
【００８１】
なお、式（２０）は、ｑｉ＝ｓｑｒｔ（Ｅｉ）やｑｉ＝Ｅｉ×Ｅｉなどのように、様々な関数で与えることが可能である。また、ｑｉ＝Ｗとして、反発係数を定数として与えることも可能である。
このように、重みを加えることによって、ラベルの重なりを回避する精度の向上が見られた。この結果については、後記する。
【００８２】
次に、式（８）と式（１６）との相違点を、図１６を用いて説明する。図１６は、第１実施形態のポテンシャル場の考え方と第２実施形態のポテンシャル場の考え方との相違を示す図である。
図１６の基準座標に示すように、ｉ番目のラベルの形状が縦長で、ｊ番目のラベルの形状が横長だった場合を考える。この場合、第１実施形態の考え方では、ｉ番目のノードが受ける力は、ｊ番目のノードの大きさおよびラベルの横長の形状のみを考慮していたため、ｊ番目のノードに比例した力となる。すなわち、式（１１）と式（１２）とから、ｉ番目のノードは、ｊ番目のノードのラベルの形状がＡｊ＞Ｂｊなので、ｊ番目のノードに対して縦側に配置される方向に力を受けることがわかる。また、同様にｊ番目のノードが受ける力は、ｉ番目のノードの大きさおよびラベルの縦長の形状のみを考慮していたため、ｉ番目のノードに比例した力となる。すなわち、ｊ番目のノードは、ｉ番目のラベルの形状がＢｉ＞Ａｉなので、ｉ番目のノードに対して横側に配置される方向に力を受ける。
【００８３】
それに対して、第２実施形態の考え方では、ｉ番目のノードが受ける力は、自身（ｉ番目のノード）の大きさおよび形状を考慮しているため、すなわち、Ａｉ＋ＡｊおよびＢｉ＋Ｂｊというように、自身のＡｉとＢｉを考慮しているため、式（１７）と式（１８）とから、ｉ番目とｊ番目のノードの大きさの和に比例した力となる。また、ｊ番目のノードが受ける力についても、同様に、自身（ｊ番目のノード）の大きさおよび形状を考慮しているため、ｉ番目とｊ番目のノードの大きさの和に比例した力となる。したがって、第２実施形態におけるポテンシャル場は、力の対称性が保たれた状態となる。そのため、第２実施形態では、計算の精度が向上するとともに計算の収束性が向上し、計算量を軽減させることが可能である。
【００８４】
次に、式（１７）および式（１８）について、以下に説明する。
各式（１７），（１８）は、系のエネルギー式（１５）に対応して得られる加速度である。この加速度の各式を用いることで、ポテンシャルの形状、つまり、ラベルのサイズや形状に適した目的関数の算出式を設定することができる。
なお、３次元の場合には、次の式（２１）として定義される。
【００８５】
【数２０】
0004939486.tif 000015
【００８６】
（第２実施形態における実験例）
次に、第１実施形態の実験例において用いた図１５Ａのデータを対象として、第２実施形態における実験例について以下に説明する。
【００８７】
（スケーリング）
まず、ラベル付きグラフ可視化において、ラベルの重なりを確実に回避する方法として、縮尺の変更、すなわち、スケーリングについて、図１７を用いて説明する。図１７は、スケーリングによる重なりの回避手法の一例を示す図である。
図１７では、ｉ番目のラベルとｊ番目のラベルとを対象として、その重なりを、ｘ軸方向については、ｓｘ＝（Ａｉ＋Ａｊ）／｛２｜ｘｊ−ｘｉ｜｝として表し、ｙ軸方向については、ｓｙ＝（Ｂｉ＋Ｂｊ）／｛２｜ｙｊ−ｙｉ｜｝として表す。すなわち、重なりが大きいほど、｜ｘｊ−ｘｉ｜または｜ｙｊ−ｙｉ｜が小さくなるため、ｓｘまたはｓｙは大きくなる。
したがって、重なり回避する最小スケーリングｓｉｊは、ｉ番目のノードの座標（ｘｉ，ｙｉ）およびｊ番目のノードの座標（ｘｊ，ｙｊ）を用いて、次の式（２２）として定義される。
【００８８】
【数２１】
0004939486.tif 000016
【００８９】
ここで、全体の最小スケーリングＳは、全てのｉ，ｊの組み合わせに対してのｓｉｊの最大値であって、次の式（２３）として定義される。
【００９０】
【数２２】
0004939486.tif 000017
【００９１】
そして、可視化計算によって得られた座標値全体をＳ倍することによって、ラベル同士が重ならないように配置することが可能となる。
【００９２】
（ハードウェア構成など）
第２実施形態におけるグラフ可視化座標計算装置１のハードウェア構成および処理の流れは、第１実施形態と同様であるので説明を省略する。
（実験結果）
第２実施形態のグラフ可視化座標計算装置１による実験結果について、図１８Ａ〜図１８Ｄを用いて以下に説明する。図１８Ａは、ＦＲ法による可視化の計算結果を示す図である。図１８Ｂは、第１実施形態の手法（式（５ａ）；α＝２の場合）による可視化の計算結果を示す図である。図１８Ｃは、第２実施形態の手法（式（１５）；α＝２、ｑｉ＝１の場合）による可視化の計算結果を示す図である。図１８Ｄは、第２実施形態の手法（式（１５）；α＝２、ｑｉ＝Ｅｉの場合）による可視化の計算結果を示す図である。
【００９３】
図１８Ａに示すように、ＦＲ法による可視化では、ノードが密集した領域の影響によって、描画領域全体の広がりに対して、個々のラベルのサイズが相対的に小さくなっていることがわかる。
図１８Ｂでは、図１８Ａと比較して、個々のラベルのサイズが大きくなっている。
図１８Ｃは、図１８Ｂと比較して、わずかながらラベルのサイズが大きくなっている。
図１８Ｄでは、図１８Ｃと比較して、ラベルのサイズが大きくなっている。つまり、ラベルが重ならず、かつ、サイズが大きくなっているため、ラベルの視認性が高くなっている。
【００９４】
次に、図１８Ａ〜図１８Ｄに示した結果を、定量的に比較するために、ラベルの面積占有率を用いた評価結果について、図１９を用いて説明する。図１９は、可視化結果の一例を示した図である。
【００９５】
まず、図１９に示した変数Ｘ，Ｙ，ＸＹ，Ｌについて説明する。
Ｘ，Ｙはそれぞれ、ラベルの全体が描かれている範囲を現す描画領域の、ｘ軸方向の大きさとｙ軸方向の大きさとを表していて、次の式（２４），式（２５）として定義される。
【００９６】
【数２３】
0004939486.tif 000018
【００９７】
このとき、描画領域の面積がＸＹである。そして、ラベルの面積占有率Ｌは、次の式（２６）として定義される。
【００９８】
【数２４】
0004939486.tif 000019
【００９９】
すなわち、ラベルの面積占有率Ｌが大きいほど、ラベルが大きく表示されるため、良い手法であるといえる。
図１９に示されたラベルの面積占有率Ｌを比較すると、ＦＲ法に比べて、各実施形態において、大きな改善が見られる。特に、第２実施形態において、最も大きな改善が見られる。
【０１００】
以上説明したように、第１実施形態のグラフ可視化座標計算装置１と同様に、第２実施形態のグラフ可視化座標計算装置１によれば、ノードが密集した領域や、サイズの異なるラベルについても、重なりが無いようにラベルを配置することができる。
さらに、第２実施形態では、式（１６）および式（２１）の｜ｘ〜ｉｊ｜を用いることにより、ポテンシャル場において、力の対称性が保たれた状態となる。また、反発係数ｑｉ，ｑｊを導入することにより、力の対称性を保ちつつ、さらにリンクの密な領域（複数のエッジが狭い領域で複雑に交差している状況）での計算精度を向上させることができる。そして、計算精度が向上したことによって、計算の収束性も向上し、計算量を軽減させることが可能である。
【０１０１】
以上で各実施形態の説明を終えるが、本発明の態様はこれらに限定されるものではない。
例えば、グラフ可視化座標計算装置１の演算手段２を構成する各部は、複数の装置に機能を分散配置してもよい。これにより、各装置への負荷が分散され、高速な処理が実現可能となる。
その他、ハードウェア、プログラムなどの具体的な構成について、本発明の主旨を逸脱しない範囲で適宜変更が可能である。
【図面の簡単な説明】
【０１０２】
【図１】第１実施形態のグラフ可視化座標計算装置の構成図である。
【図２】ノード（点）とエッジの模式図である。
【図３】ノード（文字列）とエッジの模式図である
【図４】従来の可視化手法による、各ノードのポテンシャルの模式図である。
【図５】従来の可視化手法による、大きさの等しいラベルの可視化例である。
【図６】ラベルが長い文字列の場合の可視化表示例である。
【図７】大きさの異なるラベルの表示例である。
【図８】非軸対称ポテンシャルを利用した、各ノードのポテンシャルの模式図である。
【図９】大きさの異なるラベルの表示例である。
【図１０】非軸対称ポテンシャルを利用した、各ノードのポテンシャルの模式図（その２）である。
【図１１】図６の各ラベルの配置を変えることで重なりを無くした様子を示している。
【図１２】（ａ）は式（１４）の右辺第１項成分、（ｂ）は式（１４）の右辺第２項成分、（ｃ）は（ａ）と（ｂ）の和を示したものである。
【図１３】グラフ可視化座標計算装置１による処理の流れを示すフローチャートである。
【図１４】（ａ）はラベル形状が三角形の場合、（ｂ）はラベル形状が五角形の場合、（ｃ）はラベル形状が六角形の場合、（ｄ）はラベル形状が自由形状の場合、をそれぞれ示している。
【図１５Ａ】ラベルのサイズおよびエッジに関する情報の一覧表である。
【図１５Ｂ】ＦＲ法による可視化の計算結果を示す図である。
【図１５Ｃ】第１実施形態の手法による可視化の計算結果を示す図である。
【図１６】第１実施形態のポテンシャル場の考え方と第２実施形態のポテンシャル場の考え方との相違を示す図である。
【図１７】スケーリングによる重なりの回避手法の一例を示す図である。
【図１８Ａ】ＦＲ法による可視化の計算結果を示す図である。
【図１８Ｂ】第１実施形態の手法（式（５ａ）；α＝２の場合）による可視化の計算結果を示す図である。
【図１８Ｃ】第２実施形態の手法（式（１５）；α＝２、ｑｉ＝１の場合）による可視化の計算結果を示す図である。
【図１８Ｄ】第２実施形態の手法（式（１５）；α＝２、ｑｉ＝Ｅｉの場合）による可視化の計算結果を示す図である。
【図１９】可視化結果の一例を示した図である。
【符号の説明】
【０１０３】
１      グラフ可視化座標計算装置
２      演算手段
３      入力手段
４      記憶手段
５      出力手段
６      バスライン
２１    初期配置部
２２    加速度導出部（ポテンシャル勾配導出部）
２３    座標更新処理部
２４    エネルギー導出部
２５    計算終了条件判定部
２６    データ制御部
【図１】
0004939486.tif 000026
【図２】
0004939486.tif 000027
【図３】
0004939486.tif 000028
【図４】
0004939486.tif 000029
【図５】
0004939486.tif 000030
【図６】
0004939486.tif 000031
【図７】
0004939486.tif 000032
【図８】
0004939486.tif 000033
【図９】
0004939486.tif 000034
【図１０】
0004939486.tif 000035
【図１１】
0004939486.tif 000036
【図１２】
0004939486.tif 000037
【図１３】
0004939486.tif 000038
【図１４】
0004939486.tif 000039
【図１５Ａ】
0004939486.tif 000040
【図１５Ｂ】
0004939486.tif 000041
【図１５Ｃ】
0004939486.tif 000042
【図１６】
0004939486.tif 000043
【図１７】
0004939486.tif 000044
【図１８Ａ】
0004939486.tif 000045
【図１８Ｂ】
0004939486.tif 000046
【図１８Ｃ】
0004939486.tif 000047
【図１８Ｄ】
0004939486.tif 000048
【図１９】
0004939486.tif 000049