(57)【特許請求の範囲】
【請求項１】
ワールドワイドウェブのリンク構造であるグラフ構造に関連する活性化拡散アルゴリズムの結果を表示するための装置であって、
プロセッサと、
前記プロセッサに結合される表示デバイスと、
前記プロセッサに結合され、一般化されたグラフ構造に関連する活性化拡散アルゴリズムの結果を表示する方法を実行するように前記装置をプログラムするためのプログラムコードを含むプロセッサ読み出し可能記憶媒体と、
を備え、前記方法が、
（ａ）活性化入力ベクトルＣを得るステップと、
（ｂ）前記（ａ）ステップで得た前記活性化入力ベクトルＣとフローマトリックスＭを用いて、ステップｔでの活性化ベクトルＡ（ｔ）がＡ（ｔ）＝Ｃ＋ＭＡ（ｔ−１）となるように、Ｎ回の反復について活性化ベクトルＡを反復的に計算するステップと、
（ｃ）複数の構造的に同一である、前記グラフ構造の平面グラフ表現を表示するステップとを含み、該平面グラフ表現の各々は前記（ｂ）ステップにおけるＮ回の反復のうちの一意的な一つに対応し、ノードの活性化レベルが該平面グラフ表現に色で符号化されることを特徴とする装置。
【請求項２】
ワールドワイドウェブのリンク構造であるグラフ構造に関連する活性化拡散アルゴリズムの結果を表示するための装置であって、
プロセッサと、
前記プロセッサに結合される表示デバイスと、
前記プロセッサに結合され、前記一般化されたグラフ構造に関連する活性化拡散アルゴリズムの結果を表示する方法を実行するように前記装置をプログラムするためのプロセッサ読み出し可能プログラムコードを含むプロセッサ読み出し可能記憶媒体と、を備え、前記方法が、
（ａ）前記グラフ構造のすべてのノードを木構造で表示するステップと、
（ｂ）活性化入力ベクトルＣを得るステップと、
（ｃ）前記（ｂ）ステップで得た前記活性化入力ベクトルＣとフローマトリックスＭを用いて、ステップｔでの活性化ベクトルＡ（ｔ）がＡ（ｔ）＝Ｃ＋ＭＡ（ｔ−１）となるように、Ｎ回の反復について活性化ベクトルＡを反復的に計算するステップと、
（ｄ）前記（ａ）ステップで表示された前記木構造のノード上に前記（ｃ）ステップでＮ回の反復後に得られた最終活性化ベクトルＡ（Ｎ）のエントリを表示するステップと、
を含むことを特徴とする装置。
【請求項３】
請求項２記載の装置において、
前記ステップ（ａ）が、前記木構造を平面的な円形木として表示するステップを含むことを特徴とする装置。
【請求項４】
請求項２記載の装置において、
前記ステップ（ａ）が、前記木構造を平面的なつぶれた円錐形として表示するステップを含むことを特徴とする装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は活性化拡散アルゴリズムの結果を表示する分野に関する。特に、本発明は、活性化入力ベクトルのインタラクティブな生成、および活性化拡散アルゴリズムにおける中間活性化ベクトルの表示に関する。本発明は、ウェブサイト上のワールドワイドウェブページに存在し得る関連性をいかにユーザーに伝え、その関連性をいかに求めるかという問題に対処する。
【０００２】
【従来の技術】
ワールドワイドウェブ(web)は、20世紀に一般社会にもたらされた情報アクセス機構のうち、おそらく最も重要なものであろう。顧客や投資家となる可能性のある人々に情報を提供するものとしてインターネットに頼る組織が多くなるにつれ、従業員やビジネスパートナーが後に検索するのに備えて大量のデータを提供、編成する上での可能性も実感することだろう。企業のウェブサイトは、急速に、最も重要なビジネスの投資対象となってきている。
【０００３】
一般に、ウェブサイトは情報リポジトリとして多く使用される。その企業の従業員がそのウェブサイトをどのように使用しているかを観察して得られるウェブサイト使用パターンにより、その企業の活動をよりよく理解できる。例えば、営業部門がどのような製品の広告をダウンロードしているかを観察することが、販売を予測する一つの方法となることも考えられる。つまり、従来の市場分析をこの情報資源にも適用することができるのである。
【０００４】
アナリストは、単にウェブページがどのように使用されているかだけでなく、それがどのようなコンテキストにあるか、例えばそのリンク構造やウェブページの内容にも興味を示している。ウェブサイトは、そのリンク構造や、そのページの内容、使用度に見られるようなトポロジーの変化が頻繁に起こるため、ダイナミックな構造である。アナリストは、その発展するウェブサイトを分析したいと願っているのである。
【０００５】
【発明が解決しようとする課題】
ユーザーのアクセスパターンやウェブページの内容同士の関係を知り、理解するとともに、ウェブサイトのトポロジーを効率的に構築したいというアナリストの希望が高まっているため、ウェブサイトの分析過程において有用な視覚化ツール群が必要とされている。
【０００６】
活性化拡散アルゴリズムは、活性化入力ベクトルに応じて、一般化されたグラフ構造のノードにおける活性化レベルに対応する時間ｔでの活性化ベクトルをモデル化または予測する反復的なプロセスである。活性化拡散アルゴリズムは、一般にＮ回にわたって反復される一次方程式の組を伴う。一次方程式のある条件が満たされていれば、活性化ベクトルは漸近収束する。
【０００７】
従来は、入力活性化ベクトルと最終活性化ベクトルのみが分析されていたが、位相変異の特定や、発散性の活性化拡散フローマトリックスの特定等、活性化ベクトルの中間値を検証することによりアナリストが貴重な情報やフィードバックを得られる可能性がある。
【０００８】
【課題を解決するための手段】
一般化されたグラフ構造を理解するための従来の技術は、一般化されたグラフ構造を構成するリンクおよびノードの表現を表示することである。ワールドワイドウェブの見方の一つは、ウェブページがノード、ハイパーリンクがノード間のリンクを表す一般化されたグラフ構造として見ることである。一般化されたグラフ構造の認知的処理を促進するため、典型的には一般化されたグラフ構造は、そのすべてのノードとリンクのサブセットのみとを含む木構造でディスプレイ上に表現される。ウェブページの構造、使用、および内容のダイナミックスを分析、予測するために活性化拡散アルゴリズムを使用することができる。本発明の一目的は、活性化拡散アルゴリズムの結果を表示することである。本発明の別の目的は、活性化拡散アルゴリズムの活性化入力ベクトルを規定する方法を提供することである。本発明のさらに別の目的は、活性化拡散アルゴリズムの種々のステップでの活性化レベルを表示することである。
【０００９】
本発明の好適な実施形態によると、活性化拡散アルゴリズムでモデル化される一般化されたグラフ構造を表すのに平面的な円形木が使用される。本発明の一局面による方法では、平面的な円形木のいくつかまたはすべてのノード上においてその垂直な次元に活性化バーを表示し、活性化拡散アルゴリズムのＮ回の反復終了時に得られる最終活性化レベルを符号化する。活性化バーを表示するノードの数は所定の数であってもよいし、すべてのノードに対しての所定の割合や、所定の活性化レベルしきい値によって決定されてもよい。
【００１０】
本発明の別の局面によると、同じ一般化されたグラフに対応する２つ以上のフローネットワークを拡散する活性化の結果として得られる最終活性化レベルが、活性化バー上において色で符号化された部分として表示される。例えば、内容、使用度、トポロジ、または推奨のフローネットワークを活性化拡散に使用してもよい。したがって、重み付け機構を用いて異なるフローネットワークが組み合わされる場合には、結果として得られるページの活性化に対する各フローネットワークの貢献度を、活性化バーにおいて各フローネットワークに異なる色を使用することで評価できる。
【００１１】
本発明のさらに別の局面によると、同じ一般化されたグラフに対応する異なるフローネットワークでの活性化拡散における差を、結果として得られる活性化パターンを各ネットワークから減じ、その差を表示することで表示してもよい。例えば、内容と使用度との差、推奨と使用度との差を表示して、ウェブサイトの設計者が予期せぬ使用パターンが起こっているページを特定するのを促進してもよい。
【００１２】
本発明のさらに別の局面によると、活性化拡散入力ベクトルは、ユーザーのカーソルが表示されたノード上にあるドエル時間を測定することで求められる。この局面によると、カーソルを１つ以上のノード上に置くことでこれらのノードにさらに入力活性化が加えられるにつれ、現在の活性化入力ベクトルに対応する最終活性化ベクトルが継続的に更新される。
【００１３】
本発明のさらに別の局面によると、Ｎ個のステップを含む活性化拡散アルゴリズムの種々の中間ステップでの活性化ベクトルがタイムチューブ内の円形木のノードに色で符号化される。この局面の一実施形態では、Ｎ個の全ステップの結果として得られる活性化ベクトルと活性化入力ベクトルが、Ｎ＋１個の平面的な円形木を有するタイムチューブにおいて表示される。別の実施形態では、Ｎ個の全活性化ベクトルの周期的なサブセットが表示される。さらに別の実施形態では、位相変異または活性化レベルにおける大きな変化を表す平面的円形木を示すサブセットは表示されるが、活性化レベルにおける小さな変化を表す平面的円形木は表示されない。
【００１４】
本発明のこれらのおよび他の特徴および利点は、発明の実施の形態で十分に説明される図面より明らかになるであろう。
【００１５】
【発明の実施の形態】
ここで図面をより詳細に説明する。図面において、同一の参照場号は同一の要素を示すが、本発明を明瞭に説明するため、異なる図面には同様の部分に異なる参照番号が付されることがある。
【００１６】
ワールドワイドウェブは、複雑で大きな有向グラフである。一般的な有向グラフの視覚化は、周知の難しい問題である。事実、現在のグラフレイアウトアルゴリズムは、どれも７０００ノードのグラフを十分に扱うことができない。しかし、有向グラフのサブドメインとして、ウェブサイトのリンク構造は階層的な傾向にある。つまり、ウェブサイトは木ではないものの、木表現でウェブサイトに近いものを表せることが多い。
【００１７】
ウェブのリンク構造を分析するに当たって、アナリストは、ある文書から別の文書への最も少ない数のホップを見つけるのに関心があることが多い。幅優先巡回は、ノードを根ノードにできるだけ近く配置することで、ウェブグラフを木に変形する。この木を得たあと、円形木視覚化技術によって構造を視覚化する。円形木は、階層を視覚化するのに円形のレイアウトを使用する。連続する各円が木におけるレベルを表す。レイアウトアルゴリズムは２つのパスで実行される。第１のパスで、アルゴリズムは後行順巡回により階層全体を巡回する。各ノードにおいて、アルゴリズムによりその部分木の葉ノードの数が計算されるため、その木の葉の数がわかる。次にアルゴリズムにより、各葉ノードに割当てるべき角度スペース量が計算される（３６０度を葉の総数で割ったもの）。第２のパスで、アルゴリズムは幅優先巡回によって階層を巡回する。各ノードにおいて、その部分木にいくつの葉ノードが根付いているかを見ることによりそのノードに角度スペース量を割当てる。このように、各葉ノードには一定量の角度スペースが保証される。
【００１８】
データを視覚表現にマッピングする際に知的かつ戦略的に選択できれば、見る者がその視覚化されたものをさらによく理解することができる。円形木にはいくつかの利点がある。まず、木の構造がコンパクトに視覚化され、そのパターンが簡単にわかる。第２に、まっすぐまたはわずかに角度を付けて見ても、全体のレイアウトが２次元平面上にあるため、オクルージョンの問題がない。第３に、円錐形の木とは異なり、２次元技術であるため、第３次元を時間等の他の情報、または各ノードの３次元グリフに使用することができる。さらに、円形であるために、視覚上、美的である。
【００１９】
実際に視覚化自体によって好適な幅優先変形アルゴリズムの選択が確認できる。通常、トラフィックの多い領域は根ノード付近に集中する。つまり、アルゴリズムにより、到達しやすいノードが根ノードを起点に配置される。文書は、根ノードから遠くなるほど、アクセスされる可能性が小さくなる。
【００２０】
図１は、本発明による方法を実現するのに適切な汎用コンピュータのアーキテクチャ１００を示す。汎用コンピュータ１００は、少なくとも、マイクロプロセッサ１０２と、ディスプレイモニタ１０４と、カーソル制御装置１０５とを備える。カーソル制御装置１０５は、マウス、ジョイスティック、一連のボタン、またはユーザーがディスプレイモニタ１０４上のカーソルまたはポインタの位置を制御するのを可能にする他の何らかの入力装置として実現されてもよい。汎用コンピュータ１００はまた、ランダムアクセスメモリ１０７と、ハードディスク１０３と、ＲＯＭメモリ１０８と、キーボード１０６と、モデム１１０と、グラフィックスコプロセッサ１０９とを備えてもよい。汎用コンピュータ１００のすべての要素を共通バス１０１で接続して、種々の要素間でデータをやり取りするようにしてもよい。一般に、バス１０１はデータ、アドレス、および制御信号を含む。図１に示される汎用コンピュータ１００は、そのすべての要素を接続する単一のデータバス１０１を含んでいるが、汎用コンピュータ１００の種々の要素を接続する単一の通信バス１０１がなくてはならないという要件はない。例えば、マイクロプロセッサ１０２と、ＲＡＭ１０７と、ＲＯＭ１０８と、グラフィックスコプロセッサ１０９とをデータバスで接続し、一方、ハードディスク１０３と、モデム１１０と、キーボード１０６と、ディスプレイモニタ１０４と、カーソル制御装置１０５とを第２のデータバス（図示せず）で接続してもよい。この場合、第１のデータバス１０１と第２のデータバス（図示せず）を双方向バスインターフェース（図示せず）で接続してもよい。または、要素のうちのいくつか、例えばマイクロプロセッサ１０２とグラフィックコプロセッサ１０９等を第１のデータバス１０１と第２のデータバス（図示せず）の両方で接続して、第１のデータバスと第２のデータバス（図示せず）との間の通信をマイクロプロセッサ１０２とグラフィックスコプロセッサ１０９とを介して行うようにしてもよい。このように、本発明の方法は、図１に１００で示されるようないかなる汎用コンピュータアーキテクチャにおいても実行可能であるが、本発明の方法を実行できるアーキテクチャはこのアーキテクチャのみに限定されるわけではないことは明らかである。
【００２１】
図２は、１５のノード２０１−２１５からなる一般化されたグラフ構造２００を示す。一般化されたグラフ構造２００の種々のノード２０１−２１５は、２１６−２２５で示されるようなリンクによって互いに接続される。種々のノードを接続するリンクは双方向でも単方向でもありうる。本明細書およびその図面を通して、双方向のリンクは、いずれの端にも矢印のないリンクとして表され、単方向のリンクは一方または他方の端部に矢印のあるリンクとして表されて、その矢印が指す方向にのみリンクがあることを示す。例えば、図２のリンク２１７は、ノード２０２から２０３へと移動することも、ノード２０３から２０２へと移動することもできる。あるノードから別のノードへと移動するのにいくつか異なる根が存在することが明らかである。大きな一般化されたグラフ構造にはリンクが多数存在するため、そのリンクをすべて表示するのは非実用的であることが多い。したがって、一般化されたグラフ構造の視覚表現をユーザーに呈示するとき、一般化されたグラフ構造に存在する全リンクのうちのサブセットのみが表示される。表示するように選択されるリンクのサブセットは、一般化されたグラフ構造のすべてのノードからその他のすべてのノードへの経路を示さなくてはならない。この目的を達成するのに木構造が多く用いられる。
【００２２】
図３は、図２に示される一般化されたグラフ構造２００の木構造表現３００を示す。一般化されたグラフ構造２００に対応する木構造３００にはリンク２１６−２２５は示されていない。このようにリンク２１６−２２５が省略されているのは、これらが一般化されたグラフ構造２００においてサイクルを形成するからである。木構造にはサイクルがなく、つまり、あるノードから別のノードへの経路は一つしかない。木構造表現３００では、すべてのサイクルが断たれるため、あるノードから別のノードに対して経路は１つしかないのである。
【００２３】
図４は、図３に示される木構造表現３００の別の木構造表現４００を示す。木構造４００では、ノード２０１が根ノードとされる。根ノード２０１の深さはゼロである。根ノード２０１の子はノード２０２，２０３，および２０４であり、これらの深さは１である。ノード２０２には子が１つ（ノード２０５）、ノード２０４には子が３つ（ノード２０６，２０７，および２０８）ある。ノード２０５−２０８の深さは２である。どのノードの深さも、根ノードに至るまでに巡回しなくてはならないリンクの数によって決定される。ノード２０９，２１０，２０３，２１４，２１５，２０７，２１２，および２１３には子がないため、これらは葉ノードである。
【００２４】
図５は、図４に示される木構造４００の円形木表現５００を示す。円形木表現５００の中心点５０１は、木構造４００の根ノード２０１に対応する。点５０１−５１５は各々、ノード２０１−２１５のうちのひとつを表しており、具体的には、木構造４００の各ノードに関連する参照番号に３００を加えることにより、木構造４００の各ノードに関する円形木５００における点に対応する参照番号を計算できる。すなわち、図４のノード２０１は円形木５００のノード５０１として示され、ノード２０２は点５０２、ノード２０３は点５０３、ノード２１５は点５１５で表される。円５５０は、点５０１で表される根ノードからの深さが１であるノードを表すすべての点を含む。円５６０は、深さが２であるノードを表すすべての点を含む。円５７０は、深さが３であるノードを表すすべての点を含み、円５８０は、深さが４であるノードを表すすべての点を含む（図５の点は図４のノードを表示、表現しているため、以下、表示上のノードを表す点を指してノードということがある）。円形木５００のノードを表す各点の角度的配置は以下のように決定される。葉ノードの総数を求め、円の角度である３６０度をその葉ノードの総数で割る。円形木５００の場合、点５１２，５１３，５０９，５１０，５０３，５１４，５１５，および５０７で表される８つの葉ノードがあるため、各葉ノードは、円形木５００においてそれ専用の角度スペースを４５度有する。親ノードの角度配置は、その最も外側の葉ノードと根ノードが形成する角度を２等分する角度にされる。例えば、ノード２０４を表す点５０４は、最も外側の葉２１４および２１３を有し、これらは円形木５００においてそれぞれ点５１４および５１３に対応する。最も外側の葉の点５１４と、最も外側の葉の点５１３と、根ノード５０１とにより形成される角度は１８０度である。したがって、親ノード５０４の角度はその１８０度を２等分する角度である。同様に、親ノード５１１は子の点５１５および５１４を有する。子の点５１５および５１４は根ノード５０１とともに４５度の角度を成し、したがって親の点５１１はその４５度を２等分する角度に配置される。
【００２５】
本発明によると、グラフ構造のレイアウトは使用情報に基づいて行われる。従来のレイアウト方法が主にトポロジまたは内容に基づくのに対し、本発明による方法では、使用度に優先順位をつける（ランク付けする）ことでさらなる情報を符号化する。これらの方法は、グラフの視覚化に興味度の関数を与え、それにより認知に関する負担を最小限にする。本発明の範囲はウェブへの応用よりはるかに広い範囲に及ぶが、ウェブによって本発明による方法を例示する。
【００２６】
本発明は、ワールドワイドウェブに見られるような大きな有向グラフをレイアウトする問題に対処し、関連のある関係が表れるようにする。本発明によると、使用度ベースの巡回によって一般のグラフが木にされる。巡回の順、またはレイアウトの順、またはその双方が、単純な頻度または共通の引用の頻度等の使用度データに基づいて選択される。本発明の方法を用いると、企業のイントラネットのビューをダイナミックに編成できる。
【００２７】
本発明によると、使用度ベースの情報に基づいてグラフをレイアウトすることにより、グラフの視覚化にさらなる情報が符号化される。例えば、情報の検索において、ハイパーテキスト文書は様々な頻度でアクセスされる（他と比較してより人気のあるものがある）。本発明によると、アイテムの人気度が、グラフのレイアウトにおいてそのアイテムが受ける優先順位を決定する一助となる。使用度データとそれをグラフの構造レイアウトに符号化することとをあわせることで、使用度およびトポロジにおける変化を同時に見ることができる。
【００２８】
ここで提案する発明の範囲はワールドワイドウェブ上の文書に限られるわけではないが、本発明の概念の基本を説明するのにウェブサイトの管理者が見るウェブを例として用いる。本発明は、メンテナンスを行うウェブの管理者が、ウェブサイトの使用パターンとそのトポロジとの関係を理解することを可能にする。
【００２９】
複雑なリンク構造を理解するための従来の技術として、リンクおよびノードを視覚化または表現したものを呈示することが挙げられる。ウェブの見方の一つとして、文書がノードを表し、ハイパーリンクが文書間のリンクを表すグラフとして見ることができる。リンクは数が多く複雑であるため、通常、情報のいくらかは省いたり、抜粋したりして、効果的に認知できる視覚処理を実現する。レイアウトアルゴリズムによってより重要な情報を呈示することを確実にするため、これらのアルゴリズムは興味度の関数を使用することが多い。
【００３０】
従来のシステムには、その使用度の特徴に基づいてアイテムのレイアウトを変更するものはない。ウェブサイトのメンテナンスを行う者およびその内容の設計者は、そのサイトの使用パターンとそのリンクトポロジとの関係を理解する必要がある。ウェブサイトはダイナミックであり時間とともに変化するため、メンテナンスを行う者はトポロジへの変化が使用にどのような影響を与えるかを理解する必要があることが多い。使用パターンからの情報を用いることにより、レイアウトアルゴリズムはサイトのトポロジを呈示し、ユーザーの経路および使用度が時間とともに（例えば、より多くのユーザーによるその構造へのアクセス、そのニーズの変化、そしてその根底にあるトポロジの発展に伴って）どのように変化するかを明らかにすることができる。
【００３１】
本発明による方法は、種々のレイアウトアルゴリズムについてレイアウトの決定を行うのに使用情報を利用する。これらのアルゴリズムの中には、スクリーンの空間を最大限にしようとするものや、要素間の微妙な関係を表そうとするよう機能するものもある。頻度、新しさ、アクセスの間隔、および経路情報は、すべて、本発明の方法によって参照してもよい使用情報の形態である。さらに、共通の引用のクラスト化およびニーズの可能性等の導出された使用情報を利用することもできるが、本発明はこれらの形態に限られるわけではない。
【００３２】
本発明によるトポロジのレイアウト方法の一つとして、根ノードと称するノードから始めて、そのノードを中心に半径方向にリンクを広げるものがある。スクリーンの空間がある限り、これを補助ノードで繰り返す。ノードを最適にレイアウトするために、レイアウトアルゴリズムでは、最もよく使用されるノード同士を互いから最も離れた所に配置して、その発展スペースが最大になるようにすることが望まれる場合もある。最も使用度が低いノードは、使用度の高いノード間の残りのスペースに配置される。レイアウトにより、その使用度値に基づいて、ハブを中心として互いから最も離れた所へのノードの配置が続けられる。使用度の最も高いノードは互いから最適に離されていて、その関連する子ノードを配置するのに充分なスクリーン空間を与える。これは、使用度がより低いノードを犠牲にして行われる。
【００３３】
本発明による別のレイアウト方法では、使用度によりノードを順序付けて、それらを高い方から低い方へ（または低い方から高い方へ）とレイアウトして、人気度（または人気の無さ）を示す。
【００３４】
使用度ベースのレイアウトの一例として、本発明による改良されたグラフの幅優先巡回ではその構造における使用度を符号化する。従来の幅優先巡回ベースのレイアウトでは、根ノードの子ノードをレイアウトして、その次にそのまた子ノードをレイアウトする。従来は、巡回の際に子ノードを訪ねる順序は特定されていなかった。しかし、本発明によると、単にあるパラメータに基づいて訪ねる順序を選択することにより、さらなる情報をグラフレイアウトに符号化する。例えば、使用量に基づいてノードをソートすることで訪ねる順序が決定される（より人気のないウェブページより人気のあるページを優先する）。
【００３５】
本発明によって使用度パラメータを参照するように改良できる別のレイアウトアルゴリズムは、共通の祖先を持つノードが呈示される深さ優先巡回である。この場合、その近傍にあるものを考慮せず、縦のスライスを呈示する。各ステップで、アルゴリズムによりどの子を選んで探索するかを決めなくてはならない。本発明による最良の幅優先巡回と同様に、使用度が最も高い子がまず訪ねられる。
【００３６】
本発明に従って他の多くのレイアウトの組み合わせが可能である。例えば、あるノードから幅優先または深さ優先のトポロジの順序でグラフをたどるのではなく、ある使用度レベルのすべてのノードが根ノードとして表示される。ウェブに関していえば、この技術を用いてエントリポイントの組（サイトに入るのに使用するページ）と、それらのページからユーザーがたどる経路を視覚化できる。それらの間のスペースは、根ノード間のリンクおよび使用度に基づいて割当てられる。
【００３７】
使用パターンによって、ある集中した時間の間に文書構造がどのようにアクセスされているかが明らかにされるだけでなく、ある時間にわたって集められるとトポロジにおける流れも明らかにされる。これは表現にさらに別の次元を与える。メンテナンスを行う者は、使用が時間とともに（おそらくは、ユーザーの変化または外部事象によって）どう変化するか、さらに、構造の変化が使用パターンにどう影響するかを見て取ることができる。これらのタイムスライスを比較することによって、メンテナンスを行う者は、どれだけ多くの人がその構造のどこを現在巡回しているかがわかるだけでなく、変化を相関させることができる。
【００３８】
図６は、９つのノード１−９を有し、多くのサイクルを含む一般化されたグラフ構造であって、本発明による種々の使用度ベースの木構造生成方法を示すのに使用する構造を示す。明瞭にするために、ノード間の双方向リンクは、単方向リンクの対として表現される。例えば、ノード１はノード２に対してリンク６１２を有し、ノード２はノード１に対してリンク６２１を有する。
【００３９】
図７は、一般化されたグラフ構造６００に対応するトポロジマトリックス７００を示す。トポロジマトリックス７００の行１−９はノード１−９に対応し、その列１−９もノード１−９に対応する。行ｉおよび列ｊのトポロジマトリックスのエントリは、ノードｉからノードｊに対するリンクの有無を表す。例えば、ノード６はノード３に対してリンク６６３を有し、ノード７はノード８に対してリンク６７８を有する。従って、ノードｉからノードｊに対してリンクがあることが、トポロジマトリックス７００の行ｉ、列ｊにおいて１で表される。一般化されたグラフ構造６００のノードｉからノードｊに対してリンクが存在しないことは、トポロジマトリックス７００の行ｉ、列ｊにおいて０で表される。トポロジマトリックスは、一般化されたグラフ構造の各ノードからその他すべてのノードに対するリンクを特定するため、一般に正方形である。トポロジマトリックスの対角線上のエントリは常にゼロである。一般化されたグラフ構造６００のリンクは双方向であるため、トポロジマトリックス７００はその対角線を中心に対称であるが、そうでなくてはならないというわけではない。
【００４０】
図８は、図６の一般化されたグラフ構造６００に対応する使用パラメータベクトル８００を示す。ノード１の使用度パラメータは、使用度パラメータベクトル８００のエントリ８０１に示されるように７５である。同様に、ノード８に関する使用度パラメータは２９であり、使用度パラメータベクトル８００のエントリ８０８に見られる。このように、使用度パラメータベクトル８００は単に、一般化されたグラフ構造の各ノードと関連する使用度パラメータのリストである。一般に、Ｎ個のノードを有する一般化されたグラフ構造には、それと関連するＮ個のエントリの使用度パラメータベクトルがある。このように、使用度パラメータベクトル８００の使用度パラメータは、対応するノードで得られた使用度に対応する。例えば、一般化されたグラフ構造６００のノード１−９の各々が９ページからなるウェブサイトのウェブページを表すとすると、そのウェブサイトの各ウェブページの１日の平均アクセス数を表すのに各ノードと関連する使用度パラメータを用いてもよい。または、各ノードと関連するユーザーパラメータで、そのページにアクセスした様々なユーザーがそのページを開いていた時間の合計を表してもよい。この場合の使用度パラメータは、ある一定時間の間にそのページにアクセスした全ユーザーによって測られた合計ドエル時間を符号化してもよい。各ノードと関連する使用度パラメータによって符号化される量は様々な方法で計算でき、その各々が異なるタイプの使用度を測定する。本発明による方法は、各ノードについて考慮され、計算されることが可能ないかなる使用度パラメータにも適用できる。したがって、本発明は、頻度、またはドエル時間等の単一の使用度パラメータのタイプに限られるのではない。使用度パラメータは、ある予め規定された尺度に正規化される可能性が高い。例えば、図８に示される使用度パラメータは０から１００の尺度に正規化される。使用度パラメータは、例えば０から１、または−１０２４から＋１０２４等に正規化されてもよい。
【００４１】
図９は、本発明による一般化されたグラフ構造から木構造を生成するための使用度ベースの幅優先方法９００を示す。この方法９００では、初めにステップ９０１で根ノードを承認する。幅優先アルゴリズムによって木構造を生成するには、根ノードを特定し、そのルートノードに対するノードの深さを計算できるようにしなくてはならない。ステップ９０１において根ノードは、種々の機構によって承認できる。例えば、カーソル制御装置を用いてユーザーがコンピュータのモニタ上に表示される一般化されたグラフ構造のある特定のノード上にカーソルを置いて、マウス１０５のボタンを押すことでそのノードを選択してもよい。または、そのノード名で暗に表すことで根ノードを承認してもよい。例えば、ウェブサイトにおいて、ウェブのホームページはそれが根ノードであろう事を示す意味構造を有するＵＲＬ(universal resource locator)を有することがある。例えば、www.xerox.com というＵＲＬにあるゼロックス社のホームウェブページを、本発明による方法を実施するプログラムで構文解析し、そのノード名によりこのウェブページがプログラムを適用しているウェブサイトの根ノードであることをプログラムが認識するようにしてもよい。いずれにせよ、根ノードがステップ９０１で特定されると、ステップ９０２において現在の深さがゼロに設定される。ステップ９０２では、単に、根ノードの深さを定義上ゼロであると指定するに過ぎない。この定義は、図４の木構造４００において深さがゼロである根ノード２０１に関して図示されている。ステップ９０３において、この方法により、認定されたノードで現在の深さにあり、まだ訪ねられておらず、関連の使用度パラメータが最高であるノードを訪ねる。方法９００の実行中に初めてステップ９０３に至った場合には、これまで承認されている唯一のノードは根ノードであり、かつ、これが現在の深さにある唯一のノードであるとともに、まだ訪ねられていない。従って、方法９００において初めてステップ９０３に至った場合には、根ノードが訪ねられる。
【００４２】
ステップ９０４において、この方法では、現在訪ねているノードのまだ承認されていないすべての子ノードを承認する。ステップ９０４で承認されるノードは、トポロジマトリックスおよび使用度パラメータベクトルを参照することにより簡単に特定できる。ステップ９０４で承認すべき子ノードは、訪ねられたノードの行のエントリがトポロジマトリックスにおいてゼロでないノードであって、まだ承認されていないものである。
【００４３】
ステップ９０５において、方法９００により、現在の深さにあってまだ訪ねていない承認されるノードがあるかどうかが判断される。方法９００において最初にステップ９０５を実行するときは、現在の深さゼロにおける唯一のノードは根ノード自体であるため、この９０５におけるテストの答えはノーである。従って、分岐９５２により該方法はステップ９０６へと進み、現在の深さが増分される。方法９００で始めてステップ９０６を実行するときには、現在の深さは１に設定される。
【００４４】
ステップ９０７で、方法９００により、（増分されたばかりである）現在の深さにノードが存在するかどうかが判断される。すなわち、テスト９０７により、一般化されたグラフ構造のすべてのノードが、承認され、訪ねられているかどうかを判断する。現在の深さにノードがなければ、すべてのノードが承認、訪ねられており、分岐９５４によりステップ９０８で終了する。しかし、新しく増分された現在の深さにノードがあれば、分岐９５３によりステップ９０４へと戻る。ステップ９０３において、現在の深さにあってその使用度パラメータが最高である承認ノードが訪ねられる。すなわち、現在の深さにあって承認されているすべてのノードについて、使用度パラメータベクトルから使用度パラメータが参照され、その使用度パラメータが最高である承認されるノードが最初に訪ねられるものとして選択される。
【００４５】
各承認ノードについて、現在の深さにある承認ノードと関連する使用度パラメータが高い順にステップ９０３，９０４，および９０５が繰り返される。すべてのノードが承認され、訪ねられるまで方法９００が継続され、ステップ９０８で終了する。
【００４６】
図１０は、図８に示される使用度パラメータベクトル８００を参照して、図９に示される幅優先方法９００によって図６に示される一般化されたグラフ構造６００から生成される木構造を示す。図１０の木構造１０００において、ユーザーはノード１を根ノードとして特定し、ノード２および４を根ノードの子として承認している。深さが１に増分されてから、ノード２の使用度パラメータ（使用度パラメータベクトルのエントリ８０２を参照）の方が使用度パラメータベクトル８００のエントリ８０４にあるノード４に対応する使用度パラメータより大きかったため、ノード４より先にノード２が訪ねられている。つまり、ノード２の使用度パラメータは８４、一方、ノード４の使用度パラメータは５１で、８４は５１よりも大きいため、ノード２を最初に訪ねるように選択している。ノード２を訪ねた際、ノード３および５がノード２の子として承認されている。深さが１のときノード４を訪ねた際に、ノード７をその子として承認している。深さ１のすべてのノードを訪ねた後、方法９００において深さを２に増分して、ノード５の使用度パラメータである８６（使用度パラメータベクトル８００のエントリ８０５を参照）の方がノード３の使用度パラメータ６、ノード７の使用度パラメータ４４よりも大きいため、ノード５をノード３および７よりも先に訪ねるように選択している。ノード５が訪ねられたとき、方法９００により、ノード６および８がノード５の子として承認されている。次に、ノード７を訪ねるが、ノード７に対して承認する子は存在しない。同様に、ノード３が深さ２で訪ねられるが、子を承認することはない。従って、深さは３に増分され、使用度パラメータが９６であるノード６が訪ねられ、ノード９がノード６の子として承認されている。深さ３のノード８と深さ４のノード９は、訪ねられた際も子を承認することはない。ノード９を訪ねた後、現在の深さが５に増分されるが、方法９００はステップ９０７においてこの深さにはノードが存在しないことを判断し、分岐９５４によりステップ９０８で方法９００が終了する。
【００４７】
図１１は、使用度パラメータマトリックス１１００を示す。使用度パラメータマトリックス１１００は、図６の一般化されたグラフ構造６００の各リンクに関する使用度パラメータを含む。使用度パラメータマトリックス１１００に見られる使用度パラメータは、図６の一般化されたグラフ構造６００に示される各リンクについて測定された使用量を特定する。例えば、ノード５からノード２への経路となるリンク６５２の使用量は２８である。一般化すると、ノードｉからノードｊへのリンクと関連する使用度パラメータは、使用度パラメータマトリックス１１００の行ｉ、列ｊにある使用度パラメータで特定される。方法９００を別の使用尺度に適用する例として、ステップ９０３で訪ねる順序を決定する際に、使用度パラメータベクトル８００の使用度パラメータではなく、使用度パラメータマトリックス１１００のリンク使用度パラメータを参照してもよい。すなわち、同じ深さのノードを訪ねる順を決める使用度パラメータとして、承認された子を指すリンクと関連する使用度パラメータを参照してもよい。使用度パラメータマトリックス１１００に示されるリンク使用度パラメータが、９ページからなるウェブサイトにおけるハイパーリンクの使用度のモデルとするのであれば、この例は、他の個々のウェブページの使用度よりもむしろハイパーリンクの使用度と関連する。
【００４８】
図１２は、本発明による方法９００によって使用度パラメータマトリックス１１００を用いて一般化されたグラフ構造６００から生成される木構造１２００を示す。図１２の木構造１２００において、ユーザーはノード２を根ノードとして選択し、ノード１，３，５を根ノード２の子として承認し、深さ１のノード３が最初に訪ねられる。これは、ノード２からノード３へのリンク６２３に対応する使用度パラメータが７４であって、リンク６２１の使用度パラメータおよびリンク６２５の使用度パラメータよりも大きいためである。ノード３を訪ねた際、ノード６をその子として承認しており、深さ１でノード１が訪ねられている。ノード１はノード４をその子として承認し、次に深さ１のノード５が訪ねられている。ノード５はノード８をその子として承認し、深さ２ではノード８が最初に訪ねられている。これは、リンク６５８と関連する使用度パラメータが、リンク６３６の使用度パラメータおよびリンク６１４の使用度パラメータよりも大きいためである。このように、ノード８を訪ねた際、ノード７および９を承認している。
【００４９】
本発明による方法では、訪ねる順序を決定するのにいかなる使用度パラメータを使用してもよい。例えば、ノードベース、およびリンクベースの幅優先巡回アルゴリズムを開示したが、本発明による方法がこれらの特定の使用度パラメータ、またはこの特定の幅優先アルゴリズムを使用しなくてはならないという要件はない。例えば、各ノードと関連する使用度パラメータを、（使用度パラメータベクトル８００に示されるような）ノード使用度パラメータおよび（使用度パラメータマトリックス１１００に示されるような）リンク使用度パラメータの重み付き一次関数として、使用度パラメータを導出するようにしてもよい。さらに、リンクおよびノード使用度パラメータの積を求めて使用度パラメータとして用いて、ステップ９０３でノードを訪ねる順序を決定してもよい。更に別の例として、根ノードからあるノードへのリンク使用度の積を計算して、ステップ９０３で訪ねる順序を決定するのに、そのノードの使用度パラメータとして使用してもよい。さらに、図９に示される方法９００は、本発明に従って用いることのできる使用度ベースの幅優先方法の一例に過ぎず、これに代えて、現在訪ねているノードのすべての兄弟ノードを同じ深さにある遠縁のノードまたは従兄弟ノードよりも先に訪ねるように方法９００を変形してもよい。
【００５０】
図１３は、本発明による一般化されたグラフ構造から木構造を生成する使用度ベースの深さ優先方法を示す。根ノードを特定してから、ステップ１３０１で根ノードを訪ね、その根ノードの子をステップ１３０２で承認する。ステップ１３０３で、この方法では、承認された子ノードのうち、まだ訪ねていないもので使用度パラメータが最高であるものを訪ねる。ステップ１３０４で、この方法では、現在訪ねているノードにまだ承認していない子があるかどうかを判断する。承認されていない子ノードがある場合には、分岐１３５０によりこれらの子ノードを承認し、ステップ１３０３で、承認された子ノードのうち、まだ訪ねられておらず、使用度パラメータを有するものを訪ねる。つまり、一連の子ノードの終わりに達するまで、ステップ１３０３，１３０４，および１３０５が実行される。まだ承認されていない子がないノードに達すると、分岐１３５１により方法１３００はステップ１３０６へと進み、ここで現在訪ねているノードの親を再び訪ねる。ステップ１３０７で、方法１３００では、現在訪ねているノードに承認された子のうちまだ訪ねていないものがあるかどうかを判断する。承認された子でまだ訪ねていないものがあれば、分岐１３５２により該方法はステップ１３０３へと戻る。しかし、承認された子でまだ訪ねていない子がなければ、分岐１３５３により方法１３００はステップ１３０８へと進む。ステップ１３０８で、方法１３００は、根ノードが再び訪ねられているかどうかをチェックする。方法１３００により根ノードが再び訪ねられていなければ、分岐１３５４により方法１３００はステップ１３０６へと戻り、現在訪ねているノードの親を再び訪ねる。ステップ１３０８で方法１３００により根ノードが再び訪ねられていると判断されると、分岐１３５５により方法１３００はステップ１３０９で終了する。
【００５１】
つまり、本発明による使用度ベースの深さ優先方法１３００は、葉ノードに達するまで、リンクされた一連のノードがある限りこれを訪ねる。方法１３００が葉ノードに達すると、ステップ１３０６により方法１３００は葉ノードの親へと戻り、その葉ノードの親の他の子を訪ねられるようにする。本質的に、訪ねられたノードの兄弟を訪ねる前に、その子孫全体の部分木を承認し、訪ねる。
【００５２】
図１４は、本発明による深さ優先方法１３００により、図８の使用度パラメータベクトル８００を使用して一般化された木構造６００から生成された木構造１４００を示す。ノード１が、木構造１４００の根ノードである。ノード２および４は、ノード１の子として承認され、ノード２の使用度パラメータの方がノード４の使用度パラメータよりも高いため、ノード４よりも先にノード２が訪ねられる。ノード２が訪ねられた際に、ノード３および５がその子として承認される。次に、ノード５の使用度パラメータの方がノード３の使用度パラメータよりも高いため、ノード５が訪ねられる。ノード５が訪ねられた時、ノード６および８がその子として承認される。次に、ノード６の使用度パラメータの方がノード８の使用度パラメータよりも高いため、ノード６が訪ねられる。ノード６が訪ねられた時、ノード９がその子として承認され、訪ねられる。ノード９が訪ねられた時、ステップ１３０４により、ノード９によって承認される子がないことが判断され、ステップ１３０６でノード６を再び訪ねるように指示し、ステップ１３０７により、ノード６の承認される子のうちまだ訪ねていないものがもうないことが判断される。従って、分岐１３５３により方法はステップ１３０８へと進み、ノード６が根ノードではないことが判断される。分岐１３５４により、方法はステップ１３０６へと戻り、ノード６の親が再び訪ねられる。方法１３００におけるこの時点では、ノード５が再び訪ねられている。ステップ１３０７により、ノード５の承認された子でまだ訪ねられていないもの、すなわちノード８があることが判断される。従って、分岐１３５２により方法１３００はステップ１３０３へと戻り、ノード８が訪ねられる。ノード８が訪ねられているとき、ノード７がその子として承認される。ノード７が訪ねられているとき、ステップ１３０４によりノード７が承認できる子がないことが判断され、従ってステップ１３０６によりノード８を再び訪ねるように指示される。ステップ１３０７および１３０８を経て、ステップ１３０６により再び方法はノード５へと戻り、ステップ１３０７および１３０８の別のループによって方法はノード２へと戻る。次に、ノード３が訪ねられてから、ノード２が再び訪ねられ、その後根ノード１が再び訪ねられる。ステップ１３０６により根ノード１を再び訪ねるように指示されると、ステップ１３０７により、根ノード１の承認された子でまだ訪ねられていないもの、すなわちノード４があることが判断される。従って、分岐１３５２によって方法はステップ１３０３へと戻り、ノード４が訪ねられる。しかし、ステップ１３０４により、ノード４が承認できる子がないことが判断され、そのため、分岐１３５１により方法はステップ１３０６へと戻り、根ノードがまた再び訪ねられる。このとき、ステップ１３０７により、根ノードの承認された子すべてが訪ねられたことが判断され、そのため分岐１３５３により方法はステップ１３０８へと進み、方法１３００により根ノードが再び訪ねられていることが判断され、分岐１３５５により方法はステップ１３０９へと至って終了する。
【００５３】
本発明による深さ優先方法１３００における子ノードを訪ねる順序の決定に使用する使用度パラメータは、使用度ベースの幅優先方法９００に関して上述したように様々な変形が可能である。すなわち、図１３の方法１３００を使用する際に、根ノードから所与のノードへの各リンクの関数で表される経路使用度、ノード使用度、リンクおよびノード使用度の一次または非線形関数、リンク使用度や、種々の他の使用度パラメータを使用してもよい。さらに、使用度ベースの幅優先方法１３００をわずかに変形したものを本発明によって実施することも可能である。
【００５４】
図１５は、親ノード１５０１を中心に半径方向に木構造の表示をレイアウトする態様を示す。ノード１５１０，１５２０，１５３０，１５４０，１５６０，１５７０，１５８０，および１５９０は、親ノード１５０１の子である。便宜上、兄弟ノードの使用度パラメータに単純に関連するように参照番号が付されている。例えば、ノード１５９０はノード１５８０よりもその使用度パラメータが高く、一番使用度の低いノードはノード１５１０である。図１５において、使用度の最も高いノード同士は、より使用度の低いノードを犠牲にして、互いに最適に離されている。したがって、ノード１５９０（最も使用度の高いノード）は、ノード１５８０（二番目に使用度の高いノード）から１８０度離れて配置される。使用度が最も高い４つのノード１５９０，１５８０，１５７０，および１５６０は、９０度の角度を４つ形成するように配置され、使用度の最も低いノードは合計の使用度が最も高い２つの隣接するノードによって形成される角度を２等分するように配置される。
【００５５】
このとき、その使用度パラメータによって兄弟ノードをソートする際にそのランクを考慮するのが有用である。ノード１５９０のランクは１であり、ノード１５１０のランクは８である。兄弟ノードのうちの使用度の高い半分のノードがレイアウトされると、そのランクの合計が最も低い２つの隣接する兄弟ノードが形成する角度を使用度の最も低いノードが二等分するように配置されるように、残りの半分である使用度の低い兄弟ノードをレイアウトしてもよい。例えば、ノード１５９０（ランク１）とノード１５７０（ランク３）の合計ランクは４であり、これは、４つの使用度の高いノードによって形成される直角のうち最もランクが小さい（つまり使用度が最高である）。したがって、使用度の最も低いノード１５１０はノード１５９０および１５７０を２分するように配置される。次に使用度の低いノードであるノード１５２０は、使用度の最も低いノードに対向して配置され、使用度の低い半分のノードのうちの残りのノードも、同様に、使用度の高い半分の兄弟ノードであるノードによって形成される角度を２分するようにレイアウトされる。この使用度ベースの表示を行うのに本発明によって様々な方法が考えられる。たとえば、兄弟ノードの総数に基づいて各兄弟ノードに一定量の角度スペースを割当て、使用度の高い半分の兄弟ノードが使用度に基づいて互いから最適に離されるようにこれらをプロットし、使用度の低い半分の兄弟ノードは、上述のように使用度の高い半分のノードによって形成される角度を二分するようにレイアウトしてもよい。この場合、使用度の最も高いノード同士を常に互いから１８０度の所に配置して、兄弟ノードの数がちょうど２のべき乗でない場合でも、新しいノードをレイアウトするたびに、すでにレイアウトされた隣接するノード間の角度スペースを２分するようにしてもよい。
【００５６】
図１６は、その親ノード１５０１を中心とした兄弟ノード群の配置を決定するのにその使用度パラメータを使用してこれらを表示するための本発明による別の方法を示す。この方法では、使用度の最も高いノードを配置する角度としてある角度が指定される。円の角度、３６０度を兄弟ノードの総数で割る。使用度の最も高いノードはその指定された角度に配置され、その残りのノードはその次に使用度の高いノードに隣接して配置される。つまり、使用度が最高のノードが指定された角度に配置され、その使用度が最高のノードの隣に２番目に使用度の高いノードが配置され、その２番目に使用度の高いノードの隣に３番目に使用度の高いノードが配置されるという具合に最も使用度の低いノードまでレイアウトする。従って、各ノードの角度的配置がその親に対してのレイアウト角度と単純に関連する。
【００５７】
図１７は、２３のノード１７０１−１７２３からなる一般化されたグラフ構造１７００を示す。ノード１７０１を根ノードとして選択し、一般化された木構造１７００の幅優先巡回を行うことで、サイクルを排除するようにリンク１７５０−１７６２を排除し、木構造を形成する。
【００５８】
図１８は、本発明による使用度ランクを用いて木構造を表示する方法を示す。ステップ１８０１で、木構造の各兄弟群について、各兄弟ノードがその使用度パラメータに従ってランク付けされる。ステップ１８０２で、木構造内のすべての兄弟群のランクに基づいて木構造がレイアウトされる。
【００５９】
図１９は、図１７に示される一般化されたグラフ構造１７００から得られる木構造のつぶれた円錐形の木を表示したものである。一般化されたグラフ構造１７００のノードを表す点は、図１７のノードの参照番号に対応する参照番号で示される。例えば、ノード１７２３は、表示１９００の点１９２３で示される。このように、図１７の参照番号に２００を加えることにより、参照されるノードを表す点が得られる。図１７において、種々のノードと関連する使用度パラメータは参照番号と逆の関係にある。例えば、兄弟ノード１７０２−１７０５の群の中で、ノード１７０２の使用度が最も高く、ノード１７０５は使用度が最も低い。つまり、参照番号は、その兄弟に関しての使用度パラメータのランクとしてみることができる。図１９において、根ノード１９０１が中心に配置され、その子ノード１９０２，１９０３，１９０４，および１９０５が、図１５に関して上述した最適に分離する方法によってレイアウトされる。同様に、ノード１９０２の８つの子ノードであるノード１９０６−１９１３は、図１５に関して上述した態様でその中心にある親ノード１９０２から半径方向にレイアウトされる。同様に、ノード１９０６の子ノードであるノード１９１９−１９２２も、図１５に関して上述した態様で最適な分離をとるようにレイアウトされる。ノード１９０３の子ノードであるノード１９１４−１９１７は、ランクが最高であり使用度も最高であるノード１９１４が中心１９０１からできるだけ離れるように配置され、その兄弟も上述のように配置される。子ノード１９０４は、点１９１８で中心１９０１からできるだけ離れて配置される。点１９１８の子（ノード１９２３）は、ノード１９０４からできるだけ遠く配置される。一般に、どの兄弟群における使用度が最高のノードも、その祖父ノードからできるだけ遠い角度に配置されるのが好ましいが、そうでなくてはならないという本発明による要件があるわけではない。兄弟ノードをその隣接する兄弟ノードと線（例えば半透明の線（破線））で接続して、その兄弟関係をさらに明白にするようにしてもよい。このオプションの線が図１９に示されているが、参照番号は付されていない。
【００６０】
図１９では、すべての兄弟ノードがその共通の親から一定半径の距離に配置される。図１９に示される例では、この半径は、木構造においてノードの深さが増すごとに２分の１に減少する。しかし、その親からの兄弟ノードの半径がこのように深さと関連しなくてはならないわけではない。図１９に示される表示１９００では、各子ノードのレイアウト角度はその親から測定される。
【００６１】
図２０は、図１７の一般化されたグラフ構造１７００から生成された木構造の円形木表示を示す。図２０において、使用度が最高のノードは、垂直に最も近い角度で配置される。例えば、ノード２００２は深さ１において使用度が最高のノードであり、ノード２００３は深さ１における次に使用度の高いノードであり、ノード２００５は深さ１のうちで使用度が最も低いノードである。このように、垂直から始まって、時計回りに各深さの円周上に続けて配置することで、ユーザーはその深さのノードをその使用度の順に見ることができ、使用度が最も高いノードを最初に見ることとなる。兄弟ノード２００６−２０１３のうち、ノード２００６の使用度が最も高く、ノード２０１３の使用度が最も低い。図５を参照して説明したように、図２０のレイアウトにおいて各葉ノードには一定量の角度スペースが割当てられる。図２０のレイアウトでは、各子ノードのレイアウト角度を木構造のレイアウトの中心から測定する。したがって、各ノードのレイアウト角度は、中心２００１からそのノードに伸びる半径と、中心２００１から垂直に伸びる半径（図１９の点２０１９を通る）とによって形成される角度として測定される。
【００６２】
つぶれた円錐形の木の表示１９００は、図１５を参照して説明した最適な分離をとるレイアウト技術を使用しており、また、円形木表現２０００は、ランクとレイアウト角度との単純な関係を用いてレイアウトされているが、兄弟の配置と表示アルゴリズムのタイプとの間にこの関係がなくてはならないという本発明による要件があるわけではない。たとえば、図示はされていないが、つぶれた円錐形の木表現において、図１６に関連して説明した、レイアウト角度と兄弟ノードとの間に単純な関係が成り立つ方法によって決定されるように兄弟ノードを配置してもよい。同様に、円形木表示で、図１５に関して説明した最適な分離をとる兄弟ノードレイアウト法を使用してもよい。
【００６３】
本発明によるタイムチューブは、様々な変形をとげるデータへの迅速なアクセスおよびその興味深い変更の特定を可能にする視覚化の一種である。タイムチューブは、３次元の作業空間に存在し、２次元の円形のスライス（例えば円形木）を重ねて丸太のような円筒形の表現に整列させることによって形成される。円形木の各々は、（たとえばクラスタ化や時間的な）変形段階におけるデータの視覚表現である。結果として得られる視覚化により、ユーザーはある時点から別の時点においてデータがどのように変形されたかを見て取ることができる。このより高度なレベルの表現によって、ユーザーは、種々の操作（例えば、回転、ピッキング、ブラッシング等）およびナビゲーション技術（例えば視点の変更やズーム）を行って、大きなデータセットの複雑な変形を理解するとともに、データセットの中で興味深い領域を特定、分離することができる。タイムチューブはまた、新規な視覚化、レイアウトアルゴリズム、およびインタラクションの実例を示す枠組みを与える。
【００６４】
本発明によるタイムチューブは、大きな文書の集まりの使用および構造における経時変化をいかに示すかという問題に対処する。様々な時点での２次元の環状木（または他のレイアウト）が計算される。存在するすべてのノードを用いて木をレイアウトする。ノードおよびリンクに色をつけて、付加、削除、および使用を示すようにしてもよい。本発明にしたがって様々な変形が可能である。本発明を使用して、ゼロックス社の１０−Ｋをファイルしてからのゼロックスのサイトの使用における変化等のインターネットの事象を解釈することもできる。
【００６５】
円形木を使用して、第３次元を時間を表すのに使用してもよい。タイムチューブの視覚化では、多数の円形木が空間軸に沿ってレイアウトされる。時間を表すのに空間軸を用いることにより、情報空間−時間を単一の視覚化で見ることとなり、情報空間−時間空間全体で簡単に理解するのを促進する。従来のディスプレイモニタ１０４は２次元の表示装置であるため、この２次元のディスプレイ１０４上に３次元表示構造を投射しなくてはならない。したがって、第３の次元は最初の２つの次元に投射されるが、この投射は３次元構造の力を無効にするものではない。この読者の多くは、映画は２次元スクリーンに投射されるが表示されている３次元の内容は簡単に理解、鑑賞できることを簡単に証明できるだろう。
【００６６】
本発明によるタイムチューブの情報空間−時間におけるスライスは、実際には互いに平行にレイアウトされるわけではない。各スライスは回転され、他のスライスと同じスクリーン面積を占めるようにされる。遠近法により、各スライスが互いに平行であれば、中央のスライスは側部のスライスよりも占める空間が小さくなる。さらに、見ている切頭体の左側にあるスライスの前面と、その右側にあるスライスの裏面を見ることになる。見ている際の興味度を注意深くモニタすることにより、システムによってあるスライスを強調したり、その他を弱めたりして、焦点＋内容の効果を得ることができる。円形木を見る者に向かって回転させると、このような多数の変数のマッピングが簡単になる。３次元の世界において円形木を２次元にすることにより、遠近感のゆがみおよび読みにくさはあるものの、マッピングの柔軟性がさらに大きくなる。
【００６７】
円形木の各々に異なるレイアウトを持たせるのではなく、すべての木に対して組み合わされたレイアウトが生成される。タイムチューブの時間範囲全体において存在したことのある全文書を考慮に入れて、単一の円形木のレイアウトを計算することにより、スライステンプレートを生成し、これを円形木のスライスのすべてにおいて使用する。
【００６８】
別の興味深いタイムチューブの変形例は、タイムチューブにおいて円形木を重ね、チューブ内を飛ばすか、または同様に、時間の順に円形木を次から次へと投げて、変化のアニメーションを形成することである。つまり、時間を空間にマッピングするのではなく、単に時間が時間にマッピングされる。この方法は、円形木が大きくなる可能性もあるため、よりコンパクトであり、人間の知覚システムの動き検出能力にからむものである。異なる時点での比較を行う能力は犠牲にするものの、変化の検出および一連の変化の解釈は高められる。
【００６９】
本発明によるタイムチューブは、シリンダ（円筒形）内に整列された一連の個々の２次元の視覚化体（スライス）からなる。ある状態から別の状態へと変形する際に一連のデータに対して行われる変形（例えば、新しいエンティティの追加、既存のエンティティの値の変更、物理的サイズのゆがみ）が視覚化される。タイムチューブは、ある状態から別の状態へと１つ以上の変形を遂げる可能性がある。変形は円筒形チューブの長さを利用し、チューブの長さ全体に種々の変形段階でのデータの２次元表現またはスライスが配置される。タイムチューブは、表現のサイズ、色、およびレイアウトを替えることによって一度に変形のいくつかの次元を符号化できる。タイムチューブが視覚化できる変形の例としては、（１）時間的なもの（ウェブサイト分析ツールに関していえば、ウェブページは時間が経つにつれて追加、変更、削除される）、（２）値ベースのもの（ウェブサイト分析ツールに関していえば、頻度が色で符号化されるため、ページの訪問率が変わると、その対応する色も変化する）、（３）空間的なもの（ウェブサイト分析ツールはこの機能を使用しないが、エンティティは縮小したり拡大したりし得る）等が挙げられるが、これに限られるわけではない。
【００７０】
データがいかにクラスタ化されるかというプロセスと、どの要素がどのクラスタに落ち着くかということを本発明により示すことができる。これらのタスク両方を同時に視覚的に行う機能はかなり便利なものである。さらに、サイズ、色、およびレイアウトにより重複してクラスタ化の種々の面を符号化でき、データにおける傾向およびパターンを特定するのが簡単になる。
【００７１】
本発明によるタイムチューブによって、いくつかの動作が可能になる。タイムチューブは円筒形の丸太状であるため、これをその軸に沿って回転させ、ユーザーの視点の近くにデータを移動させることができる。ユーザーはまた、１つのエンティティを選択し、各スライスにおいて対応するエンティティを強調する（ブラッシングといわれる技術）ことができる。ユーザーがあるスライスを特に面白いと感じると、それを捕らえて、タイムチューブからそのスライスをドラッグし、さらに調べることができる。スライスを回転させて、ユーザーに各スライスの正面の透視図を呈示できる。タイムチューブが３次元の作業空間にあるのであれば、ユーザーはタイムチューブを飛び回り、興味のある領域に対して近づいたり、離れたりできる。
【００７２】
図２１は、本発明による一連の関連したグラフを表示する方法を示す。ステップ２１０１で、すべてのグラフの一意的なノードすべてのインベントリ（一覧）を作成し、関連する一連のグラフのいずれかに存在したことのあるすべてのノードのリストを作成する。ステップ２１０２で、ステップ２１０１で生成されたインベントリに基づいて、スライステンプレート内でのノード位置が割当てられる。ステップ２１０３で、関連する一連のグラフの各々に存在する各ノードを、各ノードがあるグラフに対応する平面スライスに配置することによって、タイムチューブの平面スライスがレイアウトされる。
【００７３】
図２２は、本発明による方法２１００によって表示するのに適切な一連の関連グラフを示す。図２２は、関連する４つの別個のグラフを示す。すなわち、これらのグラフは共通ノードを有する。この４つのグラフをある時間にわたって起こったウェブサイトの発展として見てもよく、時間１に対応して示されるグラフの構造は、ウェブサイトの開始構造と見てもよい。時間２で、ノードＨおよびＩがノードＢの子として付加される。時間３で、ノードＤの子であったノードＮ，Ｏ，Ｐ，およびＱが削除される。時間４で、ノードＩ，Ｄ，Ｔ，およびＵが削除される。このように、数多くのノードが時間１から４にかけて常に残っているが、ある時間にかけてしか存在しないノードもあることが明らかとなる。
【００７４】
図２３は、タイムチューブを形成する平面スライスにおけるノードの配置を決定する平面テンプレートを示す。平面テンプレート２３００は、任意の時間に存在したことのあるすべてのノードのインベントリを作成することによって構築される。ステップ２１０１で行われるインベントリ作成の際に、任意の時間に存在したことのあるすべてのノードを表す木構造を形成するために各ノードの親も記録しなくてはならない。平面テンプレート２３００に示される点は、本発明によるタイムチューブを構成する各平面スライスにおける各ノードの配置に対応する。中央の点２３Ａは、ノードＡを表示するための点であり、点２３ＨはノードＨを表示するための点である。ノードの文字に２３を付けることで、各ノードに対応する平面テンプレートにおける位置の参照番号が簡単に得られる。
【００７５】
図２４は、本発明によるタイムチューブを構成する一連の平面スライスを示す。図２４の平面スライス２４００は、図２２の一連の関連グラフと図２３の平面テンプレート２３００に対応する。
【００７６】
図２５は、本発明による関連した一連のグラフを表示する方法のいくつかの局面を示す。図２５は、一連の平面スライスの次元の物理的なスケーリングを示す。点２５０１，２５０２，２５０３，および２５０４は各々同じノードを表す。ユーザーがカーソル２５７０を点２５０１上に置くと、線２５５０が、点２５０１−２５０４の関係を強調する。図２５はまた、時間４から時間３を見たときの４つの要素２５１１−２５１４の１つの要素２５１０へのクラスト化または凝集を示す。線２５６１−２５６４は、クラスト化されたノード２５１１−２５１４が時間３でノード２５１０になる関係を強調している。簡潔にするために、図２５は本発明による方法のいくつかの特徴を図示するのに用いられている。クラスタ化の状況を見るには、ユーザーは時間４の後に時間３が来るように、時間が右から左の方向に流れると考える必要がある。図２５はまた、ノード２５９０および２５９１のように時間３での深さ３におけるノードの追加と、ノード２５９２および２５９３のように時間４での深さ４におけるノードの追加を示す。時間が右から左の方向に流れるように見ると、図２５は、時間４で表示される一般化されたグラフ構造に適用できる一種のズームを示す。例えば、時間４に示されるグラフの深さ０，１，２のノードのズームまたは拡大された状態を時間１が示している。
【００７７】
さらに、本発明によるタイムチューブは、サイクルを含み得る任意の一般化されたグラフを示すことができる。また、各平面スライスの各ノードが平面テンプレートで特定されたのと同じ位置に配置されなくてはならないわけではない。例えば、ノード間の対応関係を示すのに平面スライスにおける物理的な位置の継続性に頼るのではなく、図２５の線２５５０等の半透明の線を使用してノード間の対応関係を示してもよい。
【００７８】
本発明のタイムチューブの局面での好適な実施形態のインタラクティブな方法により、ユーザーは、視覚化されたものと様々な態様でインタラクションをとることができる。たとえば、ボタンをクリックすることにより、システムによりすべてのスライスが回転されて、これらを正面から見ることができる。あるスライスをクリックすると、そのスライスを中心に焦点が合わされ、その週（またはその期間）の分のデータをより詳細に見ることができる。そのスライスは透明で円形の背景へともたらされ、タイムチューブ内のスライスが見える状態にされる。はじき上げるようなジェスチャにより、スライスはタイムチューブへと戻り、はじき落とすようなジェスチャによって、スライスは（わずかな角度を付けて）底部となる。スライス内を探索するのにカーソル制御装置１０５を使ってもよい。カーソルがあるノード上にあると、すべてのスライスにおいてそのノードが強調される。さらに、小さな情報領域がそのノードの詳細を示す。このインタラクションは、ユーザーが指でタイムチューブをブラッシングするようなもので、興味のある点の詳細を知ることができる。マウス１０５で探索しているとき、ユーザーはプログラムに対してブラウザ（Netscapeなど）にその特定のページを開くように指示することができ、本発明をウェブサーフィンツールとすることが可能である。マウス１０５があるノード上で活性化されると、ホップが１回のリンクが青線で示される。別のボタンでは視点が変わり、タイムチューブを真っ直ぐ見下ろすこととなる。また、連続する各スライスのアニメーションを正面から見ることもできる。これは、データの時間の次元を視覚化における時間の次元へとマッピングする。ノードを右クリックすると、そのノードのローカルな領域にズーミングされて、より詳細が示される。ホームキーをたたくと、グローバル（全体）な視界に戻る。これにより、アナリストの間で好まれる「ドリルダウン」操作が可能になる。ローカルなパターンを迅速に探索することは、アナリストたちにとって大いに興味のあることである。
【００７９】
ウェブサイトの使用パターンを視覚化することができると、アナリストは、本発明による方法を利用して興味深い質問に対する答えを得ることができる（例えば、何が人気のないものとなったのか、いつそうなったのか、ウェブサイトの再構築と相関関係があったのか、何が人気のあるページになったのか、いつそうなったのか、それはウェブサイトの再構築と相関関係があったのか、時間とともに追加されたアイテムにより使用度はどのような影響を受けたか、時間とともに削除されたアイテムにより使用度はどのような影響を受けたか、等）。アナリストがよく行うタスクに、２つの使用パターンの違いを求めることがある。視覚パターンを「見る」ことができると、アナリストは、そのもっとも大きな違いがどこにあるのかを知りたいと考えるであろう。すなわち、使用度が最も大きく上昇したのはどこか、最も大きく下降したのはどこか、使用度の変化は、ウェブサイトのある特定のトピックまたは領域と関係があるのか、等である。
【００８０】
本発明の別の局面では、接続される要素群における活性化拡散のプロセスおよび結果の両方を視覚化する新奇な方法を説明する。活性化拡散とは、接続される要素のネットワークにある量（活性化）を投入することによる影響を求める一般化されたプロセスである。具体的には、活性化拡散は、接続の強さを表すフローマトリックスＭを活性化ベクトルＡ（ｔ）で乗じ、新しいベクトルＡ（ｔ＋１）を得ることにより行われる。本発明によるタイムチューブおよび円形木を使用して、活性化拡散のプロセスを視覚化できる。
【００８１】
本発明は、ネットワーク状の文書群に存在する可能性のある関連性と、その関連性がいかに求められたかをどうやってユーザーに伝えるかという問題を解決する。これは特に文書の集まりが大きい場合に有用である。
【００８２】
本発明によると、活性化拡散によって興味度が予測され、ユーザーにわかりやすくするためにその活性化拡散が視覚化される。カーソルでネットワーク内のいくつかの箇所を探索し、活性化が拡散されるのを観察することにより、静止表示では不可能である、ユーザーのリンクの理解につながる。
【００８３】
本発明の非常に実用的な応用は、自分のまたは競争相手のウェブサイトに応用することである。より一般的に言えば、概ね木に例えることのできるどんなネットワークにも応用可能である。本発明はウェブサイトの視覚化を可能にし、それによってウェブサイトの管理者および設計者の理解を高め、競争力を持たせることができる。
【００８４】
活性化拡散のアルゴリズムでは、一般化されるグラフ構造に埋め込まれた活性化ネットワークが活性化マトリックスＲとしてモデル化される。活性化マトリックスＲは、各ノードがそれ専用の列および行を有するため、正方形である。対角線上にない各要素Ｒijは、ノードｊからノードｉに対する関連の強さを含み、対角線はゼロを含む。Ｒマトリックスの強さは、活性化の反復中に各ノードからそれ以外の各ノードに対してどれだけの活性化フローがあるかを決定する。一般化されたグラフ構造にもたらされている入力の活性化は、活性化入力ベクトルＣによって表され、Ｃiは、各反復中にノードｉにもたらされた活性化を表す。活性化のダイナミックスは、離散的な時間ステップｔ＝１，２，…，Ｎに対してモデル化され、ステップｔでの活性化はベクトルＡ（ｔ）によって表され、要素Ａi（ｔ）はステップｔでのノードｉにおける活性化レベルを表す。活性化フローの経時的進展は、以下の反復の式によって決定される。
【００８５】
Ａ（ｔ）＝Ｃ＋ＭＡ（ｔ−１）
上記の活性化拡散反復の式において、Ｍは、ノード間の活性化のフローおよび減衰を決定するフローマトリックスである。フローマトリックスＭは、以下の式により特定される。
【００８６】
Ｍ＝（１−ｇ）Ｉ＋ａＲ
上記式において、０＜ｇ＜１であり、ｇは、それ以上活性化入力を受けないときにゼロに戻るノード活性の緩和を決定するパラメータであり、ａは、あるノードからその近傍のものへの活性化の拡散量を表す。Ｉは、恒等行列である。
【００８７】
上述のように、円形木は、接続されるアイテムの集まりの２次元表現である。ウェブ分析ツールの場合、アイテムはウェブページであり、接続は文書間に存在するハイパーリンクである。円形木に垂直な面は、そのページが選択されたときに訪ねられた頻度を符号化するのに使用してもよい。本発明による活性化拡散に応用した場合、円形木に垂直な面は各ノードが受ける活性化量を符号化し、活性化バーとも呼ばれる。対応する活性化拡散値を示す要素の数は可変である。表示する要素の数は、これに限定されるわけではないが、たとえば、あらかじめ定められたもの（たとえば上位１００の文書について活性化拡散値が示される場合など）、特定された上位のパーセンテージや所定のしきい値等に基づいて、決定することができる。各活性化バーの色は、本発明によると１色に限られるわけではなく、活性化の値によって様々な色を使ったり、グラデーションであってもよい。活性化を拡散するのに種々のネットワークを使用できる。本発明によるウェブサイト分析ツールでは、内容、使用度、およびトポロジネットワークが使用されているが、推奨等の他のネットワークを使用してもよい。活性化は１つ以上のページや１つ以上のネットワークに同時に拡散されてもよい。
【００８８】
活性化拡散の視覚化によって行えるよりパワフルな機能の一つに、種々のネットワークにおける活性化拡散の結果を示すことが挙げられる。さらに、重みづけ機構を用いてネットワークが組み合わされる場合、活性化バーにおいて各ネットワークに異なる色を利用することにより、ページの活性化に対する各ネットワークの貢献度を評価することができる。根底にある様々なフローネットワーク（例えば内容や使用度等）を使用することの効果は、結果として得られる活性化パターンを各ネットワークから減じ、その差を表示することによって判断できる。
【００８９】
視覚化はインタラクティブであるため、ネットワークで拡散する活性化の量は、ページ上でカーソルが費やした時間量によって決定できる。このプロセスをドエル時間と称する。活性化入力を投入するのに使用するページの組は、ユーザーが視覚化において選択したページの履歴または他の何らかの手段（ユーザーがページをそこへ、かつそこからドラッグ・アンド・ドロップできる現在の活性化源を表示するテキストウィンドウなど）によって決定できる。さらに、そのページの組は、選択されたページの近傍にあるもの（ハイパーリンク構造、内容、使用度または他の何らかの尺度で）によってページが決定される一種の「ファジイブラッシング」によって決定できる。本発明による活性化拡張の結果を視覚化する特徴を、以下にさらに説明する。
【００９０】
図２６は、Matlab（従来の数学パッケージ）においてモデル化されるような活性化拡散を示す。ｘ軸はゼロックス社のウェブサイトの幅優先探索により順序決めされた個々の文書を表し、ｙ軸は各文書が受ける活性化の量を表し、ｚ軸は活性化拡散プロセスの各ステップを表す。プロセスの結果はベクトルであり、Matlabでは２次元のプロットとして視覚化できる。
【００９１】
活性化拡散の反復的なプロセスを本発明によるタイムチューブを用いて視覚化できる。タイムチューブの連続した円形木の各々（平面スライスとも称する）を用いて、活性化プロセスの各段階における活性化の結果を示す。この目的のためには活性化バーは活性化を表示する好適な方法ではない。というのは、各円形木に垂直な面を用いて変形を符号化するからである。これに代わって、円形木における各ノードの色を用いて活性化値を表示する。タイムチューブを用いた活性化拡散の視覚化により、ユーザーが位相変移の特定等、アルゴリズムにおける興味深い事象を特定、分析することが可能になる。位相変移は、活性化拡散アルゴリズムの連続するステップにおけるノードの活性化における変更がその符号を逆にする時に起こる。
【００９２】
図２７は、本発明による一般化されたグラフ構造に関連する活性化拡散アルゴリズム結果表示方法を示す。ステップ２７０１において、円形木が平面に表示される。ステップ２７０２で、活性化拡散アルゴリズムの入力ベクトルＣが決定される。ステップ２７０３で、活性化拡散ベクトルＡがＮ回の反復について反復的に計算される。ステップ２７０４で、最終活性化ベクトルＡ（Ｎ）が円形木の平面に垂直に表示される。ステップ２７０５で、方法２７００により、活性化拡散アルゴリズムに対する入力がさらにあるかどうかが判断される。入力がさらにあれば、分岐２７５０によって方法はステップ２７０２へと戻り、新しい活性化入力ベクトルＣが使用される。ステップ２７０５でそれ以上入力がなければ、分岐２７５１により方法はステップ２７０６で終了する。
【００９３】
図２８は、本発明による活性化拡散アルゴリズムの結果を表示する方法を示す。本発明によると、活性化入力は種々のインタラクティブな態様で指定できる。たとえば、図２８に示されるように、カーソル２８０１を表示されたノード２８０５に置き、このノードで活性化入力を経時的に累積加算するようにしてもよい。例えば、カーソル２８０１がノード２８０５上に長くあるほど、このノードに対してより多くの活性化入力が生成される。別の変形例として、あるノードに対して活性化入力を蓄積し始めるようにするのに、カーソルをそのノードの上に置き、マウスのボタンを押すことなどで選択しなくてはならないようにしてもよい。ユーザーはあるノードに対して活性化を加算してしまうと、カーソル２８０１を別のノードに移して、前に選択したノードに対して生成された活性化入力を維持しながら、その別のノードでの活性化の加算を始めるようにしてもよい。例えば、図２８において、ユーザーは、カーソルを根ノード２８９９上に置いて根ノードをある期間にわたって選択することにより根ノードに対する活性化入力を加算しており、次にカーソル２８０１をノード２８０５へと動かして、根ノード２８９９に対してすでに定められた活性化入力に影響を与えることなく、ノード２８０５に対する活性化入力を加算し始めている。いかなる時も、表示２８００は、そのときに存在する活性化入力ベクトルＣから結果として得られる最終活性化ベクトルＡ（Ｎ）を反映する。したがって、Ｎ個のステップの反復型活性化拡散アルゴリズムは、一般化されたグラフ構造の任意のノードについて活性化入力の量を変えることによって新しい活性化入力ベクトルＣが生成される限り、継続的に実行される。図２８は一般化されたグラフ構造の円形木の表現を示しているが、上述のように、一般化されたグラフ構造に存在する多くのリンクを、この表示される木構造から省略してもよい。したがって、本発明による活性化拡散アルゴリズムの結果表示方法の別の局面によると、ユーザーがノードを選択するたびに半透明の線が現れ、一般化されたグラフ構造における省略されたリンクを示す。例えば、図２８において、ユーザーはノード２８０５を選択しており、半透明の線２８２０および２８２１はノード２８０５をそれぞれノード２８０６および２８０７に接続する。半透明の線２８２０および２８２１は、一般化されたグラフ構造に存在するものの木構造では省略されたリンクを表す。これらの半透明の線２８２０および２８２１により、ユーザーは活性化入力が加えられたノードから活性化が拡散したノードへとどのように活性化が拡散したかを理解しやすくなるであろう。例えば、２８０５で加えられた活性化の一部が恐らく、木構造では示されなかったリンク２８２１を介してノード２８０７へと拡散しているであろう。活性化入力をノードに加える別の機構では、ノードを選択し、加えるべき活性化量をタイプする。ユーザーはいつでも活性化入力ベクトルＣをリセットして活性化入力を再びゼロから加算し始めることができる。ノード上のカーソルのドエル時間を測定することによる活性化入力ベクトルの形成と最終の活性化の表示がインタラクティブな特徴を持つことで、フローネットワークのダイナミックなシミュレーションが実現され、それによりユーザーの一般化されたグラフ構造のダイナミックスに対する理解を大きく促進する。
【００９４】
図２９は、（図２８を参照して説明したＮ回反復した後のものだけでなく）Ｎ回の反復中の活性化ベクトルＡ（ｔ）の状態を表示する方法を示す。入力ベクトルＣがステップ２９０１で決定されると、ステップ２９０２で活性化拡散ベクトルＡがＮ回の反復について計算され、その反復ステップのいくつかまたはすべてにおいて活性化拡散ベクトルＡ（ｔ）の値（０ないしＮにおけるいくつかまたはすべてのｔの値）が保存される。ステップ２９０３で、選択された活性化ベクトルが、タイムチューブを構成する平面スライスに色で符号化された種々のリンクおよび／またはノードにおける活性化レベルを有するタイムチューブ内の円形木として表示される。これに代わる実施形態として、活性化拡散アルゴリズムの種々の時間ステップでの活性化ベクトルをタイムチューブの時間軸と一致した活性化バーで表示してもよいが、これは平面スライス間の時間の次元に十分な間隔があって、活性化バーがタイムチューブの隣接する平面スライスと交差しない場合に限られる。これを図３０に示す。
【００９５】
図３０において、時間１で大量の活性化がノード３０１１に加えられる。時間２において、その活性化のいくらかがノード３０２２，３０３２，３０４２，３０５２，３０７２，３０６２，３０８２，および３０９２へと拡散している。時間４までに、最終活性化ベクトルＡ（Ｎ）が示される。大量の活性化が、Ｎ回の反復後、ノード３０８４で終了している。活性化拡散アルゴリズムは（適切なフローマトリックスＭと使用すると）漸近収束する最終活性化ベクトルＡ（Ｎ）を生成するため、反復の最後の方における変化が小さくなることから、反復の最後の方よりも最初の方をより頻繁に表示するのが有用な場合がある。または、表示すると選択した反復は、変化が最も大きいところに基づいても良いし、活性化拡散アルゴリズム中に検出された位相変移に基づいても良く、または、もちろんＮ−１のすべての中間活性化ベクトルを表示してもよい。図２８の円形木表示および図３０のタイムチューブ表示において、２つ以上の活性化ベクトルを計算し、表示しても良い。たとえば、ウェブサイトの分析者は、推奨する使用パターンと観察された使用パターンとの差の表示を、２つの別個のフローマトリックスＭ１およびＭ２に同じ活性化入力ベクトルＣを拡散させて、結果として得られる最終活性化ベクトル間の差をその円形木に表示することで行いたいと考えるかもしれない。もちろん、この差の計算のプロセスは、図３０に示されるようにタイムチューブ上に示すことができる。
【００９６】
さらに、異なるフローマトリックスＭ１およびＭ２の重み付けした組合わせを計算して、その結果をタイムチューブまたは円形木上に表示し、活性化ベクトルを表す活性化バーを分割して、各活性化レベルのどの部分がどのフローマトリックスによるものかがユーザーにわかるようにしても良い。
【００９７】
ウェブはまだ初期段階にあるため、ウェブ環境におけるインタラクションや関係があまり良く理解されていないのも不思議ではない。ワールドワイドウェブがユーザーの数においてもアクセスできる文書の数においても拡大するにつれて、情報の提供者と、情報の特徴と、情報のユーザーとの相関関係の理解という問題は恐らく残っていくであろう。
【００９８】
本発明による視覚化方法は、表示できるデータ量の面でウェブ分析プログラムの機能を拡張するとともに、ウェブ環境の発展パターンをより明らかにするものである。
【００９９】
本発明の種々の局面をその実施形態に照らして説明してきたが、これらの実施形態は単に例であり、これに限定されるものではない。上記の本発明の詳細な説明は、単に例示および説明を目的とするものである。本発明はここに開示した形態に尽きるものでも限定されるものでもなく、明らかに上述の教示に鑑みて数多くの変形および変更が可能である。ここで説明した実施形態は本発明の原理とその実用を最も良く説明し、当業者が本発明を種々の実施形態で意図する用途に適したように種々の変更を加えて最良に利用できるように選択されたものである。当業者であれば、この開示によって上記の実施形態に種々の追加または変更を加えることが可能である。これらの追加および変更も本発明の範囲内であり、その範囲は前掲の特許請求の範囲によって定義される。
（付記）本願は以下の発明を提供する。一般化されたグラフ構造に関連する活性化拡散アルゴリズムの結果を表示する方法であって、（ａ）前記一般化されたグラフ構造のすべてのノードを木構造で表示するステップと、（ｂ）活性化入力ベクトルＣを得るステップと、（ｃ）フローマトリックスＭを用いてＮ回の反復について活性化ベクトルＡを反復的に計算するステップと、（ｄ）前記木構造のノード上に最終活性化ベクトルＡ（Ｎ）のエントリを表示するステップと、を含むことを特徴とする方法。上記発明であって、前記ステップ（ａ）が、（ｅ）前記木構造を平面的な円形木として表示するステップを含むことを特徴とする方法。上記発明であって、前記ステップ（ａ）が、（ｆ）前記木構造を平面的なつぶれた円錐形として表示するステップを含むことを特徴とする方法。上記発明であって、前記ステップ（ｃ）が、（ｇ）Ｎ回の反復について第１および第２のフローマトリックスＭ１およびＭ２を用いて第１および第２の活性化ベクトルＡ１およびＡ２を反復的に計算するステップを含み、前記ステップ（ｄ）が、（ｈ）第１および第２の最終活性化ベクトルＡ１（Ｎ）およびＡ２（Ｎ）の対応するエントリの差を、該対応するエントリが関連する前記木構造のノード上に表示するステップを含むことを特徴とする方法。上記発明であって、前記ステップ（ｃ）が、（ｉ）Ｎ回の反復について第１および第２のフローマトリックスＭ１およびＭ２を用いて第１および第２の活性化ベクトルＡ１およびＡ２を反復的に計算するステップを含み、前記ステップ（ｄ）が、（ｊ）第１および第２の最終活性化ベクトルＡ１（Ｎ）およびＡ２（Ｎ）の対応するエントリの和を、該対応するエントリと関連する前記木構造のノード上に、該対応するエントリのうちの１つをその各々が表す第１および第２の異なる色のセグメント（部分）を有する活性化バーとして表示するステップを含むことを特徴とする方法。
一般化されたグラフ構造に関連する活性化拡散アルゴリズムの結果を表示する方法であって、（ａ）活性化入力ベクトルＣを得るステップと、（ｂ）フローマトリックスＭを用いてＮ回の反復について活性化ベクトルＡを反復的に計算するステップと、（ｃ）複数の構造的に同一である、前記一般化されたグラフ構造の平面グラフ表現を表示するステップとを含み、該平面グラフ表現の各々はＮ回の反復のうちの一意的な一つに対応し、ノードの活性化レベルが該平面グラフ表現に色で符号化されることを特徴とする方法。上記発明であって、前記複数の構造的に同一なグラフ表現における最初の平面グラフ表現が活性化入力ベクトルＣに対応し、前記複数の構造的に同一なグラフ表現における最後の平面グラフ表現が最終活性化ベクトルＡ（Ｎ）に対応することを特徴とする方法。
コンピュータ読み出し可能記憶媒体であって、前記コンピュータ読み出し可能記憶媒体上で実現され、一般化されたグラフ構造に関連する活性化拡散アルゴリズムの結果を表示する方法を実行するようにコンピュータをプログラムするためのコンピュータ読み出し可能プログラムコードを含み、前記方法が（ａ）前記一般化されたグラフ構造のすべてのノードを木構造で表示するステップと、（ｂ）活性化入力ベクトルＣを得るステップと、（ｃ）フローマトリックスＭを用いてＮ回の反復について活性化ベクトルＡを反復的に計算するステップと、（ｄ）前記木構造のノード上に最終活性化ベクトルＡ（Ｎ）のエントリを表示するステップと、を含むことを特徴とするコンピュータ読み出し可能記憶媒体。上記発明における、コンピュータ読み出し可能プログラムコードを含むコンピュータ読み出し可能記憶媒体であって、前記ステップ（ａ）が、（ｅ）前記木構造を平面的な円形木として表示するステップを含むことを特徴とするコンピュータ読み出し可能記憶媒体。上記発明におけるコンピュータ読み出し可能プログラムコードを含むコンピュータ読み出し可能記憶媒体であって、前記ステップ（ａ）が、（ｆ）前記木構造を平面的なつぶれた円錐形として表示するステップを含むことを特徴とするコンピュータ読み出し可能記憶媒体。上記発明におけるコンピュータ読み出し可能プログラムコードを含むコンピュータ読み出し可能記憶媒体であって、前記ステップ（ｃ）が、（ｇ）Ｎ回の反復について第１および第２のフローマトリックスＭ１およびＭ２を用いて第１および第２の活性化ベクトルＡ１およびＡ２を反復的に計算するステップを含み、前記ステップ（ｄ）が、（ｈ）第１および第２の最終活性化ベクトルＡ１（Ｎ）およびＡ２（Ｎ）の対応するエントリの差を、該対応するエントリが関連する前記木構造のノード上に表示するステップを含むことを特徴とするコンピュータ読み出し可能記憶媒体。上記発明におけるコンピュータ読み出し可能プログラムコードを含むコンピュータ読み出し可能記憶媒体であって、前記ステップ（ｃ）が、（ｉ）Ｎ回の反復について第１および第２のフローマトリックスＭ１およびＭ２を用いて第１および第２の活性化ベクトルＡ１およびＡ２を反復的に計算するステップを含み、前記ステップ（ｄ）が、（ｊ）第１および第２の最終活性化ベクトルＡ１（Ｎ）およびＡ２（Ｎ）の対応するエントリの和を、該対応するエントリと関連する前記木構造のノード上に、該対応するエントリのうちの１つをその各々が表す第１および第２の異なる色のセグメント（部分）を有する活性化バーとして表示するステップを含むことを特徴とするコンピュータ読み出し可能記憶媒体。
コンピュータ読み出し可能記憶媒体であって、前記コンピュータ読み出し可能記憶媒体上で実現され、一般化されたグラフ構造に関連する活性化拡散アルゴリズムの結果を表示する方法を実行するようにコンピュータをプログラムするためのコンピュータ読み出し可能プログラムコードを含み、前記方法が（ａ）活性化入力ベクトルＣを得るステップと、（ｂ）フローマトリックスＭを用いてＮ回の反復について活性化ベクトルＡを反復的に計算するステップと、（ｃ）複数の構造的に同一である、前記一般化されたグラフ構造の平面グラフ表現を表示するステップとを含み、該平面グラフ表現の各々はＮ回の反復のうちの一意的な一つに対応し、ノードの活性化レベルが該平面グラフ表現に色で符号化されることを特徴とするコンピュータ読み出し可能記憶媒体。上記発明におけるコンピュータ読み出し可能プログラムコードを含むコンピュータ読み出し可能記憶媒体であって、前記複数の構造的に同一なグラフ表現における最初の平面グラフ表現が活性化入力ベクトルＣに対応し、前記複数の構造的に同一なグラフ表現における最後の平面グラフ表現が最終活性化ベクトルＡ（Ｎ）に対応することを特徴とするコンピュータ読み出し可能記憶媒体。
一般化されたグラフ構造に関連する活性化拡散アルゴリズムの結果を表示するための装置であって、プロセッサと、前記プロセッサに結合される表示デバイスと、前記プロセッサに結合され、前記一般化されたグラフ構造に関連する活性化拡散アルゴリズムの結果を表示する方法を実行するように前記装置をプログラムするためのプロセッサ読み出し可能プログラムコードを含むプロセッサ読み出し可能記憶媒体と、を備え、前記方法が、（ａ）前記一般化されたグラフ構造のすべてのノードを木構造で表示するステップと、（ｂ）活性化入力ベクトルＣを得るステップと、（ｃ）フローマトリックスＭを用いてＮ回の反復について活性化ベクトルＡを反復的に計算するステップと、（ｄ）前記木構造のノード上に最終活性化ベクトルＡ（Ｎ）のエントリを表示するステップと、を含むことを特徴とする装置。
一般化されたグラフ構造に関連する活性化拡散アルゴリズムの結果を表示するための装置であって、プロセッサと、前記プロセッサに結合される表示デバイスと、前記プロセッサに結合され、一般化されたグラフ構造に関連する活性化拡散アルゴリズムの結果を表示する方法を実行するように前記装置をプログラムするためのプログラムコードを含むプロセッサ読み出し可能記憶媒体と、を備え、前記方法が、（ａ）活性化入力ベクトルＣを得るステップと、（ｂ）フローマトリックスＭを用いてＮ回の反復について活性化ベクトルＡを反復的に計算するステップと、（ｃ）複数の構造的に同一である、前記一般化されたグラフ構造の平面グラフ表現を表示するステップとを含み、該平面グラフ表現の各々はＮ回の反復のうちの一意的な一つに対応し、ノードの活性化レベルが該平面グラフ表現に色で符号化されることを特徴とする装置。
【図面の簡単な説明】
【図１】  本発明の方法を実行するのに適切な汎用コンピュータを示す図である。
【図２】  一般化されたグラフ構造を示す図である。
【図３】  図２の一般化されたグラフ構造から生成される木構造を示す図である。
【図４】  各ノードの深さを示す図３の木構造の別の図である。
【図５】  図３および図４の木構造の円形木表現を示す図である。
【図６】  ９つのノードを有し、多くのサイクルを含む一般化されたグラフ構造の図であって、本発明による種々の使用度ベースの木構造生成方法を説明するのに用いる図である。
【図７】  図６の一般化されたグラフ構造に対応するトポロジマトリックスを示す図である。
【図８】  図６の一般化されたグラフ構造のノードに関する使用度パラメータベクトルを示す図である。
【図９】  本発明による一般化されたグラフ構造から木構造を生成するための幅優先方法を示す図である。
【図１０】  図８のノード使用度パラメータベクトルを用いて、図９の幅優先方法によって図６の一般化されたグラフ構造から生成される木構造の図である。
【図１１】  図６の一般化されたグラフ構造のリンクに関する使用度パラメータマトリックスの図である。
【図１２】  図１１のリンク使用度パラメータマトリックスを用いて、図９の幅優先方法によって図６の一般化されたグラフ構造から生成される木構造の図である。
【図１３】  本発明による一般化されたグラフ構造から木構造を生成するための深さ優先方法を示す図である。
【図１４】  図８のノード使用度パラメータベクトルを用いて、図１３の深さ優先方法によって図６の一般化されたグラフ構造から生成される木構造の図である。
【図１５】  その親に対して兄弟ノードを表示するための本発明によるノード配置の図であって、そのレイアウト角度がその使用度パラメータによってランク付けされた最高ランクの兄弟ノード同士が最適に分離されることを示す図である。
【図１６】  その親に対して兄弟ノードを表示するための本発明によるノード配置の図であって、そのレイアウト角度がその使用度パラメータによってランク付けされたランクとともに単純に増大することを示す図である。
【図１７】  別の一般化されたグラフ構造を示す図である。
【図１８】  本発明による使用度に基づいて木構造を表示する方法を示す図である。
【図１９】  本発明による方法によって表示される図１７の一般化されたグラフ構造のつぶれた円錐形の木表現を示す図である。
【図２０】  本発明による方法によって表示される図１７の一般化されたグラフ構造の円形木表現を示す図である。
【図２１】  本発明によるタイムチューブにおける関連した一連のグラフを表示する方法を示す図である。
【図２２】  本発明によるタイムチューブ内の一連の平面スライスとして表示するのに適切な関連した一連のグラフを示す図である。
【図２３】  本発明による関連した一連のグラフのタイムチューブの表現の平面スライスにおけるノード配置を決定するための平面テンプレートを示す図である。
【図２４】  本発明による方法によって表示される変化する木構造を表すタイムチューブ内の一連の平面スライスを示す図である。
【図２５】  タイムチューブにおける一連の平面スライスを示す図であって、時間軸が左から右へと動くように解釈すると新しいノードの追加と空間の縮小を示すとともに、時間軸が右から左へと動くように解釈するとノードのクラスト化および空間の拡大を示す図である。
【図２６】  従来の数学パッケージによって表示された活性化拡散アルゴリズムにおけるウェブページの活性化レベルを示す図である。
【図２７】  本発明による活性化拡散アルゴリズムにおいてインタラクティブに活性化入力を受け、その結果を表示するための方法を示す図である。
【図２８】  図２６の方法による活性化拡散結果の表示と新しい活性化入力の指定を示す図である。
【図２９】  タイムチューブの一連の平面スライスにおいて活性化拡散プロセスを表示するための本発明の方法を示す図である。
【図３０】  本発明の図２８の方法によって生成されるタイムチューブの一連の平面スライスにおける活性化拡散プロセスの表示を示す図である。
【符号の説明】
１０２  マイクロプロセッサ、１０３  ハードディスク、１０４  ディスプレイモニタ、１０５  カーソル制御装置、１０６  キーボード、１０９  グラフィックスコプロセッサ、１１０  モデム。
【図１】
0004223133.tif 000002
【図２】
0004223133.tif 000003
【図３】
0004223133.tif 000004
【図４】
0004223133.tif 000005
【図５】
0004223133.tif 000006
【図６】
0004223133.tif 000007
【図７】
0004223133.tif 000008
【図８】
0004223133.tif 000009
【図９】
0004223133.tif 000010
【図１０】
0004223133.tif 000011
【図１１】
0004223133.tif 000012
【図１２】
0004223133.tif 000013
【図１３】
0004223133.tif 000014
【図１４】
0004223133.tif 000015
【図１５】
0004223133.tif 000016
【図１６】
0004223133.tif 000017
【図１７】
0004223133.tif 000018
【図１８】
0004223133.tif 000019
【図１９】
0004223133.tif 000020
【図２０】
0004223133.tif 000021
【図２１】
0004223133.tif 000022
【図２２】
0004223133.tif 000023
【図２３】
0004223133.tif 000024
【図２４】
0004223133.tif 000025
【図２５】
0004223133.tif 000026
【図２６】
0004223133.tif 000027
【図２７】
0004223133.tif 000028
【図２８】
0004223133.tif 000029
【図２９】
0004223133.tif 000030
【図３０】
0004223133.tif 000031