動的グラフ用アニメーション・プランニング方法及び装置
【課題】動的グラフ用アニメーション・プランニング方法及び装置を提供する。
【解決手段】動的グラフ内の変更ノードと既存ノードとの間の関係に従って前記変更ノードをアトミック・パーティション１〜４にグループ化するステップと、前記アトミック・パーティション間のクラスタリング距離に従って、アトミック・パーティション・クラスタ又はアトミック・パーティションあるいはその両方を要素として含むランニング・リストが生成されるように、前記アトミック・パーティションをクラスタリングするステップと、を含む。更に、前記動的グラフ内のノードと、各変更接続が直接接続されるノードを指すキー・ノードとの間の相関に従って前記動的グラフ内のノードを様々なノード・グループにグループ化するステップと、前記接続変更に起因するノード移動のアニメーション・デモンストレーションを前記ノード・グループによってプランニングするステップと、を含む。
【解決手段】動的グラフ内の変更ノードと既存ノードとの間の関係に従って前記変更ノードをアトミック・パーティション１〜４にグループ化するステップと、前記アトミック・パーティション間のクラスタリング距離に従って、アトミック・パーティション・クラスタ又はアトミック・パーティションあるいはその両方を要素として含むランニング・リストが生成されるように、前記アトミック・パーティションをクラスタリングするステップと、を含む。更に、前記動的グラフ内のノードと、各変更接続が直接接続されるノードを指すキー・ノードとの間の相関に従って前記動的グラフ内のノードを様々なノード・グループにグループ化するステップと、前記接続変更に起因するノード移動のアニメーション・デモンストレーションを前記ノード・グループによってプランニングするステップと、を含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は動的グラフ・ビジュアライゼーションに関するものであり、より詳細には、動的グラフ用アニメーション・プランニング方法及び装置に関するものである。
【背景技術】
【０００２】
グラフ・ビジュアライゼーションとも呼ばれるグラフ描画は、トポロジ及びジオメトリを使用することによってグラフの２次元（２Ｄ）又は３次元（３Ｄ）表現を取得し表示する処理を指し、ＶＬＳＩ回路設計、ソーシャル・ネットワーク分析、カートロジー（cartology）、バイオ・インフォーマティックス等、様々な分野で広く応用されている。グラフ・ビジュアライゼーションでは、ドットを使用してグラフ内の頂点が表現され、ドット同士を接続する線を使用して頂点間の辺（edge）が示され、矢印を使用して有向辺が示される。１つの同じグラフでも、その頂点及び辺の可視化構成が異なれば、グラフの理解性、有用性、生産コスト、美的特性等に影響が及ぶ。グラフ・ビジュアライゼーションの主な目的は、適切なレイアウト・アルゴリズムを使用することにより、（例えば辺の交差を可能な限り少なくし、様々な辺の長さをほぼ同一とすること等により）理解性及び美的特性に優れるグラフの２次元又は３次元表現を取得し提示することである。
【０００３】
動的グラフとは、経時的に変化するグラフであって、それ自体の要素（ノード又は辺）が動的に追加及び削除され、それらの属性も動的に変更され得るグラフを指す。動的グラフ・ビジュアライゼーションの主な目的は、動的グラフの時間次元に沿った変化パターンを開示し、グラフ又はネットワークの発展プロセスを明示することである。例えば、動的グラフ・ビジュアライゼーションは、社会学者によるソーシャル・ネットワークの発展プロセスの解明や、ビジネス・インテリジェンス（ＢＩ）・アナリストによる様々な企業の潜在顧客の発掘、生物学者によるタンパク変異の発見等に役立つ可能性がある。
【０００４】
動的グラフ・ビジュアライゼーションには多くの課題が存在する。最も重要な課題の１つは、様々な時間フレームにおけるグラフ変化をユーザのメンタル・マップが維持されるように円滑に遷移させることである。この問題を解決するために、アニメーション技術が広く使用されている。アニメーションは、人々の関心を引くことができ、物事の変更部分と不変部分とを表現することができる。図１は、あるコミュニティの年単位のソーシャル・ネットワーク・グラフのアニメーション変化をデモンストレーションした一例を示し、各フレームは、このコミュニティの２００４〜２００８年の各年におけるソーシャル・ネットワーク・グラフを示す。ソーシャル・ネットワーク・グラフ内の各ノードは、コミュニティを形成する個人を示し、ノード間の各辺は、それらの個人間の関係を示す。これらの各フレームを連続的に再生することによりソーシャル・ネットワーク・グラフ内のノード及び辺の数年間の増減変化が表示され、それ故コミュニティの年単位の変化パターンが直感的に開示される。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、動的グラフ・ビジュアライゼーションの分野の既存のアニメーション技術は、いくつかの欠点を有する。例えば、複数のノードを追加又は削除することによってグラフが変更される場合、既存のアニメーション技術ではそれらのすべてのノードが同時に追加又は削除される。これによって時間コストは最小となるが、変更数が多すぎる故に動的グラフの変更時に発生する重要な構造上の更新をハイライトすることができず、その結果ユーザの視覚的な混乱が生じ、アニメーションの可読性が低下することになる。一方、ノード変更が１つずつ実行される場合も、多数の変更が存在すれば時間がかかりすぎてしまう。したがって、当業界ではアニメーション速度と可読性との所望のバランスをとるアニメーション・プランニング方法が必要とされている。
【０００６】
また、動的ソーシャル・ネットワークのようなネットワークでは、関係（ソーシャル・ネットワークを表す動的グラフでは辺として表現される）の変更はごく一般的なことである。例えば、このような関係変更には個人間の関連付けの追加又は削除が含まれる。関係変更はソーシャル・ネットワーク・グラフのトポロジ構造を大きく変化させる可能性があるので、ソーシャル・ネットワークに対する関係変更の影響を分析し完全に提示することは困難である。従来のアニメーション技術において、関係変更は通常以下の２つのステップでデモンストレーションされる。第１ステップでは、各辺がそれぞれの始点ノードからターゲット・ノードに伸ばされ、各ノードが接続される。本ステップは、グラフ・トポロジの変化を示すのに使用される。換言すると、本ステップによってグラフ・ビジュアライゼーションに変更が生じた理由が描写される。第２ステップでは、新しい辺によって接続されたすべてのノード及び関係するノードが、それぞれの新しい位置に一緒にドラッグされる。これにより、グラフ・ビジュアライゼーションの変更現象又は変更結果が示される。この２ステップ・モデルでは、変更理由と最終的な変更結果との間にギャップが存在する。異なるノード移動は通常異なる接続に起因するものであり、最終的な移動結果は複数の接続（理由）に起因する可能性があるので、このような従来のアニメーション技術では各ノード移動の主要理由を発見し表示することができない。ノード移動理由の発見及び可視化は、ソーシャル・ネットワーク関係分析で非常に重要となる。したがって、当業界では、ソーシャル・ネットワーク・グラフのような動的グラフの関係変更とノード移動との間の内部関係が表示可能であるとともに可読性に優れたアニメーション・プランニング方法が必要とされている。
【課題を解決するための手段】
【０００７】
本発明の一態様によれば、動的グラフ用アニメーション・プランニング方法であって、動的グラフ内のノード変更が適用されたことに応答して、前記変更ノードと既存ノードとの間の関係に従って前記変更ノードをアトミック・パーティション（atomic partition）にグループ化するステップと、前記アトミック・パーティション間のクラスタリング距離に従って、前記動的グラフ内のノード変更のアニメーション・デモンストレーションをプランニングするランニング・リスト（running list）であって、アトミック・パーティション・クラスタ又はアトミック・パーティションあるいはその両方を要素として含むランニング・リストが生成されるように、前記アトミック・パーティションをクラスタリングするステップと、を含む方法が提供される。
【０００８】
本発明の別の態様によれば、動的グラフ用アニメーション・プランニング装置であって、動的グラフ内のノード変更が適用されたことに応答して、前記変更ノードと既存ノードとの間の関係に従って前記変更ノードをアトミック・パーティションにグループ化するアトミック・パーティショニング・モジュール（atomic partitioningmodule）と、前記アトミック・パーティション間のクラスタリング距離に従って、前記動的グラフ内のノード変更のアニメーション・デモンストレーションをプランニングするランニング・リストであって、アトミック・パーティション・クラスタ又はアトミック・パーティションあるいはその両方を要素として含むランニング・リストが生成されるように、前記アトミック・パーティションをクラスタリングするクラスタリング・モジュールと、を備える装置が提供される。
【０００９】
本発明のまた別の態様によれば、動的グラフ用アニメーション・プランニング方法であって、動的グラフ内の接続変更が適用されたことに応答して、前記動的グラフ内のノードと、各変更接続が直接接続されるノードを指すキー・ノードとの間の相関に従って前記動的グラフ内のノードを様々なノード・グループにグループ化するステップと、前記接続変更に起因するノード移動のアニメーション・デモンストレーションを前記ノード・グループによってプランニングするステップと、を含む方法が提供される。
【００１０】
本発明の他の態様によれば、動的グラフ用アニメーション・プランニング装置であって、動的グラフ内の接続変更が適用されたことに応答して、前記動的グラフ内のノードと、各変更接続（change connection）が直接接続されるノードを指すキー・ノードとの間の相関に従って前記動的グラフ内のノードを様々なノード・グループにグループ化するグループ化モジュールと、前記接続変更に起因するノード移動のアニメーション・デモンストレーションを前記ノード・グループによってプランニングするプランニング・モジュールと、を備える装置が提供される。
【００１１】
本発明の技術的解決を用いると、動的グラフのノード変更又は接続変更に関するマルチ・ステージ・アニメーション・デモンストレーションのプランニング、ならびに動的グラフ内の変更要素間の相関、及びそれらの変更要素と既存の要素との間の相関を開示するアニメーション・デモンストレーション効果を得ることが可能となり、それ故、可読性の改善及びアニメーション・デモンストレーション速度の高速化が実現される。
【００１２】
添付の特許請求範囲には、本発明の特徴と見なされる発明の特徴が記載されている。しかしながら、本発明ならびに本発明の好ましいモード、目的、特徴、及び利点は、例示的な諸実施形態に関する以下の詳細な説明を添付図面と併せて読めばより良く理解されるだろう。
【図面の簡単な説明】
【００１３】
【図１】あるコミュニティの年単位のソーシャル・ネットワーク・グラフのアニメーション変化をデモンストレーションした一例を示す図である。
【図２】本発明の一実施形態に係る動的グラフ用アニメーション・プランニング方法の全体の流れを示す概略図である。
【図３】本発明の一実施形態に従って変更ノードをアトミック・パーティションにグループ化する方法の一例を示す図である。
【図４】本発明の一実施形態に係るクラスタリング・プロセスによって生成されるアニメーション・プランニング・モデルの一例を示す図である。
【図５】本発明の別の実施形態に係る動的グラフ用アニメーション・プランニング方法の全体の流れを示す図である。
【図６】動的グラフの接続変更の一例を示す図である。
【図７】すべてのグループのノード移動が並行してアニメーション・デモンストレーションされる場合を示す図である。
【図８】異なるグループのノード移動が１つずつアニメーション・デモンストレーションされる場合を示す図である。
【図９】ノード位置の重複が検出されたときに、次のグループのノード移動のアニメーション・デモンストレーションが直ちに開始される場合を示す図である。
【図１０】ある力場内の初期位置Ａからターゲット位置Ｂに移動するノードの移動経路を示す概略図である。
【発明を実施するための形態】
【００１４】
以下、添付図面を参照して本発明の諸実施形態について説明する。以下の説明では、本発明の十分な理解が得られるように様々な詳細が説明される。しかしながら、本発明は、これらの詳細の一部が与えられない場合にも実現され得ることが当業者には理解されるだろう。また、本発明は、本明細書に記載される特定の実施形態に限定されるものではないことも理解していただきたい。そうではなく、本発明は、それらが異なる実施形態に関与するものであるか否かに関わらず、後述する各特徴及び要素の任意の組合せを使用して実施されることが企図される。したがって、後述する各態様、特徴、実施形態、及び利点は、特許請求範囲に記載の各請求項に特に明記しない限り、各請求項の要素となるものでもそれらを限定するものでもなく、単なる例示にすぎない。
【００１５】
本発明の一態様では、動的グラフ内のノード変更（即ち、ノードの増加又は減少）に関するアニメーション・デモンストレーションのプランニングに使用される動的グラフ用アニメーション・プランニング方法が提供される。本方法では、動的グラフ内の変更ノードとそれらのノードの重要度との間の相関に従って各ノードが様々な次数でクラスタリングされ、このクラスタリングに従って、他の変更ノードとの相関が小さい変更ノード又はより重要度が高いノードは独立して又はより小さいクラスタでアニメーション・デモンストレーションされ、互いの相関が大きい変更ノードは一緒にアニメーション・デモンストレーションされるものとしてクラスタリングされるように、ノード変更のアニメーション・デモンストレーションがプランニングされる。したがって、可読性が良く時間コストも低いアニメーション・デモンストレーション効果が達成される。
【００１６】
次に図２を参照すると、本発明の一実施形態に係る動的グラフ用アニメーション・プランニング方法の全体の流れが概略的に示されている。図示のとおり、本方法は以下の主なステップ、即ち、アトミック・パーティショニングを実行するステップと、アトミック・パーティションをクラスタリングするステップと、任意選択で動的ソートを実行するステップと、を含む。以下、本発明の方法の各ステップについて詳細に説明する。
【００１７】
ステップ１：アトミック・パーティショニング
本ステップは、変更ノードが動的グラフに適用されたことに応答して、グラフ内の変更ノードと既存ノードとの間の関係に従って、変更ノードをいくつかのアトミック・パーティションにグループ化する。当業界では周知のとおり、動的グラフに対するノード変更の適用とは、動的グラフのトポロジ構造に変化が生じるようにノード変更を動的グラフのトポロジに適用し、その後、採用された適切なレイアウト・アルゴリズムを適用してノード変更後の動的グラフのレイアウト、即ち各ノードのターゲット位置を取得することを指す。
【００１８】
既存ノードと直接接続されるすべての新規追加ノードは、同じアトミック・パーティションにグループ化することができる。このようなグループ化方法が図２に示される。ここでは、１０個の新規追加ノードが４つの既存ノードと直接接続され、それ故、これらの１０個の新規追加ノードはそれぞれ４つのアトミック・パーティションにグループ化され得る。
【００１９】
いくつかの新規追加ノードが既存ノードと直接接続されない比較的複雑な条件では、まず各新規追加ノードのキー・ノードが発見され、同じキー・ノードを有する新規追加ノードが同じアトミック・パーティションにグループ化される。本方法の実行プロセスは、以下のように説明することができる。
【００２０】
入力：
（１）新規追加ノードｎｉ；
（２）動的グラフＧ
出力：
（１）アトミック・パーティション集合Ｃ
説明：
１．各ｎｉについて、グラフＧに対して幅優先探索（Breadth-First-Search）を実行し、ｎｉとノード｛ｍｉ｜ｍｉ∈Ｇ｝とを結合するすべての最短経路を記録し、経路集合をＳとする。
２．Ｓ内の各最短経路について、当該経路内の各辺の重みを単純に加算することにより、それぞれの重みを計算する。
３．ｎｉとｍｋを結合する経路を仮定して、すべての最短経路の中から重みが最も大きい経路を選択する。
４．ノードｍｋを新規追加ノードｎｉのキー・ノードとする。
５．同じキー・ノードｍｋを有するすべてのｎｉをアトミック・パーティションｃｉとしてグループ化し、Ｃに入れる。
６．Ｃを返す。
【００２１】
図３は、変更ノードをアトミック・パーティションにグループ化する方法の実行プロセスの一例を示す。図示のとおり、５、６、７は既存ノードであり、１、２、３、４は新規追加ノードである。
【００２２】
新規追加ノード１から既存ノードまでの最短経路の集合は、Ｓ１＝｛（１，２，５），（１，３，５），（１，３，６）｝、各経路の重みは、Ｗ１＝｛４，４，５｝（最大の重みは５）であり、したがって新規追加ノード１のキー・ノードは、Ｐ１＝６となる。
【００２３】
新規追加ノード２から既存ノードまでの最短経路の集合は、Ｓ＝｛（２，５）｝、経路の重みは、Ｗ２＝｛２｝（最大の重みは２）であり、したがって新規追加ノード２のキー・ノードは、Ｐ２＝５となる。
【００２４】
新規追加ノード３から既存ノードまでの最短経路の集合は、Ｓ＝｛（３，５），（３，６）｝、経路の重みは、Ｗ３＝｛１，２｝（最大の重みは２）であり、したがって新規追加ノード３のキー・ノードは、Ｐ３＝６となる。
【００２５】
新規追加ノード４から既存ノードまでの最短経路の集合は、Ｓ＝｛（４，７）｝、経路の重みは、Ｗ４＝｛１｝（最大の重みは１）であり、したがって新規追加ノード４のキー・ノードは、Ｐ４＝７となる。
【００２６】
それ故、新規追加ノード１及び３は、１つの同じアトミック・パーティションにグループ化されるが、新規追加ノード２は、別のアトミック・パーティションに、新規追加ノード４は、また別のアトミック・パーティションにグループ化される。
【００２７】
ステップ２：アトミック・パーティションのクラスタリング
本ステップは、各アトミック・パーティションとそれぞれの重要度との間の相関に従ってアトミック・パーティションをいくつかのクラスタにクラスタリングし、それらのクラスタから構成される適切なランニング・リストを取得し、それによってアニメーション速度と情報の可読性とのバランスをとるものである。クラスタリング・プロセス中に、アトミック・パーティション、中間クラスタ、及び最終クラスタから構成される階層構造が形成され、この階層構造は、アニメーション・プランニング・モデルと呼ばれることがある。アトミック・パーティションを階層的にクラスタリングする上で最も重要なことは、任意の２つのアトミック・パーティション又はクラスタ間のクラスタ距離を計算することである。クラスタ距離の計算では多くの方法が使用され得る。１つの単純な手法は、ユークリッド幾何学距離公式を使用してアトミック・パーティション又はクラスタ間のスクリーン距離を計算し、スクリーン距離をクラスタ距離とするものである。スクリーン距離は、例えば２つのアトミック・パーティション又はクラスタに含まれるノード間の最短経路の長さであることも、２つのアトミック・パーティション又はクラスタに含まれるノード間の経路の平均長さであることもある。一方、本発明は、以下の要因のうちの１つ又は複数を考慮することによってクラスタ距離を計算する新しい方法を提案する。
【００２８】
１．アトミック・パーティション又はクラスタの重要度。重要なアトミック・パーティションは、他のアトミック・パーティションと共にクラスタリングされずに独立して表示されることが望ましく、また、あるクラスタの重要度がアトミック・パーティションのクラスタリング・プロセス中に一定の次数まで累積された場合は、それ以降当該クラスタが他のアトミック・パーティション又はクラスタと共にクラスタリングされることはなくなる。
【００２９】
２．２つのアトミック・パーティション又はクラスタ間のトポロジ距離。２つのアトミック・パーティション又はクラスタ同士を接続する辺が多数存在する場合、それらの２つのアトミック・パーティション又はクラスタ同士の結び付きは通常強くなり、また、各アトミック・パーティション又はクラスタに対する変更は通常、それらのアトミック・パーティション又はクラスタが一緒にクラスタリングしやすくなるように関係付けられる。ここで、２つのアトミック・パーティション又はクラスタ間のトポロジ距離は、それらの間の共通辺の数として定義することができる。
【００３０】
３．２つのアトミック・パーティション又はクラスタ間のジオメトリ距離。上述のとおり、ジオメトリ距離は、２つのアトミック・パーティション又はクラスタ間のスクリーン距離を指し、通常は２つのアトミック・パーティション又はクラスタ内のノード間の最短経路の長さ、又は２つのアトミック・パーティション又はクラスタ内のノード間の経路の平均長さで示される。
【００３１】
上記を考慮すると、任意の２つのアトミック・パーティション又はクラスタ間のクラスタリング距離は、次式を使用して計算することができる。
【数１】
【００３２】
上式で、ｉ及びｊは、２つのアトミック・パーティション又はクラスタを示し、
ｄｉｓｔ（ｉ，ｊ）は、２つのアトミック・パーティション又はクラスタ間のクラスタリング距離を示し、
ｄは、ｉとｊの間のジオメトリ距離を示し、次式が得られる。
【数２】
【００３３】
上式で、ｅｉｊはｉとｊを結合する辺の数であり、｜ｉ｜はｉ内のノード数、｜ｊ｜はｊ内のノード数を示す。
ａ＝（０，１）は、０〜１の範囲の重みパラメータを指し、関連要因の必要とされる重みに従って指定することができる。
ｃは、ｉとｊの組合せの重要度を示し、式：ｃ＝（｜ｉ｜ｃｉ＋｜ｊ｜ｃｊ）／（｜ｉ｜＋｜ｊ｜）を使用して計算される。ここで、ｃｉ及びｃｊは、それぞれｉ及びｊの重要度を示し、これらの重要度は、次式を使用して計算することができる。
【数３】
【００３４】
即ち、ｃｉは、ｉ内のノードの重要度の合計である。上式は更に、ノードｎの重要度の計算方法も提案する。上式で、Ｃ（ｎ）はノードｎの近接中心性（closeness centrality）、Ｂ（ｎ）はノードｎの媒介中心性（between centrality）、βは重みパラメータである。実際には、ノードの重要度は当業界で周知の多くの方法を使用して計算することができる。例えば、ノードの次数中心性（degree centrality）や固有ベクトル中心性（eigenvector centrality）等も考慮することができる。
【００３５】
上記では、アトミック・パーティション又はクラスタ間のクラスタリング距離の例示的な計算方法を提示したが、以下では、クラスタリング距離を使用してアトミック・パーティションに対する階層クラスタリングを実行し、それによってランニング・リストを取得する方法の実行プロセスについて説明する。
【００３６】
入力：
１）アトミック・パーティション集合Ｃ
２）重要度閾値λ１
３）動的グラフＧ
出力：
１）ランニング・リストＬ
説明：
１．初期集合Ｓ＝Ｃにセットする。
２．Ｓ内の各要素ｉの重要度ｃｉを計算する。ｉがアトミック・パーティションである場合には、その重要度はすべての収容ノードの重要度の合計となるが、ｉがクラスタである場合には、その重要度はクラスタに含まれるアトミック・パーティション又はクラスタの重要度の合計となる。ノードの重要度計算では複数の方法が使用され得る。例えば、ノードの重要度は、ノードの次数中心性、近接中心性、媒介中心性、及び固有ベクトル中心性のうちの任意の１つ又はそれらの組合せを使用して計算することができる。
３．Ｓ内の各ｉについて、ｃｉ≧λ１である場合は、ｉをＬに入れる。ここで、λ１は重要度閾値であり、λ１の値は、関連要因の必要とされる重みに従って設定することができる。
４．Ｓ内の２つの要素ｉ及びｊ毎に、上述の方法を使用してｄｉｓｔ（ｉ，ｊ）が計算される。
ａ）クラスタｉ及びｊをクラスタＭとして、ｉとｊの間のクラスタリング距離が平均距離閾値λ２未満である場合は、ｉ及びｊをＳから削除し、ＭをＳに追加する。
ｂ）ｉとＳ内の他の任意の要素との間のクラスタ距離が平均距離閾値λ２以上である場合は、ｉをＬに入れる。
５．ステップ２に進んで、Ｓ内のすべての要素間のクラスタリング距離が平均距離閾値λ２以上となるまで新しいクラスタリング・ラウンドを開始し、Ｓ内のすべての要素をＬに入れる。
６．Ｌを返す。
【００３７】
上記の平均距離閾値λ２は、次式によって計算することができる。
λ２＝ｍａｘ（Ｄ（ｉ，ｊ））／（ｃｏｕｎｔ−１）
上式で、ｍａｘ（Ｄ（ｉ，ｊ））はＳ内の既存要素間の最大クラスタリング距離、ｃｏｕｎｔはＳ内の既存要素数である。
【００３８】
上記のクラスタリング・プロセスによってアニメーション・プランニング・モデルが生成される。図４は、このようなクラスタリング・プロセスによって生成されるアニメーション・プランニング・モデルの一例を示す。図示のとおり、このモデルは階層的であり、最下層はアトミック・パーティション１〜１８である。クラスタリング・プロセスの第１ラウンドにおいて、アトミック・パーティション１〜４、５‐６、７‐８、９‐１０、１３〜１５、１６〜１８は、それぞれクラスタＡ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆにクラスタリングされ、アトミック・パーティション１１及び１２は、それらの重要度が重要度閾値を超える、又は他の任意の要素との間のクラスタリング距離がいずれも平均距離閾値以上となる故に、ランニング・リストに転送される。クラスタリング・プロセスの第２ラウンドにおいて、クラスタＡ‐Ｂ、Ｅ‐Ｆは更に、クラスタＧ、Ｈにクラスタリングされ、クラスタＣ及びＤは、それらの重要度が重要度閾値を超える、又は他の任意の要素との間のクラスタリング距離がいずれも平均距離閾値以上となる故に、ランニング・リストに転送される。クラスタリング・プロセスの第３ラウンドにおいて、クラスタＧ及びＨは、それらの重要度が重要度閾値を超える、又は他の任意の要素との間のクラスタリング距離がいずれも平均距離閾値以上となる故に、ランニング・リストに転送される。したがって、取得されるランニング・リストは、図４の破線で接続される要素、即ちクラスタＧ、Ｃ、Ｄ、アトミック・パーティション１１、１２、及びクラスタＨを含むことになる。このようにして、アニメーション・デモンストレーションは、ランニング・リストの内容に従って実行されるようにプランニングされ、それ故、可読性とデモンストレーション速度とのバランスが良いアニメーション・デモンストレーション効果が得られる。
【００３９】
ステップ３：動的ソート
本ステップは任意選択であり、ランニング・リスト内の要素（クラスタ又はアトミック・パーティション）のアニメーション・デモンストレーション順序を決定する。人間の視覚的な平滑追跡能力は非対称的であり、通常は縦方向の平滑追跡能力よりも横方向の平滑追跡能力の方が優れており、上方向の平滑追跡能力よりも下方向の平滑追跡能力の方が優れている。これに基づき、動的ソートの目的は、横方向の移動ならびに下方向の移動を最大化すること、即ち、ランニング・リスト内のクラスタ又はアトミック・パーティションのスクリーン位置に従って、クラスタ又はアトミック・パーティションのデモンストレーションが左から右、上から下、右から左の順に可能な限り離れた位置まで実行されるように、アニメーション・デモンストレーションの順序を決定することである。また、重要度の高いクラスタ又はアトミック・パーティションほど高い優先度が割り当てられ、即ち、重要なクラスタ又はアトミック・パーティションから先にデモンストレーションされる。
【００４０】
具体的には、まずランニング・リスト内の要素の重要度［ａ１，ａ２，．．．，ａｉ，．．．，ａｎ］が取得される。クラスタ又はアトミック・パーティションの重要度は、上述の方法を使用して計算することができる。
【００４１】
次に、ランニング・リスト内の要素のスクリーン位置に従って、各要素の視覚的順序の重み（visual order weight）［ｂ１，ｂ２，．．．，ｂｉ，．．．，ｂｎ］が決定される。視覚的順序の重みは、上記のアニメーション・デモンストレーション順序に従って指定することができる。例えば、スクリーンの左側の要素がスクリーンの右側の要素よりも大きい視覚的順序の重みを有し、スクリーンの上部の要素がスクリーンの下部の要素よりも大きい視覚的順序の重みを有するように指定することができる。
【００４２】
次に、ランニング・リスト内の各要素のアニメーション・デモンストレーション順序の重み（animationdemonstration order weight）を次式を使用して計算することができ、ランニング・リスト内の各要素のアニメーション・デモンストレーション順序をアニメーション・デモンストレーション順序の重みに従って決定することができる。
【数４】
【００４３】
上式で、Ｏｉは、要素ｉのアニメーション・デモンストレーション順序の重みであり、αは、要素重要度の重みと視覚的順序の重みとの間の相対重みを表す係数である。
【００４４】
ステップ２で変更ノードがクラスタリングされ、適切なランニング・リストが生成され、任意選択のステップ３でクラスタ又はアトミック・パーティションのデモンストレーション順序が決定された後は、良好な可読性と高速なデモンストレーション速度を兼ね備えたアニメーション・デモンストレーションが得られるように、ノード変更のアニメーション・デモンストレーションをランニング・リスト及びデモンストレーション順序に従ってプランニングすることができる。
【００４５】
上記では、動的グラフにノードを追加する場合を一例として本発明の一実施形態に係る動的グラフ用アニメーション・プランニング方法について説明したが、上記の説明は単なる例示であり、本発明を限定するものではないことを指摘しておきたい。例えば、本発明は、動的グラフのノードを減少させるのにも適しており、また、動的グラフへのノード追加と動的グラフのノード減少を同時に実行するのにも適している。動的グラフのノードが減少される場合は、減少対象ノードの処理は追加対象ノードの処理と同じになる。即ち、各ノードがアトミック・パーティションにグループ化された後、当該アトミック・パーティションのクラスタリングが実行され、任意選択でクラスタ（場合によってはアトミック・パーティション）に対して動的ソートが実行され、その結果、各ノードのアニメーション・デモンストレーションがこれらのクラスタリング及び動的ソートに従ってプランニングされる。動的グラフのノード追加及びノード減少が同時に実行される場合は、追加対象ノードと減少対象ノードはそれぞれ個別に処理され得る。即ち、追加対象ノード及び減少対象ノードがそれぞれ個別にアトミック・パーティションにグループ化された後、それぞれのアトミック・パーティションのクラスタリングが実行され、任意選択でそれぞれのクラスタ（場合によってはアトミック・パーティション）に対して動的ソートが実行され、その結果、追加対象ノード及び減少対象ノードのアニメーション・デモンストレーションがそれぞれのクラスタリング及び動的ソートに従ってプランニングされる。好ましくは、アニメーション・デモンストレーションは、最初に減少対象ノードがデモンストレーションされ、次に動的グラフ内のオリジナル・ノードがターゲット位置に移動するようにデモンストレーションされ、最後に追加対象ノードがデモンストレーションされるようにプランニングされる。動的グラフ内のオリジナル・ノードのターゲット・ノードは、ノード変更が動的グラフに適用された後に、採用されたレイアウト・アルゴリズムを使用して計算することができる。
【００４６】
本発明は更に、上述した動的グラフ用アニメーション・プランニング方法を実行するのに使用され得る動的グラフ用アニメーション・プランニング装置も提供する。以下では動的グラフ用アニメーション・プランニング装置の概要のみを説明し、本装置の詳細情報に関しては上記の説明を参照していただきたい。
【００４７】
本発明の一実施形態によれば、動的グラフ用アニメーション・プランニング装置は、動的グラフ内の変更ノードと既存ノードとの間の関係に従って前記変更ノードをアトミック・パーティションにグループ化するアトミック・パーティショニング・モジュールと、前記アトミック・パーティション間のクラスタリング距離に従って、前記動的グラフ内の前記変更ノードのアニメーション・デモンストレーションをプランニングするランニング・リストであって、アトミック・パーティション・クラスタ又はアトミック・パーティションあるいはその両方を要素として含むランニング・リストが生成されるように、前記アトミック・パーティションをクラスタリングするクラスタリング・モジュールと、を備える。
【００４８】
本発明の一実施形態によれば、前記装置は、前記要素のスクリーン位置及び前記要素の重要度に従って、前記ランニング・リスト内の前記要素のアニメーション・デモンストレーション順序をソートするソート・モジュールを更に備える。
【００４９】
本発明の一実施形態によれば、前記アトミック・パーティショニング・モジュールは、各変更ノードについて、当該ノードが前記動的グラフ内の既存ノードと接続される最短経路内で重みが最も大きい経路を取得し、前記経路によって接続される前記動的グラフ内の前記既存ノードを前記変更ノードのキー・ノードとする手段と、同じキー・ノードを有する前記変更ノードを同じアトミック・パーティションにグループ化する手段と、を備える。
【００５０】
本発明の一実施形態によれば、前記クラスタリング・モジュールは、それ自体の重要度が重要度閾値に達した又はそれを超えた前記アトミック・パーティション又はクラスタを前記ランニング・リストに転送する手段と、それらの間の前記クラスタリング距離が距離閾値よりも小さい２つのアトミック・パーティション又はクラスタをクラスタリングする手段と、他の任意のアトミック・パーティション又はクラスタとの間の前記クラスタリング距離が前記距離閾値以上である前記アトミック・パーティション又はクラスタを前記ランニング・リストに転送する手段と、を備え、上記の処理は、すべての前記アトミック・パーティションがアトミック・パーティション又はクラスタの一部として前記ランニング・リストに入れられるまで繰り返し実行される。
【００５１】
本発明の一実施形態によれば、２つのアトミック・パーティション又はクラスタ間の前記クラスタリング距離は、前記２つのアトミック・パーティション又はクラスタ間のジオメトリ距離、前記２つのアトミック・パーティション又はクラスタ同士を接続する辺の数、及び前記２つのアトミック・パーティション又はクラスタの組合せの重要度、のうちの１つ又は複数に依存する。
【００５２】
本発明の一実施形態によれば、アトミック・パーティション又はクラスタの重要度は、前記アトミック・パーティション又はクラスタに含まれるノードの重要度に依存し、ノードの重要度は、前記ノードの次数中心性、近接中心性、媒介中心性、及び固有ベクトル中心性のうちの１つ又は複数に依存する。
【００５３】
本発明の別の態様によれば、動的グラフ用アニメーション・プランニング方法が提供される。前記方法は、動的グラフ内の接続（即ち辺）の変更に起因するノード移動のアニメーション・デモンストレーションをプランニングするのに使用される。前記方法では、ノードの接続変更がノード移動の内部理由とされ、様々なノードの位置変更を生じさせた内部理由、即ち、どの辺の変更がどのノードの位置変更原因であるかを突き止める試行がなされ、次に、それらの移動が主に同じ辺に起因するノードが一緒にグループ化され、最後に、同じグループ内のノードの移動が同時にアニメーション・デモンストレーションされ、異なるグループ内のノードの移動が異なる時点でアニメーション・デモンストレーションされるように、ノード移動のアニメーション・デモンストレーションがプランニングされる。
【００５４】
次に図５を参照すると、本発明の一実施形態に係る動的グラフ用アニメーション・プランニング方法の全体の流れが示されている。図示のとおり、本方法は、以下の主なステップ、即ち、接続変更を適用するステップと、ノード・グループ化を実行するステップと、マルチ・ステージ・アニメーション・プランニングを実行するステップと、を含む。以下、添付図面を参照して本発明の一実施形態に係る動的グラフ用アニメーション・プランニング方法について説明する。
【００５５】
ステップ１：接続変更の適用
本ステップでは、動的グラフのトポロジ構造を変化させる接続変更が動的グラフのトポロジに適用され、その後、採用された適切なレイアウト・アルゴリズムを適用して接続変更後の動的グラフのレイアウト、即ち各ノードのターゲット位置が取得される。図６は、動的グラフの接続変更の一例を示す。図示のとおり、２つの接続ｅＡＤ及びｅＢＣが動的グラフに追加され、これらの２つの接続によってすべてのノードの移動が発生する。本ステップは、ここでは詳細な説明は省略するが、http://sonia.stanford.edu等から入手可能な既存の動的グラフ・ビジュアライゼーション・システムによって達成することができる。
【００５６】
ステップ２：ノード・グループ化
本ステップでは、すべてのノードの接続変更を１つずつ検査してその接続変更がノード移動の主要理由となるかどうかが判定され、移動が同じ接続変更に起因するノード同士が一緒にグループ化される。従来技術の方法では、すべてのノードが一緒に移動するので、ノード移動を生じさせた主要理由を表示することができない。本発明の方法は、ノード移動を生じさせた主要理由に従って各ノードを様々なグループに分け、それらのグループに従って、可読性に優れたアニメーション・デモンストレーション効果が得られるようにノード移動のアニメーション・デモンストレーションをプランニングする。
【００５７】
本発明の一実施形態によれば、ノード・グループ化の詳細なステップは以下のとおりとなる。
【００５８】
１．各変更接続ｅｉｊについて、初期グループＧｉｊが作成され、ノードｉ及びｊがＧｉｊに入れられると同時にキー・ノード集合Ｋに入れられる。即ち、接続変更によって直接接続されるノードがキー・ノードと見なされ、これらのキー・ノードは、各キー・ノードが属する接続変更に従って様々なグループにグループ化される。例えば、図６の動的グラフの接続変更の場合、作成される初期グループは、ＧＡＤ＝｛Ａ，Ｄ｝、ＧＢＣ＝｛Ｂ，Ｃ｝であり、キー・ノード集合は、Ｋ＝｛Ａ，Ｄ，Ｂ，Ｃ｝である。２つ以上の変更接続が共通のノードを共有する場合は、初期グループを作成し、これらの変更接続によって直接接続されるすべてのノードを作成された初期グループに入れることができる。
【００５９】
２．すべての初期グループ内の各ノードｉについて、ｉとグラフ内の他の任意のノードとの間の相関が計算される。即ち、動的グラフ内の各非キー・ノードと各キー・ノードとの間の相関が計算される。ノードｉとｊの間の相関は、次式を使用して計算することができる。
【数５】
【００６０】
上式で、Ｒ（ｉ，ｊ）はノードｉとｊの間の相関、Ｐｉｊはノードｉからｊまでのすべての経路を含む経路集合、ｗｋｌはノードｋとｌの間の辺の重み、｜ｐ｜は経路ｐのトポロジ長、Ｅはグラフ内のすべての辺の集合、ｅｋｌはノードｋとｌの間の辺、ｅｉｊはノードｉとｊの間の辺である。即ち、上式によれば、２つのノード間の相関は、２つのノード間のすべての経路内の各辺の重みに依存する。
【００６１】
３．各非キー・ノードについて、非キー・ノードは、それ自体との相関が最も大きいキー・ノードを含むグループに入れられる。即ち、すべての非キー・ノードとすべてのキー・ノードとの間の相関を比較して各非キー・ノードとの相関が最も大きいキー・ノードが取得され、その後、各非キー・ノードは、それ自体との相関が最も大きいキー・ノードが存在するグループに入れられる。例えば、図６の各ノードＥ、Ｆ、Ｇ、Ｈ、Ｉについて、各ノードは、それらとキー・ノードＡ、Ｄ、Ｂ、Ｃとの間の計算される相関に従ってグループＧＡＤ又はＧＢＣに入れられる。
【００６２】
このようにして、動的グラフ内の各ノードは、接続変更が動的グラフに適用されたことに応答して、動的グラフ内の各ノードの移動を生じさせた主要理由に従って、即ち、各ノードの移動を生じさせた対応する主要接続変更に従って様々なグループにグループ化される。
【００６３】
ステップ３：マルチ・ステージ・アニメーション・プランニング
本ステップは、アニメーションのマルチ・ステージ・デモンストレーションをステップ２で取得されるノード・グループに従ってプランニングする。即ち、グラフ中の同じグループ内のノード移動は、一緒にアニメーション・デモンストレーションされるようにプランニングされ、異なるグループ内のノード移動は、ノード移動を生じさせた主要理由がより明確に表示されるよう異なる時点でアニメーション・デモンストレーションされるようにプランニングされる。異なるグループ内のノード移動のアニメーション・デモンストレーションの相対時間は、状況に応じて異なる可能性がある。図７は、すべてのグループのノード移動が並行してアニメーション・デモンストレーションされる場合、即ち、複数の接続変更に起因するすべてのグループのノード移動が同時にアニメーション・デモンストレーションされる場合を示す。これは事実上、すべてのノード移動を同時にデモンストレーションする従来技術のアプローチであり、この場合はグラフ変更の詳細が失われ、グラフ変更の因果関係を開示することができない。図８は、異なるグループ内のノード移動が１つずつアニメーション・デモンストレーションされる場合、即ち、前のグループのノード移動のアニメーション・デモンストレーションが完了した後に、次のグループのノード移動が直ちにアニメーション・デモンストレーションされる場合を示す。このようなアプローチでは、グラフ変更の詳細を維持し、グラフ変更の因果関係を開示することが可能となる。しかしながら、このアプローチの欠点は、ノード重複が発生する可能性があることである。即ち、あるグループのノードの移動がアニメーション・デモンストレーションされるときに、そのグループ内のいくつかのノードの位置が他のノードの位置と重複する可能性があり、それ故視覚的な混乱が生じる恐れがある。したがって、ノード移動をグループ単位でアニメーション・デモンストレーションすると同時にノード位置の重複を可能な限り回避することが必要とされる。
【００６４】
このため、本発明の他の実施形態は更に、各グループのノードの移動時に発生するノード位置の重複を検出するステップと、あるグループのノード位置の移動中に別のグループのノード位置との重複が発生したときに、当該別のグループのノードの移動が直ちに開始されるようにアニメーション・デモンストレーションをプランニングするステップと、を含む。図９は、ノード位置の重複が検出されたときに、次のグループのノードの移動が直ちに開始される場合を示す図である。当業者には理解されるように、動的グラフ内の各ノードの初期位置は既知であり、各ノードのターゲット位置も上述のステップで適切なレイアウト・アルゴリズムを適用することによって取得済みであり、また、選択された経路計算方法（例えば後述の力指向的（force-directed）アニメーション・モデル）に従って、各ノードの初期位置からターゲット位置までの移動経路を計算することができ、それ故各ノードが移動中に他のノードと重複するかどうか、重複する場合はいつ重複が起きるかを検出することが可能となる。
【００６５】
各グループのノード移動のアニメーション・デモンストレーションを具体的にプランニングするために、各ノードの初期位置とターゲット位置との間の移動経路を解決する必要がある。各ノードの初期位置とターゲット位置との間の移動経路は、様々な方法を使用して計算することができ、例えば、各ノードの移動経路は、単純に線形補間法を使用することにより、各ノードの初期位置及び最終位置に従って計算することができる。より良い方法は、各ノードの移動経路を力指向的アニメーション・モデルを使用して計算することである。力指向的アニメーション・モデルの目的は、力場の消費エネルギーが最小となる曲線経路を発見することである。具体的に、このモデルでは、ある接続によって結合される各ノード対についてばね力が指定され、互いに分離又は接続される各ノード対について普遍的な斥力（universal expulsionforce）が指定され、各ノードについて当該ノードが最終的にターゲット位置に移動し得ることを保証する可変外力Ｆが指定され、ノードの移動時に発生するエネルギー消費量｜｜Ｆ｜｜２が最小化される。このモデルは、関係制約最適化問題に変換することによって解くことができる。
【００６６】
例えば、ノードの移動経路は、以下の制約最適化方程式を作成することによって計算することができる。
【数６】
【００６７】
上式で、ｔ０はノード移動の開始時間、ｔ１はノード移動の終了時間、ｔは時間変数、Ｆｉはノードｉが受ける可変力、ｆｉｊはノードｉとｊの間のばね力、Ｅは動的グラフ内の辺の集合、ｐｉｊはｉ及びｊから成る任意のノード対間の斥力、ｍｉはノードｉの重要度、Ｘｉはノードｉの位置、ｋ１はばね力とノード移動速度との間の関係を表す係数、ｋ２は斥力とノード移動速度との間の関係を表す係数、Ｉｎｉｔｉａｌはノードｉの初期位置、Ｆｉｎａｌはノードｉの最終位置である。当業者には周知のとおり、上記の各方程式は、離散方程式を使用して上式中の偏微分方程式を置き換え、有限差分法及び逐次２次計画法（Sequential QuadraticProgramming）を使用して解くことができ、その結果ノードｉの移動経路が取得される。図１０は、上記の方法を使用して得られる力場内の初期位置Ａからターゲット位置Ｂまでのノードの移動経路を概略的に示す。各ノード・グループ内の各ノードの移動経路が上記の方法を使用して計算されると、各グループのノード移動のアニメーション・デモンストレーションを具体的にプランニングすることが可能となる。
【００６８】
上記では、本発明の一実施形態に係る動的グラフ用アニメーション・プランニング方法について説明したが、上記の説明は単なる例示であり、本発明を限定するものではないことを指摘しておきたい。例えば、上記では接続を追加する場合を一例として本発明について説明したが、本発明は、動的グラフの接続を減少させる場合にも適しており、また、動的グラフの接続追加及び接続減少を同時に実行する場合にも適している。これらの場合において、本発明の方法は、減少対象接続と追加対象接続とを均一に処理する。即ち、追加対象接続の場合であれ減少対象接続の場合であれ、各ノードは、それらの接続によって直接接続されるキー・ノード、及び他のノードとキー・ノードとの間の相関に従ってグループ化され、それらのノード・グループに従ってアニメーション・デモンストレーションがプランニングされる。
【００６９】
本発明は更に、上述した動的グラフ用アニメーション・プランニング方法を実行するのに使用され得る動的グラフ用アニメーション・プランニング装置も提供する。以下では動的グラフ用アニメーション・プランニング装置の概要のみを説明し、本装置の詳細情報に関しては上記の説明を参照していただきたい。
【００７０】
本発明の一実施形態によれば、動的グラフ用アニメーション・プランニング装置は、動的グラフ内の接続変更が適用されたことに応答して、前記動的グラフ内のノードと、前記動的グラフ内の各変更接続が直接接続されるノードを指すキー・ノードとの間の相関に従って前記動的グラフ内のノードを様々なノード・グループにグループ化するグループ化モジュールと、前記接続変更に起因するノード移動のアニメーション・デモンストレーションを前記ノード・グループによってプランニングするプランニング・モジュールと、を備える。
【００７１】
本発明の一実施形態によれば、前記グループ化モジュールは、前記動的グラフ内の各非キー・ノードと各キー・ノードとの間の相関を計算する計算サブ・モジュールと、各非キー・ノードと各キー・ノードとの間の前記相関を比較することによって各非キー・ノードとの間の相関が最も大きいキー・ノードを取得する比較サブ・モジュールと、各非キー・ノードを、それ自体との相関が最も大きいキー・ノードが存在するノード・グループにグループ化するグループ化サブ・モジュールと、を備える。
【００７２】
本発明の一実施形態によれば、２つのノード間の相関は、前記２つのノード間の各経路内の各辺の重みに依存する。
【００７３】
本発明の一実施形態によれば、前記装置は、前記ノード移動中に発生する前記ノード・グループ内のノードと他のノードとの位置重複を検出する重複検出モジュールを更に備え、前記プランニング・モジュールは、前記ノード移動中に前記ノード・グループ内のノードと別のノード・グループ内のノードとの位置重複が発生したときに、前記別のノード・グループ内の前記ノードの移動が直ちに開始されるように前記ノード移動の前記アニメーション・デモンストレーションをプランニングする手段を備える。
【００７４】
本発明の一実施形態によれば、前記プランニング・モジュールは、前記接続変更が適用される前に前記動的グラフ内の各ノードの初期位置を取得し、前記接続変更が適用された後に各ノードのターゲット位置を取得する手段と、前記初期位置と前記ターゲット位置との間の各ノードの移動経路を力指向的アニメーション・モデルを使用して計算する手段と、を備え、前記力指向的アニメーション・モデルは、直接接続されるノードから成る各ノード対間のばね力と、各ノード対間の斥力と、各ノードの移動を推進する可変力と、を含み、力場内の消費エネルギーが最小となる曲線経路を発見するモデルである。
【００７５】
本発明は、ハードウェア、ソフトウェア、あるいはハードウェアとソフトウェアの組合せの形で実現することができる。本発明は、１つのコンピュータ・システムにおいて集中的な構成で実現することも、様々な構成要素がいくつかの相互接続コンピュータ・システムに分散される分散的な構成で実現することもできる。本明細書に記載の方法を実行するのに適した任意のコンピュータ・システム又は他の装置を利用することが可能である。ハードウェアとソフトウェアの典型的な組合せは、それ自体がロードされ実行されたときにコンピュータ・システムによって本発明の方法が実行され本発明の装置が構成されるように制御するコンピュータ・プログラムを備えたコンピュータ・システムである可能性がある。
【００７６】
本発明は、本明細書に記載される方法のすべての特徴を実現し、それ自体がコンピュータ・システムにロードされたときに当該方法を実行することが可能なコンピュータ・プログラムの形で実施することもできる。
【００７７】
以上、本発明を好ましい諸実施形態に関して図示し説明してきたが、本発明の形態及び詳細には本発明の趣旨及び範囲を逸脱しない限り様々な変更を加えることができることが、当業者には理解されるであろう。
【符号の説明】
【００７８】
ｅＡＤ、ｅＢＣ 追加される接続
【技術分野】
【０００１】
本発明は動的グラフ・ビジュアライゼーションに関するものであり、より詳細には、動的グラフ用アニメーション・プランニング方法及び装置に関するものである。
【背景技術】
【０００２】
グラフ・ビジュアライゼーションとも呼ばれるグラフ描画は、トポロジ及びジオメトリを使用することによってグラフの２次元（２Ｄ）又は３次元（３Ｄ）表現を取得し表示する処理を指し、ＶＬＳＩ回路設計、ソーシャル・ネットワーク分析、カートロジー（cartology）、バイオ・インフォーマティックス等、様々な分野で広く応用されている。グラフ・ビジュアライゼーションでは、ドットを使用してグラフ内の頂点が表現され、ドット同士を接続する線を使用して頂点間の辺（edge）が示され、矢印を使用して有向辺が示される。１つの同じグラフでも、その頂点及び辺の可視化構成が異なれば、グラフの理解性、有用性、生産コスト、美的特性等に影響が及ぶ。グラフ・ビジュアライゼーションの主な目的は、適切なレイアウト・アルゴリズムを使用することにより、（例えば辺の交差を可能な限り少なくし、様々な辺の長さをほぼ同一とすること等により）理解性及び美的特性に優れるグラフの２次元又は３次元表現を取得し提示することである。
【０００３】
動的グラフとは、経時的に変化するグラフであって、それ自体の要素（ノード又は辺）が動的に追加及び削除され、それらの属性も動的に変更され得るグラフを指す。動的グラフ・ビジュアライゼーションの主な目的は、動的グラフの時間次元に沿った変化パターンを開示し、グラフ又はネットワークの発展プロセスを明示することである。例えば、動的グラフ・ビジュアライゼーションは、社会学者によるソーシャル・ネットワークの発展プロセスの解明や、ビジネス・インテリジェンス（ＢＩ）・アナリストによる様々な企業の潜在顧客の発掘、生物学者によるタンパク変異の発見等に役立つ可能性がある。
【０００４】
動的グラフ・ビジュアライゼーションには多くの課題が存在する。最も重要な課題の１つは、様々な時間フレームにおけるグラフ変化をユーザのメンタル・マップが維持されるように円滑に遷移させることである。この問題を解決するために、アニメーション技術が広く使用されている。アニメーションは、人々の関心を引くことができ、物事の変更部分と不変部分とを表現することができる。図１は、あるコミュニティの年単位のソーシャル・ネットワーク・グラフのアニメーション変化をデモンストレーションした一例を示し、各フレームは、このコミュニティの２００４〜２００８年の各年におけるソーシャル・ネットワーク・グラフを示す。ソーシャル・ネットワーク・グラフ内の各ノードは、コミュニティを形成する個人を示し、ノード間の各辺は、それらの個人間の関係を示す。これらの各フレームを連続的に再生することによりソーシャル・ネットワーク・グラフ内のノード及び辺の数年間の増減変化が表示され、それ故コミュニティの年単位の変化パターンが直感的に開示される。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、動的グラフ・ビジュアライゼーションの分野の既存のアニメーション技術は、いくつかの欠点を有する。例えば、複数のノードを追加又は削除することによってグラフが変更される場合、既存のアニメーション技術ではそれらのすべてのノードが同時に追加又は削除される。これによって時間コストは最小となるが、変更数が多すぎる故に動的グラフの変更時に発生する重要な構造上の更新をハイライトすることができず、その結果ユーザの視覚的な混乱が生じ、アニメーションの可読性が低下することになる。一方、ノード変更が１つずつ実行される場合も、多数の変更が存在すれば時間がかかりすぎてしまう。したがって、当業界ではアニメーション速度と可読性との所望のバランスをとるアニメーション・プランニング方法が必要とされている。
【０００６】
また、動的ソーシャル・ネットワークのようなネットワークでは、関係（ソーシャル・ネットワークを表す動的グラフでは辺として表現される）の変更はごく一般的なことである。例えば、このような関係変更には個人間の関連付けの追加又は削除が含まれる。関係変更はソーシャル・ネットワーク・グラフのトポロジ構造を大きく変化させる可能性があるので、ソーシャル・ネットワークに対する関係変更の影響を分析し完全に提示することは困難である。従来のアニメーション技術において、関係変更は通常以下の２つのステップでデモンストレーションされる。第１ステップでは、各辺がそれぞれの始点ノードからターゲット・ノードに伸ばされ、各ノードが接続される。本ステップは、グラフ・トポロジの変化を示すのに使用される。換言すると、本ステップによってグラフ・ビジュアライゼーションに変更が生じた理由が描写される。第２ステップでは、新しい辺によって接続されたすべてのノード及び関係するノードが、それぞれの新しい位置に一緒にドラッグされる。これにより、グラフ・ビジュアライゼーションの変更現象又は変更結果が示される。この２ステップ・モデルでは、変更理由と最終的な変更結果との間にギャップが存在する。異なるノード移動は通常異なる接続に起因するものであり、最終的な移動結果は複数の接続（理由）に起因する可能性があるので、このような従来のアニメーション技術では各ノード移動の主要理由を発見し表示することができない。ノード移動理由の発見及び可視化は、ソーシャル・ネットワーク関係分析で非常に重要となる。したがって、当業界では、ソーシャル・ネットワーク・グラフのような動的グラフの関係変更とノード移動との間の内部関係が表示可能であるとともに可読性に優れたアニメーション・プランニング方法が必要とされている。
【課題を解決するための手段】
【０００７】
本発明の一態様によれば、動的グラフ用アニメーション・プランニング方法であって、動的グラフ内のノード変更が適用されたことに応答して、前記変更ノードと既存ノードとの間の関係に従って前記変更ノードをアトミック・パーティション（atomic partition）にグループ化するステップと、前記アトミック・パーティション間のクラスタリング距離に従って、前記動的グラフ内のノード変更のアニメーション・デモンストレーションをプランニングするランニング・リスト（running list）であって、アトミック・パーティション・クラスタ又はアトミック・パーティションあるいはその両方を要素として含むランニング・リストが生成されるように、前記アトミック・パーティションをクラスタリングするステップと、を含む方法が提供される。
【０００８】
本発明の別の態様によれば、動的グラフ用アニメーション・プランニング装置であって、動的グラフ内のノード変更が適用されたことに応答して、前記変更ノードと既存ノードとの間の関係に従って前記変更ノードをアトミック・パーティションにグループ化するアトミック・パーティショニング・モジュール（atomic partitioningmodule）と、前記アトミック・パーティション間のクラスタリング距離に従って、前記動的グラフ内のノード変更のアニメーション・デモンストレーションをプランニングするランニング・リストであって、アトミック・パーティション・クラスタ又はアトミック・パーティションあるいはその両方を要素として含むランニング・リストが生成されるように、前記アトミック・パーティションをクラスタリングするクラスタリング・モジュールと、を備える装置が提供される。
【０００９】
本発明のまた別の態様によれば、動的グラフ用アニメーション・プランニング方法であって、動的グラフ内の接続変更が適用されたことに応答して、前記動的グラフ内のノードと、各変更接続が直接接続されるノードを指すキー・ノードとの間の相関に従って前記動的グラフ内のノードを様々なノード・グループにグループ化するステップと、前記接続変更に起因するノード移動のアニメーション・デモンストレーションを前記ノード・グループによってプランニングするステップと、を含む方法が提供される。
【００１０】
本発明の他の態様によれば、動的グラフ用アニメーション・プランニング装置であって、動的グラフ内の接続変更が適用されたことに応答して、前記動的グラフ内のノードと、各変更接続（change connection）が直接接続されるノードを指すキー・ノードとの間の相関に従って前記動的グラフ内のノードを様々なノード・グループにグループ化するグループ化モジュールと、前記接続変更に起因するノード移動のアニメーション・デモンストレーションを前記ノード・グループによってプランニングするプランニング・モジュールと、を備える装置が提供される。
【００１１】
本発明の技術的解決を用いると、動的グラフのノード変更又は接続変更に関するマルチ・ステージ・アニメーション・デモンストレーションのプランニング、ならびに動的グラフ内の変更要素間の相関、及びそれらの変更要素と既存の要素との間の相関を開示するアニメーション・デモンストレーション効果を得ることが可能となり、それ故、可読性の改善及びアニメーション・デモンストレーション速度の高速化が実現される。
【００１２】
添付の特許請求範囲には、本発明の特徴と見なされる発明の特徴が記載されている。しかしながら、本発明ならびに本発明の好ましいモード、目的、特徴、及び利点は、例示的な諸実施形態に関する以下の詳細な説明を添付図面と併せて読めばより良く理解されるだろう。
【図面の簡単な説明】
【００１３】
【図１】あるコミュニティの年単位のソーシャル・ネットワーク・グラフのアニメーション変化をデモンストレーションした一例を示す図である。
【図２】本発明の一実施形態に係る動的グラフ用アニメーション・プランニング方法の全体の流れを示す概略図である。
【図３】本発明の一実施形態に従って変更ノードをアトミック・パーティションにグループ化する方法の一例を示す図である。
【図４】本発明の一実施形態に係るクラスタリング・プロセスによって生成されるアニメーション・プランニング・モデルの一例を示す図である。
【図５】本発明の別の実施形態に係る動的グラフ用アニメーション・プランニング方法の全体の流れを示す図である。
【図６】動的グラフの接続変更の一例を示す図である。
【図７】すべてのグループのノード移動が並行してアニメーション・デモンストレーションされる場合を示す図である。
【図８】異なるグループのノード移動が１つずつアニメーション・デモンストレーションされる場合を示す図である。
【図９】ノード位置の重複が検出されたときに、次のグループのノード移動のアニメーション・デモンストレーションが直ちに開始される場合を示す図である。
【図１０】ある力場内の初期位置Ａからターゲット位置Ｂに移動するノードの移動経路を示す概略図である。
【発明を実施するための形態】
【００１４】
以下、添付図面を参照して本発明の諸実施形態について説明する。以下の説明では、本発明の十分な理解が得られるように様々な詳細が説明される。しかしながら、本発明は、これらの詳細の一部が与えられない場合にも実現され得ることが当業者には理解されるだろう。また、本発明は、本明細書に記載される特定の実施形態に限定されるものではないことも理解していただきたい。そうではなく、本発明は、それらが異なる実施形態に関与するものであるか否かに関わらず、後述する各特徴及び要素の任意の組合せを使用して実施されることが企図される。したがって、後述する各態様、特徴、実施形態、及び利点は、特許請求範囲に記載の各請求項に特に明記しない限り、各請求項の要素となるものでもそれらを限定するものでもなく、単なる例示にすぎない。
【００１５】
本発明の一態様では、動的グラフ内のノード変更（即ち、ノードの増加又は減少）に関するアニメーション・デモンストレーションのプランニングに使用される動的グラフ用アニメーション・プランニング方法が提供される。本方法では、動的グラフ内の変更ノードとそれらのノードの重要度との間の相関に従って各ノードが様々な次数でクラスタリングされ、このクラスタリングに従って、他の変更ノードとの相関が小さい変更ノード又はより重要度が高いノードは独立して又はより小さいクラスタでアニメーション・デモンストレーションされ、互いの相関が大きい変更ノードは一緒にアニメーション・デモンストレーションされるものとしてクラスタリングされるように、ノード変更のアニメーション・デモンストレーションがプランニングされる。したがって、可読性が良く時間コストも低いアニメーション・デモンストレーション効果が達成される。
【００１６】
次に図２を参照すると、本発明の一実施形態に係る動的グラフ用アニメーション・プランニング方法の全体の流れが概略的に示されている。図示のとおり、本方法は以下の主なステップ、即ち、アトミック・パーティショニングを実行するステップと、アトミック・パーティションをクラスタリングするステップと、任意選択で動的ソートを実行するステップと、を含む。以下、本発明の方法の各ステップについて詳細に説明する。
【００１７】
ステップ１：アトミック・パーティショニング
本ステップは、変更ノードが動的グラフに適用されたことに応答して、グラフ内の変更ノードと既存ノードとの間の関係に従って、変更ノードをいくつかのアトミック・パーティションにグループ化する。当業界では周知のとおり、動的グラフに対するノード変更の適用とは、動的グラフのトポロジ構造に変化が生じるようにノード変更を動的グラフのトポロジに適用し、その後、採用された適切なレイアウト・アルゴリズムを適用してノード変更後の動的グラフのレイアウト、即ち各ノードのターゲット位置を取得することを指す。
【００１８】
既存ノードと直接接続されるすべての新規追加ノードは、同じアトミック・パーティションにグループ化することができる。このようなグループ化方法が図２に示される。ここでは、１０個の新規追加ノードが４つの既存ノードと直接接続され、それ故、これらの１０個の新規追加ノードはそれぞれ４つのアトミック・パーティションにグループ化され得る。
【００１９】
いくつかの新規追加ノードが既存ノードと直接接続されない比較的複雑な条件では、まず各新規追加ノードのキー・ノードが発見され、同じキー・ノードを有する新規追加ノードが同じアトミック・パーティションにグループ化される。本方法の実行プロセスは、以下のように説明することができる。
【００２０】
入力：
（１）新規追加ノードｎｉ；
（２）動的グラフＧ
出力：
（１）アトミック・パーティション集合Ｃ
説明：
１．各ｎｉについて、グラフＧに対して幅優先探索（Breadth-First-Search）を実行し、ｎｉとノード｛ｍｉ｜ｍｉ∈Ｇ｝とを結合するすべての最短経路を記録し、経路集合をＳとする。
２．Ｓ内の各最短経路について、当該経路内の各辺の重みを単純に加算することにより、それぞれの重みを計算する。
３．ｎｉとｍｋを結合する経路を仮定して、すべての最短経路の中から重みが最も大きい経路を選択する。
４．ノードｍｋを新規追加ノードｎｉのキー・ノードとする。
５．同じキー・ノードｍｋを有するすべてのｎｉをアトミック・パーティションｃｉとしてグループ化し、Ｃに入れる。
６．Ｃを返す。
【００２１】
図３は、変更ノードをアトミック・パーティションにグループ化する方法の実行プロセスの一例を示す。図示のとおり、５、６、７は既存ノードであり、１、２、３、４は新規追加ノードである。
【００２２】
新規追加ノード１から既存ノードまでの最短経路の集合は、Ｓ１＝｛（１，２，５），（１，３，５），（１，３，６）｝、各経路の重みは、Ｗ１＝｛４，４，５｝（最大の重みは５）であり、したがって新規追加ノード１のキー・ノードは、Ｐ１＝６となる。
【００２３】
新規追加ノード２から既存ノードまでの最短経路の集合は、Ｓ＝｛（２，５）｝、経路の重みは、Ｗ２＝｛２｝（最大の重みは２）であり、したがって新規追加ノード２のキー・ノードは、Ｐ２＝５となる。
【００２４】
新規追加ノード３から既存ノードまでの最短経路の集合は、Ｓ＝｛（３，５），（３，６）｝、経路の重みは、Ｗ３＝｛１，２｝（最大の重みは２）であり、したがって新規追加ノード３のキー・ノードは、Ｐ３＝６となる。
【００２５】
新規追加ノード４から既存ノードまでの最短経路の集合は、Ｓ＝｛（４，７）｝、経路の重みは、Ｗ４＝｛１｝（最大の重みは１）であり、したがって新規追加ノード４のキー・ノードは、Ｐ４＝７となる。
【００２６】
それ故、新規追加ノード１及び３は、１つの同じアトミック・パーティションにグループ化されるが、新規追加ノード２は、別のアトミック・パーティションに、新規追加ノード４は、また別のアトミック・パーティションにグループ化される。
【００２７】
ステップ２：アトミック・パーティションのクラスタリング
本ステップは、各アトミック・パーティションとそれぞれの重要度との間の相関に従ってアトミック・パーティションをいくつかのクラスタにクラスタリングし、それらのクラスタから構成される適切なランニング・リストを取得し、それによってアニメーション速度と情報の可読性とのバランスをとるものである。クラスタリング・プロセス中に、アトミック・パーティション、中間クラスタ、及び最終クラスタから構成される階層構造が形成され、この階層構造は、アニメーション・プランニング・モデルと呼ばれることがある。アトミック・パーティションを階層的にクラスタリングする上で最も重要なことは、任意の２つのアトミック・パーティション又はクラスタ間のクラスタ距離を計算することである。クラスタ距離の計算では多くの方法が使用され得る。１つの単純な手法は、ユークリッド幾何学距離公式を使用してアトミック・パーティション又はクラスタ間のスクリーン距離を計算し、スクリーン距離をクラスタ距離とするものである。スクリーン距離は、例えば２つのアトミック・パーティション又はクラスタに含まれるノード間の最短経路の長さであることも、２つのアトミック・パーティション又はクラスタに含まれるノード間の経路の平均長さであることもある。一方、本発明は、以下の要因のうちの１つ又は複数を考慮することによってクラスタ距離を計算する新しい方法を提案する。
【００２８】
１．アトミック・パーティション又はクラスタの重要度。重要なアトミック・パーティションは、他のアトミック・パーティションと共にクラスタリングされずに独立して表示されることが望ましく、また、あるクラスタの重要度がアトミック・パーティションのクラスタリング・プロセス中に一定の次数まで累積された場合は、それ以降当該クラスタが他のアトミック・パーティション又はクラスタと共にクラスタリングされることはなくなる。
【００２９】
２．２つのアトミック・パーティション又はクラスタ間のトポロジ距離。２つのアトミック・パーティション又はクラスタ同士を接続する辺が多数存在する場合、それらの２つのアトミック・パーティション又はクラスタ同士の結び付きは通常強くなり、また、各アトミック・パーティション又はクラスタに対する変更は通常、それらのアトミック・パーティション又はクラスタが一緒にクラスタリングしやすくなるように関係付けられる。ここで、２つのアトミック・パーティション又はクラスタ間のトポロジ距離は、それらの間の共通辺の数として定義することができる。
【００３０】
３．２つのアトミック・パーティション又はクラスタ間のジオメトリ距離。上述のとおり、ジオメトリ距離は、２つのアトミック・パーティション又はクラスタ間のスクリーン距離を指し、通常は２つのアトミック・パーティション又はクラスタ内のノード間の最短経路の長さ、又は２つのアトミック・パーティション又はクラスタ内のノード間の経路の平均長さで示される。
【００３１】
上記を考慮すると、任意の２つのアトミック・パーティション又はクラスタ間のクラスタリング距離は、次式を使用して計算することができる。
【数１】
【００３２】
上式で、ｉ及びｊは、２つのアトミック・パーティション又はクラスタを示し、
ｄｉｓｔ（ｉ，ｊ）は、２つのアトミック・パーティション又はクラスタ間のクラスタリング距離を示し、
ｄは、ｉとｊの間のジオメトリ距離を示し、次式が得られる。
【数２】
【００３３】
上式で、ｅｉｊはｉとｊを結合する辺の数であり、｜ｉ｜はｉ内のノード数、｜ｊ｜はｊ内のノード数を示す。
ａ＝（０，１）は、０〜１の範囲の重みパラメータを指し、関連要因の必要とされる重みに従って指定することができる。
ｃは、ｉとｊの組合せの重要度を示し、式：ｃ＝（｜ｉ｜ｃｉ＋｜ｊ｜ｃｊ）／（｜ｉ｜＋｜ｊ｜）を使用して計算される。ここで、ｃｉ及びｃｊは、それぞれｉ及びｊの重要度を示し、これらの重要度は、次式を使用して計算することができる。
【数３】
【００３４】
即ち、ｃｉは、ｉ内のノードの重要度の合計である。上式は更に、ノードｎの重要度の計算方法も提案する。上式で、Ｃ（ｎ）はノードｎの近接中心性（closeness centrality）、Ｂ（ｎ）はノードｎの媒介中心性（between centrality）、βは重みパラメータである。実際には、ノードの重要度は当業界で周知の多くの方法を使用して計算することができる。例えば、ノードの次数中心性（degree centrality）や固有ベクトル中心性（eigenvector centrality）等も考慮することができる。
【００３５】
上記では、アトミック・パーティション又はクラスタ間のクラスタリング距離の例示的な計算方法を提示したが、以下では、クラスタリング距離を使用してアトミック・パーティションに対する階層クラスタリングを実行し、それによってランニング・リストを取得する方法の実行プロセスについて説明する。
【００３６】
入力：
１）アトミック・パーティション集合Ｃ
２）重要度閾値λ１
３）動的グラフＧ
出力：
１）ランニング・リストＬ
説明：
１．初期集合Ｓ＝Ｃにセットする。
２．Ｓ内の各要素ｉの重要度ｃｉを計算する。ｉがアトミック・パーティションである場合には、その重要度はすべての収容ノードの重要度の合計となるが、ｉがクラスタである場合には、その重要度はクラスタに含まれるアトミック・パーティション又はクラスタの重要度の合計となる。ノードの重要度計算では複数の方法が使用され得る。例えば、ノードの重要度は、ノードの次数中心性、近接中心性、媒介中心性、及び固有ベクトル中心性のうちの任意の１つ又はそれらの組合せを使用して計算することができる。
３．Ｓ内の各ｉについて、ｃｉ≧λ１である場合は、ｉをＬに入れる。ここで、λ１は重要度閾値であり、λ１の値は、関連要因の必要とされる重みに従って設定することができる。
４．Ｓ内の２つの要素ｉ及びｊ毎に、上述の方法を使用してｄｉｓｔ（ｉ，ｊ）が計算される。
ａ）クラスタｉ及びｊをクラスタＭとして、ｉとｊの間のクラスタリング距離が平均距離閾値λ２未満である場合は、ｉ及びｊをＳから削除し、ＭをＳに追加する。
ｂ）ｉとＳ内の他の任意の要素との間のクラスタ距離が平均距離閾値λ２以上である場合は、ｉをＬに入れる。
５．ステップ２に進んで、Ｓ内のすべての要素間のクラスタリング距離が平均距離閾値λ２以上となるまで新しいクラスタリング・ラウンドを開始し、Ｓ内のすべての要素をＬに入れる。
６．Ｌを返す。
【００３７】
上記の平均距離閾値λ２は、次式によって計算することができる。
λ２＝ｍａｘ（Ｄ（ｉ，ｊ））／（ｃｏｕｎｔ−１）
上式で、ｍａｘ（Ｄ（ｉ，ｊ））はＳ内の既存要素間の最大クラスタリング距離、ｃｏｕｎｔはＳ内の既存要素数である。
【００３８】
上記のクラスタリング・プロセスによってアニメーション・プランニング・モデルが生成される。図４は、このようなクラスタリング・プロセスによって生成されるアニメーション・プランニング・モデルの一例を示す。図示のとおり、このモデルは階層的であり、最下層はアトミック・パーティション１〜１８である。クラスタリング・プロセスの第１ラウンドにおいて、アトミック・パーティション１〜４、５‐６、７‐８、９‐１０、１３〜１５、１６〜１８は、それぞれクラスタＡ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆにクラスタリングされ、アトミック・パーティション１１及び１２は、それらの重要度が重要度閾値を超える、又は他の任意の要素との間のクラスタリング距離がいずれも平均距離閾値以上となる故に、ランニング・リストに転送される。クラスタリング・プロセスの第２ラウンドにおいて、クラスタＡ‐Ｂ、Ｅ‐Ｆは更に、クラスタＧ、Ｈにクラスタリングされ、クラスタＣ及びＤは、それらの重要度が重要度閾値を超える、又は他の任意の要素との間のクラスタリング距離がいずれも平均距離閾値以上となる故に、ランニング・リストに転送される。クラスタリング・プロセスの第３ラウンドにおいて、クラスタＧ及びＨは、それらの重要度が重要度閾値を超える、又は他の任意の要素との間のクラスタリング距離がいずれも平均距離閾値以上となる故に、ランニング・リストに転送される。したがって、取得されるランニング・リストは、図４の破線で接続される要素、即ちクラスタＧ、Ｃ、Ｄ、アトミック・パーティション１１、１２、及びクラスタＨを含むことになる。このようにして、アニメーション・デモンストレーションは、ランニング・リストの内容に従って実行されるようにプランニングされ、それ故、可読性とデモンストレーション速度とのバランスが良いアニメーション・デモンストレーション効果が得られる。
【００３９】
ステップ３：動的ソート
本ステップは任意選択であり、ランニング・リスト内の要素（クラスタ又はアトミック・パーティション）のアニメーション・デモンストレーション順序を決定する。人間の視覚的な平滑追跡能力は非対称的であり、通常は縦方向の平滑追跡能力よりも横方向の平滑追跡能力の方が優れており、上方向の平滑追跡能力よりも下方向の平滑追跡能力の方が優れている。これに基づき、動的ソートの目的は、横方向の移動ならびに下方向の移動を最大化すること、即ち、ランニング・リスト内のクラスタ又はアトミック・パーティションのスクリーン位置に従って、クラスタ又はアトミック・パーティションのデモンストレーションが左から右、上から下、右から左の順に可能な限り離れた位置まで実行されるように、アニメーション・デモンストレーションの順序を決定することである。また、重要度の高いクラスタ又はアトミック・パーティションほど高い優先度が割り当てられ、即ち、重要なクラスタ又はアトミック・パーティションから先にデモンストレーションされる。
【００４０】
具体的には、まずランニング・リスト内の要素の重要度［ａ１，ａ２，．．．，ａｉ，．．．，ａｎ］が取得される。クラスタ又はアトミック・パーティションの重要度は、上述の方法を使用して計算することができる。
【００４１】
次に、ランニング・リスト内の要素のスクリーン位置に従って、各要素の視覚的順序の重み（visual order weight）［ｂ１，ｂ２，．．．，ｂｉ，．．．，ｂｎ］が決定される。視覚的順序の重みは、上記のアニメーション・デモンストレーション順序に従って指定することができる。例えば、スクリーンの左側の要素がスクリーンの右側の要素よりも大きい視覚的順序の重みを有し、スクリーンの上部の要素がスクリーンの下部の要素よりも大きい視覚的順序の重みを有するように指定することができる。
【００４２】
次に、ランニング・リスト内の各要素のアニメーション・デモンストレーション順序の重み（animationdemonstration order weight）を次式を使用して計算することができ、ランニング・リスト内の各要素のアニメーション・デモンストレーション順序をアニメーション・デモンストレーション順序の重みに従って決定することができる。
【数４】
【００４３】
上式で、Ｏｉは、要素ｉのアニメーション・デモンストレーション順序の重みであり、αは、要素重要度の重みと視覚的順序の重みとの間の相対重みを表す係数である。
【００４４】
ステップ２で変更ノードがクラスタリングされ、適切なランニング・リストが生成され、任意選択のステップ３でクラスタ又はアトミック・パーティションのデモンストレーション順序が決定された後は、良好な可読性と高速なデモンストレーション速度を兼ね備えたアニメーション・デモンストレーションが得られるように、ノード変更のアニメーション・デモンストレーションをランニング・リスト及びデモンストレーション順序に従ってプランニングすることができる。
【００４５】
上記では、動的グラフにノードを追加する場合を一例として本発明の一実施形態に係る動的グラフ用アニメーション・プランニング方法について説明したが、上記の説明は単なる例示であり、本発明を限定するものではないことを指摘しておきたい。例えば、本発明は、動的グラフのノードを減少させるのにも適しており、また、動的グラフへのノード追加と動的グラフのノード減少を同時に実行するのにも適している。動的グラフのノードが減少される場合は、減少対象ノードの処理は追加対象ノードの処理と同じになる。即ち、各ノードがアトミック・パーティションにグループ化された後、当該アトミック・パーティションのクラスタリングが実行され、任意選択でクラスタ（場合によってはアトミック・パーティション）に対して動的ソートが実行され、その結果、各ノードのアニメーション・デモンストレーションがこれらのクラスタリング及び動的ソートに従ってプランニングされる。動的グラフのノード追加及びノード減少が同時に実行される場合は、追加対象ノードと減少対象ノードはそれぞれ個別に処理され得る。即ち、追加対象ノード及び減少対象ノードがそれぞれ個別にアトミック・パーティションにグループ化された後、それぞれのアトミック・パーティションのクラスタリングが実行され、任意選択でそれぞれのクラスタ（場合によってはアトミック・パーティション）に対して動的ソートが実行され、その結果、追加対象ノード及び減少対象ノードのアニメーション・デモンストレーションがそれぞれのクラスタリング及び動的ソートに従ってプランニングされる。好ましくは、アニメーション・デモンストレーションは、最初に減少対象ノードがデモンストレーションされ、次に動的グラフ内のオリジナル・ノードがターゲット位置に移動するようにデモンストレーションされ、最後に追加対象ノードがデモンストレーションされるようにプランニングされる。動的グラフ内のオリジナル・ノードのターゲット・ノードは、ノード変更が動的グラフに適用された後に、採用されたレイアウト・アルゴリズムを使用して計算することができる。
【００４６】
本発明は更に、上述した動的グラフ用アニメーション・プランニング方法を実行するのに使用され得る動的グラフ用アニメーション・プランニング装置も提供する。以下では動的グラフ用アニメーション・プランニング装置の概要のみを説明し、本装置の詳細情報に関しては上記の説明を参照していただきたい。
【００４７】
本発明の一実施形態によれば、動的グラフ用アニメーション・プランニング装置は、動的グラフ内の変更ノードと既存ノードとの間の関係に従って前記変更ノードをアトミック・パーティションにグループ化するアトミック・パーティショニング・モジュールと、前記アトミック・パーティション間のクラスタリング距離に従って、前記動的グラフ内の前記変更ノードのアニメーション・デモンストレーションをプランニングするランニング・リストであって、アトミック・パーティション・クラスタ又はアトミック・パーティションあるいはその両方を要素として含むランニング・リストが生成されるように、前記アトミック・パーティションをクラスタリングするクラスタリング・モジュールと、を備える。
【００４８】
本発明の一実施形態によれば、前記装置は、前記要素のスクリーン位置及び前記要素の重要度に従って、前記ランニング・リスト内の前記要素のアニメーション・デモンストレーション順序をソートするソート・モジュールを更に備える。
【００４９】
本発明の一実施形態によれば、前記アトミック・パーティショニング・モジュールは、各変更ノードについて、当該ノードが前記動的グラフ内の既存ノードと接続される最短経路内で重みが最も大きい経路を取得し、前記経路によって接続される前記動的グラフ内の前記既存ノードを前記変更ノードのキー・ノードとする手段と、同じキー・ノードを有する前記変更ノードを同じアトミック・パーティションにグループ化する手段と、を備える。
【００５０】
本発明の一実施形態によれば、前記クラスタリング・モジュールは、それ自体の重要度が重要度閾値に達した又はそれを超えた前記アトミック・パーティション又はクラスタを前記ランニング・リストに転送する手段と、それらの間の前記クラスタリング距離が距離閾値よりも小さい２つのアトミック・パーティション又はクラスタをクラスタリングする手段と、他の任意のアトミック・パーティション又はクラスタとの間の前記クラスタリング距離が前記距離閾値以上である前記アトミック・パーティション又はクラスタを前記ランニング・リストに転送する手段と、を備え、上記の処理は、すべての前記アトミック・パーティションがアトミック・パーティション又はクラスタの一部として前記ランニング・リストに入れられるまで繰り返し実行される。
【００５１】
本発明の一実施形態によれば、２つのアトミック・パーティション又はクラスタ間の前記クラスタリング距離は、前記２つのアトミック・パーティション又はクラスタ間のジオメトリ距離、前記２つのアトミック・パーティション又はクラスタ同士を接続する辺の数、及び前記２つのアトミック・パーティション又はクラスタの組合せの重要度、のうちの１つ又は複数に依存する。
【００５２】
本発明の一実施形態によれば、アトミック・パーティション又はクラスタの重要度は、前記アトミック・パーティション又はクラスタに含まれるノードの重要度に依存し、ノードの重要度は、前記ノードの次数中心性、近接中心性、媒介中心性、及び固有ベクトル中心性のうちの１つ又は複数に依存する。
【００５３】
本発明の別の態様によれば、動的グラフ用アニメーション・プランニング方法が提供される。前記方法は、動的グラフ内の接続（即ち辺）の変更に起因するノード移動のアニメーション・デモンストレーションをプランニングするのに使用される。前記方法では、ノードの接続変更がノード移動の内部理由とされ、様々なノードの位置変更を生じさせた内部理由、即ち、どの辺の変更がどのノードの位置変更原因であるかを突き止める試行がなされ、次に、それらの移動が主に同じ辺に起因するノードが一緒にグループ化され、最後に、同じグループ内のノードの移動が同時にアニメーション・デモンストレーションされ、異なるグループ内のノードの移動が異なる時点でアニメーション・デモンストレーションされるように、ノード移動のアニメーション・デモンストレーションがプランニングされる。
【００５４】
次に図５を参照すると、本発明の一実施形態に係る動的グラフ用アニメーション・プランニング方法の全体の流れが示されている。図示のとおり、本方法は、以下の主なステップ、即ち、接続変更を適用するステップと、ノード・グループ化を実行するステップと、マルチ・ステージ・アニメーション・プランニングを実行するステップと、を含む。以下、添付図面を参照して本発明の一実施形態に係る動的グラフ用アニメーション・プランニング方法について説明する。
【００５５】
ステップ１：接続変更の適用
本ステップでは、動的グラフのトポロジ構造を変化させる接続変更が動的グラフのトポロジに適用され、その後、採用された適切なレイアウト・アルゴリズムを適用して接続変更後の動的グラフのレイアウト、即ち各ノードのターゲット位置が取得される。図６は、動的グラフの接続変更の一例を示す。図示のとおり、２つの接続ｅＡＤ及びｅＢＣが動的グラフに追加され、これらの２つの接続によってすべてのノードの移動が発生する。本ステップは、ここでは詳細な説明は省略するが、http://sonia.stanford.edu等から入手可能な既存の動的グラフ・ビジュアライゼーション・システムによって達成することができる。
【００５６】
ステップ２：ノード・グループ化
本ステップでは、すべてのノードの接続変更を１つずつ検査してその接続変更がノード移動の主要理由となるかどうかが判定され、移動が同じ接続変更に起因するノード同士が一緒にグループ化される。従来技術の方法では、すべてのノードが一緒に移動するので、ノード移動を生じさせた主要理由を表示することができない。本発明の方法は、ノード移動を生じさせた主要理由に従って各ノードを様々なグループに分け、それらのグループに従って、可読性に優れたアニメーション・デモンストレーション効果が得られるようにノード移動のアニメーション・デモンストレーションをプランニングする。
【００５７】
本発明の一実施形態によれば、ノード・グループ化の詳細なステップは以下のとおりとなる。
【００５８】
１．各変更接続ｅｉｊについて、初期グループＧｉｊが作成され、ノードｉ及びｊがＧｉｊに入れられると同時にキー・ノード集合Ｋに入れられる。即ち、接続変更によって直接接続されるノードがキー・ノードと見なされ、これらのキー・ノードは、各キー・ノードが属する接続変更に従って様々なグループにグループ化される。例えば、図６の動的グラフの接続変更の場合、作成される初期グループは、ＧＡＤ＝｛Ａ，Ｄ｝、ＧＢＣ＝｛Ｂ，Ｃ｝であり、キー・ノード集合は、Ｋ＝｛Ａ，Ｄ，Ｂ，Ｃ｝である。２つ以上の変更接続が共通のノードを共有する場合は、初期グループを作成し、これらの変更接続によって直接接続されるすべてのノードを作成された初期グループに入れることができる。
【００５９】
２．すべての初期グループ内の各ノードｉについて、ｉとグラフ内の他の任意のノードとの間の相関が計算される。即ち、動的グラフ内の各非キー・ノードと各キー・ノードとの間の相関が計算される。ノードｉとｊの間の相関は、次式を使用して計算することができる。
【数５】
【００６０】
上式で、Ｒ（ｉ，ｊ）はノードｉとｊの間の相関、Ｐｉｊはノードｉからｊまでのすべての経路を含む経路集合、ｗｋｌはノードｋとｌの間の辺の重み、｜ｐ｜は経路ｐのトポロジ長、Ｅはグラフ内のすべての辺の集合、ｅｋｌはノードｋとｌの間の辺、ｅｉｊはノードｉとｊの間の辺である。即ち、上式によれば、２つのノード間の相関は、２つのノード間のすべての経路内の各辺の重みに依存する。
【００６１】
３．各非キー・ノードについて、非キー・ノードは、それ自体との相関が最も大きいキー・ノードを含むグループに入れられる。即ち、すべての非キー・ノードとすべてのキー・ノードとの間の相関を比較して各非キー・ノードとの相関が最も大きいキー・ノードが取得され、その後、各非キー・ノードは、それ自体との相関が最も大きいキー・ノードが存在するグループに入れられる。例えば、図６の各ノードＥ、Ｆ、Ｇ、Ｈ、Ｉについて、各ノードは、それらとキー・ノードＡ、Ｄ、Ｂ、Ｃとの間の計算される相関に従ってグループＧＡＤ又はＧＢＣに入れられる。
【００６２】
このようにして、動的グラフ内の各ノードは、接続変更が動的グラフに適用されたことに応答して、動的グラフ内の各ノードの移動を生じさせた主要理由に従って、即ち、各ノードの移動を生じさせた対応する主要接続変更に従って様々なグループにグループ化される。
【００６３】
ステップ３：マルチ・ステージ・アニメーション・プランニング
本ステップは、アニメーションのマルチ・ステージ・デモンストレーションをステップ２で取得されるノード・グループに従ってプランニングする。即ち、グラフ中の同じグループ内のノード移動は、一緒にアニメーション・デモンストレーションされるようにプランニングされ、異なるグループ内のノード移動は、ノード移動を生じさせた主要理由がより明確に表示されるよう異なる時点でアニメーション・デモンストレーションされるようにプランニングされる。異なるグループ内のノード移動のアニメーション・デモンストレーションの相対時間は、状況に応じて異なる可能性がある。図７は、すべてのグループのノード移動が並行してアニメーション・デモンストレーションされる場合、即ち、複数の接続変更に起因するすべてのグループのノード移動が同時にアニメーション・デモンストレーションされる場合を示す。これは事実上、すべてのノード移動を同時にデモンストレーションする従来技術のアプローチであり、この場合はグラフ変更の詳細が失われ、グラフ変更の因果関係を開示することができない。図８は、異なるグループ内のノード移動が１つずつアニメーション・デモンストレーションされる場合、即ち、前のグループのノード移動のアニメーション・デモンストレーションが完了した後に、次のグループのノード移動が直ちにアニメーション・デモンストレーションされる場合を示す。このようなアプローチでは、グラフ変更の詳細を維持し、グラフ変更の因果関係を開示することが可能となる。しかしながら、このアプローチの欠点は、ノード重複が発生する可能性があることである。即ち、あるグループのノードの移動がアニメーション・デモンストレーションされるときに、そのグループ内のいくつかのノードの位置が他のノードの位置と重複する可能性があり、それ故視覚的な混乱が生じる恐れがある。したがって、ノード移動をグループ単位でアニメーション・デモンストレーションすると同時にノード位置の重複を可能な限り回避することが必要とされる。
【００６４】
このため、本発明の他の実施形態は更に、各グループのノードの移動時に発生するノード位置の重複を検出するステップと、あるグループのノード位置の移動中に別のグループのノード位置との重複が発生したときに、当該別のグループのノードの移動が直ちに開始されるようにアニメーション・デモンストレーションをプランニングするステップと、を含む。図９は、ノード位置の重複が検出されたときに、次のグループのノードの移動が直ちに開始される場合を示す図である。当業者には理解されるように、動的グラフ内の各ノードの初期位置は既知であり、各ノードのターゲット位置も上述のステップで適切なレイアウト・アルゴリズムを適用することによって取得済みであり、また、選択された経路計算方法（例えば後述の力指向的（force-directed）アニメーション・モデル）に従って、各ノードの初期位置からターゲット位置までの移動経路を計算することができ、それ故各ノードが移動中に他のノードと重複するかどうか、重複する場合はいつ重複が起きるかを検出することが可能となる。
【００６５】
各グループのノード移動のアニメーション・デモンストレーションを具体的にプランニングするために、各ノードの初期位置とターゲット位置との間の移動経路を解決する必要がある。各ノードの初期位置とターゲット位置との間の移動経路は、様々な方法を使用して計算することができ、例えば、各ノードの移動経路は、単純に線形補間法を使用することにより、各ノードの初期位置及び最終位置に従って計算することができる。より良い方法は、各ノードの移動経路を力指向的アニメーション・モデルを使用して計算することである。力指向的アニメーション・モデルの目的は、力場の消費エネルギーが最小となる曲線経路を発見することである。具体的に、このモデルでは、ある接続によって結合される各ノード対についてばね力が指定され、互いに分離又は接続される各ノード対について普遍的な斥力（universal expulsionforce）が指定され、各ノードについて当該ノードが最終的にターゲット位置に移動し得ることを保証する可変外力Ｆが指定され、ノードの移動時に発生するエネルギー消費量｜｜Ｆ｜｜２が最小化される。このモデルは、関係制約最適化問題に変換することによって解くことができる。
【００６６】
例えば、ノードの移動経路は、以下の制約最適化方程式を作成することによって計算することができる。
【数６】
【００６７】
上式で、ｔ０はノード移動の開始時間、ｔ１はノード移動の終了時間、ｔは時間変数、Ｆｉはノードｉが受ける可変力、ｆｉｊはノードｉとｊの間のばね力、Ｅは動的グラフ内の辺の集合、ｐｉｊはｉ及びｊから成る任意のノード対間の斥力、ｍｉはノードｉの重要度、Ｘｉはノードｉの位置、ｋ１はばね力とノード移動速度との間の関係を表す係数、ｋ２は斥力とノード移動速度との間の関係を表す係数、Ｉｎｉｔｉａｌはノードｉの初期位置、Ｆｉｎａｌはノードｉの最終位置である。当業者には周知のとおり、上記の各方程式は、離散方程式を使用して上式中の偏微分方程式を置き換え、有限差分法及び逐次２次計画法（Sequential QuadraticProgramming）を使用して解くことができ、その結果ノードｉの移動経路が取得される。図１０は、上記の方法を使用して得られる力場内の初期位置Ａからターゲット位置Ｂまでのノードの移動経路を概略的に示す。各ノード・グループ内の各ノードの移動経路が上記の方法を使用して計算されると、各グループのノード移動のアニメーション・デモンストレーションを具体的にプランニングすることが可能となる。
【００６８】
上記では、本発明の一実施形態に係る動的グラフ用アニメーション・プランニング方法について説明したが、上記の説明は単なる例示であり、本発明を限定するものではないことを指摘しておきたい。例えば、上記では接続を追加する場合を一例として本発明について説明したが、本発明は、動的グラフの接続を減少させる場合にも適しており、また、動的グラフの接続追加及び接続減少を同時に実行する場合にも適している。これらの場合において、本発明の方法は、減少対象接続と追加対象接続とを均一に処理する。即ち、追加対象接続の場合であれ減少対象接続の場合であれ、各ノードは、それらの接続によって直接接続されるキー・ノード、及び他のノードとキー・ノードとの間の相関に従ってグループ化され、それらのノード・グループに従ってアニメーション・デモンストレーションがプランニングされる。
【００６９】
本発明は更に、上述した動的グラフ用アニメーション・プランニング方法を実行するのに使用され得る動的グラフ用アニメーション・プランニング装置も提供する。以下では動的グラフ用アニメーション・プランニング装置の概要のみを説明し、本装置の詳細情報に関しては上記の説明を参照していただきたい。
【００７０】
本発明の一実施形態によれば、動的グラフ用アニメーション・プランニング装置は、動的グラフ内の接続変更が適用されたことに応答して、前記動的グラフ内のノードと、前記動的グラフ内の各変更接続が直接接続されるノードを指すキー・ノードとの間の相関に従って前記動的グラフ内のノードを様々なノード・グループにグループ化するグループ化モジュールと、前記接続変更に起因するノード移動のアニメーション・デモンストレーションを前記ノード・グループによってプランニングするプランニング・モジュールと、を備える。
【００７１】
本発明の一実施形態によれば、前記グループ化モジュールは、前記動的グラフ内の各非キー・ノードと各キー・ノードとの間の相関を計算する計算サブ・モジュールと、各非キー・ノードと各キー・ノードとの間の前記相関を比較することによって各非キー・ノードとの間の相関が最も大きいキー・ノードを取得する比較サブ・モジュールと、各非キー・ノードを、それ自体との相関が最も大きいキー・ノードが存在するノード・グループにグループ化するグループ化サブ・モジュールと、を備える。
【００７２】
本発明の一実施形態によれば、２つのノード間の相関は、前記２つのノード間の各経路内の各辺の重みに依存する。
【００７３】
本発明の一実施形態によれば、前記装置は、前記ノード移動中に発生する前記ノード・グループ内のノードと他のノードとの位置重複を検出する重複検出モジュールを更に備え、前記プランニング・モジュールは、前記ノード移動中に前記ノード・グループ内のノードと別のノード・グループ内のノードとの位置重複が発生したときに、前記別のノード・グループ内の前記ノードの移動が直ちに開始されるように前記ノード移動の前記アニメーション・デモンストレーションをプランニングする手段を備える。
【００７４】
本発明の一実施形態によれば、前記プランニング・モジュールは、前記接続変更が適用される前に前記動的グラフ内の各ノードの初期位置を取得し、前記接続変更が適用された後に各ノードのターゲット位置を取得する手段と、前記初期位置と前記ターゲット位置との間の各ノードの移動経路を力指向的アニメーション・モデルを使用して計算する手段と、を備え、前記力指向的アニメーション・モデルは、直接接続されるノードから成る各ノード対間のばね力と、各ノード対間の斥力と、各ノードの移動を推進する可変力と、を含み、力場内の消費エネルギーが最小となる曲線経路を発見するモデルである。
【００７５】
本発明は、ハードウェア、ソフトウェア、あるいはハードウェアとソフトウェアの組合せの形で実現することができる。本発明は、１つのコンピュータ・システムにおいて集中的な構成で実現することも、様々な構成要素がいくつかの相互接続コンピュータ・システムに分散される分散的な構成で実現することもできる。本明細書に記載の方法を実行するのに適した任意のコンピュータ・システム又は他の装置を利用することが可能である。ハードウェアとソフトウェアの典型的な組合せは、それ自体がロードされ実行されたときにコンピュータ・システムによって本発明の方法が実行され本発明の装置が構成されるように制御するコンピュータ・プログラムを備えたコンピュータ・システムである可能性がある。
【００７６】
本発明は、本明細書に記載される方法のすべての特徴を実現し、それ自体がコンピュータ・システムにロードされたときに当該方法を実行することが可能なコンピュータ・プログラムの形で実施することもできる。
【００７７】
以上、本発明を好ましい諸実施形態に関して図示し説明してきたが、本発明の形態及び詳細には本発明の趣旨及び範囲を逸脱しない限り様々な変更を加えることができることが、当業者には理解されるであろう。
【符号の説明】
【００７８】
ｅＡＤ、ｅＢＣ 追加される接続
【特許請求の範囲】
【請求項１】
動的グラフ用アニメーション・プランニング方法であって、
動的グラフ内のノード変更が適用されたことに応答して、変更ノードと既存ノードとの間の関係に従って前記変更ノードをアトミック・パーティションにグループ化するステップと、
前記アトミック・パーティション間のクラスタリング距離に従って、前記動的グラフ内のノード変更のアニメーション・デモンストレーションをプランニングするランニング・リストであって、アトミック・パーティション・クラスタ又はアトミック・パーティションあるいはその両方を要素として含むランニング・リストが生成されるように、前記アトミック・パーティションをクラスタリングするステップと、
を含む方法。
【請求項２】
前記要素のスクリーン位置及び前記要素の重要度に従って、前記ランニング・リスト内の前記要素のアニメーション・デモンストレーション順序をソートするステップ
を更に含む、請求項１に記載の方法。
【請求項３】
前記変更ノードを前記アトミック・パーティションにグループ化する前記ステップは、
各変更ノードについて、当該ノードが前記動的グラフ内の既存ノードと接続される最短経路内で重みが最も大きい経路を取得し、前記経路によって接続される前記動的グラフ内の前記既存ノードを前記変更ノードのキー・ノードとするステップと、
同じキー・ノードを有する前記変更ノードを同じアトミック・パーティションにグループ化するステップと、
を含む、請求項１に記載の方法。
【請求項４】
前記アトミック・パーティション間のクラスタリング距離に従って、前記動的グラフ内のノード変更のアニメーション・デモンストレーションをプランニングするランニング・リストが生成されるように前記アトミック・パーティションをクラスタリングする前記ステップは、
それ自体の重要度が重要度閾値に達した又はそれを超えた前記アトミック・パーティション又はクラスタを前記ランニング・リストに転送するステップと、
それらの間の前記クラスタリング距離が距離閾値よりも小さい２つのアトミック・パーティション又はクラスタをクラスタリングするステップと、
他の任意のアトミック・パーティション又はクラスタとの間の前記クラスタリング距離が前記距離閾値以上である前記アトミック・パーティション又はクラスタを前記ランニング・リストに転送するステップと、
を含み、
前記各ステップは、すべての前記アトミック・パーティションがアトミック・パーティション又はクラスタの一部として前記ランニング・リストに入れられるまで繰り返し実行される、
請求項１に記載の方法。
【請求項５】
２つのアトミック・パーティション又はクラスタ間の前記クラスタリング距離は、
前記２つのアトミック・パーティション又はクラスタ間のジオメトリ距離、
前記２つのアトミック・パーティション又はクラスタ同士を接続する辺の数、及び
前記２つのアトミック・パーティション又はクラスタの組合せの重要度、
のうちの１つ又は複数に依存する、請求項４に記載の方法。
【請求項６】
アトミック・パーティション又はクラスタの重要度は、前記アトミック・パーティション又はクラスタに含まれるノードの重要度に依存し、ノードの重要度は、前記ノードの次数中心性、近接中心性、媒介中心性、及び固有ベクトル中心性のうちの１つ又は複数に依存する、請求項４に記載の方法。
【請求項７】
動的グラフ用アニメーション・プランニング装置であって、
動的グラフ内のノード変更が適用されたことに応答して、変更ノードと既存ノードとの間の関係に従って前記変更ノードをアトミック・パーティションにグループ化するアトミック・パーティショニング・モジュールと、
前記アトミック・パーティション間のクラスタリング距離に従って、前記動的グラフ内のノード変更のアニメーション・デモンストレーションをプランニングするランニング・リストであって、アトミック・パーティション・クラスタ又はアトミック・パーティションあるいはその両方を要素として含むランニング・リストが生成されるように、前記アトミック・パーティションをクラスタリングするクラスタリング・モジュールと、
を備える装置。
【請求項８】
前記要素のスクリーン位置及び前記要素の重要度に従って、前記ランニング・リスト内の前記要素のアニメーション・デモンストレーション順序をソートするソート・モジュール
を更に備える、請求項７に記載の装置。
【請求項９】
前記アトミック・パーティショニング・モジュールは、
各変更ノードについて、当該ノードが前記動的グラフ内の既存ノードと接続される最短経路内で重みが最も大きい経路を取得し、前記経路によって接続される前記動的グラフ内の前記既存ノードを前記変更ノードのキー・ノードとする手段と、
同じキー・ノードを有する前記変更ノードを同じアトミック・パーティションにグループ化する手段と、
を備える請求項７に記載の装置。
【請求項１０】
前記クラスタリング・モジュールは、
それ自体の重要度が重要度閾値に達した又はそれを超えた前記アトミック・パーティション又はクラスタを前記ランニング・リストに転送する手段と、
それらの間の前記クラスタリング距離が距離閾値よりも小さい２つのアトミック・パーティション又はクラスタをクラスタリングする手段と、
他の任意のアトミック・パーティション又はクラスタとの間の前記クラスタリング距離が前記距離閾値以上である前記アトミック・パーティション又はクラスタを前記ランニング・リストに転送する手段と、
を備え、
すべての前記アトミック・パーティションがアトミック・パーティション又はクラスタの一部として前記ランニング・リストに入れられるまで繰り返し実行される、
請求項７に記載の装置。
【請求項１１】
２つのアトミック・パーティション又はクラスタ間の前記クラスタリング距離は、
前記２つのアトミック・パーティション又はクラスタ間のジオメトリ距離、
前記２つのアトミック・パーティション又はクラスタ同士を接続する辺の数、及び
前記２つのアトミック・パーティション又はクラスタの組合せの重要度、
のうちの１つ又は複数に依存する、請求項１０に記載の装置。
【請求項１２】
アトミック・パーティション又はクラスタの重要度は、前記アトミック・パーティション又はクラスタに含まれるノードの重要度に依存し、ノードの重要度は、前記ノードの次数中心性、近接中心性、媒介中心性、及び固有ベクトル中心性のうちの１つ又は複数に依存する、請求項１０に記載の装置。
【請求項１３】
動的グラフ用アニメーション・プランニング方法であって、
動的グラフ内の接続変更が適用されたことに応答して、前記動的グラフ内のノードと、各変更接続が直接接続されるノードを指すキー・ノードとの間の相関に従って前記動的グラフ内のノードを様々なノード・グループにグループ化するステップと、
前記接続変更に起因するノード移動のアニメーション・デモンストレーションを前記ノード・グループによってプランニングするステップと、
を含む方法。
【請求項１４】
前記動的グラフ内のノードと前記キー・ノードとの間の相関に従って前記動的グラフ内のノードを様々なノード・グループにグループ化する前記ステップは、
前記動的グラフ内の各非キー・ノードと各キー・ノードとの間の相関を計算するステップと、
各非キー・ノードと各キー・ノードとの間の前記相関を比較することによって各非キー・ノードとの間の相関が最も大きいキー・ノードを取得するステップと、
各非キー・ノードを、それ自体との相関が最も大きいキー・ノードが存在するノード・グループにグループ化するステップと、
を含む、請求項１３に記載の方法。
【請求項１５】
２つのノード間の相関は、前記２つのノード間の各経路内の各辺の重みに依存する、請求項１３に記載の方法。
【請求項１６】
前記ノード移動中に発生する前記ノード・グループ内のノードと他のノードとの位置重複を検出するステップを更に含み、前記接続変更に起因する前記ノード移動の前記アニメーション・デモンストレーションを前記ノード・グループによってプランニングする前記ステップは、
前記ノード移動中に前記ノード・グループ内のノードと別のノード・グループ内のノードとの位置重複が発生したときに、前記別のノード・グループ内の前記ノードの移動が直ちに開始されるように前記ノード移動の前記アニメーション・デモンストレーションをプランニングするステップ
を含む、請求項１３に記載の方法。
【請求項１７】
前記接続変更に起因する前記ノード移動の前記アニメーション・デモンストレーションを前記ノード・グループによってプランニングする前記ステップは、
前記接続変更が適用される前に前記動的グラフ内の各ノードの初期位置を取得し、前記接続変更が適用された後にターゲット位置を取得するステップと、
前記初期位置と前記ターゲット位置との間の各ノードの移動経路を力指向的アニメーション・モデルを使用して計算するステップと、
を含み、
前記力指向的アニメーション・モデルは、直接接続されるノードから成る各ノード対間のばね力と、各ノード対間の斥力と、各ノードの移動を推進する可変力と、を含み、力場内の消費エネルギーが最小となる曲線経路を発見するモデルである、
請求項１３に記載の方法。
【請求項１８】
動的グラフ用アニメーション・プランニング装置であって、
動的グラフ内の接続変更が適用されたことに応答して、前記動的グラフ内のノードと、各変更接続が直接接続されるノードを指すキー・ノードとの間の相関に従って前記動的グラフ内のノードを様々なノード・グループにグループ化するグループ化モジュールと、
前記接続変更に起因するノード移動のアニメーション・デモンストレーションを前記ノード・グループによってプランニングするプランニング・モジュールと、
を備える装置。
【請求項１９】
前記グループ化モジュールは、
前記動的グラフ内の各非キー・ノードと各キー・ノードとの間の相関を計算する計算サブ・モジュールと、
各非キー・ノードと各キー・ノードとの間の前記相関を比較することによって各非キー・ノードとの間の相関が最も大きいキー・ノードを取得する比較サブ・モジュールと、
各非キー・ノードを、それ自体との相関が最も大きいキー・ノードが存在するノード・グループにグループ化するグループ化サブ・モジュールと、
を備える、請求項１８に記載の装置。
【請求項２０】
２つのノード間の相関は、前記２つのノード間の各経路内の各辺の重みに依存する、請求項１８に記載の装置。
【請求項２１】
前記ノード移動中に発生する前記ノード・グループ内のノードと他のノードとの位置重複を検出する重複検出モジュールを更に備え、前記プランニング・モジュールは、
前記ノード移動中に前記ノード・グループ内のノードと別のノード・グループ内のノードとの位置重複が発生したときに、前記別のノード・グループ内の前記ノードの移動が直ちに開始されるように前記ノード移動の前記アニメーション・デモンストレーションをプランニングする手段
を備える、請求項１８に記載の装置。
【請求項２２】
前記プランニング・モジュールは、
前記接続変更が適用される前に前記動的グラフ内の各ノードの初期位置を取得し、前記接続変更が適用された後にターゲット位置を取得する手段と、
前記初期位置と前記ターゲット位置との間の各ノードの移動経路を力指向的アニメーション・モデルを使用して計算する手段と、
を備え、
前記力指向的アニメーション・モデルは、直接接続されるノードから成る各ノード対間のばね力と、各ノード対間の斥力と、各ノードの移動を推進する可変力と、を含み、力場内の消費エネルギーが最小となる曲線経路を発見するモデルである、
請求項１８に記載の装置。
【請求項１】
動的グラフ用アニメーション・プランニング方法であって、
動的グラフ内のノード変更が適用されたことに応答して、変更ノードと既存ノードとの間の関係に従って前記変更ノードをアトミック・パーティションにグループ化するステップと、
前記アトミック・パーティション間のクラスタリング距離に従って、前記動的グラフ内のノード変更のアニメーション・デモンストレーションをプランニングするランニング・リストであって、アトミック・パーティション・クラスタ又はアトミック・パーティションあるいはその両方を要素として含むランニング・リストが生成されるように、前記アトミック・パーティションをクラスタリングするステップと、
を含む方法。
【請求項２】
前記要素のスクリーン位置及び前記要素の重要度に従って、前記ランニング・リスト内の前記要素のアニメーション・デモンストレーション順序をソートするステップ
を更に含む、請求項１に記載の方法。
【請求項３】
前記変更ノードを前記アトミック・パーティションにグループ化する前記ステップは、
各変更ノードについて、当該ノードが前記動的グラフ内の既存ノードと接続される最短経路内で重みが最も大きい経路を取得し、前記経路によって接続される前記動的グラフ内の前記既存ノードを前記変更ノードのキー・ノードとするステップと、
同じキー・ノードを有する前記変更ノードを同じアトミック・パーティションにグループ化するステップと、
を含む、請求項１に記載の方法。
【請求項４】
前記アトミック・パーティション間のクラスタリング距離に従って、前記動的グラフ内のノード変更のアニメーション・デモンストレーションをプランニングするランニング・リストが生成されるように前記アトミック・パーティションをクラスタリングする前記ステップは、
それ自体の重要度が重要度閾値に達した又はそれを超えた前記アトミック・パーティション又はクラスタを前記ランニング・リストに転送するステップと、
それらの間の前記クラスタリング距離が距離閾値よりも小さい２つのアトミック・パーティション又はクラスタをクラスタリングするステップと、
他の任意のアトミック・パーティション又はクラスタとの間の前記クラスタリング距離が前記距離閾値以上である前記アトミック・パーティション又はクラスタを前記ランニング・リストに転送するステップと、
を含み、
前記各ステップは、すべての前記アトミック・パーティションがアトミック・パーティション又はクラスタの一部として前記ランニング・リストに入れられるまで繰り返し実行される、
請求項１に記載の方法。
【請求項５】
２つのアトミック・パーティション又はクラスタ間の前記クラスタリング距離は、
前記２つのアトミック・パーティション又はクラスタ間のジオメトリ距離、
前記２つのアトミック・パーティション又はクラスタ同士を接続する辺の数、及び
前記２つのアトミック・パーティション又はクラスタの組合せの重要度、
のうちの１つ又は複数に依存する、請求項４に記載の方法。
【請求項６】
アトミック・パーティション又はクラスタの重要度は、前記アトミック・パーティション又はクラスタに含まれるノードの重要度に依存し、ノードの重要度は、前記ノードの次数中心性、近接中心性、媒介中心性、及び固有ベクトル中心性のうちの１つ又は複数に依存する、請求項４に記載の方法。
【請求項７】
動的グラフ用アニメーション・プランニング装置であって、
動的グラフ内のノード変更が適用されたことに応答して、変更ノードと既存ノードとの間の関係に従って前記変更ノードをアトミック・パーティションにグループ化するアトミック・パーティショニング・モジュールと、
前記アトミック・パーティション間のクラスタリング距離に従って、前記動的グラフ内のノード変更のアニメーション・デモンストレーションをプランニングするランニング・リストであって、アトミック・パーティション・クラスタ又はアトミック・パーティションあるいはその両方を要素として含むランニング・リストが生成されるように、前記アトミック・パーティションをクラスタリングするクラスタリング・モジュールと、
を備える装置。
【請求項８】
前記要素のスクリーン位置及び前記要素の重要度に従って、前記ランニング・リスト内の前記要素のアニメーション・デモンストレーション順序をソートするソート・モジュール
を更に備える、請求項７に記載の装置。
【請求項９】
前記アトミック・パーティショニング・モジュールは、
各変更ノードについて、当該ノードが前記動的グラフ内の既存ノードと接続される最短経路内で重みが最も大きい経路を取得し、前記経路によって接続される前記動的グラフ内の前記既存ノードを前記変更ノードのキー・ノードとする手段と、
同じキー・ノードを有する前記変更ノードを同じアトミック・パーティションにグループ化する手段と、
を備える請求項７に記載の装置。
【請求項１０】
前記クラスタリング・モジュールは、
それ自体の重要度が重要度閾値に達した又はそれを超えた前記アトミック・パーティション又はクラスタを前記ランニング・リストに転送する手段と、
それらの間の前記クラスタリング距離が距離閾値よりも小さい２つのアトミック・パーティション又はクラスタをクラスタリングする手段と、
他の任意のアトミック・パーティション又はクラスタとの間の前記クラスタリング距離が前記距離閾値以上である前記アトミック・パーティション又はクラスタを前記ランニング・リストに転送する手段と、
を備え、
すべての前記アトミック・パーティションがアトミック・パーティション又はクラスタの一部として前記ランニング・リストに入れられるまで繰り返し実行される、
請求項７に記載の装置。
【請求項１１】
２つのアトミック・パーティション又はクラスタ間の前記クラスタリング距離は、
前記２つのアトミック・パーティション又はクラスタ間のジオメトリ距離、
前記２つのアトミック・パーティション又はクラスタ同士を接続する辺の数、及び
前記２つのアトミック・パーティション又はクラスタの組合せの重要度、
のうちの１つ又は複数に依存する、請求項１０に記載の装置。
【請求項１２】
アトミック・パーティション又はクラスタの重要度は、前記アトミック・パーティション又はクラスタに含まれるノードの重要度に依存し、ノードの重要度は、前記ノードの次数中心性、近接中心性、媒介中心性、及び固有ベクトル中心性のうちの１つ又は複数に依存する、請求項１０に記載の装置。
【請求項１３】
動的グラフ用アニメーション・プランニング方法であって、
動的グラフ内の接続変更が適用されたことに応答して、前記動的グラフ内のノードと、各変更接続が直接接続されるノードを指すキー・ノードとの間の相関に従って前記動的グラフ内のノードを様々なノード・グループにグループ化するステップと、
前記接続変更に起因するノード移動のアニメーション・デモンストレーションを前記ノード・グループによってプランニングするステップと、
を含む方法。
【請求項１４】
前記動的グラフ内のノードと前記キー・ノードとの間の相関に従って前記動的グラフ内のノードを様々なノード・グループにグループ化する前記ステップは、
前記動的グラフ内の各非キー・ノードと各キー・ノードとの間の相関を計算するステップと、
各非キー・ノードと各キー・ノードとの間の前記相関を比較することによって各非キー・ノードとの間の相関が最も大きいキー・ノードを取得するステップと、
各非キー・ノードを、それ自体との相関が最も大きいキー・ノードが存在するノード・グループにグループ化するステップと、
を含む、請求項１３に記載の方法。
【請求項１５】
２つのノード間の相関は、前記２つのノード間の各経路内の各辺の重みに依存する、請求項１３に記載の方法。
【請求項１６】
前記ノード移動中に発生する前記ノード・グループ内のノードと他のノードとの位置重複を検出するステップを更に含み、前記接続変更に起因する前記ノード移動の前記アニメーション・デモンストレーションを前記ノード・グループによってプランニングする前記ステップは、
前記ノード移動中に前記ノード・グループ内のノードと別のノード・グループ内のノードとの位置重複が発生したときに、前記別のノード・グループ内の前記ノードの移動が直ちに開始されるように前記ノード移動の前記アニメーション・デモンストレーションをプランニングするステップ
を含む、請求項１３に記載の方法。
【請求項１７】
前記接続変更に起因する前記ノード移動の前記アニメーション・デモンストレーションを前記ノード・グループによってプランニングする前記ステップは、
前記接続変更が適用される前に前記動的グラフ内の各ノードの初期位置を取得し、前記接続変更が適用された後にターゲット位置を取得するステップと、
前記初期位置と前記ターゲット位置との間の各ノードの移動経路を力指向的アニメーション・モデルを使用して計算するステップと、
を含み、
前記力指向的アニメーション・モデルは、直接接続されるノードから成る各ノード対間のばね力と、各ノード対間の斥力と、各ノードの移動を推進する可変力と、を含み、力場内の消費エネルギーが最小となる曲線経路を発見するモデルである、
請求項１３に記載の方法。
【請求項１８】
動的グラフ用アニメーション・プランニング装置であって、
動的グラフ内の接続変更が適用されたことに応答して、前記動的グラフ内のノードと、各変更接続が直接接続されるノードを指すキー・ノードとの間の相関に従って前記動的グラフ内のノードを様々なノード・グループにグループ化するグループ化モジュールと、
前記接続変更に起因するノード移動のアニメーション・デモンストレーションを前記ノード・グループによってプランニングするプランニング・モジュールと、
を備える装置。
【請求項１９】
前記グループ化モジュールは、
前記動的グラフ内の各非キー・ノードと各キー・ノードとの間の相関を計算する計算サブ・モジュールと、
各非キー・ノードと各キー・ノードとの間の前記相関を比較することによって各非キー・ノードとの間の相関が最も大きいキー・ノードを取得する比較サブ・モジュールと、
各非キー・ノードを、それ自体との相関が最も大きいキー・ノードが存在するノード・グループにグループ化するグループ化サブ・モジュールと、
を備える、請求項１８に記載の装置。
【請求項２０】
２つのノード間の相関は、前記２つのノード間の各経路内の各辺の重みに依存する、請求項１８に記載の装置。
【請求項２１】
前記ノード移動中に発生する前記ノード・グループ内のノードと他のノードとの位置重複を検出する重複検出モジュールを更に備え、前記プランニング・モジュールは、
前記ノード移動中に前記ノード・グループ内のノードと別のノード・グループ内のノードとの位置重複が発生したときに、前記別のノード・グループ内の前記ノードの移動が直ちに開始されるように前記ノード移動の前記アニメーション・デモンストレーションをプランニングする手段
を備える、請求項１８に記載の装置。
【請求項２２】
前記プランニング・モジュールは、
前記接続変更が適用される前に前記動的グラフ内の各ノードの初期位置を取得し、前記接続変更が適用された後にターゲット位置を取得する手段と、
前記初期位置と前記ターゲット位置との間の各ノードの移動経路を力指向的アニメーション・モデルを使用して計算する手段と、
を備え、
前記力指向的アニメーション・モデルは、直接接続されるノードから成る各ノード対間のばね力と、各ノード対間の斥力と、各ノードの移動を推進する可変力と、を含み、力場内の消費エネルギーが最小となる曲線経路を発見するモデルである、
請求項１８に記載の装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２０１０−２６２６４６（Ｐ２０１０−２６２６４６Ａ）
【公開日】平成２２年１１月１８日（２０１０．１１．１８）
【国際特許分類】
【出願番号】特願２０１０−１００５５５（Ｐ２０１０−１００５５５）
【出願日】平成２２年４月２６日（２０１０．４．２６）
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
【公開日】平成２２年１１月１８日（２０１０．１１．１８）
【国際特許分類】
【出願日】平成２２年４月２６日（２０１０．４．２６）
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
[ Back to top ]