分断された動的ネットワークのための表示領域におけるレイアウト方法およびシステム
【課題】複数のグラフ・コンポーネントを含む分断された動的ネットワークのために表示領域においてレイアウトを行う方法を提供する。
【解決手段】方法は、複数のグラフ・コンポーネントをそれらの重要度に従ってソートするステップと、ソートされた複数のグラフ・コンポーネントを第１サブセットＳ１および第２サブセットＳ２に、それらの重要度の順に従って分割するために第１分割を行うステップであって、第１サブセットＳ１は少なくとも最も重要なグラフ・コンポーネントを含む、ステップと、前記第１サブセットＳ１を上位サブセットＣｐおよび下位サブセットＣｍに、それらの重要度の順に従って分割するために第２分割を行うステップを含む。
【解決手段】方法は、複数のグラフ・コンポーネントをそれらの重要度に従ってソートするステップと、ソートされた複数のグラフ・コンポーネントを第１サブセットＳ１および第２サブセットＳ２に、それらの重要度の順に従って分割するために第１分割を行うステップであって、第１サブセットＳ１は少なくとも最も重要なグラフ・コンポーネントを含む、ステップと、前記第１サブセットＳ１を上位サブセットＣｐおよび下位サブセットＣｍに、それらの重要度の順に従って分割するために第２分割を行うステップを含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、可視化に関し、特に、本発明は、分断された動的ネットワーク（disconnected dynamicnetwork）のための表示領域におけるレイアウト方法およびシステムに関する。
【背景技術】
【０００２】
社会的ネットワーク、インターネット、及び金融ネットワーク等のようなネットワーク・データセットは、多くの分野において広範に利用可能である。ネットワーク内の関係を実証する有効な技術の1つとして、グラフが長い間研究されてきたし、ユーザがこれらのネットワーク・データセットにおいて興味あるパターンを見つけ出すのを助けるために、多くのレイアウト方法および有用な対話型ツールが提案されている。最近、実生活における多くのネットワークが徐々に変化しているので、益々多くの注目が動的ネットワークに移りつつある。従来の方法は、静的ネットワークに対してはうまく作用するが、動的ネットワークに対しては、時間的コヒーレンスを保つことが出来ず、フレーム間の安定した遷移を示すことができない。従って、レイアウト・アルゴリズムおよびアニメーション技術の両方を考察することによって、動的ネットワークの更新を安定的に且つ円滑的に可視化するための幾つもの方法が設計されている。
【０００３】
しかし、分断された動的なネットワーク、即ち、最も人気のあるタイプのネットワークにとって、上述の可視化方法は、下記のような大きな挑戦事項である新たな挑戦事項を惹起するので、直接採用することができない。第１に、ネットワーク内の分断されたコンポーネントを、それらが動的に変化しつつある場合には言うまでもなく、それらが静的であるとき、スクリーン上に明瞭に且つ情報提供可能にレイアウトすることは極めて難しい。第２に、表示された多数のコンポーネントの変化を円滑的に且つ安定的に保つことも非常に難しい。現在の位置と前の位置との間の移動を単に最小にする場合、いくつかのコンポーネントが或る時間フレーム内でマージされるとき、それは大きな部分的重複を引き起こすことがある。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
従って、本発明の目的は、上記の問題点に対処する方法およびシステムを提供することにある。
【課題を解決するための手段】
【０００５】
本発明の一側面によれば、複数のグラフ・コンポーネントを含む分断された動的ネットワークのために表示領域においてレイアウトを行う方法が提供される。その方法は、複数のグラフ・コンポーネントをそれらの重要度に従ってソートするステップと、そのソートされた複数のグラフ・コンポーネントを第１サブセットＳ１および第２サブセットＳ２に、それらの重要度の順に従って分割するために第１分割を行うステップであって、第１サブセットＳ１は少なくとも最も重要なグラフ・コンポーネントを含む、ステップと、第１サブセットＳ１を上位サブセットＣｐおよび下位サブセットＣｍに、それらの重要度の順に従って分割するために第２分割を行うステップであって、上位サブセットＣｐは最も重要なグラフ・コンポーネントのみを含む、ステップと、第１サブセットＳ１および第２サブセットＳ２の重要度の値に従って比例的に表示領域を表示部分Ｓ１'およびＳ２'に分割するステップと、上位サブセットＣｐおよび下位サブセットＣｍの重要度の値に従って比例的に表示部分Ｓ１’ を表示部分Ｃｐ' およびＣｍ'に分割するステップと、表示部分Ｃｐ’ のアスペクト比が１に近くなるまで、第１分割および第２分割、並びに表示領域の対応する分割を反復的に実行するステップとを含む。
【０００６】
本発明の別の側面によれば、そのレイアウト方法は、第２サブセットＳ２を左サブセットＣｌおよび右サブセットＣｒに分割するために第３分割を行うステップであって、左サブセットＣlの重要度は右サブセットＣｒの重要度に近い、ステップと、表示部分Ｃｐ'およびＣｍ'以外の表示部分を左サブセットＣｌおよび右サブセットＣｒの重要度の値に従って比例的に表示部分Ｃｌ'およびＣr'に分割するステップとを更に含む。
【０００７】
本発明の別の側面によれば、分断された動的ネットワークのために表示領域においてレイアウトを行うシステムが提供される。そのシステムは、複数のグラフ・コンポーネントをそれらの重要度に従ってソートするためのコンポーネント・ソート手段と、ソートされた複数のグラフ・コンポーネントを第１サブセットＳ１および第２サブセットＳ２に、それらの重要度の順に従って分割するために第１分割を行うための第１分割手段であって、第１サブセットＳ１は少なくとも最も重要なグラフ・コンポーネントを含む、第１分割手段と、第１サブセットＳ１を上位サブセットＣｐおよび下位サブセットＣｍに、それらの重要度の順に従って分割するために第２分割を行うための第２分割手段であって、上位サブセットＣｐは最も重要なグラフ・コンポーネントのみを含む、第２分割手段と、第１サブセットＳ１および第２サブセットＳ２の重要度の値に従って比例的に表示領域を表示部分Ｓ１'およびＳ２'に分割するための第１表示領域分割手段と、上位サブセットＣｐおよび下位サブセットＣｍの重要度の値に従って比例的に表示部分Ｓ１'を表示部分Ｃｐ'およびＣｍ'に分割するための第２表示領域分割手段と、表示部分Ｃｐ'のアスペクト比が１に近くなるまで、第１分割および第２分割、並びに表示領域の対応する分割を反復的に実行するための実行手段とを含む。
【０００８】
本発明の更に別の側面によれば、分断された動的ネットワークのために表示領域においてレイアウトを行うシステムは、第２サブセットＳ２を左サブセットＣｌおよび右サブセットＣｒに分割するための第３分割手段であって、左サブセットＣlの重要度は右サブセットＣｒの重要度に近い、第３分割手段と、表示部分Ｃｐ'およびＣｍ'以外の表示部分を左サブセットＣｌおよび右サブセットＣｒの重要度の値に従って比例的に表示部分Ｃｌ'およびＣｒ'に分割するための第３表示部分分割手段とを更に含む。
【０００９】
本発明による方法およびシステムを利用することによって、ネットワーク内の分断されたコンポーネントのスクリーンにおけるレイアウトが明瞭になり且つ情報提供可能になると同時に、動的ネットワークの更新が安定的且つ円滑的に示される。
【図面の簡単な説明】
【００１０】
【図１】グラフを使用して、分断された動的ネットワークの一例を示す概略図である。
【図２】本発明に従って、分断された動的ネットワークのための表示領域における例示的なレイアウト方法を示すフローチャートである。
【図３】本発明のレイアウト方法による表示領域の分割結果を示す概略図である。
【図４】本発明のレイアウト方法による表示領域の分割結果を示す概略図である。
【図５】本発明のレイアウト方法による表示領域の分割結果を示す概略図である。
【図６】本発明の実施例による表示領域の分割結果を示す概略図である。
【図７】本発明の実施例による表示領域の分割結果を示す概略図である。
【図８】図７の表示領域の分割に対応するトリプル・ツリー構造の概略図である。
【図９】本発明による分断された動的ネットワークのための表示領域における例示的なレイアウト・システムを表わす概略図である。
【図１０】本発明を適用し得るコンピュータ・システムの構造を示すブロック図である。
【発明を実施するための形態】
【００１１】
以下では、図面を参照して本発明の実施例を説明する。下記の説明では、本発明が十分に理解されるよう、多数の特定の細部を説明する。しかし、本発明の実施態様がこれらの特定の細部を持たないことがあり得るということは当業者には明らかであろう。更に、本発明が、本明細書において開示された特定の実施例に限定されないということも当然である。その代わりに、下記の特徴および要素の任意の組合せを使用することは、それらが種々の実施例に関与しているかどうかに関係なく、本発明を具現化することを意図する。従って、下記の特徴事項、機能、実施態様、および利点は単に説明のために使用されるものであり、「特許請求の範囲」に明瞭に示されてなければ、発明の構成要素または定義と見なされるべきではない。
【００１２】
便宜上、当業者には知られているが本発明には含まれないコンポーネントおよびプロセスに関する表示および記述は、図面および明細書において省略されているということに留意されたい。
【００１３】
次に、図１を参照すると、分断された動的ネットワークの一例がグラフを使って示される。 図１において、破線のボックスは、分断された動的ネットワークのグラフ・コンポーネントを表わす。図１における破線のボックスは、単にグラフ・コンポーネントを示すためのものであり、ネットワークを可視化する際に表示または隠蔽されることが可能であるということに留意されたい。
【００１４】
本発明の基本概念は、分断された動的ネットワークの各グラフ・コンポーネントを、それぞれ、独立したパッキング・セルの各々に組み入れることである。なお、パッキング・セルは表示領域の最適な区画です。
【００１５】
本発明の基本概念に従って、先ず、相互に独立している多数のパッキング・セルを形成するように表示領域が分割される。複数のパッキング・セルは、それぞれ、分断された動的ネットワークのグラフ・コンポーネントを表示するために使用される。表示領域を分割するとき、下記の要件の少なくとも１つが考慮されなければならない。
（１）比較的高い重要度を持つグラフ・コンポーネントがより大きい表示領域を占めなければならない。
（２）個々の独立したパッキング・セルのアスペクト比ができるだけ１に近くなければならない。
（３）最も高い重要度を持つグラフ・コンポーネントが表示領域の中心を占めなければならない。
（４）レイアウトは、分断された動的ネットワークが徐々に発展するとき、グラフ・コンポーネントの変化が安定的に且つ円滑的に示されるという要求を考慮しなければならない。
【００１６】
上記の要件を考慮すると、図１におけるレイアウトは良好な例ではない。
【００１７】
次に、図２を参照すると、本発明による分断された動的ネットワークのための表示領域における例示的なレイアウト方法が示される。図２の方法２００はステップ２０２から開始する。次のステップ２０４において、複数のグラフ・コンポーネントをそれらの重要度に従ってソートする。しかる後、ステップ２０６において、そのソートされた複数のグラフ・コンポーネントを第１サブセットＳ１および第２サブセットＳ２に、それらの重要度の順に従って分割するために、第１分割が行なわれる。この場合、第１サブセットＳ１は少なくとも最も重要なグラフ・コンポーネントを含む。しかる後、ステップ２０８において、第１サブセットＳ１を上位サブセットＣｐおよび下位サブセットＣｍに、それらの重要度の順に従って分割するために第２分割が行なわれる。この場合、上位サブセットＣｐは最も重要なグラフ・コンポーネントだけを含む。次のステップ２１０において、第１サブセットＳ１および第２サブセットＳ２の重要度の値に従って比例的に表示領域を表示部分Ｓ１'およびＳ２'に分割する。しかる後、ステップ２１２において、上位サブセットＣｐおよび下位サブセットＣｍの重要度の値に従って比例的に表示部分Ｓ１'を表示部分Ｃｐ'およびＣｍ'に分割する。しかる後、ステップ２１４において、表示部分Ｃｐ'のアスペクト比が１に近くなるまで、第１分割、第２分割、および表示領域の対応する分割を反復的に実行する。サブセットへのグラフ・コンポーネントの分割が行なわれた後に表示領域の分割を行うことも可能となる、ということは当業者には明らかであろう。
【００１８】
説明の便宜上、データセットを使用することによって上記の方法を説明する。分断された動的ネットワークが本明細書では複数のグラフ・コンポーネントc０, c１,・・・、cｎを含むものと仮定すると、それはデータセットＣ＝{c０,c１,・・・、cｎ}として記述されるであろう。この場合、ｎは整数である。分断された動的ネットワークのグラフ・コンポーネントは、それらの重要度に従って降順にソートされ、従って、ソートされたグラフ・コンポーネント・セットが得られ、ここではＣ＝{cｉ|i∈[0,n]}として参照される。この場合、ｎは整数であり、複数のグラフ・コンポーネントの重要度の順は、c０>c１>・・・>cｎである。しかる後、そのソートされた複数のグラフ・コンポーネントＣ＝{cｉ|∈i[0,n]}を重要度に従って第１サブセットＳ１＝{cｉ|i∈[0,k]}および第２サブセットＳ２＝{cｉ|i∈[k+1,n]}に分割するために第１分割が行なわれる。なお、ｎ>ｋ>＝０であり、ｋは整数である。しかる後、第１サブセットＳ１＝{cｉ|i∈[0,k]}をそれらの重要度の順に従って上位サブセットＣｐ＝{c０}および下位サブセットＣｍ＝{Ｓ１・Ｃｐ}に分割するために第２分割が行なわれる。しかる後、表示領域が、第１サブセットＳ１および第２サブセットＳ２の重要度の値に従って比例的に表示部分Ｓ１'およびＳ２'に分割され、表示部分Ｓ１'が上位サブセットＣｐおよび下位サブセットＣｍの重要度の値に従って比例的に表示部分Ｃｐ'およびＣｍ'に分割される。表示部分Ｃｐ'のアスペクト比が１に近づくまで、第１分割、第２分割、および表示領域の対応する分割が反復的に行なわれる。望ましくは、その分割の反復的実行に対してｎ/２>ｋ>＝０ が使用され、従って、その計算の半分が節約される。本明細書で説明される分割は、分断された動的ネットワークの対応するグラフ・コンポーネントの重要度に従って表示領域を分割することである。先ず、最も重要なグラフ・コンポーネントが分割され、その分割が行なわれるときにはいつも、最も重要なグラフ・コンポーネントのための表示部分のアスペクト比が計算される。しかる後、最も重要なグラフ・コンポーネントに対する表示部分のアスペクト比が１に近くなる場合の分割がその表示領域の最終分割として選ばれる。重要度をパラメータとして使用する反復的実行によって、（１）高い重要度を有するグラフ・コンポーネントは大きい表示領域を占めなければならない、および（２）各独立したパッキング・セルのアスペクト比はできるだけ１に近くなければならない、という要件が満たされる。分断された動的ネットワークのグラフ・コンポーネントの重要度を考慮すると、分断された動的ネットワークのレイアウトおよび構造の焦点を、従来技術に比べてより明瞭に示すことが可能となる。
【００１９】
次に、図３乃至図５を用いて表示領域の分割の結果を説明する。ここでは、分断された動的ネットワークには６個のグラフ・コンポーネントが存在するものと仮定すると、降順でソートした後のネットワークのグラフ・コンポーネントを表わすためにグラフ・コンポーネント・セットＣ＝{cｉ|i∈[0,n]}が使用される。この場合、ｉ＝６であり、各グラフ・コンポーネントに対する重要度の順は、c０>c１>、・・・、>c６である。各グラフ・コンポーネントの重要度を表わすためにウェイト・セットＷ＝{wｉ|i∈[0,n]}が使用される。この場合、ｉ＝６である。上述した実施例に従って、グラフ・コンポーネント・セットＣ＝{cｉ|i∈[0,n]}に対して第１分割が行なわれる。グラフ・コンポーネント・セットＣ＝{cｉ|i∈[0,n]}が、サブセットＳ１＝{cｉ|i∈[0,k]}およびＳ２＝{cｉ|i∈[k+1,n]}に分割される。この場合、ｎ>ｋ>＝0 およびｋは整数である。ｋ＝０であるとき、Ｓ１＝{c０}およびＳ２＝{c１、c２、c３、c４、c５、c６}である。表示領域がサブセットＳ１およびＳ２の重要度の値に従って比例的に分割され、従って、表示部分Ｓ１'およびＳ２'が形成される。サブセットＳ１およびＳ２のウェイトが、Ｗ１＝{w０}およびＷ２＝{w１,w２, w３, w４, w５, w６}であるので、表示部分Ｓ１'およびＳ２'は、図３に示されるようにサブセットＳ１およびＳ２の重要度の値に従って、即ち、Ｓ１'＝Ｗ１/（Ｗ１+Ｗ２）およびＳ２'＝Ｗ２/（Ｗ１+Ｗ２）に分割される。図３では、表示領域は、垂直に表示部分Ｓ１'およびＳ２'に分割される。これは単に例示的な分割であるということに留意されたい。表示領域が水平に表示部分Ｓ１'およびＳ２'に分割され得るということは当業者には明らかであろう。しかる後、サブセットＳ１の第２分割が行われ、サブセットＣｐ＝{c０}およびＣｍ＝{Ｓ１・Ｃｐ}を形成する。ｋ＝０であるとき、Ｃｐ＝{c０}およびＣｍ＝{0}である。Ｃｍ＝{0}であるので、表示部分Ｓ１'はそのまま変わらない。即ち、その結果は、図３に示されたものと同じままである。しかる後、ｎ/２>ｋ>＝０を用いて上記の方法が反復的に実行される。ｋ＝１であるとき、Ｓ１＝{c０, c１}であり、Ｓ２＝{c２,c３, c4, c５、c５}である。サブセットＳ１およびＳ２の重要度の値に従って比例的に表示領域が分割され、従って、表示部分Ｓ１'およびＳ２'が形成される。サブセットＳ１およびＳ２のウェイトはＷ１＝{w０,w１}およびＷ２＝{w２, w３, w４, w５,w６}であるので、表示部分Ｓ１'およびＳ２'は、図４に示されるように、サブセットＳ１およびＳ２の重要度の値に従って、即ち、Ｓ１'＝Ｗ１/(Ｗ１+Ｗ２)およびＳ２'＝Ｗ２/(Ｗ１+Ｗ２)に分割される。しかる後、サブセットＳ１の第２分割が行われ、サブセットＣｐ＝{c０}およびＣｍ＝{Ｓ１・Ｃｐ}を形成する。ｋ＝１であるとき、Ｃｐ＝{c０}およびＣｍ＝{c１}である。表示部分Ｓ１'は、サブセットＣｐおよびＣｍの重要度の値に従って比例的に分割される。従って、表示部分Ｃｐ'およびＣｍ'が形成される。サブセットＣｐおよびＣｍのウェイトが、Ｗｐ＝{w０}およびＷｍ＝{w１}であるので、表示部分Ｃｐ'およびＣｍ'は、図４に示されるように、サブセットＣｐおよびＣｍの重要度の値に従って、即ち、Ｃｐ'＝Ｗｐ/(Ｗｐ+Ｗｍ)およびＣｍ'＝Ｗｍ/(Ｗｐ+Ｗｍ)に分割される。図４に示されるように、表示部分Ｃｐ'のアクペクト比はＲｐ＝Ｗｐ/Ｗ１である。従って、ｋの別の値に対するＲｐを計算することが可能である。ｎ/２>ｋ>＝０を用いて（本明細書における例に関しては、ｋ＝０,１,２,３を用いて）その方法を反復的に実行した後、Ｃｐ'のアスペクト比Ｒｐが１近くなる分割が、分断された動的ネットワークに対する最良のレイアウトとして選ばれる。ここでは、Ｃｐ'のアスペクト比Ｒｐが１近くなる分割を行うｋの値は、分断された動的ネットワークのレイアウトに対するパラメータとして選ばれ、ｑ１と呼ばれる。例えば、ｋ＝２である場合、Ｃｐ'のアスペクト比Ｒｐが１に近いＲｐ＝Ｗｐ/Ｗ１＝０.９９となり、図５に示されるように、ｋ＝２が、分断された動的ネットワークのレイアウトに対するパラメータ、即ち、ｑ１＝２として、選ばれる。
【００２０】
本発明の別の実施例によれば、Ｓ２＝{cｉ|i∈[k+1,n]}が重要度の順に従って分割されてサブセットＣlおよびＣrを形成する第３分割が行われ、更に、サブセットＣｌおよびＣｒの重要度の値に従って比例的に表示領域が分割され、従って表示部分Ｃｐ'およびＣｍ'が形成される。以下で、その第３分割を説明する。先ず、Ｓ２＝{cｉ|i∈[k+1,n]}が、サブセットＣl＝{cｉ|i∈[q1+1,j]}およびＣｒ＝{cｉ|i∈[j+1,n]}に、ｊ＝ｑ１＋１からｊ＝ｎ−１まで反復的に分割される第３分割が行われ、ＣｌおよびＣｒを作るｊの値が、最も類似したアスペクト比を有すること、即ち、Ｃｌ'およびＣｒ'が占める表示領域が近接していることを見つけ、そのｊの値がｑ２として記録される。次に、Ｃｐ、Ｃｍ、ＣｌおよびＣｒに対応する表示部分Ｃｐ'、Ｃｍ'、Ｃｌ'、およびＣｒ'のレイアウトが図６に示される。ここでは、最も高い重要度を有するグラフ・コンポーネントが表示領域の中央を占めるべきであるという要求が満たされ、Ｃｌ'およびＣｒ'が各側において垂直方向にある。ここでは、分断された動的ネットワークに６個のグラフ・コンポーネントがあるものと仮定する。サブセットＣｐ、Ｃｍ、Ｃｌ、およびＣｒは、トリプル・ツリー構造Ｔを構成し、その構造では、ツリーのルート・ノードＣｐがそれで３本のサブ・ツリー、即ち、中心サブ・ツリーＣｍ、左サブ・ツリーＣｌ、および右サブ・ツリーＣｒを有し、その各々がそれぞれの表示部分に対応する。次に、左サブ・ツリーＣｌおよび右サブ・ツリーＣｒを分割するために第４分割が行なわれる。その分割は、ＣｌおよびＣｒの分割がそれらに最も類似したアスペクト比を持たせるｊの値をｑ２'が表わす場合、下記のルールに従って行なわれる。
【００２１】
幅が表示部分Ｃｍ'、Ｃｌ'、またはＣｒ'の高さよりも大きい場合、下側サブセットＣｍ、左サブセットＣｌ、または右サブセットＣrに対して、各サブセットに１つのグラフ・コンポーネントしか残らなくなるまで、第１分割、第２分割、および第３分割が反復的に行われる。幅が表示部分Ｃｍ'、Ｃｌ'、またはＣｒ'の高さよりも小さい場合、表示部分Ｃｍ'、Ｃl'、またはＣｒ'が９０度回転され、しかる後、下側サブセットＣｍ、左サブセットＣｌ、または右サブセットＣｒに対して、各サブセットに１つのグラフ・コンポーネントしか残らなくなるまで、第１分割、第２分割、および第３分割が反復的に行われる。次に、図６に関連して、幅が表示部分Ｃｌ'の高さより大きい場合、左サブセットＣｌに対して第１分割、第２分割、および第３分割が反復的に行われ、幅が表示部分Ｃｌ'の高さよりも小さい場合、表示部分Ｃｌ'が９０度回転させられ、しかる後、左サブセットＣｌに対して第１分割、第２分割、および第３分割が反復的に行われる。幅が表示部分Ｃｒ'の高さよりも大きい場合、右サブセットＣｒに対して第１分割、第２分割、および第３分割が反復的に行われ、幅が表示部分Ｃｒ'の高さよりも小さい場合、表示部分Ｃｒ'が９０度回転させられ、しかる後、右サブセットＣｒに対して第１分割、第２分割、および第３分割が反復的に行われる。
【００２２】
更に詳しく言えば、左サブ・ツリーＣｌに対して、
（１）幅が、左サブ・ツリーＣｌに対応する表示部分Ｃｌ'の高さよりも大きい場合、ＣlがＣｌ’＝{cｉ|i∈[q1+1,n]}およびＣｒ’＝{0}に、即ち、ｑ２'＝ｎに分割され、しかる後、それが左サブ・ツリーであるので第２分割が行なわれる。
（２）幅が、左サブ・ツリーＣｌに対応する表示部分Ｃｌ'の高さよりも小さい場合、ＣｌがＣｌ’＝{0}およびＣｒ’＝{cｉ|i∈[q1+1,n]}に、即ち、ｑ２'＝ｑ１に分割され、しかる後、それが右サブ・ツリーであるので第２分割が行なわれる。
【００２３】
右サブ・ツリーＣｒに対して、
（１）幅が、右サブ・ツリーＣｒに対応する表示部分Ｃｒ'の高さよりも大きい場合、ＣｒがＣｌ’＝{0}およびＣｒ’＝{cｉ|i∈[q1+1,n]}に、即ち、ｑ２'＝ｑ１に分割され、しかる後、それが右サブ・ツリーであるので第３分割が行なわれる。
（２）幅が、右サブ・ツリーＣｒに対応する表示部分Ｃｒ'の高さよりも小さい場合、ＣｒがＣｌ’＝{cｉ|i∈[q1+1,n]}およびＣｒ’＝{0}に、即ち、ｑ２'＝ｎに分割され、しかる後、それが左サブ・ツリーであるので第３分割が行なわれる。
【００２４】
トリプル・ツリーＴに対応するルート・ノードｔが作成される。そこにはｑ１およびｑ２が記録される。ＴがデータセットＣと相関させられる。対応する空のサブ・ツリー・ノードtl、tｍ、およびtrが作成され、それらがＣｌ、Ｃｍ、およびＣｒと相関させられる。それらが空でない場合、中央のサブ・ツリーＣｍ、左サブ・ツリーＣｌ、および右サブ・ツリーＣrに対する分割が上記の基準に基づいて反復的に行なわれ、すべてのグラフ・コンポーネントが正しい位置に置かれるまで、即ち、レイアウトが完了するまで、表示領域の対応する分割が行なわれる。更に、一例として、６個のグラフ・コンポーネントを有する分断されたネットワークを使用すると、図８に示されたトリプル・ツリー構造と共に本発明の方法を使った結果として、レイアウトは図７に示されたものと同じように見えるであろう。
【００２５】
サブセットＣｌおよびＣｒのウェイトに従って表示部分Ｃｌ’およびＣｒ’を形成するための表示部分の分割は、サブセットＳ１およびＳ２のウェイトに従って表示部分Ｓ１'およびＳ２'を形成するための表示領域の分割、およびサブセットＣｐおよびＣｍのウェイトに従って表示部分Ｃｐ’およびＣｍ’を形成するための表示部分の分割、即ち、グラフ・コンポーネントのウェイトを使用した分割と同じであり、従って、本明細書では更なる詳細な説明は行なわれない。
【００２６】
本発明の上記方法を実施した後、表示部分Ｃｐ'は表示領域の中央にあり、Ｃｍ'はＣｐ'の下にあり、Ｃｌ'およびＣｒ'はＣｐ'の左側およびＣｐ'の右側にある。
【００２７】
次に、図９を参照すると、本発明による分断された動的ネットワークのための表示領域における例示的なレイアウト・システム６００が示される。システム６００は、複数のグラフ・コンポーネントをそれらの重要度に従ってソートするためのコンポーネント・ソート手段６０２と、そのソートされた複数のグラフ・コンポーネントを、それらの重要度の順に従って、少なくとも最も重要なグラフ・コンポーネントを含む第１サブセットＳ１および第２サブセットＳ２に分割する第１分割を行うための第１分割手段６０４と、第１サブセットＳ１をそれらの重要度の順に従って、最も重要なグラフ・コンポーネントだけを含む上位サブセットＣｐおよび下位サブセットＣｍに分割する第２分割を行うための第２分割手段６０６と、第１サブセットＳ１および第２サブセットＳ２の重要度の値に従って比例的に表示領域を表示部分Ｓ１'およびＳ２'に分割するための第１表示領域分割手段６０８と、上位サブセットＣｐおよび下位サブセットＣｍの重要度の値に従って比例的に表示部分Ｓ１'を表示部分Ｃｐ'およびＣｍ'に分割するための第２表示領域分割手段６１０と、表示部分Ｃｐ'のアスペクト比が１に近くなるまで、第１分割、第２分割、および表示領域の対応する分割を反復的に実行するための実行手段６１２を含む。
【００２８】
以下では、本発明による分断された動的ネットワークの更新方法を説明する。前述したように、サブセットＣｐ、Ｃｍ、ＣｌおよびＣｒがトリプル・ツリー構造Ｔを形成した。この構造Ｔでは、ルート・ノードＣｐが、３本のサブ・ツリー、即ち、中央のサブ・ツリーＣｍ、左のサブ・ツリーＣｌおよび右のサブ・ツリーＣrを有する。そのようなトリプル・ツリーは、最新の反復的レイアウト情報を保管している。グラフ・コンポーネントcｉが削除される場合、トリプル・ツリー構造Ｔにおける対応するノードtｉが見つけられ、そのノードtｉが削除される。しかる後、cｉの親ノードが見つけられ、その見つけられたツリー・ノードのｑ１およびｑ２が１を減じられる。グラフ・コンポーネントcｉが加えられる場合、cｉが加えられるべきロケーションに従ってcｉの親ノードが見つけられ、しかる後、その見つけられたツリー・ノードのｑ１およびｑ２が１を加えられる。グラフ・コンポーネントcｉが動く場合、（１）オリジナル・ロケーションにおいてcｉが削除され、（２）新しいロケーションにおいてcｉが加えられる。
【００２９】
更新されたｑ１およびｑ２、並びに更新されたトリプル・ツリー構造Ｔを使用することにより、このレイアウト方法が再び利用されて新しいデータセットＣ'を新しいサブセットＣｐ、Ｃｌ、Ｃｍ、およびＣｒに分割し、新しいサブセットＣｐ、Ｃｌ、Ｃｍ、およびＣｒに従って表示領域を分割することができる。
【００３０】
再び、分断された動的ネットワークが、例えば、６個のグラフ・コンポーネントを含むものとし、最後の反復のレイアウトが図７に示され、対応するトリプル・ツリー構造Ｔが図８に示されるものと仮定する。
【００３１】
ルート・ノードc０、を有するトリプル・ツリー構造に対してｑ１＝２およびｑ２＝４であり、ルート・ノードＣ３を有するトリプル・ツリー構造に対してｑ２＝３およびｑ１は存在せず（Ｃ３のＣｍおよびＣlが空であるため）、ルート・ノードＣ１を有するトリプル・ツリー構造に対してｑ２＝１、ｑ１は存在せず（Ｃ１のＣｍおよびＣｒが空であるため）、ルート・ノードＣ５を有するトリプル・ツリー構造に対してｑ２＝５、ｑ１は存在しない（Ｃ５のＣｍおよびＣrが空であるため）。
【００３２】
グラフ・コンポーネントc３が上記の更新方法に従って削除される場合、先ず、トリプル・ツリー構造における対応するノードt３が見つけられ、それ（c３に対応する）が削除され、次に、t３の親ノード（ここではノードc０）が見つけられる。しかる後、見つかったツリー・ノードのｑ１およびｑ２が１を減じられる、即ち、ルート・ノードc０を有するトリプル・ツリー構造に対してｑ１＝１およびｑ２＝３にされる。しかる後、更新されたｑ１およびｑ２を使用して、新しいデータセットが分割される。その例に関しては、データセットＣ'＝{c０,c１, c２, c４, c５, c６}に対してｑ１＝１および、ｑ２＝３が使用されて（ここではｑ２＝３がc４に対応する）、そのデータセットおよび対応する表示領域を分割する。従って、その分割の後、Ｃｐ＝{c０}、Ｃｍ＝{c１}、Ｃｌ＝{c２,c４}およびＣｒ＝{c５, c６}となる。
【００３３】
本発明の基本原理を上記の実施例に関連して説明している。しかし、基本的なプログラミング技術を有する当業者が本発明の明細書を読むことによって、本発明の装置および方法のそれぞれの又はいずれのステップ又はコンポーネントも、任意のコンピューティング装置（プロセッサ、記憶媒体等を含む）またはコンピューティング装置のネットワークにおいて、ハードウェア、ファームウェア、ソフトウェア、またはそれらの組合せを用いて具現化し得るということは当業者には明らかであろう。
【００３４】
従って、任意のコンピューティング装置においてプログラム或いは一連のプログラムを実行することによって、本発明の目的を具現化することが可能である。コンピューティング装置は既知の汎用装置であってもよい。従って、本発明の方法または装置を具現化するプログラム・コードを提供するプログラム製品を通して本発明の目的を具現化することも可能である。即ち、そのようなプログラム製品も本発明を構成し、そのようなプログラム製品を記憶した記憶媒体も本発明を構成する。明らかに、その記憶媒体は、任意の既知の記憶媒体または今後開発される任意の記憶媒体であってもよい。
【００３５】
ソフトウェアおよび／またはファームウェアによって本発明の実施例を具現化する場合、そのソフトウェアを構成するプログラムは、記憶媒体またはネットワークから、専用のハードウェアを有するコンピュータ、例えば、図１０に示されるような汎用パーソナル・コンピュータ７００にインストールされてもよく、そのコンピュータは、そこに種々のプログラムがインストールされた場合、種々の機能を遂行することが可能である。
【００３６】
図１０において、中央処理装置（ＣＰＵ）７０１は、リード・オンリ・メモリ（ＲＯＭ）７０２に格納されたプログラムまたは記憶セクション７０８からランダム・アクセス・メモリ（ＲＡＭ）７０３にロードされたプログラムに基づいて種々の処理を行う。ＲＡＭ７０３では、ＣＰＵ７０１が種々の処理等を行うときに必要なデータも必要に応じて保存される。ＣＰＵ７０１、ＲＯＭ７０２、およびＲＡＭ７０３は、バス７０４を介して相互に接続される。入出力インタフェース７０５もバス７０４に接続される。
【００３７】
入出力インタフェース７０５には下記のコンポーネント、即ち、キーボード、マウス等を含む入力セクション７０６、 陰極線管（ＣＲＴ）、液晶ディスプレイ（ＬＣＤ）等のようなディスプレイおよびスピーカ等を含む出力セクション７０７、ハード・ディスク等を含む記憶装置セクション７０８、並びにＬＡＮカード、モデム等のようなネットワーク・インターフェース・カードを含む通信セクション７０９が接続される。通信セクション７０９は、インターネットのようなネットワークを介して通信処理を行う。
【００３８】
ドライブ７１０も、必要に応じて、入出力インタフェース７０５に接続される。磁気ディスク、光ディスク、光磁気ディスク、半導体メモリ等のような取外し可能媒体７１１が、必要に応じて、ドライブ７１０にインストールされ、その結果、そこから読まれたコンピュータ・プログラムが、必要に応じて、記憶装置セクション７０８にインストールされ得る。
【００３９】
上記の一連の処理がソフトウェアで具現化される場合、そのソフトウェアを構成するプログラムが、インターネットのようなネットワークまたは取外し可能媒体７１１のような記憶媒体からインストールされてもよい。
【００４０】
記憶媒体は、図１０に示されるようにプログラムを格納され、そのプログラムを提供する装置からユーザに個別に配布される取外し可能媒体７１１に限定されない、ということは当業者には明らかであろう。取外し可能媒体７１１の例は、磁気ディスク（フロッピ・ディスク（商標）を含む）、光ディスク（コンパクト・ディスク・リード・オンリ・メモリ（ＣＤ−ＲＯＭ）およびＤＶＤを含む）、光磁気ディスク（ミニ・ディスク（ＭＤ）（商標）を含む）、および半導体メモリを含む。それとは別に、記憶媒体は、ＲＯＭ７０２、記憶装置セクション７０８に内蔵されたハード・ディスク等であってもよく、それはプログラムをそこに格納され、それらを含む装置と共にユーザに配布されるものである。
【００４１】
本発明の装置および方法では、明らかに、コンポーネントまたはステップが分解され、および/または、再結合され得るということにも留意されたい。その分解および／または再結合は、本発明の等価な解決策であると考えるべきである。更に、上記の一連の処理を行うステップは自然な説明順に順次行なわれ得るが、必ずしもそのように行なわれなくてもよい。幾つかのステップが並行して行なわれてもよく、相互に無関係に行なわれてもよい。
【００４２】
本発明およびその利点を詳細に説明したが、種々の修正、結合、副次的結合、および代替が、それらが「特許請求の範囲」またはその均等物の範囲内にある限り、設計および他の要因次第で生じ得る、ということも当業者には明らかであろう。更に、「含む」という用語は、一連の要素を含むプロセス、方法、物、または装置がこれらの要素を含むのみならず、明示的に挙げられてない他の要素またはそれらに固有の他の要素も含み得るように、非排他的な包含もカバーすることを意図している。
【技術分野】
【０００１】
本発明は、可視化に関し、特に、本発明は、分断された動的ネットワーク（disconnected dynamicnetwork）のための表示領域におけるレイアウト方法およびシステムに関する。
【背景技術】
【０００２】
社会的ネットワーク、インターネット、及び金融ネットワーク等のようなネットワーク・データセットは、多くの分野において広範に利用可能である。ネットワーク内の関係を実証する有効な技術の1つとして、グラフが長い間研究されてきたし、ユーザがこれらのネットワーク・データセットにおいて興味あるパターンを見つけ出すのを助けるために、多くのレイアウト方法および有用な対話型ツールが提案されている。最近、実生活における多くのネットワークが徐々に変化しているので、益々多くの注目が動的ネットワークに移りつつある。従来の方法は、静的ネットワークに対してはうまく作用するが、動的ネットワークに対しては、時間的コヒーレンスを保つことが出来ず、フレーム間の安定した遷移を示すことができない。従って、レイアウト・アルゴリズムおよびアニメーション技術の両方を考察することによって、動的ネットワークの更新を安定的に且つ円滑的に可視化するための幾つもの方法が設計されている。
【０００３】
しかし、分断された動的なネットワーク、即ち、最も人気のあるタイプのネットワークにとって、上述の可視化方法は、下記のような大きな挑戦事項である新たな挑戦事項を惹起するので、直接採用することができない。第１に、ネットワーク内の分断されたコンポーネントを、それらが動的に変化しつつある場合には言うまでもなく、それらが静的であるとき、スクリーン上に明瞭に且つ情報提供可能にレイアウトすることは極めて難しい。第２に、表示された多数のコンポーネントの変化を円滑的に且つ安定的に保つことも非常に難しい。現在の位置と前の位置との間の移動を単に最小にする場合、いくつかのコンポーネントが或る時間フレーム内でマージされるとき、それは大きな部分的重複を引き起こすことがある。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
従って、本発明の目的は、上記の問題点に対処する方法およびシステムを提供することにある。
【課題を解決するための手段】
【０００５】
本発明の一側面によれば、複数のグラフ・コンポーネントを含む分断された動的ネットワークのために表示領域においてレイアウトを行う方法が提供される。その方法は、複数のグラフ・コンポーネントをそれらの重要度に従ってソートするステップと、そのソートされた複数のグラフ・コンポーネントを第１サブセットＳ１および第２サブセットＳ２に、それらの重要度の順に従って分割するために第１分割を行うステップであって、第１サブセットＳ１は少なくとも最も重要なグラフ・コンポーネントを含む、ステップと、第１サブセットＳ１を上位サブセットＣｐおよび下位サブセットＣｍに、それらの重要度の順に従って分割するために第２分割を行うステップであって、上位サブセットＣｐは最も重要なグラフ・コンポーネントのみを含む、ステップと、第１サブセットＳ１および第２サブセットＳ２の重要度の値に従って比例的に表示領域を表示部分Ｓ１'およびＳ２'に分割するステップと、上位サブセットＣｐおよび下位サブセットＣｍの重要度の値に従って比例的に表示部分Ｓ１’ を表示部分Ｃｐ' およびＣｍ'に分割するステップと、表示部分Ｃｐ’ のアスペクト比が１に近くなるまで、第１分割および第２分割、並びに表示領域の対応する分割を反復的に実行するステップとを含む。
【０００６】
本発明の別の側面によれば、そのレイアウト方法は、第２サブセットＳ２を左サブセットＣｌおよび右サブセットＣｒに分割するために第３分割を行うステップであって、左サブセットＣlの重要度は右サブセットＣｒの重要度に近い、ステップと、表示部分Ｃｐ'およびＣｍ'以外の表示部分を左サブセットＣｌおよび右サブセットＣｒの重要度の値に従って比例的に表示部分Ｃｌ'およびＣr'に分割するステップとを更に含む。
【０００７】
本発明の別の側面によれば、分断された動的ネットワークのために表示領域においてレイアウトを行うシステムが提供される。そのシステムは、複数のグラフ・コンポーネントをそれらの重要度に従ってソートするためのコンポーネント・ソート手段と、ソートされた複数のグラフ・コンポーネントを第１サブセットＳ１および第２サブセットＳ２に、それらの重要度の順に従って分割するために第１分割を行うための第１分割手段であって、第１サブセットＳ１は少なくとも最も重要なグラフ・コンポーネントを含む、第１分割手段と、第１サブセットＳ１を上位サブセットＣｐおよび下位サブセットＣｍに、それらの重要度の順に従って分割するために第２分割を行うための第２分割手段であって、上位サブセットＣｐは最も重要なグラフ・コンポーネントのみを含む、第２分割手段と、第１サブセットＳ１および第２サブセットＳ２の重要度の値に従って比例的に表示領域を表示部分Ｓ１'およびＳ２'に分割するための第１表示領域分割手段と、上位サブセットＣｐおよび下位サブセットＣｍの重要度の値に従って比例的に表示部分Ｓ１'を表示部分Ｃｐ'およびＣｍ'に分割するための第２表示領域分割手段と、表示部分Ｃｐ'のアスペクト比が１に近くなるまで、第１分割および第２分割、並びに表示領域の対応する分割を反復的に実行するための実行手段とを含む。
【０００８】
本発明の更に別の側面によれば、分断された動的ネットワークのために表示領域においてレイアウトを行うシステムは、第２サブセットＳ２を左サブセットＣｌおよび右サブセットＣｒに分割するための第３分割手段であって、左サブセットＣlの重要度は右サブセットＣｒの重要度に近い、第３分割手段と、表示部分Ｃｐ'およびＣｍ'以外の表示部分を左サブセットＣｌおよび右サブセットＣｒの重要度の値に従って比例的に表示部分Ｃｌ'およびＣｒ'に分割するための第３表示部分分割手段とを更に含む。
【０００９】
本発明による方法およびシステムを利用することによって、ネットワーク内の分断されたコンポーネントのスクリーンにおけるレイアウトが明瞭になり且つ情報提供可能になると同時に、動的ネットワークの更新が安定的且つ円滑的に示される。
【図面の簡単な説明】
【００１０】
【図１】グラフを使用して、分断された動的ネットワークの一例を示す概略図である。
【図２】本発明に従って、分断された動的ネットワークのための表示領域における例示的なレイアウト方法を示すフローチャートである。
【図３】本発明のレイアウト方法による表示領域の分割結果を示す概略図である。
【図４】本発明のレイアウト方法による表示領域の分割結果を示す概略図である。
【図５】本発明のレイアウト方法による表示領域の分割結果を示す概略図である。
【図６】本発明の実施例による表示領域の分割結果を示す概略図である。
【図７】本発明の実施例による表示領域の分割結果を示す概略図である。
【図８】図７の表示領域の分割に対応するトリプル・ツリー構造の概略図である。
【図９】本発明による分断された動的ネットワークのための表示領域における例示的なレイアウト・システムを表わす概略図である。
【図１０】本発明を適用し得るコンピュータ・システムの構造を示すブロック図である。
【発明を実施するための形態】
【００１１】
以下では、図面を参照して本発明の実施例を説明する。下記の説明では、本発明が十分に理解されるよう、多数の特定の細部を説明する。しかし、本発明の実施態様がこれらの特定の細部を持たないことがあり得るということは当業者には明らかであろう。更に、本発明が、本明細書において開示された特定の実施例に限定されないということも当然である。その代わりに、下記の特徴および要素の任意の組合せを使用することは、それらが種々の実施例に関与しているかどうかに関係なく、本発明を具現化することを意図する。従って、下記の特徴事項、機能、実施態様、および利点は単に説明のために使用されるものであり、「特許請求の範囲」に明瞭に示されてなければ、発明の構成要素または定義と見なされるべきではない。
【００１２】
便宜上、当業者には知られているが本発明には含まれないコンポーネントおよびプロセスに関する表示および記述は、図面および明細書において省略されているということに留意されたい。
【００１３】
次に、図１を参照すると、分断された動的ネットワークの一例がグラフを使って示される。 図１において、破線のボックスは、分断された動的ネットワークのグラフ・コンポーネントを表わす。図１における破線のボックスは、単にグラフ・コンポーネントを示すためのものであり、ネットワークを可視化する際に表示または隠蔽されることが可能であるということに留意されたい。
【００１４】
本発明の基本概念は、分断された動的ネットワークの各グラフ・コンポーネントを、それぞれ、独立したパッキング・セルの各々に組み入れることである。なお、パッキング・セルは表示領域の最適な区画です。
【００１５】
本発明の基本概念に従って、先ず、相互に独立している多数のパッキング・セルを形成するように表示領域が分割される。複数のパッキング・セルは、それぞれ、分断された動的ネットワークのグラフ・コンポーネントを表示するために使用される。表示領域を分割するとき、下記の要件の少なくとも１つが考慮されなければならない。
（１）比較的高い重要度を持つグラフ・コンポーネントがより大きい表示領域を占めなければならない。
（２）個々の独立したパッキング・セルのアスペクト比ができるだけ１に近くなければならない。
（３）最も高い重要度を持つグラフ・コンポーネントが表示領域の中心を占めなければならない。
（４）レイアウトは、分断された動的ネットワークが徐々に発展するとき、グラフ・コンポーネントの変化が安定的に且つ円滑的に示されるという要求を考慮しなければならない。
【００１６】
上記の要件を考慮すると、図１におけるレイアウトは良好な例ではない。
【００１７】
次に、図２を参照すると、本発明による分断された動的ネットワークのための表示領域における例示的なレイアウト方法が示される。図２の方法２００はステップ２０２から開始する。次のステップ２０４において、複数のグラフ・コンポーネントをそれらの重要度に従ってソートする。しかる後、ステップ２０６において、そのソートされた複数のグラフ・コンポーネントを第１サブセットＳ１および第２サブセットＳ２に、それらの重要度の順に従って分割するために、第１分割が行なわれる。この場合、第１サブセットＳ１は少なくとも最も重要なグラフ・コンポーネントを含む。しかる後、ステップ２０８において、第１サブセットＳ１を上位サブセットＣｐおよび下位サブセットＣｍに、それらの重要度の順に従って分割するために第２分割が行なわれる。この場合、上位サブセットＣｐは最も重要なグラフ・コンポーネントだけを含む。次のステップ２１０において、第１サブセットＳ１および第２サブセットＳ２の重要度の値に従って比例的に表示領域を表示部分Ｓ１'およびＳ２'に分割する。しかる後、ステップ２１２において、上位サブセットＣｐおよび下位サブセットＣｍの重要度の値に従って比例的に表示部分Ｓ１'を表示部分Ｃｐ'およびＣｍ'に分割する。しかる後、ステップ２１４において、表示部分Ｃｐ'のアスペクト比が１に近くなるまで、第１分割、第２分割、および表示領域の対応する分割を反復的に実行する。サブセットへのグラフ・コンポーネントの分割が行なわれた後に表示領域の分割を行うことも可能となる、ということは当業者には明らかであろう。
【００１８】
説明の便宜上、データセットを使用することによって上記の方法を説明する。分断された動的ネットワークが本明細書では複数のグラフ・コンポーネントc０, c１,・・・、cｎを含むものと仮定すると、それはデータセットＣ＝{c０,c１,・・・、cｎ}として記述されるであろう。この場合、ｎは整数である。分断された動的ネットワークのグラフ・コンポーネントは、それらの重要度に従って降順にソートされ、従って、ソートされたグラフ・コンポーネント・セットが得られ、ここではＣ＝{cｉ|i∈[0,n]}として参照される。この場合、ｎは整数であり、複数のグラフ・コンポーネントの重要度の順は、c０>c１>・・・>cｎである。しかる後、そのソートされた複数のグラフ・コンポーネントＣ＝{cｉ|∈i[0,n]}を重要度に従って第１サブセットＳ１＝{cｉ|i∈[0,k]}および第２サブセットＳ２＝{cｉ|i∈[k+1,n]}に分割するために第１分割が行なわれる。なお、ｎ>ｋ>＝０であり、ｋは整数である。しかる後、第１サブセットＳ１＝{cｉ|i∈[0,k]}をそれらの重要度の順に従って上位サブセットＣｐ＝{c０}および下位サブセットＣｍ＝{Ｓ１・Ｃｐ}に分割するために第２分割が行なわれる。しかる後、表示領域が、第１サブセットＳ１および第２サブセットＳ２の重要度の値に従って比例的に表示部分Ｓ１'およびＳ２'に分割され、表示部分Ｓ１'が上位サブセットＣｐおよび下位サブセットＣｍの重要度の値に従って比例的に表示部分Ｃｐ'およびＣｍ'に分割される。表示部分Ｃｐ'のアスペクト比が１に近づくまで、第１分割、第２分割、および表示領域の対応する分割が反復的に行なわれる。望ましくは、その分割の反復的実行に対してｎ/２>ｋ>＝０ が使用され、従って、その計算の半分が節約される。本明細書で説明される分割は、分断された動的ネットワークの対応するグラフ・コンポーネントの重要度に従って表示領域を分割することである。先ず、最も重要なグラフ・コンポーネントが分割され、その分割が行なわれるときにはいつも、最も重要なグラフ・コンポーネントのための表示部分のアスペクト比が計算される。しかる後、最も重要なグラフ・コンポーネントに対する表示部分のアスペクト比が１に近くなる場合の分割がその表示領域の最終分割として選ばれる。重要度をパラメータとして使用する反復的実行によって、（１）高い重要度を有するグラフ・コンポーネントは大きい表示領域を占めなければならない、および（２）各独立したパッキング・セルのアスペクト比はできるだけ１に近くなければならない、という要件が満たされる。分断された動的ネットワークのグラフ・コンポーネントの重要度を考慮すると、分断された動的ネットワークのレイアウトおよび構造の焦点を、従来技術に比べてより明瞭に示すことが可能となる。
【００１９】
次に、図３乃至図５を用いて表示領域の分割の結果を説明する。ここでは、分断された動的ネットワークには６個のグラフ・コンポーネントが存在するものと仮定すると、降順でソートした後のネットワークのグラフ・コンポーネントを表わすためにグラフ・コンポーネント・セットＣ＝{cｉ|i∈[0,n]}が使用される。この場合、ｉ＝６であり、各グラフ・コンポーネントに対する重要度の順は、c０>c１>、・・・、>c６である。各グラフ・コンポーネントの重要度を表わすためにウェイト・セットＷ＝{wｉ|i∈[0,n]}が使用される。この場合、ｉ＝６である。上述した実施例に従って、グラフ・コンポーネント・セットＣ＝{cｉ|i∈[0,n]}に対して第１分割が行なわれる。グラフ・コンポーネント・セットＣ＝{cｉ|i∈[0,n]}が、サブセットＳ１＝{cｉ|i∈[0,k]}およびＳ２＝{cｉ|i∈[k+1,n]}に分割される。この場合、ｎ>ｋ>＝0 およびｋは整数である。ｋ＝０であるとき、Ｓ１＝{c０}およびＳ２＝{c１、c２、c３、c４、c５、c６}である。表示領域がサブセットＳ１およびＳ２の重要度の値に従って比例的に分割され、従って、表示部分Ｓ１'およびＳ２'が形成される。サブセットＳ１およびＳ２のウェイトが、Ｗ１＝{w０}およびＷ２＝{w１,w２, w３, w４, w５, w６}であるので、表示部分Ｓ１'およびＳ２'は、図３に示されるようにサブセットＳ１およびＳ２の重要度の値に従って、即ち、Ｓ１'＝Ｗ１/（Ｗ１+Ｗ２）およびＳ２'＝Ｗ２/（Ｗ１+Ｗ２）に分割される。図３では、表示領域は、垂直に表示部分Ｓ１'およびＳ２'に分割される。これは単に例示的な分割であるということに留意されたい。表示領域が水平に表示部分Ｓ１'およびＳ２'に分割され得るということは当業者には明らかであろう。しかる後、サブセットＳ１の第２分割が行われ、サブセットＣｐ＝{c０}およびＣｍ＝{Ｓ１・Ｃｐ}を形成する。ｋ＝０であるとき、Ｃｐ＝{c０}およびＣｍ＝{0}である。Ｃｍ＝{0}であるので、表示部分Ｓ１'はそのまま変わらない。即ち、その結果は、図３に示されたものと同じままである。しかる後、ｎ/２>ｋ>＝０を用いて上記の方法が反復的に実行される。ｋ＝１であるとき、Ｓ１＝{c０, c１}であり、Ｓ２＝{c２,c３, c4, c５、c５}である。サブセットＳ１およびＳ２の重要度の値に従って比例的に表示領域が分割され、従って、表示部分Ｓ１'およびＳ２'が形成される。サブセットＳ１およびＳ２のウェイトはＷ１＝{w０,w１}およびＷ２＝{w２, w３, w４, w５,w６}であるので、表示部分Ｓ１'およびＳ２'は、図４に示されるように、サブセットＳ１およびＳ２の重要度の値に従って、即ち、Ｓ１'＝Ｗ１/(Ｗ１+Ｗ２)およびＳ２'＝Ｗ２/(Ｗ１+Ｗ２)に分割される。しかる後、サブセットＳ１の第２分割が行われ、サブセットＣｐ＝{c０}およびＣｍ＝{Ｓ１・Ｃｐ}を形成する。ｋ＝１であるとき、Ｃｐ＝{c０}およびＣｍ＝{c１}である。表示部分Ｓ１'は、サブセットＣｐおよびＣｍの重要度の値に従って比例的に分割される。従って、表示部分Ｃｐ'およびＣｍ'が形成される。サブセットＣｐおよびＣｍのウェイトが、Ｗｐ＝{w０}およびＷｍ＝{w１}であるので、表示部分Ｃｐ'およびＣｍ'は、図４に示されるように、サブセットＣｐおよびＣｍの重要度の値に従って、即ち、Ｃｐ'＝Ｗｐ/(Ｗｐ+Ｗｍ)およびＣｍ'＝Ｗｍ/(Ｗｐ+Ｗｍ)に分割される。図４に示されるように、表示部分Ｃｐ'のアクペクト比はＲｐ＝Ｗｐ/Ｗ１である。従って、ｋの別の値に対するＲｐを計算することが可能である。ｎ/２>ｋ>＝０を用いて（本明細書における例に関しては、ｋ＝０,１,２,３を用いて）その方法を反復的に実行した後、Ｃｐ'のアスペクト比Ｒｐが１近くなる分割が、分断された動的ネットワークに対する最良のレイアウトとして選ばれる。ここでは、Ｃｐ'のアスペクト比Ｒｐが１近くなる分割を行うｋの値は、分断された動的ネットワークのレイアウトに対するパラメータとして選ばれ、ｑ１と呼ばれる。例えば、ｋ＝２である場合、Ｃｐ'のアスペクト比Ｒｐが１に近いＲｐ＝Ｗｐ/Ｗ１＝０.９９となり、図５に示されるように、ｋ＝２が、分断された動的ネットワークのレイアウトに対するパラメータ、即ち、ｑ１＝２として、選ばれる。
【００２０】
本発明の別の実施例によれば、Ｓ２＝{cｉ|i∈[k+1,n]}が重要度の順に従って分割されてサブセットＣlおよびＣrを形成する第３分割が行われ、更に、サブセットＣｌおよびＣｒの重要度の値に従って比例的に表示領域が分割され、従って表示部分Ｃｐ'およびＣｍ'が形成される。以下で、その第３分割を説明する。先ず、Ｓ２＝{cｉ|i∈[k+1,n]}が、サブセットＣl＝{cｉ|i∈[q1+1,j]}およびＣｒ＝{cｉ|i∈[j+1,n]}に、ｊ＝ｑ１＋１からｊ＝ｎ−１まで反復的に分割される第３分割が行われ、ＣｌおよびＣｒを作るｊの値が、最も類似したアスペクト比を有すること、即ち、Ｃｌ'およびＣｒ'が占める表示領域が近接していることを見つけ、そのｊの値がｑ２として記録される。次に、Ｃｐ、Ｃｍ、ＣｌおよびＣｒに対応する表示部分Ｃｐ'、Ｃｍ'、Ｃｌ'、およびＣｒ'のレイアウトが図６に示される。ここでは、最も高い重要度を有するグラフ・コンポーネントが表示領域の中央を占めるべきであるという要求が満たされ、Ｃｌ'およびＣｒ'が各側において垂直方向にある。ここでは、分断された動的ネットワークに６個のグラフ・コンポーネントがあるものと仮定する。サブセットＣｐ、Ｃｍ、Ｃｌ、およびＣｒは、トリプル・ツリー構造Ｔを構成し、その構造では、ツリーのルート・ノードＣｐがそれで３本のサブ・ツリー、即ち、中心サブ・ツリーＣｍ、左サブ・ツリーＣｌ、および右サブ・ツリーＣｒを有し、その各々がそれぞれの表示部分に対応する。次に、左サブ・ツリーＣｌおよび右サブ・ツリーＣｒを分割するために第４分割が行なわれる。その分割は、ＣｌおよびＣｒの分割がそれらに最も類似したアスペクト比を持たせるｊの値をｑ２'が表わす場合、下記のルールに従って行なわれる。
【００２１】
幅が表示部分Ｃｍ'、Ｃｌ'、またはＣｒ'の高さよりも大きい場合、下側サブセットＣｍ、左サブセットＣｌ、または右サブセットＣrに対して、各サブセットに１つのグラフ・コンポーネントしか残らなくなるまで、第１分割、第２分割、および第３分割が反復的に行われる。幅が表示部分Ｃｍ'、Ｃｌ'、またはＣｒ'の高さよりも小さい場合、表示部分Ｃｍ'、Ｃl'、またはＣｒ'が９０度回転され、しかる後、下側サブセットＣｍ、左サブセットＣｌ、または右サブセットＣｒに対して、各サブセットに１つのグラフ・コンポーネントしか残らなくなるまで、第１分割、第２分割、および第３分割が反復的に行われる。次に、図６に関連して、幅が表示部分Ｃｌ'の高さより大きい場合、左サブセットＣｌに対して第１分割、第２分割、および第３分割が反復的に行われ、幅が表示部分Ｃｌ'の高さよりも小さい場合、表示部分Ｃｌ'が９０度回転させられ、しかる後、左サブセットＣｌに対して第１分割、第２分割、および第３分割が反復的に行われる。幅が表示部分Ｃｒ'の高さよりも大きい場合、右サブセットＣｒに対して第１分割、第２分割、および第３分割が反復的に行われ、幅が表示部分Ｃｒ'の高さよりも小さい場合、表示部分Ｃｒ'が９０度回転させられ、しかる後、右サブセットＣｒに対して第１分割、第２分割、および第３分割が反復的に行われる。
【００２２】
更に詳しく言えば、左サブ・ツリーＣｌに対して、
（１）幅が、左サブ・ツリーＣｌに対応する表示部分Ｃｌ'の高さよりも大きい場合、ＣlがＣｌ’＝{cｉ|i∈[q1+1,n]}およびＣｒ’＝{0}に、即ち、ｑ２'＝ｎに分割され、しかる後、それが左サブ・ツリーであるので第２分割が行なわれる。
（２）幅が、左サブ・ツリーＣｌに対応する表示部分Ｃｌ'の高さよりも小さい場合、ＣｌがＣｌ’＝{0}およびＣｒ’＝{cｉ|i∈[q1+1,n]}に、即ち、ｑ２'＝ｑ１に分割され、しかる後、それが右サブ・ツリーであるので第２分割が行なわれる。
【００２３】
右サブ・ツリーＣｒに対して、
（１）幅が、右サブ・ツリーＣｒに対応する表示部分Ｃｒ'の高さよりも大きい場合、ＣｒがＣｌ’＝{0}およびＣｒ’＝{cｉ|i∈[q1+1,n]}に、即ち、ｑ２'＝ｑ１に分割され、しかる後、それが右サブ・ツリーであるので第３分割が行なわれる。
（２）幅が、右サブ・ツリーＣｒに対応する表示部分Ｃｒ'の高さよりも小さい場合、ＣｒがＣｌ’＝{cｉ|i∈[q1+1,n]}およびＣｒ’＝{0}に、即ち、ｑ２'＝ｎに分割され、しかる後、それが左サブ・ツリーであるので第３分割が行なわれる。
【００２４】
トリプル・ツリーＴに対応するルート・ノードｔが作成される。そこにはｑ１およびｑ２が記録される。ＴがデータセットＣと相関させられる。対応する空のサブ・ツリー・ノードtl、tｍ、およびtrが作成され、それらがＣｌ、Ｃｍ、およびＣｒと相関させられる。それらが空でない場合、中央のサブ・ツリーＣｍ、左サブ・ツリーＣｌ、および右サブ・ツリーＣrに対する分割が上記の基準に基づいて反復的に行なわれ、すべてのグラフ・コンポーネントが正しい位置に置かれるまで、即ち、レイアウトが完了するまで、表示領域の対応する分割が行なわれる。更に、一例として、６個のグラフ・コンポーネントを有する分断されたネットワークを使用すると、図８に示されたトリプル・ツリー構造と共に本発明の方法を使った結果として、レイアウトは図７に示されたものと同じように見えるであろう。
【００２５】
サブセットＣｌおよびＣｒのウェイトに従って表示部分Ｃｌ’およびＣｒ’を形成するための表示部分の分割は、サブセットＳ１およびＳ２のウェイトに従って表示部分Ｓ１'およびＳ２'を形成するための表示領域の分割、およびサブセットＣｐおよびＣｍのウェイトに従って表示部分Ｃｐ’およびＣｍ’を形成するための表示部分の分割、即ち、グラフ・コンポーネントのウェイトを使用した分割と同じであり、従って、本明細書では更なる詳細な説明は行なわれない。
【００２６】
本発明の上記方法を実施した後、表示部分Ｃｐ'は表示領域の中央にあり、Ｃｍ'はＣｐ'の下にあり、Ｃｌ'およびＣｒ'はＣｐ'の左側およびＣｐ'の右側にある。
【００２７】
次に、図９を参照すると、本発明による分断された動的ネットワークのための表示領域における例示的なレイアウト・システム６００が示される。システム６００は、複数のグラフ・コンポーネントをそれらの重要度に従ってソートするためのコンポーネント・ソート手段６０２と、そのソートされた複数のグラフ・コンポーネントを、それらの重要度の順に従って、少なくとも最も重要なグラフ・コンポーネントを含む第１サブセットＳ１および第２サブセットＳ２に分割する第１分割を行うための第１分割手段６０４と、第１サブセットＳ１をそれらの重要度の順に従って、最も重要なグラフ・コンポーネントだけを含む上位サブセットＣｐおよび下位サブセットＣｍに分割する第２分割を行うための第２分割手段６０６と、第１サブセットＳ１および第２サブセットＳ２の重要度の値に従って比例的に表示領域を表示部分Ｓ１'およびＳ２'に分割するための第１表示領域分割手段６０８と、上位サブセットＣｐおよび下位サブセットＣｍの重要度の値に従って比例的に表示部分Ｓ１'を表示部分Ｃｐ'およびＣｍ'に分割するための第２表示領域分割手段６１０と、表示部分Ｃｐ'のアスペクト比が１に近くなるまで、第１分割、第２分割、および表示領域の対応する分割を反復的に実行するための実行手段６１２を含む。
【００２８】
以下では、本発明による分断された動的ネットワークの更新方法を説明する。前述したように、サブセットＣｐ、Ｃｍ、ＣｌおよびＣｒがトリプル・ツリー構造Ｔを形成した。この構造Ｔでは、ルート・ノードＣｐが、３本のサブ・ツリー、即ち、中央のサブ・ツリーＣｍ、左のサブ・ツリーＣｌおよび右のサブ・ツリーＣrを有する。そのようなトリプル・ツリーは、最新の反復的レイアウト情報を保管している。グラフ・コンポーネントcｉが削除される場合、トリプル・ツリー構造Ｔにおける対応するノードtｉが見つけられ、そのノードtｉが削除される。しかる後、cｉの親ノードが見つけられ、その見つけられたツリー・ノードのｑ１およびｑ２が１を減じられる。グラフ・コンポーネントcｉが加えられる場合、cｉが加えられるべきロケーションに従ってcｉの親ノードが見つけられ、しかる後、その見つけられたツリー・ノードのｑ１およびｑ２が１を加えられる。グラフ・コンポーネントcｉが動く場合、（１）オリジナル・ロケーションにおいてcｉが削除され、（２）新しいロケーションにおいてcｉが加えられる。
【００２９】
更新されたｑ１およびｑ２、並びに更新されたトリプル・ツリー構造Ｔを使用することにより、このレイアウト方法が再び利用されて新しいデータセットＣ'を新しいサブセットＣｐ、Ｃｌ、Ｃｍ、およびＣｒに分割し、新しいサブセットＣｐ、Ｃｌ、Ｃｍ、およびＣｒに従って表示領域を分割することができる。
【００３０】
再び、分断された動的ネットワークが、例えば、６個のグラフ・コンポーネントを含むものとし、最後の反復のレイアウトが図７に示され、対応するトリプル・ツリー構造Ｔが図８に示されるものと仮定する。
【００３１】
ルート・ノードc０、を有するトリプル・ツリー構造に対してｑ１＝２およびｑ２＝４であり、ルート・ノードＣ３を有するトリプル・ツリー構造に対してｑ２＝３およびｑ１は存在せず（Ｃ３のＣｍおよびＣlが空であるため）、ルート・ノードＣ１を有するトリプル・ツリー構造に対してｑ２＝１、ｑ１は存在せず（Ｃ１のＣｍおよびＣｒが空であるため）、ルート・ノードＣ５を有するトリプル・ツリー構造に対してｑ２＝５、ｑ１は存在しない（Ｃ５のＣｍおよびＣrが空であるため）。
【００３２】
グラフ・コンポーネントc３が上記の更新方法に従って削除される場合、先ず、トリプル・ツリー構造における対応するノードt３が見つけられ、それ（c３に対応する）が削除され、次に、t３の親ノード（ここではノードc０）が見つけられる。しかる後、見つかったツリー・ノードのｑ１およびｑ２が１を減じられる、即ち、ルート・ノードc０を有するトリプル・ツリー構造に対してｑ１＝１およびｑ２＝３にされる。しかる後、更新されたｑ１およびｑ２を使用して、新しいデータセットが分割される。その例に関しては、データセットＣ'＝{c０,c１, c２, c４, c５, c６}に対してｑ１＝１および、ｑ２＝３が使用されて（ここではｑ２＝３がc４に対応する）、そのデータセットおよび対応する表示領域を分割する。従って、その分割の後、Ｃｐ＝{c０}、Ｃｍ＝{c１}、Ｃｌ＝{c２,c４}およびＣｒ＝{c５, c６}となる。
【００３３】
本発明の基本原理を上記の実施例に関連して説明している。しかし、基本的なプログラミング技術を有する当業者が本発明の明細書を読むことによって、本発明の装置および方法のそれぞれの又はいずれのステップ又はコンポーネントも、任意のコンピューティング装置（プロセッサ、記憶媒体等を含む）またはコンピューティング装置のネットワークにおいて、ハードウェア、ファームウェア、ソフトウェア、またはそれらの組合せを用いて具現化し得るということは当業者には明らかであろう。
【００３４】
従って、任意のコンピューティング装置においてプログラム或いは一連のプログラムを実行することによって、本発明の目的を具現化することが可能である。コンピューティング装置は既知の汎用装置であってもよい。従って、本発明の方法または装置を具現化するプログラム・コードを提供するプログラム製品を通して本発明の目的を具現化することも可能である。即ち、そのようなプログラム製品も本発明を構成し、そのようなプログラム製品を記憶した記憶媒体も本発明を構成する。明らかに、その記憶媒体は、任意の既知の記憶媒体または今後開発される任意の記憶媒体であってもよい。
【００３５】
ソフトウェアおよび／またはファームウェアによって本発明の実施例を具現化する場合、そのソフトウェアを構成するプログラムは、記憶媒体またはネットワークから、専用のハードウェアを有するコンピュータ、例えば、図１０に示されるような汎用パーソナル・コンピュータ７００にインストールされてもよく、そのコンピュータは、そこに種々のプログラムがインストールされた場合、種々の機能を遂行することが可能である。
【００３６】
図１０において、中央処理装置（ＣＰＵ）７０１は、リード・オンリ・メモリ（ＲＯＭ）７０２に格納されたプログラムまたは記憶セクション７０８からランダム・アクセス・メモリ（ＲＡＭ）７０３にロードされたプログラムに基づいて種々の処理を行う。ＲＡＭ７０３では、ＣＰＵ７０１が種々の処理等を行うときに必要なデータも必要に応じて保存される。ＣＰＵ７０１、ＲＯＭ７０２、およびＲＡＭ７０３は、バス７０４を介して相互に接続される。入出力インタフェース７０５もバス７０４に接続される。
【００３７】
入出力インタフェース７０５には下記のコンポーネント、即ち、キーボード、マウス等を含む入力セクション７０６、 陰極線管（ＣＲＴ）、液晶ディスプレイ（ＬＣＤ）等のようなディスプレイおよびスピーカ等を含む出力セクション７０７、ハード・ディスク等を含む記憶装置セクション７０８、並びにＬＡＮカード、モデム等のようなネットワーク・インターフェース・カードを含む通信セクション７０９が接続される。通信セクション７０９は、インターネットのようなネットワークを介して通信処理を行う。
【００３８】
ドライブ７１０も、必要に応じて、入出力インタフェース７０５に接続される。磁気ディスク、光ディスク、光磁気ディスク、半導体メモリ等のような取外し可能媒体７１１が、必要に応じて、ドライブ７１０にインストールされ、その結果、そこから読まれたコンピュータ・プログラムが、必要に応じて、記憶装置セクション７０８にインストールされ得る。
【００３９】
上記の一連の処理がソフトウェアで具現化される場合、そのソフトウェアを構成するプログラムが、インターネットのようなネットワークまたは取外し可能媒体７１１のような記憶媒体からインストールされてもよい。
【００４０】
記憶媒体は、図１０に示されるようにプログラムを格納され、そのプログラムを提供する装置からユーザに個別に配布される取外し可能媒体７１１に限定されない、ということは当業者には明らかであろう。取外し可能媒体７１１の例は、磁気ディスク（フロッピ・ディスク（商標）を含む）、光ディスク（コンパクト・ディスク・リード・オンリ・メモリ（ＣＤ−ＲＯＭ）およびＤＶＤを含む）、光磁気ディスク（ミニ・ディスク（ＭＤ）（商標）を含む）、および半導体メモリを含む。それとは別に、記憶媒体は、ＲＯＭ７０２、記憶装置セクション７０８に内蔵されたハード・ディスク等であってもよく、それはプログラムをそこに格納され、それらを含む装置と共にユーザに配布されるものである。
【００４１】
本発明の装置および方法では、明らかに、コンポーネントまたはステップが分解され、および/または、再結合され得るということにも留意されたい。その分解および／または再結合は、本発明の等価な解決策であると考えるべきである。更に、上記の一連の処理を行うステップは自然な説明順に順次行なわれ得るが、必ずしもそのように行なわれなくてもよい。幾つかのステップが並行して行なわれてもよく、相互に無関係に行なわれてもよい。
【００４２】
本発明およびその利点を詳細に説明したが、種々の修正、結合、副次的結合、および代替が、それらが「特許請求の範囲」またはその均等物の範囲内にある限り、設計および他の要因次第で生じ得る、ということも当業者には明らかであろう。更に、「含む」という用語は、一連の要素を含むプロセス、方法、物、または装置がこれらの要素を含むのみならず、明示的に挙げられてない他の要素またはそれらに固有の他の要素も含み得るように、非排他的な包含もカバーすることを意図している。
【特許請求の範囲】
【請求項１】
複数のグラフ・コンポーネントを含む分断された動的ネットワークのために表示領域においてレイアウトを行う方法であって、
前記複数のグラフ・コンポーネントをそれらの重要度に従ってソートするステップと、 ソートされた複数のグラフ・コンポーネントを第１サブセットＳ１および第２サブセットＳ２に、それらの重要度の順に従って分割するために第１分割を行うステップであって、前記第１サブセットＳ１は少なくとも最も重要なグラフ・コンポーネントを含む、ステップと、
前記第１サブセットＳ１を上位サブセットＣｐおよび下位サブセットＣｍに、それらの重要度の順に従って分割するために第２分割を行うステップであって、前記上位サブセットＣｐは前記最も重要なグラフ・コンポーネントのみを含む、ステップと、
前記第１サブセットＳ１および前記第２サブセットＳ２の重要度の値に従って比例的に前記表示領域を表示部分Ｓ１'およびＳ２'に分割するステップと、
前記上位サブセットＣｐおよび前記下位サブセットＣｍの重要度の値に従って比例的に前記表示部分Ｓ１'を表示部分Ｃｐ'およびＣｍ'に分割するステップと、
前記表示部分Ｃｐ'のアスペクト比が１に近くなるまで、前記第１分割および前記第２分割、並びに前記表示領域の対応する分割を反復的に実行するステップと
を含む、方法。
【請求項２】
前記第２サブセットＳ２を左サブセットＣｌおよび右サブセットＣｒに分割するために第３分割を行うステップであって、前記左サブセットＣｌの重要度は前記右サブセットＣｒの重要度に近い、ステップと、
前記表示部分Ｃｐ'およびＣｍ'以外の表示部分を前記左サブセットＣｌおよび前記右サブセットＣｒの重要度の値に従って比例的に表示部分Ｃｌ'およびＣｒ'に分割するステップと
を更に含む、請求項１に記載の方法。
【請求項３】
前記表示部分Ｃｐ'は前記表示領域の中央にある、請求項２に記載の方法。
【請求項４】
前記表示部分Ｃｍ'は前記表示部分Ｃｐ'の下にある、請求項２に記載の方法。
【請求項５】
前記表示部分Ｃｌ'およびＣｒ'はそれぞれ前記表示部分Ｃｐ'の両側にある、請求項２に記載の方法。
【請求項６】
前記表示部分Ｃｍ'、Ｃｌ'、およびＣｒ'の幅が高さよりも大きい場合、前記下位サブセットＣｍ、前記左サブセットＣｌ、および前記右サブセットＣｒの各々に１つのグラフ・コンポーネントしか残らなくなるまで、前記下位サブセットＣｍ、前記左サブセットＣｌ、または前記右サブセットＣｒに対して前記第１分割、前記第２分割、および前記第３分割を反復的に行ない、
前記表示部分Ｃｍ'、Ｃｌ'、およびＣｒ'の幅が高さよりも小さい場合、前記表示部分Ｃｍ'、Ｃｌ'、およびＣｒ'を９０度回転させ、前記下位サブセットＣｍ、前記左サブセットＣｌ、および前記右サブセットＣｒの各々に１つのグラフ・コンポーネントしか残らなくなるまで、前記下位サブセットＣｍ、前記左サブセットＣｌ、または前記右サブセットＣｒに対して前記第１分割、前記第２分割、および前記第３分割を反復的に行う
請求項５に記載の方法。
【請求項７】
前記表示領域の分割の情報を保管するためにトリプル・ツリー構造が使用される、請求項６に記載の方法。
【請求項８】
分断された動的ネットワークのために表示領域においてレイアウトを行うシステムであって、
複数のグラフ・コンポーネントをそれらの重要度に従ってソートするためのコンポーネント・ソート手段と、
ソートされた複数のグラフ・コンポーネントを第１サブセットＳ１および第２サブセットＳ２に、それらの重要度の順に従って分割するために第１分割を行うための第１分割手段であって、前記第１サブセットＳ１は少なくとも最も重要なグラフ・コンポーネントを含む、第１分割手段と、
前記第１サブセットＳ１を上位サブセットＣｐおよび下位サブセットＣｍに、それらの重要度の順に従って分割するために第２分割を行うための第２分割手段であって、前記上位サブセットＣｐは前記最も重要なグラフ・コンポーネントのみを含む、第２分割手段と、
前記第１サブセットＳ１および前記第２サブセットＳ２の重要度の値に従って比例的に前記表示領域を表示部分Ｓ１'およびＳ２'に分割するための第１表示領域分割手段と、
前記上位サブセットＣｐおよび前記下位サブセットＣｍの重要度の値に従って比例的に前記表示部分Ｓ１’を表示部分Ｃｐ'およびＣｍ'に分割するための第２表示領域分割手段と、
前記表示部分Ｃｐ'のアスペクト比が１に近くなるまで、前記第１分割および前記第２分割、並びに前記表示領域の対応する分割を反復的に実行するための実行手段と
を含む、システム。
【請求項９】
前記第２サブセットＳ２を左サブセットＣｌおよび右サブセットＣｒに分割するための第３分割手段であって、前記左サブセットＣｌの重要度は前記右サブセットＣｒの重要度に近い、第３分割手段と、
前記表示部分Ｃｐ'およびＣｍ'以外の表示部分を前記左サブセットＣｌおよび前記右サブセットＣｒの重要度の値に従って比例的に表示部分Ｃｌ'およびＣｒ'に分割するための第３表示部分分割手段と
を更に含む、請求項８に記載のシステム。
【請求項１０】
前記表示部分Ｃｐ'は前記表示領域の中央にある、請求項９に記載のシステム。
【請求項１１】
前記表示部分Ｃｍ'は前記表示部分Ｃｐ'の下にある、請求項９に記載のシステム。
【請求項１２】
前記表示部分Ｃｌ'およびＣｒ'はそれぞれ前記表示部分Ｃｐ'の両側にある、請求項９に記載のシステム。
【請求項１３】
前記表示部分Ｃｍ'、Ｃｌ'、およびＣｒ'の幅が高さよりも大きい場合、前記下位サブセットＣｍ、前記左サブセットＣｌ、および前記右サブセットＣｒの各々に１つのグラフ・コンポーネントしか残らなくなるまで、前記下位サブセットＣｍ、前記左サブセットＣｌ、または前記右サブセットＣｒに対して前記第１分割、前記第２分割、および前記第３分割を反復的に行ない、
前記表示部分Ｃｍ'、Ｃｌ'、およびＣｒ'の幅が高さよりも小さい場合、前記表示部分Ｃｍ'、Ｃｌ'、およびＣｒ'を９０度回転させ、前記下位サブセットＣｍ、前記左サブセットＣｌ、および前記右サブセットＣｒの各々に１つのグラフ・コンポーネントしか残らなくなるまで、前記下位サブセットＣｍ、前記左サブセットＣｌ、または前記右サブセットＣｒに対して前記第１分割、前記第２分割、および前記第３分割を反復的に行う
請求項１２に記載のシステム。
【請求項１４】
前記表示領域の分割の情報を保管するためにトリプル・ツリー構造が使用される、請求項１３に記載のシステム。
【請求項１】
複数のグラフ・コンポーネントを含む分断された動的ネットワークのために表示領域においてレイアウトを行う方法であって、
前記複数のグラフ・コンポーネントをそれらの重要度に従ってソートするステップと、 ソートされた複数のグラフ・コンポーネントを第１サブセットＳ１および第２サブセットＳ２に、それらの重要度の順に従って分割するために第１分割を行うステップであって、前記第１サブセットＳ１は少なくとも最も重要なグラフ・コンポーネントを含む、ステップと、
前記第１サブセットＳ１を上位サブセットＣｐおよび下位サブセットＣｍに、それらの重要度の順に従って分割するために第２分割を行うステップであって、前記上位サブセットＣｐは前記最も重要なグラフ・コンポーネントのみを含む、ステップと、
前記第１サブセットＳ１および前記第２サブセットＳ２の重要度の値に従って比例的に前記表示領域を表示部分Ｓ１'およびＳ２'に分割するステップと、
前記上位サブセットＣｐおよび前記下位サブセットＣｍの重要度の値に従って比例的に前記表示部分Ｓ１'を表示部分Ｃｐ'およびＣｍ'に分割するステップと、
前記表示部分Ｃｐ'のアスペクト比が１に近くなるまで、前記第１分割および前記第２分割、並びに前記表示領域の対応する分割を反復的に実行するステップと
を含む、方法。
【請求項２】
前記第２サブセットＳ２を左サブセットＣｌおよび右サブセットＣｒに分割するために第３分割を行うステップであって、前記左サブセットＣｌの重要度は前記右サブセットＣｒの重要度に近い、ステップと、
前記表示部分Ｃｐ'およびＣｍ'以外の表示部分を前記左サブセットＣｌおよび前記右サブセットＣｒの重要度の値に従って比例的に表示部分Ｃｌ'およびＣｒ'に分割するステップと
を更に含む、請求項１に記載の方法。
【請求項３】
前記表示部分Ｃｐ'は前記表示領域の中央にある、請求項２に記載の方法。
【請求項４】
前記表示部分Ｃｍ'は前記表示部分Ｃｐ'の下にある、請求項２に記載の方法。
【請求項５】
前記表示部分Ｃｌ'およびＣｒ'はそれぞれ前記表示部分Ｃｐ'の両側にある、請求項２に記載の方法。
【請求項６】
前記表示部分Ｃｍ'、Ｃｌ'、およびＣｒ'の幅が高さよりも大きい場合、前記下位サブセットＣｍ、前記左サブセットＣｌ、および前記右サブセットＣｒの各々に１つのグラフ・コンポーネントしか残らなくなるまで、前記下位サブセットＣｍ、前記左サブセットＣｌ、または前記右サブセットＣｒに対して前記第１分割、前記第２分割、および前記第３分割を反復的に行ない、
前記表示部分Ｃｍ'、Ｃｌ'、およびＣｒ'の幅が高さよりも小さい場合、前記表示部分Ｃｍ'、Ｃｌ'、およびＣｒ'を９０度回転させ、前記下位サブセットＣｍ、前記左サブセットＣｌ、および前記右サブセットＣｒの各々に１つのグラフ・コンポーネントしか残らなくなるまで、前記下位サブセットＣｍ、前記左サブセットＣｌ、または前記右サブセットＣｒに対して前記第１分割、前記第２分割、および前記第３分割を反復的に行う
請求項５に記載の方法。
【請求項７】
前記表示領域の分割の情報を保管するためにトリプル・ツリー構造が使用される、請求項６に記載の方法。
【請求項８】
分断された動的ネットワークのために表示領域においてレイアウトを行うシステムであって、
複数のグラフ・コンポーネントをそれらの重要度に従ってソートするためのコンポーネント・ソート手段と、
ソートされた複数のグラフ・コンポーネントを第１サブセットＳ１および第２サブセットＳ２に、それらの重要度の順に従って分割するために第１分割を行うための第１分割手段であって、前記第１サブセットＳ１は少なくとも最も重要なグラフ・コンポーネントを含む、第１分割手段と、
前記第１サブセットＳ１を上位サブセットＣｐおよび下位サブセットＣｍに、それらの重要度の順に従って分割するために第２分割を行うための第２分割手段であって、前記上位サブセットＣｐは前記最も重要なグラフ・コンポーネントのみを含む、第２分割手段と、
前記第１サブセットＳ１および前記第２サブセットＳ２の重要度の値に従って比例的に前記表示領域を表示部分Ｓ１'およびＳ２'に分割するための第１表示領域分割手段と、
前記上位サブセットＣｐおよび前記下位サブセットＣｍの重要度の値に従って比例的に前記表示部分Ｓ１’を表示部分Ｃｐ'およびＣｍ'に分割するための第２表示領域分割手段と、
前記表示部分Ｃｐ'のアスペクト比が１に近くなるまで、前記第１分割および前記第２分割、並びに前記表示領域の対応する分割を反復的に実行するための実行手段と
を含む、システム。
【請求項９】
前記第２サブセットＳ２を左サブセットＣｌおよび右サブセットＣｒに分割するための第３分割手段であって、前記左サブセットＣｌの重要度は前記右サブセットＣｒの重要度に近い、第３分割手段と、
前記表示部分Ｃｐ'およびＣｍ'以外の表示部分を前記左サブセットＣｌおよび前記右サブセットＣｒの重要度の値に従って比例的に表示部分Ｃｌ'およびＣｒ'に分割するための第３表示部分分割手段と
を更に含む、請求項８に記載のシステム。
【請求項１０】
前記表示部分Ｃｐ'は前記表示領域の中央にある、請求項９に記載のシステム。
【請求項１１】
前記表示部分Ｃｍ'は前記表示部分Ｃｐ'の下にある、請求項９に記載のシステム。
【請求項１２】
前記表示部分Ｃｌ'およびＣｒ'はそれぞれ前記表示部分Ｃｐ'の両側にある、請求項９に記載のシステム。
【請求項１３】
前記表示部分Ｃｍ'、Ｃｌ'、およびＣｒ'の幅が高さよりも大きい場合、前記下位サブセットＣｍ、前記左サブセットＣｌ、および前記右サブセットＣｒの各々に１つのグラフ・コンポーネントしか残らなくなるまで、前記下位サブセットＣｍ、前記左サブセットＣｌ、または前記右サブセットＣｒに対して前記第１分割、前記第２分割、および前記第３分割を反復的に行ない、
前記表示部分Ｃｍ'、Ｃｌ'、およびＣｒ'の幅が高さよりも小さい場合、前記表示部分Ｃｍ'、Ｃｌ'、およびＣｒ'を９０度回転させ、前記下位サブセットＣｍ、前記左サブセットＣｌ、および前記右サブセットＣｒの各々に１つのグラフ・コンポーネントしか残らなくなるまで、前記下位サブセットＣｍ、前記左サブセットＣｌ、または前記右サブセットＣｒに対して前記第１分割、前記第２分割、および前記第３分割を反復的に行う
請求項１２に記載のシステム。
【請求項１４】
前記表示領域の分割の情報を保管するためにトリプル・ツリー構造が使用される、請求項１３に記載のシステム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２０１０−２６２６３４（Ｐ２０１０−２６２６３４Ａ）
【公開日】平成２２年１１月１８日（２０１０．１１．１８）
【国際特許分類】
【出願番号】特願２０１０−８１６１８（Ｐ２０１０−８１６１８）
【出願日】平成２２年３月３１日（２０１０．３．３１）
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
【公開日】平成２２年１１月１８日（２０１０．１１．１８）
【国際特許分類】
【出願日】平成２２年３月３１日（２０１０．３．３１）
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
[ Back to top ]