(57)【特許請求の範囲】
【請求項１】
描画エリア内にグラフの頂点を配置する頂点配置手段と、
前記頂点を包含するパワーセルを含んだパワー図を設定するパワー図設定手段と、
前記頂点に対して前記パワーセルの重心方向に向けて働く重心力を算出する重心力算出手段と、
前記頂点に対して関連性のある他の頂点の方向に向けて働く引力を算出する引力算出手段と、
前記重心力算出手段によって算出された前記重心力と、前記引力算出手段によって算出された前記引力とに基づいて、前記描画エリア内に配置された前記頂点を移動させる移動手段と、
前記パワー図における重み値を変更して前記パワーセルの大きさを調整しながら、前記頂点の移動が収束するまで前記パワー図設定手段、前記重心力算出手段、前記引力算出手段、および前記移動手段による処理を繰り返す繰り返し手段とを備えることを特徴とする情報処理装置。
【請求項２】
請求項１に記載の情報処理装置において、
前記繰り返し手段は、高い重み値のパワーセルを縮小するように、前記重み値を変更することを特徴とする情報処理装置。
【請求項３】
請求項１または２に記載の情報処理装置において、
前記頂点を包含する円形のターゲット領域を設定するターゲット領域設定手段をさらに備え、
前記重心力算出手段は、前記ターゲット領域の半径に基づいて前記重心力を算出し、
前記引力算出手段は、前記ターゲット領域の半径に基づいて前記引力を算出することを特徴とする情報処理装置。
【請求項４】
請求項１〜３のいずれか一項に記載の情報処理装置において、
前記頂点が、前記頂点を配置するために設定された境界ポリゴンの外に位置しているときには、前記頂点を前記境界ポリゴンの重心方向に引っ張る重力を算出する重力算出手段をさらに備え、
前記移動手段は、前記重力算出手段によって算出された前記重力に基づいて、前記描画エリア内に配置された前記頂点を移動させることを特徴とする情報処理装置。
【請求項５】
描画エリア内にグラフの頂点を配置する頂点配置手順と、
前記頂点を包含するパワーセルを含んだパワー図を設定するパワー図設定手順と、
前記頂点に対して前記パワーセルの重心方向に向けて働く重心力を算出する重心力算出手順と、
前記頂点に対して関連性のある他の頂点の方向に向けて働く引力を算出する引力算出手順と、
前記重心力算出手順で算出した前記重心力と、前記引力算出手順で算出した前記引力とに基づいて、前記描画エリア内に配置された前記頂点を移動させる移動手順と、
前記パワー図における重み値を変更して前記パワーセルの大きさを調整しながら、前記頂点の移動が収束するまで前記パワー図設定手順、前記重心力算出手順、前記引力算出手順、および前記移動手順による処理を繰り返す繰り返し手順とをコンピュータに実行させるための情報処理方法。
【請求項６】
請求項５に記載の情報処理方法において、
前記繰り返し手順は、高い重み値のパワーセルを縮小するように、前記重み値を変更することを特徴とする情報処理方法。
【請求項７】
請求項５または６に記載の情報処理方法において、
前記頂点を包含する円形のターゲット領域を設定するターゲット領域設定手順をさらに有し、
前記重心力算出手順は、前記ターゲット領域の半径に基づいて前記重心力を算出し、
前記引力算出手順は、前記ターゲット領域の半径に基づいて前記引力を算出することを特徴とする情報処理方法。
【請求項８】
請求項５〜７のいずれか一項に記載の情報処理方法において、
前記頂点が、前記頂点を配置するために設定された境界ポリゴンの外に位置しているときには、前記頂点を前記境界ポリゴンの重心方向に引っ張る重力を算出する重力算出手順をさらに有し、
前記移動手順は、前記重力算出手順で算出した前記重力に基づいて、前記描画エリア内に配置された前記頂点を移動させることを特徴とする情報処理方法。
【請求項９】
描画エリア内にグラフの頂点を配置する頂点配置手順と、
前記頂点を包含するパワーセルを含んだパワー図を設定するパワー図設定手順と、
前記頂点に対して前記パワーセルの重心方向に向けて働く重心力を算出する重心力算出手順と、
前記頂点に対して関連性のある他の頂点の方向に向けて働く引力を算出する引力算出手順と、
前記重心力算出手順で算出した前記重心力と、前記引力算出手順で算出した前記引力とに基づいて、前記描画エリア内に配置された前記頂点を移動させる移動手順と、
前記パワー図における重み値を変更して前記パワーセルの大きさを調整しながら、前記頂点の移動が収束するまで前記パワー図設定手順、前記重心力算出手順、前記引力算出手順、および前記移動手順による処理を繰り返す繰り返し手順とをコンピュータに実行させるための情報処理プログラム。
【請求項１０】
請求項９に記載の情報処理プログラムにおいて、
前記繰り返し手順は、高い重み値のパワーセルを縮小するように、前記重み値を変更することを特徴とする情報処理プログラム。
【請求項１１】
請求項９または１０に記載の情報処理プログラムにおいて、
前記頂点を包含する円形のターゲット領域を設定するターゲット領域設定手順をさらに有し、
前記重心力算出手順は、前記ターゲット領域の半径に基づいて前記重心力を算出し、
前記引力算出手順は、前記ターゲット領域の半径に基づいて前記引力を算出することを特徴とする情報処理プログラム。
【請求項１２】
請求項９〜１１のいずれか一項に記載の情報処理プログラムにおいて、
前記頂点が、前記頂点を配置するために設定された境界ポリゴンの外に位置しているときには、前記頂点を前記境界ポリゴンの重心方向に引っ張る重力を算出する重力算出手順をさらに有し、
前記移動手順は、前記重力算出手順で算出した前記重力に基づいて、前記描画エリア内に配置された前記頂点を移動させることを特徴とする情報処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、情報処理方法、および情報処理プログラムに関する。
【背景技術】
【０００２】
次のような情報処理装置が知られている。この情報処理装置では、描画エリア内にデータ値に応じた点を配置し、データの関連性を示す情報に基づいて、各点間に働く引力と斥力を算出し、各点を包含するボロノイ領域を設定し、ボロノイ領域の重心点を特定し、ボロノイ領域内の点に働く重心点に向けた引力を算出し、描画エリア内に配置された点を、各点間に働く引力と斥力、および重心点に向けた引力に基づいて移動させることにより、移動後の点の分布状況によりデータの関連性を視覚的に表すことを可能としている（例えば、特許文献１）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１８−１５６２３４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
従来の情報処理装置では、描画エリア内に配置された点を、各点間に働く引力と斥力、および重心点に向けた引力に基づいて移動させることにより、移動後の点の分布状況によりデータの関連性を視覚的に把握できるようにした。しかしながら、従来の装置では、関連する点が近づいた結果、多くの点がまとまって集中してしまう可能性があり、そのような場合に各点の分布状況が把握しにくくなる可能性があった。
【課題を解決するための手段】
【０００５】
本発明による情報処理装置は、描画エリア内にグラフの頂点を配置する頂点配置手段と、頂点を包含するパワーセルを含んだパワー図を設定するパワー図設定手段と、頂点に対してパワーセルの重心方向に向けて働く重心力を算出する重心力算出手段と、頂点に対して関連性のある他の頂点の方向に向けて働く引力を算出する引力算出手段と、重心力算出手段によって算出された重心力と、引力算出手段によって算出された引力とに基づいて、描画エリア内に配置された頂点を移動させる移動手段と、パワー図における重み値を変更してパワーセルの大きさを調整しながら、頂点の移動が収束するまでパワー図設定手段、重心力算出手段、引力算出手段、および移動手段による処理を繰り返す繰り返し手段とを備えることを特徴とする。
本発明による情報処理方法は、描画エリア内にグラフの頂点を配置する頂点配置手順と、頂点を包含するパワーセルを含んだパワー図を設定するパワー図設定手順と、頂点に対してパワーセルの重心方向に向けて働く重心力を算出する重心力算出手順と、頂点に対して関連性のある他の頂点の方向に向けて働く引力を算出する引力算出手順と、重心力算出手順で算出した重心力と、引力算出手順で算出した引力とに基づいて、描画エリア内に配置された頂点を移動させる移動手順と、パワー図における重み値を変更してパワーセルの大きさを調整しながら、頂点の移動が収束するまでパワー図設定手順、重心力算出手順、引力算出手順、および移動手順による処理を繰り返す繰り返し手順とをコンピュータに実行させることを特徴とする。
本発明による情報処理プログラムは、描画エリア内にグラフの頂点を配置する頂点配置手順と、頂点を包含するパワーセルを含んだパワー図を設定するパワー図設定手順と、頂点に対してパワーセルの重心方向に向けて働く重心力を算出する重心力算出手順と、頂点に対して関連性のある他の頂点の方向に向けて働く引力を算出する引力算出手順と、重心力算出手順で算出した重心力と、引力算出手順で算出した引力とに基づいて、描画エリア内に配置された頂点を移動させる移動手順と、パワー図における重み値を変更してパワーセルの大きさを調整しながら、頂点の移動が収束するまでパワー図設定手順、重心力算出手順、引力算出手順、および移動手順による処理を繰り返す繰り返し手順とをコンピュータに実行させることを特徴とする。
【発明の効果】
【０００６】
本発明によれば、グラフの頂点を包含するパワー図を設定してパワーセルの重心に向けた重心力と隣接する頂点の引力とに基づいて頂点を移動させるようにした。これによって、パワー図の重心方向に頂点を分散させつつ、関連性のある頂点を引力で引き付けることができるため、頂点が一か所にまとまってしまうことを防いで視認性を向上させることができる。
【図面の簡単な説明】
【０００７】
【図１】情報処理装置１００の一実施の形態の構成を示すブロック図である。
【図２】頂点に加わる力を模式的に示した図である。
【図３】頂点の周囲を模式的に示した図である。
【図４】第１レベルのグラフの一例を示した図である。
【図５】第２レベルのグラフの一例を示した図である。
【図６】第３レベルのグラフの一例を示した図である。
【図７】第４レベルのグラフの一例を示した図である。
【図８】第４レベルのグラフに階層エッジハンドリングを行った結果を示す図である。
【図９】情報処理装置１００で実行される処理の流れを示すフローチャート図である。
【発明を実施するための形態】
【０００８】
図１は、本実施の形態における情報処理装置１００の一実施の形態の構成を示すブロック図である。情報処理装置１００としては、例えば、サーバ装置やパソコン等の情報処理装置が用いられ、図１は、情報処理装置１００としてサーバ装置を用いた場合の一実施の形態の構成を示している。情報処理装置１００は、制御装置１０１と、記録装置１０２とを備えている。
【０００９】
制御装置１０１は、ＣＰＵ、メモリ、およびその他の周辺回路によって構成され、情報処理装置１００の全体を制御する。なお、制御装置１０１を構成するメモリは、例えばＳＤＲＡＭ等の揮発性のメモリである。このメモリは、ＣＰＵがプログラム実行時にプログラムを展開するためのワークメモリや、データを一時的に記録するためのバッファメモリとして使用される。
【００１０】
記録装置１０２は、情報処理装置１００が蓄える種々のデータや、制御装置１０１が実行するためのプログラムのデータ等を記録するための記録装置であり、例えばＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）やＳＳＤ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅ）等が用いられる。なお、記録装置１０２に記録されるプログラムのデータは、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどの記録媒体に記録されて提供されたり、ネットワークを介して提供され、操作者が取得したプログラムのデータを記録装置１０２にインストールすることによって、制御装置１０１がプログラムを実行できるようになる。
【００１１】
本実施の形態における情報処理装置１００では、記録装置１０２には、グラフＧ＝（Ｖ，Ｅ）のデータが記録されており、これが後述する処理の入力データとして用いられる。本実施の形態では、頂点の集合Ｖは、複数の頂点ｖが要素として属しており,例えば、Ｖ＝｛ｖ１,ｖ２,ｖ３,・・・, ｖＮ｝のように、集合Ｖにはｖ１からｖＮのＮ個の頂点が含まれる。エッジの集合Ｅは、各頂点の関連性を示すデータが属しており、この各頂点の関連性を示すデータに基づいて関連性のある頂点同士を直線で結ぶことができる。例えば頂点ｖと頂点ｕに関連性がある場合、頂点ｖと頂点ｕはエッジを構成する。
【００１２】
制御装置１０１は、上述したグラフＧ＝（Ｖ，Ｅ）を入力データとして、あらかじめ設定されているｘｙ座標系の描画エリア内に、集合Ｖ内に含まれている各頂点ｖをプロットして配置する。このときの配置方法は限定されないが、本実施の形態では、制御装置１０１は、各頂点ｖを描画エリア内にランダムに配置する。これによって、描画エリア内に頂点の集合Ｖに属する頂点ｖがプロットされる。
【００１３】
本実施の形態では、制御装置１０１は、描画エリア上に公知のパワー図（Ｐｏｗｅｒ  ｄｉａｇｒａｍ）を作成し、頂点ｖに対して作用する力を考慮して関連性が高い頂点ｖ同士が描画エリア内で接近して集まるように、初期配置した各頂点ｖを移動させる。以下、本実施の形態における処理の流れについて説明する。
【００１４】
なお、パワー図は公知の技術であるため、各頂点ｖに対してパワー図を設定するための処理の詳細な説明は省略するが、本実施の形態では、頂点ｖのパワー図の重みをｗｖとし、該重みの集合をＷとする。そして、重みｗｖ＝０にセットして、重みｗｖが与えられた頂点ｖの位置でパワー図ＰＤを計算して境界ポリゴンβにクリップする。なお、境界ポリゴンβは、グラフＧの配置に使用可能な面積を定義するために境界を示したポリゴンである。
【００１５】
本実施の形態では、形状と大きさが異なる境界ポリゴンβ内にグラフＧをレイアウトしようとするので、以下に説明する各頂点ｖにかかるすべての力は、境界ポリゴンβの範囲Ａβから直接影響を受ける。各頂点ｖにかかる力の相互作用を計算するために、本実施の形態では、まず各頂点ｖに対して頂点ｖを包含する円形のターゲット領域Ａｖを次式（１）のように定義する。
【数１】
0006913327.tif 000002
【００１６】
式（１）において、Ｓ（ｖ）は、各頂点ｖに割り当てられたターゲット領域Ａｖの相対面積を調整するためのスケーリング係数であって、Ｓ（ｖ）を要素とするスケーリングファクターの集合をＳとする。本実施の形態ではスケーリング係数Ｓ（ｖ）は、パワー図におけるセル（パワーセル）ＰＤｖがパワー図ＰＤでカバーすべきエリアを決定するために各頂点ｖに対して指定されており、各頂点ｖとその隣接セルの間の分離量に影響する。Ｓ（ｖ）を１とすると、すべての頂点Ｖの間隔が同じになるレイアウトをつくろうとし、特定の頂点に高い値を割り与えると、高い値を割り当てた頂点と、それに隣接する頂点の間の距離が増えることになる。Ｓ（ｖ）の値は、レイアウトの境界が静的なときは一度計算すればよく、レイアウトが動的に変化する場合は繰り返し計算される。
【００１７】
本実施の形態ではターゲット領域Ａｖを円形としたので、制御装置１０１は、ターゲット領域Ａｖの半径ｒｖを次式（２）、（３）により計算することができる。
【数２】
0006913327.tif 000003
【数３】
0006913327.tif 000004
なお、Ａｖとｒｖの値は、反復計算の間にｖに異なるスケーリング係数Ｓ（ｖ）が指定されなければ、常に一定に保たれる。
【００１８】
次に、制御装置１０１は、各頂点に対して働く力を計算する。制御装置１０１は、各頂点を、それぞれに対応するパワーセルＰＤｖの重心またはその近くであって、かつグラフ内の隣接する頂点の近くに配置する。各頂点には、図２に示すように、パワーセルＰＤｖの重心に引き付けられる力、すなわちパワーセルの重心に向かって働く重心力Ｆｃと、隣接する頂点との間で引き付けあう力、すなわち隣接する頂点に向かって働く引力Ｆａがかかる。頂点ｖとエッジを構成する頂点ｕに対してこれらの力がかかる場合に、次式（４）の関係式が成立すれば、頂点ｕにかかる力はつりあって平衡が保たれることになる。
【数４】
0006913327.tif 000005
式（４）において、ＮｕはＶの部分集合であって、頂点ｕに隣接する頂点の集合を表す。また、ｅｗ（ｕ，ｖ）は、頂点ｕと頂点ｖとの間を結ぶエッジの重みを表す。グラフが重みづけされていない場合、ｅｗ（ｕ，ｖ）＝１となる。
【００１９】
制御装置１０１は、次式（５）により頂点ｕに作用する重心力Ｆｃ（ｕ）を算出する。なお、次式（５）において、ｕは頂点ｕの（ｘ，ｙ）の座標ベクトルを示し、ＰＤｕは頂点ｕに対して設定されたパワーセルの重心の座標を示している。
【数５】
0006913327.tif 000006
【００２０】
式（５）において、パワー図ＰＤにセルがない場合を除き、もしｕ＝ＰＤｕであればＦｃ（ｕ）＝０となり、もしｕがＰＤｕから距離ｒｕの位置にある場合は、Ｆｃ（ｕ）＝１となる。レイアウトはシステム内の合計力を最小化しようとするため、これはｕがＰＤｕに理想的に置かれることを意味する。
【００２１】
制御装置１０１は、次式（６）により頂点ｕに作用する引力Ｆａ（ｕ，ｖ）を算出する。
【数６】
0006913327.tif 000007
引力Ｆａは、パワー図にパワーセルがある場合のみ適用され、ｕが境界から出ないように作用する。式（６）では、||ｕ−ｖ||＝ｒｕ＋ｒｖのとき、すなわち頂点ｕと頂点ｖが理想的な距離で離れているときには、引力Ｆａは０となる。また、||ｕ−ｖ||＝２ｒｕ＋ｒｖのとき、または頂点ｕが理想的な場所から距離ｒｕだけ離れている場合は、引力Ｆａは１となる。
【００２２】
次式（７）の特性により、頂点ｕが頂点ｖから２ｒｕ＋ｒｖの距離より遠くに位置する場合、頂点ｕは引力Ｆａ（ｕ，ｖ）によって支配され、そうでない場合は重心力Ｆｃ（ｕ）によって支配される。つまり、頂点ｕは頂点ｖから遠くに位置する時には頂点ｖに向かってより強く引っ張られ、ｕがｖに十分に近い場合は、対応するパワーセルの重心に向かってより強く引っ張られる。
【数７】
0006913327.tif 000008
式（７）により、重心力Ｆｃ（ｕ）と引力Ｆａ（ｕ，ｖ）の大きさは、ｆ（||ＰＤｕ−ｕ||，ｒｕ，１）とｆ（||ｕ−ｖ||−（ｒｕ＋ｒｖ），ｒｕ，２）で表される。
【００２３】
このように、引力Ｆａ（ｕ，ｖ）と重心力Ｆｃ（ｕ）に基づいて各頂点を移動させることにより、各頂点をパワーセルの重心方向に分散させつつ、関連度が高い点同士はＦａ（ｕ，ｖ）により近づくことになる。本実施の形態では、制御装置１０１は、移動後の各頂点に対して上記処理を繰り返し行い、各頂点の移動が収束するまで各頂点の移動を繰り返す。このように、上記処理を繰り返していくと、関連度が高い頂点は、描画エリア内で徐々にまとまっていくため、描画エリア内における頂点の分布により、各データの関連性を視覚的に把握できるようになる。本発明の適用例としては、ＳＮＳに投稿されたメッセージデータやチャットで交わされてメッセージデータを対象とし、各データを頂点として扱うことにより、メッセージ内容の関連性を可視化することが可能となる。
【００２４】
なお、上述した式（６）を用いた引力Ｆａ（ｕ，ｖ）の算出結果は、頂点ｕと頂点ｖの隣接の数が少ない場合には問題ないが、頂点ｕか頂点ｖの隣接の数が増加するにつれて乱雑になり、これは階層的にグラフをレイアウトする際に、上位の階層が乱雑になると、下位のグラフを視覚化するために必要なスペースを欠くため問題が生じる可能性がある。以下、この乱雑さを避けるための方法について説明する。
【００２５】
頂点ｕを含む頂点ｖのすべての隣接する頂点は、図３に示すように、頂点ｖを中心とする半径ｒｖの円であるＣｖ（ｒｖ）の周りの円形リング内に置かれると仮定する。この円形リングのエリアは、次式（８）に示すような頂点ｖに隣接するすべてのエリアの合計エリアに等しい。
【数８】
0006913327.tif 000009
なお、図３では、引力Ｆａは、関連する他の頂点、すなわちエッジを構成する他の頂点ｕを円Ｃｖ（ｒｖ）の周囲に引き付ける。このとき、頂点ｕは、ある円Ｃｖ（ｒｖ＋（２ｉ−１）ｒｕ）から距離ｒｕ以内のＣｖ（ｒｖ）を囲む円形リング内のどこかに配置できると仮定することができる。
【００２６】
このような理想的な設定の仮定のもとで、引力Ｆａのスケーリングバージョンを計算すると次式（９）のようになる。
【数９】
0006913327.tif 000010
式（９）による計算結果は、頂点ｕが頂点ｖに及ぼすであろう力の大きさを示している。この式（９）を用いることによって、制御装置１０１は、乱雑さを回避した引力Ｆ´ａ（ｕ，ｖ）を算出することができるため、本実施の形態では、上記の式（６）に代えて式（９）を引力Ｆａ（ｕ，ｖ）の算出のために用いることとする。
【００２７】
式（９）を計算するための式を次式（１０）〜（１５）に示す。もし、上述した円形リング領域ＡＮｖが頂点ｕと同じターゲット領域をもつ頂点のみで占められている場合、円形リング領域ＡＮｖにフィットするｕと同じ頂点の数Ｍ（ｕ，ｖ）は、次式（１０）により算出される。
【数１０】
0006913327.tif 000011
【００２８】
ここでＭ（ｕ，ｖ）が存在すると仮定すると、図３に示したように、これらは円形リング領域の中の一連のｎ同心円Ｃｖ（ｒｖ＋ｒｕ），Ｃｖ（ｒｖ＋３ｒｕ），・・・・，Ｃｖ（ｒｖ＋（２ｎ−１）ｒｕ）の境界に置かれる。半径rの円の周囲は２πｒで、円Ｃｕ（ｒｕ）の直径は２ｒｕとすると、円Ｃｖ（ｒｖ＋（２ｉ−１）ｒｕ）の境界に置かれる頂点の数ｍ（ｕ，ｖ，ｉ）は次式（１１）により推定される。
【数１１】
0006913327.tif 000012
【００２９】
そして、すべてのＭ（ｕ，ｖ）を置くのに必要な円の数ｎは、Ｍ（ｕ，ｖ）が各円のすべての頂点の合計にほぼ等しいと仮定すると、次式（１２）に示す計算式によって推測できる。
【数１２】
0006913327.tif 000013
【００３０】
そして、各円におけるＦａ（ｕ，ｖ）の値としてｆａ（ｕ，ｖ，ｉ）を推定する。ここでは、頂点は必ずしも円Ｃｖ（ｒｖ＋（２ｉ−１）ｒｕ）の境界に正確に置かれるとはかぎらないため、境界から２ｒｕ以内、すなわち||ｕ−ｖ||はｒｖ＋（２ｉ＋１）ｒｕであるとして、これを式（６）に代入することにより、次式（１３）により推定する。
【数１３】
0006913327.tif 000014
【００３１】
この場合、予想される力の大きさｆ´ａ（ｕ，ｖ）は次式（１４）により算出される。
【数１４】
0006913327.tif 000015
【００３２】
最後に、次式（１５）に示すように、これらの合計を該当するパワー合計式によって置き換える。
【数１５】
0006913327.tif 000016
【００３３】
なお、境界形状間のランダムな初期化または遷移により、頂点ｕが境界ポリゴンの外に出てしまう可能性がある。この場合、その頂点ｕは他の境界ポリゴンに隣接していなければ、描画領域の外側に出てしまう可能性がある。本実施の形態では、このような問題を解消するために、追加の力として各頂点を境界ポリゴンの重心方向に引っ張る重力Ｆｇを定義し、これを頂点ｕに適用することで、頂点ｕが境界ポリゴンの内側に位置するように境界ポリゴンに引き付ける。頂点ｕにかかる重力Ｆｇ（ｕ）は次式（１６）のように定義される。
【数１６】
0006913327.tif 000017
式（１６）において、Ｂは境界ポリゴンβの重心である。この式（１６）により、頂点ｕは、同じ座標を共有する２つ以上の頂点を避けるために、Ｂに向かって距離ｒｕまで引き付けられる。本実施の形態では、制御装置１０１は、頂点ｕが境界ポリゴンの外に位置しているときは式（１６）を用いて頂点ｕに境界ポリゴンβの重心方向への力をかけ、頂点ｕを境界ポリゴンβ内へ移動させる。そして、制御装置１０１は、頂点ｕが境界ポリゴンβ内に位置しているときは、式（５）と（９）により算出される力を頂点ｕにかけて、頂点ｕを移動させる。
【００３４】
また、本実施の形態では、頂点ｕの移動が限りなく続くのを防ぐために、摩擦係数μを導入し、頂点ｕの位置が、μｒｕより大きくない限り変化しないように制御する。ここで、μの値は、例えば０．０１とする。
【００３５】
次に、パワー図における重み係数の調整処理について説明する。パワー図では、特定のジェネレータポイントに重み係数を指定でき、これは直接、パワーセルのサイズに影響する。グラフレイアウトの頂点間のスペースを操作するのに、この重み係数を使用することができる。上記では、各頂点ｕには関連する重みｗｕがあり、これはゼロに初期化された後に、パワーセルＰＤｕがターゲット領域Ａｕに到達するように繰り返し調整される。
【００３６】
上述した処理の中では、各ｗｕはゼロまたは負の値をとることのみ許される。言い換えると、すべての頂点は可能な限り高い重み値ではじまり、結果として低い重み値のパワーセルを理想的なサイズに拡大するために、その目標に届くまで、高い重み値のセルを縮小するように変換すると、グラフを拡張するという点において高速化が可能となる。本実施の形態では、この高い重み値のセルを縮小するように変換していくアプローチを軽量化アプローチと呼ぶ。
【００３７】
高度に接続された頂点は、隣接する頂点からの引力の作用により、小さいパワーセルをとる傾向にあり、接続された頂点ではそのパワーセルがスペースの大部分を占めることになる。また、拡大しているパワーセルは、同時に、隣接する頂点が及ぼす力の効果に抵抗しながらスペースを作るために、隣接するパワーセルを押しのける必要がある。このため、上述した軽量化アプローチを使うと、低い重み値の頂点に、パワーセルを拡大させるためのスペースを速く作ることができる。この方法では、すべての頂点はできるだけ最大の重み値ではじまるので、重み値の高い頂点ｕに隣接するパワーセルは、重み係数ｗｕの突然の増加によって消失するリスクが低くなり、ほとんどの場合で重み値を減らすことができる。
【００３８】
本実施の形態では、制御装置１０１は、次式（１７）を用いた重み係数ｗｕの算出を繰り返すことにより、重み値の調整を行う。制御装置１０１は、重み値を変更した後は、上述したパワー図の作成から処理を繰り返し、結果が収束するまで一連の処理を繰り返す。
【数１７】
0006913327.tif 000018
式（１７）において、Ａ（ＰＤｕ）はパワーセルＰＤｕの現在のエリアである。また、αは学習率を表す。学習率αは０．０〜１．０の範囲をとるパラメータで、式（１７）を用いた反復処理の中で各パワーセルのターゲットに到達しようとするスピードをコントロールするために用いられる。学習率αの値が低いと収束が遅く、学習率αの値が高いとレイアウトが不安定になる可能性があるため、例えばα＝０．１２５とする。また、λは減衰率を示す変数であって、０．０〜１．０の値をとる。本実施の形態では、例えばλ＝０．９とする。
【００３９】
次に、本実施の形態における階層的なグラフの生成方法について説明する。本実施の形態では、グラフのノード（頂点）で利用可能な情報に基づいて、階層的またはマルチレベルのレイアウトをつくることができる。最初のステップは階層グラフの作成である。ここでは、頂点の集合Ｖとエッジの集合Ｅで構成されたグラフＧ（Ｖ，Ｅ）から階層グラフＧＨ（ＶＨ，ＥＨ）を作成する方法について説明する。グラフＧ（Ｖ，Ｅ）から階層グラフＧＨ（ＶＨ，ＥＨ）を作るために、まず集合Ｖを複数の集合（サブセット）Ｖ１，・・・，Ｖｎに分ける。また、集合Ｅも複数の集合（サブセット）Ｅ１，・・・，Ｅｎに分ける。Ｅ１に含まれる全てのエッジは、集合Ｖ１に含まれる頂点だけを繋いでいる。集合Ｅを複数の集合に分けたときに、Ｅ１，・・・，Ｅｎのいずれにも入っていないエッジがある場合は、そのエッジを以下に説明する階層グラフのエッジの集合ＥＨを作るために使用する。なお、集合Ｅを複数の集合に分けたときに、Ｅ１，・・・，Ｅｎのいずれにも入っていないエッジとは、例えば、集合Ｖ１に含まれる頂点と集合Ｖ２に含まれる頂点とを繋いでいるエッジなどを意味する。その後、サブグラフＧ１（Ｖ１，Ｅ１），・・・，Ｇｎ（Ｖｎ，Ｅｎ）を作成し、頂点ｖ１Ｈ，・・・，ｖｎＨをＶＨに入れる。なお、頂点ｖ１Ｈは階層グラフの中でサブグラフＧ１（Ｖ１，Ｅ１）を指している。
【００４０】
そして、頂点の集合ＶＨに属する各頂点ｖｉＨが、サブグラフＧｉに対応する第１レベルのグラフＧＨ（ＶＨ，ＥＨ）を作成する。第１レベルのグラフＧＨ（ＶＨ，ＥＨ）は、例えば、図４に示すような粗いグラフとなる。この第１レベルのグラフでは、各エッジ（ｖｉＨ，ｖｊＨ）は、頂点の集合Ｖｉを頂点の集合Ｖｊに接続するエッジがあるかどうかを表し、頂点の集合Ｖｉを頂点の集合Ｖｊの間のエッジには重みが割り当てられる。なお、頂点の集合Ｖｉと頂点の集合Ｖｊの間を接続するエッジが複数存在する可能性があり、その場合、頂点の集合Ｖｉと頂点の集合Ｖｊの間を接続するエッジの重みは、複数のエッジの重みの合計値となる。例えば、ソーシャルネットワークでは、各Ｇｉは特定の国ｉに属する個人のサブセットを含むことができ、国全体はｖｉＨによって表され、各エッジ（ｖｉＨ，ｖｊＨ）は、国ｉと国ｊの間に個人の関係があるかどうかを示すことができる。
【００４１】
このプロセスは、例えば図５に示す第２レベルのグラフ、図６に示す第３レベルのグラフ、図７に示す第４レベルのグラフのように、必要に応じて階層の追加レベルごとに各サブグラフＧｉで繰り返すことができる。本実施の形態では、図４に示した第１レベルのグラフが最も粗く、第２レベル、第３レベル、第４レベルの順に細かいグラフになっている。
【００４２】
上述した階層グラフＧＨ（ＶＨ，ＥＨ）は、最も粗いレベルから最も細かいレベルに配置される。まず、各ｖｉＨには、次式（１８）に示すスケーリング係数ｓ（ｖｉＨ）が割り当てられる。
【数１８】
0006913327.tif 000019
【００４３】
次に、図４に示したような階層の最上位レベルのＧＨ（ＶＨ，ＥＨ）に対して、上述したパワー図を作成するための処理を実行するが、このとき、各頂点ｖＨとエッジ（ｖｉＨ，ｖｊＨ）を描画するかわりに、各サブレイアウトの境界としてパワーセルＰＤｖＨを使用しながら各頂点ｖＨに関連付けられたサブグラフＧｉ（Ｖｉ，Ｅｉ）で処理を繰り返す。
【００４４】
一度、階層の最下位レベルに達すると、図７に示したように、元のグラフＧ（Ｖ，Ｅ）の頂点とエッジは最下位レベルサブグラフの境界の中で計算された位置に従って描画スペースに配置される。このとき、階層全体のより良い視覚化の為に、各レベルでパワー図を計算する前に、値が０．０から１．０の範囲をとるスケーリング係数ＳＨによって、各サブグラフの境界を重心に関してダウンスケールするようにしてもよい。また、必要に応じてサブグラフの境界の形を変更してもよい。サブグラフの境界を指定するためには、例えば、各頂点ｖＨに通常の境界ポリゴンを指定し、その重心がパワーセルＰＤｖＨに置かれるように変換する。パワーセルＰＤｖＨの重心から側面までが最小になるように半径をスケーリングすることにより、サブグラフの境界がパワーセルＰＤｖＨの中におさまるように変更することができる。
【００４５】
制御装置１０１は、公知の階層エッジバンドリングを採用してエッジをバンドルすることにより、例えば図８に示すように、グラフ内の階層レベル全体の関係の視覚化を容易にすることができる。これは定義済みの階層に基づき、各エッジ（ｕ，ｖ）のコントロールポイントを定義することで構成され、Ｂ−ｓｐｌｉｎｅをｕからｖにトレースするのに使われる。階層全体で同じ経路となるエッジは共通したコントロールポイントを持っているため一緒にバンドルされることになる。ここでのバンドリングの量は、エッジの曖昧さを避けるために、バンドル強化パラメータを用いて調整される。バンドル強化パラメータは、例えば０．９８のような値が設定され、これはユーザーが必要に応じて調整できるようにしてもよい。
【００４６】
例えば、各エッジ（ｕ，ｖ）は、まず頂点ｕからＬＣＡ（ｕ，ｖ）、次に頂点ｖに至る複数の階層レベルにわたるパスを見つける。ここでＬＣＡ（ｕ，ｖ）は頂点ｕと頂点ｖの最も低い共通した祖先である。エンドポイントである頂点ｕと頂点ｖを除いて、（ｕ，ｖ）のコントロールポイントは、このパスに沿って見つけられたすべての階層ノードのパワーセルの重心として定義される。
【００４７】
公知の階層エッジバンドリングのように、ＬＣＡへの乱れと不必要な湾曲を防ぐために、実際のコントロールポイントのセットからＬＣＡを削除する。また、頂点ｕとその階層の兄弟からレイアウトのいくつかの部分まで複数の曲線がトレースされるため、頂点ｕの親ノードｕ´と頂点ｖの親ノードｖ´の重心の近くでクラッタリングが発生する傾向がある。これに対処するために、本実施の形態では、コントロールポイントにＰＤｕ´とＰＤｖ´を含めるのではなく、代わりに頂点ｕの兄弟に到達する頂点ｖのすべての階層兄弟の平均座標を使用する。
【００４８】
そして、制御装置１０１は、スプラインが計算されたコントロールポイントをトレースする。オリジナルのエッジバンドリングアプローチが３次のＢスプライン曲線では採用されているが、本実施の形態によれば、階層関係が二次のものよりも良く視覚化されていることがわかった。なお、コントロールポイントのリストの中でポイントが繰り返されると、クラッタリングがおこる可能性がある。これは、一つまたはそれ以上の階層ノードが、単一の子孫を持つことが原因になり得る。このような場合、リストから繰り返しポイントを削除し、重複の数同様にそれぞれ重みを割り当てる。曲線は代わりに、二次の非一様有理Ｂスプライン（ＮＵＲＢＳ：Ｎｏｎ−Ｕｎｉｆｏｒｍ  Ｒａｔｉｏｎａｌ  Ｂ−Ｓｐｌｉｎｅ）としてトレースされる。
【００４９】
本実施の形態では、制御装置１０１は、頂点が階層の最上位にある同じノードの子孫である場合には同じ色で描画することにより視認性を向上させる。このとき、同じノードの子孫に対して、違う色のスキームを使用することもできる。オプションで、階層関係をよりよく視覚化するために、階層の最下位レベルのポリゴンを描写するようにしてもよい。エッジは、もし、階層の違うブランチの頂点を接続する場合はグレーでレンダリングされ、もし両方の頂点が階層の底の同じサブグラフにある場合、エンドポイントと同じ色でレンダリングされる。階層的エッジバンドリングのように、このアプローチで描かれるエッジは、その長さに従って不透明にスケーリングされるため、短いエッジは長いエッジより高い不透明度で描かれることになる。
【００５０】
図９は、本実施の形態における情報処理装置１００で実行される処理の流れを示すフローチャートである。図９に示す処理は、情報処理装置１００の操作者によってプログラムの実行が指示されると起動するプログラムとして、制御装置１０１によって実行される。
【００５１】
ステップＳ１０において、制御装置１０１は、上述したように、あらかじめ設定されているｘｙ座標系の描画エリア内に、集合Ｖ内に含まれている各頂点ｖをプロットして配置する。その後、ステップＳ２０へ進む。
【００５２】
ステップＳ２０では、制御装置１０１は、式（１）により各頂点ｖに対してターゲット領域Ａｖを設定し、式（２）、（３）を用いてターゲット領域Ａｖの半径ｒｖを算出する。その後、ステップＳ３０へ進む。
【００５３】
ステップＳ３０では、制御装置１０１は、上述したように、式（５）により頂点ｕに作用する重心力Ｆｃ（ｕ）を算出する。また、制御装置１０１は、式（９）により頂点ｕに作用する引力Ｆ´ａ（ｕ，ｖ）を算出する。その後、ステップＳ４０へ進む。
【００５４】
ステップＳ４０では、制御装置１０１は、引力Ｆ´ａ（ｕ，ｖ）と重心力Ｆｃ（ｕ）に基づいて各頂点ｕを移動させる。なお、移動の過程で頂点が境界ポリゴンの外に位置してしまったときは、制御装置１０１は、上述した境界ポリゴンの重心方向に向けて働く重力を算出し、該重力に基づいて、描画エリア内に配置された頂点を移動させる。その後、ステップＳ５０へ進む。
【００５５】
ステップＳ５０では、制御装置１０１は、各頂点の移動が収束したか否かを判断する。本実施の形態では、制御装置１０１は、例えば、上述した摩擦係数μを考慮して、頂点ｕの位置が変化しなくなったときに、各頂点の移動が収束したと判断する。ステップＳ５０で否定判断した場合には、ステップＳ２０へ戻る。これに対して、ステップＳ５０で肯定判断した場合には、処理を終了する。
【００５６】
以上説明した本実施の形態によれば、以下のような作用効果を得ることができる。
（１）制御装置１０１は、描画エリア内にグラフの頂点を配置し、頂点を包含するパワーセルを含んだパワー図を設定し、頂点に対してパワーセルの重心方向に向けて働く重心力を算出し、頂点に対して関連する他の頂点の方向に向けて働く引力を算出し、重心力と引力とに基づいて、描画エリア内に配置された頂点を移動させるようにした。これによって、パワー図の重心方向に頂点を分散させつつ、関連性のある頂点を引力で引き付けることができるため、頂点が一か所にまとまってしまうことを防いで視認性を向上させることができる。
【００５７】
（２）制御装置１０１は、パワー図における重み値を変更してパワーセルの大きさを調整しながら、頂点の移動が収束するまでパワー図の設定、重心力の算出、引力の算出、および頂点の移動を繰り返すようにした。これによって、パワーセルの大きさが小さくなりすぎないように重み値を制御することができるため、頂点が一点に集中してしまうことを防いでグラフの視認性を向上させることができる。
【００５８】
（３）制御装置１０１は、繰り返し手段は、高い重み値のパワーセルを縮小するように、重み値を変更するようにした。これによって、低い重み値の頂点に、パワーセルを拡大させるためのスペースを作ることができる。また、すべての頂点はできるだけ最大の重み値ではじまるので、重み値の高い頂点に隣接するパワーセルは、重み値の突然の増加によって消失するリスクが低くなり、ほとんどの場合で重み値を減らすことができる。
【００５９】
（４）制御装置１０１は、頂点を包含する円形のターゲット領域を設定し、ターゲット領域の半径に基づいて重心力と引力を算出するようにした。これによって、各頂点に作用する力を精度高く算出することができる。
【００６０】
（５）制御装置１０１は、頂点が、頂点を配置するために設定された境界ポリゴンの外に位置しているときには、頂点を境界ポリゴンの重心方向に引っ張る重力を算出し、該重力に基づいて、描画エリア内に配置された頂点を移動させるようにした。これによって、頂点を移動させた結果、頂点が境界ポリゴンの外に出てしまった場合でも、頂点を境界ポリゴンの重心に向けて引き付けて境界ポリゴン内に位置させることができる。
【００６１】
―変形例―
なお、上述した実施の形態の情報処理装置１００は、以下のように変形することもできる。
（１）上述した実施の形態では、データを２次元の直交座標系で示す描画エリアにプロットして、引力Ｆ´ａ（ｕ，ｖ）と重心力Ｆｃ（ｕ）に基づいて各頂点ｕを描画エリア内で移動させる例について説明した。しかしながら、本発明は、データを３次元の座標空間上にプロットする場合にも適用可能である。また、本発明の適用範囲は、直交座標系に限定されず、極座標系や球面座標系などの他の座標系にも適用することができる。
【００６２】
なお、本発明の特徴的な機能を損なわない限り、本発明は、上述した実施の形態における構成に何ら限定されない。また、上述の実施の形態と複数の変形例を組み合わせた構成としてもよい。
【符号の説明】
【００６３】
１００  情報処理装置
１０１  制御装置
１０２  記録装置
【要約】
【課題】データの関連性を視覚的に表すこと。
【解決手段】
情報処理装置１００は、描画エリア内にグラフの頂点を配置する頂点配置手段と、頂点を包含するパワーセルを含んだパワー図を設定するパワー図設定手段と、頂点に対してパワーセルの重心方向に向けて働く重心力を算出する重心力算出手段と、頂点に対して関連性のある他の頂点の方向に向けて働く引力を算出する引力算出手段と、重心力算出手段によって算出された重心力と、引力算出手段によって算出された引力とに基づいて、描画エリア内に配置された頂点を移動させる移動手段とを備える。
【選択図】図１【図１】
0006913327.tif 000020
【図２】
0006913327.tif 000021
【図３】
0006913327.tif 000022
【図４】
0006913327.tif 000023
【図５】
0006913327.tif 000024
【図６】
0006913327.tif 000025
【図７】
0006913327.tif 000026
【図８】
0006913327.tif 000027
【図９】
0006913327.tif 000028