(57)【要約】【課題】階層を考慮してウェブページをランク付けすることを対象とするシステム、方法、およびデータ構造を提供する。【解決手段】ワールドワイドウェブの階層構造およびリンク関係を用いて、ウェブ検索のためのページ重要性ランキングを提供する。リンク関係は、階層構造のそれぞれにおけるハイレベルのノードに集約される。リンクグラフ分析を集約されたリンク関係に関して実行して、各ノードの重要性を判定する。各ノードの重要性は、そのノードに関連付けられたページに伝搬することができる。各ページにつき、そのページの重要性と、そのページに関連付けられたノードの重要性とを用いて、ページ重要性ランキングを計算する。【選択図】図１
2006127529.tif 000002
【特許請求の範囲】
【請求項１】
ウェブ上のコンテンツを評価する方法であって、
ウェブ上の複数のページを識別することと、
複数のノードを識別することであって、各ノードは前記ページの少なくとも１つが対応する階層構造に関連付けられていることと、
前記複数のページを前記対応するノードにグループ化することと、
各ノードにつき、そのノードと他のノードとの間のリンク関係に少なくとも部分的に基づいて第１の値を判定することと、
各ページにつき、そのページの特性に少なくとも部分的に基づいて第２の値を判定することと、
各ページの重要性値を、そのページに関連付けられた前記第２の値と、そのページが対応するノードに関連付けられた前記第１の値とに少なくとも部分的に基づいて判定することと
を備えることを特徴とする方法。
【請求項２】
前記ノードは、ホスト、ドメイン、インデックスページの少なくとも１つを含むことを特徴とする請求項１に記載の方法。
【請求項３】
各ノードにつき、
そのノードに対応するページのインターリンクを識別することであって、前記インターリンクは前記ノードに対応するページを指し、他のノードに対応する他のページに含まれるリンクを表すことと、
前記識別されたインターリンクを集約することと、
集約されたインターリンクの総数に少なくとも部分的に基づいて第３の値を判定することと、
前記第３の値に少なくとも部分的に基づいて前記ノードの前記第１の値を判定することと
をさらに備えることを特徴とする請求項１に記載の方法。
【請求項４】
前記複数の第３の値を行列として表すことと、
前記行列に関し操作して、前記ノードの複数の第１の値を計算することと
をさらに備えることを特徴とする請求項３に記載の方法。
【請求項５】
前記行列はデータアレイによって表され、前記複数の第１の値は前記データアレイから反復的に計算されることを特徴とする請求項４に記載の方法。
【請求項６】
前記特性は、前記対応するノードの階層構造内の前記ページのレベルを含むことを特徴とする請求項１に記載の方法。
【請求項７】
前記ページのレベルは、前記ページに関連付けられたＵＲＬ（Ｕｎｉｆｏｒｍ  Ｒｅｓｏｕｒｃｅ  Ｌｏｃａｔｏｒ）によって表されることを特徴とする請求項６に記載の方法。
【請求項８】
前記特性は、前記ページに関連付けられたインターリンクおよびイントラリンクの数を含み、前記イントラリンクは特定のノードに対応するページを指し、前記特定のノードに対応するページに含まれるリンクを表し、前記インターリンクは前記ページを指し、他のノードに対応する他のページに含まれるリンクを表すことを特徴とする請求項１に記載の方法。
【請求項９】
前記特性は、前記ページがインデックスページであるかどうかを含むことを特徴とする請求項１に記載の方法。
【請求項１０】
クエリを受け取ることと、
前記クエリとの類似性を有するページを検索することと、
検索によって返された各ページにつき、そのページと前記クエリとの間の類似性に少なくとも部分的に基づいて関連性値を判定することと
をさらに備えることを特徴とする請求項１に記載の方法。
【請求項１１】
返された各ページを、そのページに関連付けられた前記関連性値および前記重要性値に少なくとも部分的に基づいてランク付けすることと、
前記クエリに応答して、前記返されたページに関連付けられたリンクのリストを提供することであって、前記リンクは前記返されたページがランク付けされた順序に少なくとも部分的に基づいて前記リスト上でランク付けされることと
をさらに備えることを特徴とする請求項１０に記載の方法。
【請求項１２】
ウェブ上のページに関するデータを収容するデータストアであって、各ページの前記データは、前記ページの特性と、前記ページが対応するホストとを示すデータストアと、
前記データストア中の前記データから前記ページのそれぞれを指すリンクを判定するように構成されたランク付けモジュールであって、前記ランク付けモジュールはまた、各ホストに関連付けられた前記リンクを集約し、前記集約されたリンクに基づいて前記ホストの重み値を計算するように構成され、前記ランク付けモジュールは、各ページの重要性値を、そのページに対応する前記ホストの重み値と、そのページの前記特性とに少なくとも部分的に基づいて計算するようにさらに構成されたランク付けモジュールと
を備えたことを特徴とするシステム。
【請求項１３】
前記ページの特性は、前記ページを指すリンク、前記対応するノードの階層構造内の前記ページのレベル、前記ページがインデックスページであるかどうかの少なくとも１つを含むことを特徴とする請求項１２に記載のシステム。
【請求項１４】
前記ウェブ上の所望のページに対するクエリに応答するように構成された検索エンジンであって、前記クエリは前記所望のページ中のコンテンツを表すパラメータを含み、前記検索エンジンはまた、前記クエリに関連のあるページを返し、前記返されたページのそれぞれに関連性値を割り当てるように構成され、前記検索エンジンは、前記ランク付けモジュールからの、前記返されたページのそれぞれの前記重要性値を識別するようにさらに構成された検索エンジンをさらに備えたことを特徴とする請求項１２に記載のシステム。
【請求項１５】
前記検索エンジンは、前記返されたページのそれぞれを、そのページに関連付けられた関連性値および重要性値に少なくとも部分的に基づいてランク付けし、前記返されたページのリンクのリストを返し、前記リンクは、前記返されたページに関連付けられたランク付けに従って前記リンク中で順序付けられるようにさらに構成されたことを特徴とする請求項１４に記載のシステム。
【請求項１６】
前記ウェブを検索し、前記データストアに含まれる前記ページに関するデータを提供するように構成されたウェブクローラをさらに備えたことを特徴とする請求項１２に記載のシステム。
【請求項１７】
前記ウェブクローラは、前記ページに関するデータを検索可能データベースとして提供するようにさらに構成されたことを特徴とする請求項１６に記載のシステム。
【請求項１８】
データ構造で符号化された１つまたは複数のコンピュータ可読媒体であって、
識別子を含む第１のデータフィールドであって、各識別子はウェブ上のページを識別する第１のデータフィールドと、
第１のセットの値を含む第２のデータフィールドであって、前記第１のセット中の値のそれぞれはホストの重要性を表し、ホストのそれぞれは前記第１のデータフィールド中のページの少なくとも１つが対応する階層構造に関連付けられた第２のデータフィードと、
第２のセットの値を含む第３のデータフィールドであって、前記第２のセット中の値のそれぞれは前記第１のデータフィールド中で識別されるページの重要性を表す第３のデータフィールドと、
第３のセットの値を含む第４のデータフィールドであって、前記第３のセット中の値のそれぞれは前記第１のデータフィールド中で識別されるページのランク付けを表し、前記ランク付けは前記ページに関連付けられた前記第２のセットからの値と、前記ページが対応するホストに関連付けられた前記第１のセットからの値とに少なくとも部分的に基づいて判定される第４のデータフィールドと
を備えたことを特徴とする１つまたは複数のコンピュータ可読媒体。
【請求項１９】
前記第１のデータフィールド中の前記識別子は、前記ページに関連付けられたＵＲＬを含むことを特徴とする請求項１８に記載の１つまたは複数のコンピュータ媒体。
【請求項２０】
前記第１のセット中の値は、前記ホスト間のリンク関係に少なくとも部分的に基づいて判定されることを特徴とする請求項１８に記載の１つまたは複数のコンピュータ媒体。
【請求項２１】
前記リンク関係は、前記ホストに対応するページ間の集約されたリンクを表すことを特徴とする請求項２０に記載の１つまたは複数のコンピュータ媒体。
【請求項２２】
前記第１のセット中の値は、各ページの特性に少なくとも部分的に基づいて判定されることを特徴とする請求項１８に記載の１つまたは複数のコンピュータ媒体。
【請求項２３】
前記特性は、前記ページを指すリンク、前記対応するホストの階層構造内の前記ページのレベル、前記ページがインデックスページであるかどうかの少なくとも１つを含むことを特徴とする請求項２２に記載の１つまたは複数のコンピュータ媒体。
【請求項２４】
前記第１のセット中の値および前記第２のセット中の値は、前記第４のセット中の値を判定するために正規化されることを特徴とする請求項２２に記載の１つまたは複数のコンピュータ媒体。
【請求項２５】
ウェブ上のページに関するデータを収集するための手段と、
前記ページが対応するホストを判定するための手段と、
各ホストの重要性を判定するための手段と、
各ページの重要性を判定するための手段と、
各ページを、そのページの重要性および対応するホストの重要性に少なくとも部分的に基づいてランク付けするための手段と
を備えたことを特徴とする装置。
【請求項２６】
階層ランダムウォーク分析に少なくとも部分的に基づいて各ホストの前記重要性を判定するための手段をさらに備えたことを特徴とする請求項２５に記載の装置。
【請求項２７】
ホストの前記重要性を、前記ホストに対応する各ページに伝搬するための手段をさらに備えたことを特徴とする請求項２５に記載の装置。
【請求項２８】
各ホストにおける前記ページのリンク関係を集約するための手段と、
各ホストの前記重要性を、そのホストに関連付けられた前記集約されたリンク関係に少なくとも部分的に基づいて判定するための手段と
をさらに備えたことを特徴とする請求項２５に記載の装置。
【請求項２９】
前記ホストに関連付けられた前記集約されたリンク関係を、前記ホストに関連付けられたページを指すインターリンクに少なくとも部分的に基づいて判定するための手段をさらに備えたことを特徴とする請求項２８に記載の装置。
【請求項３０】
各ページの前記重要性を、そのページに関連付けられた特性に少なくとも部分的に基づいて判定するための手段をさらに備えたことを特徴とする請求項２５に記載の装置。
【請求項３１】
各ページの前記特性を、そのページを指すインターリンクおよびイントラリンクに少なくとも部分的に基づいて判定するための手段をさらに備えたことを特徴とする請求項３０に記載の装置。
【請求項３２】
各ページの前記特性を、そのページがインデックスページであるかどうかに少なくとも部分的に基づいて判定するための手段をさらに備えたことを特徴とする請求項３０に記載の装置。
【請求項３３】
各ページの前記特性を、そのページが属する階層構造におけるレベルに少なくとも部分的に基づいて判定するための手段をさらに備えたことを特徴とする請求項３０に記載の装置。
【請求項３４】
クエリに応答して検索を実行するための手段と、
前記クエリに関連のあるページを返すための手段と、
返された各ページを、前記クエリに対する前記ページの関連性に少なくとも部分的に基づいてランク付けする手段と
をさらに備えたことを特徴とする請求項２５に記載の装置。
【請求項３５】
返された各ページの前記重要性を決定するための手段と、
返された各ページを、前記ページの前記重要性に少なくとも部分的に基づいて再ランク付けするための手段と
をさらに備えたことを特徴とする請求項３４に記載の装置。
【請求項３６】
前記返されたページに関連付けられたリンクのリストを判定するための手段と、
前記返されたページの再ランク付け順序に従って前記リンクを前記リスト中で配置するための手段と、
前記再ランク付けされたリンクのリストを前記クエリの結果として提供するための手段と
をさらに備えたことを特徴とする請求項３５に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、階層を考慮したウェブページのランク付けに関する。
【背景技術】
【０００２】
ワールドワイドウェブでは、情報およびリソースは通常、ウェブページとして編成される。ウェブ上の所望の情報およびリソースを突き止めるためには、ユーザは通常、検索エンジンを用いて関連のあるウェブページを検索する。通常、検索エンジンは、ウェブ上のページに関するコンテンツベースの情報が入ったデータベースを検索する。このコンテンツベースの情報は普通、系統立った形でウェブを定期的にブラウズするウェブクローラ（Ｗｅｂ  ｃｒａｗｌｅｒ）によって収集される。検索エンジンは、ある検索タームを有するクエリを受け取ると、ウェブ情報データベースを検索し、検索タームに対してコンテンツベースの類似性を有するウェブページを探す。次いで検索エンジンは、これらのウェブページのアドレスをユーザに返す。
【０００３】
ウェブが発達し続けるにつれて、ユーザがウェブ上のページを正確に突き止めるのがますます困難になる。例えば、クエリの結果として法外に数多くのウェブページが得られ、これらページの多くがそのクエリに関連のないものであることがある。既存の検索エンジンの中には、検索によって返されたウェブページの重要性に基づく順序で検索結果をユーザに提示することによって、この問題を緩和しようとするものがある。これらの既存の検索エンジンによって使用されるデータベースでは、各ウェブページは、データベース中の他のすべてのウェブページ中でそのウェブページを指しているハイパーリンクに従って、ランク付けされている。言い換えれば、あるウェブページを指すハイパーリンクは、そのページに対する一票として働く。各ウェブページは、そのページが受け取った票数に従ってランク付けされる。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ランク付けされたウェブページを返す検索エンジンは、よりよいユーザ体験を生み出すものの、これらの検索エンジンはいくつかの重大な欠点も有している。例えば、ウェブ上のほとんどのウェブページには、そのページを指すハイパーリンクがごくわずかしかないか、またはまったくないので、ハイパーリンクに基づいてウェブページをランク付けすると、偏向した非現実的な重要性の配分を生じる。また、新しいハイパーリンクはウェブページ中に編成しなければならないが、これには多くの時間が必要なので、新しいページには、それらの重要性を反映したランク付けがなされない場合がある。
【０００５】
したがって、現実的な形でウェブページの重要性を配分することができ、ウェブ上の新しいページをより正確に計上することができる、検索エンジンが必要とされている。
【課題を解決するための手段】
【０００６】
記載のシステム、方法、およびデータ構造は、階層を考慮してウェブページをランク付けすることを対象とする。ワールドワイドウェブの階層構造およびリンク関係を使用して、ウェブ検索のためのページ重要性ランキングを提供する。リンク関係は、階層構造のそれぞれにおけるハイレベルのノードに集約される。集約されたリンク関係に関してリンクグラフ分析を実行して、各ノードの重要性を判定する。各ノードの重要性は、そのノードに関連付けられたページに伝搬することができる。各ページにつき、そのページの重要性と、そのページに関連付けられたノードの重要性とを使用して、ページ重要性ランキングを計算する。
【０００７】
本発明についての前述の態様および付随する利点の多くは、添付の図面と共に以下の詳細な説明を参照することによってよりよく理解されるので、より容易に認識されるようになるであろう。
【発明を実施するための最良の形態】
【０００８】
図１に、階層を考慮してウェブページをランク付けするための例示的な階層ランク付けシステム１００を示す。最も基本的な構成では、システム１００は、ウェブクローラ１０５およびランク付けモジュール１１０を含むことができる。図１に示すように、システム１００は、検索エンジン１３０にデータを提供するように構成することができ、検索エンジン１３０は、システム１００によって提供されたデータを使用してクエリに応答するように構成することができる。
【０００９】
ワールドワイドウェブ（ウェブ）１５０は、ＨＴＭＬ（Ｈｙｐｅｒ−Ｔｅｘｔ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ）などの共通規格でフォーマットされたドキュメントをサポートするインターネットサーバのシステムである。これらのフォーマットされたドキュメントは、ウェブページとも呼ばれ、ハイパーテキスト、画像、オーディオまたはビデオデータ、グラフィックスなど、任意のタイプのコンテンツを含むことができる。ウェブページは通常、他のウェブページへのリンク（すなわちハイパーリンク）を含む。
【００１０】
ウェブクローラ１０５は、ウェブを検索してウェブ１５０上のページに関するデータを収集するように構成された論理コンポーネントである。ウェブクローラ１０５は、任意のタイプの技法を使用して、ウェブページに関する任意の情報を見つけ、収集することができる。例えば、ウェブクローラ１０５は、ウェブページ中のリンクを辿って他のウェブページを発見することができ、これら他のウェブページ中のリンクを辿ってより多くのウェブページを見つけることができる。ウェブクローラ１０５は、継続的にこの検索方法を実行して、ウェブページデータ１１５など、ウェブ上のページに関する情報のデータベースを構築することができる。
【００１１】
ウェブページデータ１１５は、ウェブ上のページに関連付けられた任意のタイプのデータを含むことができる。例えば、ウェブページのデータは、キーワード、メタデータ、コンテンツのサマリなどを含むことができる。ウェブページデータ１１５はまた、ウェブページに関連付けられた構造データ１２０を含むこともできる。構造データ１２０は、ウェブページがウェブ上でどのように編成されているかに関する情報を含む。例えば、構造データ１２０は、各ウェブページのレベルを階層構造で含むことができる。レベルは、ＵＲＬ（Ｕｎｉｆｏｒｍ  Ｒｅｓｏｕｒｃｅ  Ｌｏｃａｔｏｒ）やファイルのパスなど、ウェブページに関連付けられたロケータから判定することができる。ＵＲＬで表される典型的な階層構造を以下の表１に示す。
【００１２】
【表１】
2006127529.tif 000003
【００１３】
表１は、ＵＲＬ「cs.zyxuniversity.edu/research/index.html」に関連付けられたウェブページの例示的な階層構造を示す。この例では、このＵＲＬに関連付けられたウェブページがＺＹＸ  Ｕｎｉｖｅｒｓｉｔｙドメイン中のページであり、このページは調査部門ウェブサイトのインデックスである。ウェブページの階層構造は、任意の形で確立することができる。一実施形態では、ウェブ階層構造のトップレベルはホストから確立され、ホストは、ウェブページの集まりを関連付けているエンティティとして定義することができる。例えばホストは、会社や政府やその他のエンティティによって提供される公共のウェブサイトなど、専用のウェブサイトであってもよい。ホストはまた、サービスプロバイダのドメイン中の個人ウェブサイトなど、コミュニティウェブサイトの一部であってもよい。この実施形態では、ウェブページに関連付けられたＵＲＬの構造を使用して、このページのレベルを階層構造で確立することができる。
【００１４】
ランク付けモジュール１１０は、ウェブページをランク付けするように構成された論理コンポーネントである。ランク付けモジュール１１０は通常、ウェブページデータ１１５や構造データ１２０など、ページに関連付けられるコンテンツおよび構造に関するデータに基づいてウェブページをランク付けする。ランク付けモジュール１１０は、各ウェブページ内のリンクを判定するように構成することができる。リンクは、別のウェブページにリンクする、ウェブページ中の要素である。ランク付けモジュール１１０は、ウェブページデータ１１５中のウェブページのリンクを、あるレベルで集約するように構成することができる。一実施形態では、リンクはホストレベルで集約される。ランク付けモジュール１１０はまた、集約されたリンクに基づいて各ホストの重み値を計算するように構成することもできる。ランク付けモジュール１１０はさらに、各ウェブページに対応するホストの重み値と、ホストの階層構造内の各ウェブページの特性とに基づいて、各ウェブページの重要性値を計算するように構成することができる。各ウェブページの重要性値は、階層型ランク付けデータ１２５などのデータストア中に集めることができる。
【００１５】
検索エンジン１３０は、ウェブ上のページを突き止めるように構成された論理コンポーネントである。検索エンジン１３０は、所望のウェブページ中のあるコンテンツを表す検索パラメータを含むクエリ１４０を受け取るように構成することができる。例えば、検索パラメータは、キーワード、画像、メディアデータなどを含むことができる。検索エンジン１３０はまた、ウェブページデータ１１５を検索して、そのクエリに関連のあるウェブページを判定するように構成することができる。検索エンジン１３０は、判定されたウェブページのそれぞれに関連性値を割り当てて、そのクエリに対する関連性を反映することができる。検索エンジン１３０はまた、これらの判定されたウェブページの重要性値を階層型ランク付けデータ１２５から判定することもできる。次いで検索エンジン１３０は、関連性値および重要性値に基づいて、判定されたウェブページをランク付けすることができる。次いで、ランク付けされた結果１４５がクエリ１４０に応答して提供される。ランク付けされた結果１４５は、検索によって返されたウェブページのリンクをそれらのランキングに従って順序付けたリストなど、任意のフォーマットとすることができる。
【００１６】
図２に、２つの異なるホストに関連付けられたウェブページを表す例示的なウェブグラフ２００を示す。ここに記載した階層ランク付けシステムおよび方法は、細分性の異なるレベルでリソースをランク付けすることができる。例えば、細分性のあるレベルでは、ウェブは、相互に多かれ少なかれ独立して成長するホストの集まりと見なすことができる。考察を簡単にするために、図２には、ホスト２０５（Ｈｉ）、ホスト２１０（Ｈｊ）、ウェブページＰ１〜Ｐ１１だけが示してある。しかし、ウェブ全体をウェブグラフ２００などのウェブグラフによって表すこともできることを理解されたい。ウェブグラフ２００は、図１に示したウェブクローラ１０５によって使用されるような任意の学習アルゴリズムによって検出することができる。
【００１７】
図２に示すように、ウェブページＰ１〜Ｐ６はホストＨｉに関連付けられ、ウェブページＰ７〜Ｐ１１はホストＨｊに関連付けられる。各ウェブページは、リンクによって他のウェブページに関連付けることができる。ウェブページＰ４などウェブページのいくつかは、そのホスト（すなわちホストＨｉ）内の他のウェブページだけにリンクされている。これらのリンクを本明細書ではイントラリンクと呼ぶ。ウェブページのいくつかは、そのホスト内にないウェブページにリンクされている。例えば、ホストＨｉに関連付けられたＰ５が、ホストＨｊに関連付けられたＰ１０にリンクされている。２つの異なるホストのウェブページ間のリンクを、本明細書ではインターリンクと呼ぶ。
【００１８】
図３に、図２に示したウェブグラフ２００から導出される例示的なホストグラフ３００を示す。ホストグラフ３００は、ホスト間のリンク関係を表す。記載のシステムおよび方法によれば、ウェブグラフ中に示されたインターリンクをホストレベルで集約することができる。例えば、ウェブグラフ２００はホストＨｉとホストＨｊに区分することができ、したがってインターリンクのすべては２つのホストにそれぞれ集約される。各ホスト内のリンクは考慮しなくてよい。重み値ｗｉｊおよびｗｊｉは、ホストＨｉおよびホストＨｊに関連付けられたウェブページ中の集約されたインターリンクの数を表す。図３に示すように、重み値ｗｉｊは、ホストＨｊを指すホストＨｉのウェブページ中の集約リンクを表し、重み値ｗｊｉは、ホストＨｉを指すホストＨｊのウェブページ中の集約リンクを表す。したがって、ホストグラフ３００などのホストグラフは一般に以下のように表すことができる。
Ｇ’＝（Ｖ’，Ｅ’）            （１）
【００１９】
ここで、Ｇ’は重み付き有向グラフであり、Ｖ’はホストを表し、Ｅ’はホスト間のリンクを包含する。各リンクｌｉｊ∈Ｅ’は、ホストＨｉに対するホストＨｊの重みを記す重み値ｗｉｊに関連付けることができ、この重みはホスト間のリンクに従って計算される。
【００２０】
ウェブグラフ中のリンクをホストレベルで集約することによって、結果として得られるホストグラフのリンク密度はずっと高くなることを理解されたい。ある情報ソースによれば、ホストごとのリンクの密度はあるホストグラフで約１３６であり、ページごとのリンク密度はあるウェブグラフで約７．１８である。通常、リンク密度が高いほど、よりよいランク付け結果が生み出される。
【００２１】
ホストグラフを得た後、リンク分析アルゴリズムを適用して、ホストの重要性を計算することができる。ホストグラフを記述するために行列を構築することができる。例えば、ホストグラフがｍ個のホストを含むとすると、ｍ×ｍの次元の隣接行列Ａを使用して、ホストグラフを表すことができる。エントリＡ［ｉ，ｊ］のそれぞれは、リンクｌｉｊの重みを表すことができる。この隣接行列を使用して、各ホストのランクスコアを計算することができる。１つの形態では、ホストＨｉのランクスコアＨＩｉは、ホストＨｉを指すホストのすべてのランクスコアの関数によって評価することができる。
【００２２】
【数１】
2006127529.tif 000004
【００２３】
この再帰的定義は、各ホストに、そのホストを指す他の各ホストのリンク値の一部分を与えることがある。例えば、リンク値は、そのホストのリンクの強さによって逆に重み付けすることができる。上で論じた式２は、以下のような行列の形態で書くことができる。
【００２４】
【数２】
2006127529.tif 000005
【００２５】
しかし実際には、多くのホストがインターリンクを有さないことがある（例えばホストの重みが０）。上式の固有ベクトルは、大抵は０となるかもしれない。そのため、基本モデルを修正して、ランダムウォークを用いて「実際のモデル」を得る。例えば、ホストをブラウズすると、確率１−εで、ユーザは、現在のホスト上のリンクの１つをランダムに選択し、現在のホストがリンクされている別のホストにジャンプする。また、確率εで、ユーザは、現在のホスト中のどのリンクにも関連付けられていないランダムに選択された別のホストにジャンプすることによって、「リセット」することがある。ランク付けの公式は以下の形態に修正することができる。
【００２６】
【数３】
2006127529.tif 000006
【００２７】
または、行列の形態では以下のようになる。
【００２８】
【数４】
2006127529.tif 000007
【００２９】
ここで、
【００３０】
【数５】
2006127529.tif 000008
【００３１】
はすべて１のベクトルであり、ε（０＜ε＜１）は、所与のホストから任意のホストへのジャンプがランダムに発生するランダムウォークの確率を表している。一実施形態では、よい結果を生むためにεは０．１５に設定することができる。
【００３２】
ホストの重要性を判定した後、ホストに関連付けられたウェブページの重要性をホストの評判および階層構造に従って、計算することができる。一実施形態では、ウェブページには、そのウェブページが属するホストの重要性が割り当てられる。ウェブページのＵＲＬに関連付けられたパスの深さ、ウェブページがインデックスページなのかコンテンツページなのか、ウェブページに関連付けられたインターリンクの数などその他の要因を考慮することもできる。どの要因を適用するかを決める際、以下の事項を考慮することができる。 
１）ある評判のためにホストを高くランク付けすべきである場合、このホスト中のウェブページは、ある程度までホストの評判の恩恵を受けることができる。いくつかの観察は、多くのトップランクのウェブページはトップランクのホストに関連付けられることを示している。 
２）ホスト中のウェブページがホスト外のウェブページによってリンクされている場合、このようなインターリンクの数をウェブページの重要性に反映させることができる。 
３）ホスト中のウェブページのレベルをウェブページの重要性によって反映することができる。通常、ユーザにホスト中の重要なコンテンツを効率的に見つさせるために、作成者は一般に、このような重要なコンテンツを長いパスのウェブページに置くことはしない。 
４）ウェブページがインデックスページである場合、その有用性を反映させるために、ウェブページにより高い重要性を与えることができる。
【００３３】
上記の考察に基づいて、いくつかのプロパティを使用してホストの階層構造を重み付き有向木構造として定式化し、木構造上でウェブページの重要性を分析することができる。一般に、ホストは親ノードと見なすことができ、ウェブページは子ノードと見なすことができる。関数を使用して、親ノードからその子ノードへの重みを表すことができる。
【００３４】
図４に、ホストと、このホストに関連付けられるウェブページとを表す例示的な階層構造４００を示す。この例では、階層構造４００は、図２に示したホストＨｊに関連付けられる。ウェブページＰ７〜Ｐ１１はホストＨｊに関連付けられる。図４に示すように、ウェブページＰ７〜Ｐ１１は、重み値ｗ７〜ｗ１１、インターリンク値ＬＩ７〜ＬＩ１１、イントラリンク値ＬＩ７〜ＬＩ１１に関連付けられる。具体的には、インターリンク値ＬＩｉは、このホストの外にある他のウェブページにあるリンクであって、ウェブページｐｉを指すリンクの数を表す。イントラリンク値ＬＡｉは、このホストの一部である他のウェブページになるリンクであって、ウェブページｐｉを指すリンクの数を表す。
【００３５】
一般に、ホスト中にウェブページｐｉを仮定して、ページｐｉの重みｗは以下のように計算することができる。 
ｗ（ｐｉ）＝δ×Ｌｉｎｋ（ｐｉ）×Ｉｎｄｅｘ（ｐｉ）            （６）
【００３６】
ここで、Ｌｉｎｋは、ウェブページｐｉに関連付けられるインターリンクおよびイントラリンクの関数である。Ｉｎｄｅｘは、ウェブページｐｉがインデックスページかどうかの関数である。δは減衰係数である。
【００３７】
Ｌｉｎｋ関数は、ホストの内側または外側の他のウェブページからウェブページｐｉを指すリンクの数に依存する因数を計算するように設計することができる。Ｌｉｎｋ関数は、インターリンクとイントラリンクとを区別するように構成することができる。例えばＬｉｎｋ関数は、インターリンクとイントラリンクに、それらの相対的な重要性に従って異なる重みを割り当てることができる。Ｌｉｎｋ関数は以下のように定義することができる。
【００３８】
【数６】
2006127529.tif 000009
【００３９】
ここで、ωは、インターリンクとイントラリンクとの間の相対的な重み配分を割り当てる係数である。例えば、式（８）では、大きいωの値により（すなわち１に近い）、インターリンクがイントラリンクよりも大きな相対的なリンク重みを有する結果になる。
【００４０】
関数Ｉｎｄｅｘは、ウェブページがインデックスページかどうかを判定し、以下のように定義することができる。
【００４１】
【数７】
2006127529.tif 000010
【００４２】
ここで、φ１およびφ２は、ウェブページがインデックスページかどうかに応じて関数に割り当てることのできる値である。
【００４３】
上記の分析に基づいて、ホストの構造特性を考慮した重み付き有向木構造を得ることができる。各ページｐｉの重要性は、以下のように階層重み付き構造に基づいて決定することができる。
【００４４】
【数８】
2006127529.tif 000011
【００４５】
ここで、ｐｊは、ｐｉからその親ウェブページおよびホストＨｊまでのウェブページである。
【００４６】
式９は、より高いレベルのウェブページからより低いレベルのウェブページへと再帰的に計算することができ、各ウェブページに重要性スコアを割り当てることができる。
【００４７】
全ウェブグラフにおけるウェブページｐｉの全体的な重要性ＰＩは、以下の式で計算することができる。 
ＰＩ（ｐｉ）＝ＨＩ（Ｈｊ）×Ｉｍｐ（ｐｉ，Ｈｊ）        （１０）
【００４８】
式１０によれば、所与のホストが高い評判を有する場合、このホスト中のウェブページもまた高い評価を有することができる。ウェブページの全体的な重要性に対する、ホストの重要性の影響は、以下の式で調整することができる。 
ＰＩ（ｐｉ）＝ＨＩ（Ｈｊ）×［α＋β×Ｉｍｐ（ｐｉ，Ｈｊ）］      （１１）
ここで、αおよびβは重み付けパラメータである。 
【００４９】
上で論じたウェブページ重要性分析をコンテンツベースの類似性分析と組み合わせて使用して、クエリに応答してウェブページのリストをランク付けすることができる。このプロセスを再ランク付けと呼ぶことができる。任意の技法を使用して、ウェブページ重要性分析とコンテンツベースの分析とを組み合わせることができる。例えば、スコアベースの再ランク付けおよび順序ベースの再ランク付けを用いて、よい結果を生み出すことができる。
【００５０】
スコアベースの再ランク付けは、ウェブページの、コンテンツベースの類似性スコアとウェブページ重要性スコアとの一次結合を使用する。ウェブページｐｉの全体的なスコアは、以下の式で判定することができる。 
Ｓｃｏｒｅ（ｐｉ）＝λＳｉｍ（ｐｉ）＋（１−λ）ＰＩ（ｐｉ）  （λ∈［０，１］）                                                              （１２）
【００５１】
ここで、Ｓｉｍは、ウェブページｐｉとクエリとの間のコンテンツベースの類似性である。λは、ウェブページ重要性とコンテンツベースの類似性との間の相対的な配分を割り当てる係数である。ＳｉｍおよびＰＩは値によって表すことができる。スコアするメトリックスが異なるため、式１２の一次結合を使用して全体的なスコアを計算する前に、ＳｉｍおよびＰＩの値を同じ範囲に正規化することができる。
【００５２】
順序ベースの再ランク付けは、ウェブページのランク順序に基づいて決定することができる。２つのリストにおけるウェブページの位置の一次結合であって、一方のリストはコンテンツベースの類似性スコアによってソートされ、他方のリストはウェブページ重要性スコアによってソートされる。順序ベースの再ランク付けは、以下の式によって実施することができる。 
Ｓｃｏｒｅ（ｗ）＝λＯＳｉｍ（ｐｉ）＋（１−λ）ＯＰＩ（ｐｉ）  （λ∈［０，１］）
（１３）
【００５３】
ここで、ＯＳｉｍおよびＯＰＩはそれぞれ、類似性スコアリストおよび重要性スコアリストにおけるウェブページｐｉの位置（または順序）である。
【００５４】
上記で論じた技法は、本明細書ではウェブページをランク付けするコンテキストで論じていることを理解されたい。しかし、この方法は、階層構造に編成されている任意のタイプのデータをランク付けするのに適用することができる。例えば、ノードを相互接続することによって表すことのできるシステムであって、各ノードが階層構造中のあるレベルに関連付けられたどんなシステムも、この論じた技法を用いてランク付けすることができる。
【００５５】
図５に、ウェブページの重要性値を判定するのに使用することのできる例示的なプロセス５００を示す。プロセス５００は、図１に示したランク付けモジュール１１０など、ウェブ検索システムのモジュールによって使用することができる。考察のために、プロセス５００をウェブページおよびホストのコンテキストで論じる。しかし、プロセス５００は、階層構造として編成された任意のシステム中のノードに適用することができる。
【００５６】
ブロック５０５で、ウェブ上のページに関するデータを識別する。データは、ウェブ上のページを検出するウェブクローラによって収集することができる。データは、ランク付けモジュールによる使用のためにデータベースに格納することができる。データは、キーワードやメタデータなど、コンテンツベースのデータを含むことができる。データはまた、ウェブページのＵＲＬなど、構造化データを含むこともできる。
【００５７】
ブロック５１０で、ウェブページは、それらに対応するホストに従ってグループ化される。通常、各ウェブページはあるホストに関連付けられ、このホストはウェブページのＵＲＬから判定することができる。ブロック５１５で、ホスト間のリンク関係に基づいて各ホストの重み値を判定する。ホストの重み値を判定するための例示的なプロセスについては、図６と共に論じる。簡単に言うと、インターリンク（例えば、ホストに関連付けられたウェブページを指す、ホスト外のウェブページ中のリンク）が収集される。各ホストの収集されたインターリンクを使用して、ホストの重み値を判定する。
【００５８】
ブロック５２０で、各ホスト内の各ページの重み値を判定する。ウェブページの重み値は、ウェブページのインターリンクおよびイントラリンクに関連付けられた重み値に基づいて判定することができる。ウェブページの重み値はまた、ホストにおけるウェブページのレベル、ウェブページがインデックスページかどうかなど、他の要因に基づくこともできる。ウェブページの重み値を判定するための例示的なプロセスについては、図７と共に論じることになるであろう。
【００５９】
ブロック５２５で、ホストの重み値およびウェブページの重み値に基づいて、各ウェブページの重要性値を判定する。判定された重み値は検索エンジンによって使用されて、クエリに応答して検索によって返されるウェブページをランク付けすることができる。判定された重み値はまた、ページをランク付けするのに使用することもでき、検索エンジンによって重み値の代わりにページの順序が使用されてもよい。
【００６０】
図６に、ホストの重み値を判定するための例示的なプロセス６００を示す。ブロック６０５で、各ホストに関連付けられたウェブページのインターリンクを識別する。ブロック６１０で、インターリンクをホストレベルで集約する。ブロック６１５で、各ホストにつき、このホストと他のホストのそれぞれとの間の集約されたインターリンクの総数を判定する。集約されたインターリンクは、行列またはデータアレイによって表すことができる。ブロック６２０で、集約されたインターリンクの数に基づいて、各ホストの重み値を計算することができる。ホストの重み値は、集約されたインターリンクを表す行列に関して操作することによって計算することができる。例えばこのような操作は、行列を表すデータアレイに関して反復的に計算することができる。
【００６１】
図７に、ウェブページに関連付けられた重み値を判定するための例示的なプロセス７００を示す。ブロック７０５で、ホストに関連付けられた階層構造内のウェブページを識別する。ブロック７１０で、ホストにおけるウェブページのレベルに基づいて、レベル値を判定する。ウェブページのレベルは、ウェブページのＵＲＬを分析するなど、任意の方法で判定することができる。
【００６２】
ブロック７１５で、ウェブページに関連付けられたインターリンクおよびイントラリンクの数に基づいて、リンク値を判定する。インターリンクおよびイントラリンクがリンク値に関して有する相対的な影響を調整するために因数を使用してもよい。ブロック７２０で、ページがインデックスページかどうかに基づいてインデックス値を判定する。インデックスページは通常、リンクとこれらのリンクに関連付けられたウェブページに関する情報の編成されたセットを含む。通常、インデックスは、ウェブサイトをナビゲートするために有用であり、通常、サイト中の他のウェブページよりも重要である。ブロック７２５で、レベル値、リンク値およびインデックス値に基づいて、ウェブページの重み値を判定する。
【００６３】
図８に、クエリに応答するための例示的なプロセス８００を示す。プロセス８００は、クエリに関連のあるウェブページへのリンクのリストを返すように検索エンジンによって実施することができる。ブロック８０５でクエリを受け取る。通常、クエリは、ユーザが見つけようとしているウェブページに関係するタームを含む。
【００６４】
ブロック８１０で、コンテンツベースの類似性を有するウェブページについてウェブページデータを検索する。ウェブページデータは通常、ウェブクローラによって供給される。ブロック８１５で、検索によって返された各ウェブページに関連付けられた関連性値を判定する。ブロック８２０で、返された各ウェブページに関連付けられた重要性値を判定する。重要性値は、ウェブページの階層およびリンク関係に基づいて判定することができる。ウェブページデータ中で参照される各ウェブページの重要性値は、ランク付けモジュールによって判定することができる。
【００６５】
ブロック８２５で、返されたウェブページは、そのそれぞれの関連性値および重要性値に基づいてランク付けされる。ブロック８３０で、返されたウェブページへのリンクのランク付けされたリストを、クエリ結果として提供する。
【００６６】
図９に、記載のシステムおよび方法を実施するための例示的なコンピュータデバイス９００を示す。最も基本的な構成では、コンピューティングデバイス９００は通常、少なくとも１つの中央処理装置（ＣＰＵ）９０５と、メモリ９１０とを含む。
【００６７】
コンピューティングデバイスの正確な構成およびタイプに応じて、メモリ９１０は揮発性（ＲＡＭなど）、不揮発性（ＲＯＭやフラッシュメモリなど）、またはこの２つの何らかの組合せとすることができる。さらに、コンピューティングデバイス９００は、追加の特徴／機能を有することもできる。例えばコンピューティングデバイス９００は、複数のＣＰＵを含んでもよい。記載の方法は、コンピューティングデバイス９００中の任意の処理ユニットによって任意の方法で実行することができる。例えば、記載のプロセスは、両方の複数のＣＰＵによって並列に実行することができる。
【００６８】
コンピューティングデバイス９００は、追加の記憶装置（リムーバブルおよび／または非リムーバブル）を備えることもでき、限定しないがこれらには、磁気または光学のディスクまたはテープが含まれる。図９では、このような追加の記憶装置を記憶装置９１５によって示す。コンピュータ記憶媒体には、コンピュータ可読命令、データ構造、プログラムモジュール、またはその他のデータなどの情報を格納するための任意の方法または技術で実現された、揮発性および不揮発性、リムーバブルおよび非リムーバブルの媒体が含まれる。メモリ９１０および記憶装置９１５は、コンピュータ記憶媒体の例にすぎない。コンピュータ記憶媒体には、限定しないがＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたはその他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）またはその他の光記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置またはその他の磁気記憶デバイスが含まれ、あるいは、所望の情報を記憶するのに使用できコンピューティングデバイス９００によってアクセスできるその他の任意の媒体が含まれる。このような任意のコンピュータ記憶媒体をコンピューティングデバイス９００の一部とすることができる。
【００６９】
コンピューティングデバイス９００はまた、デバイスが他のデバイスと通信できるようにするための通信デバイス９４０を含むこともできる。通信デバイス９４０は、通信媒体の一例である。通信媒体は通常、コンピュータ可読命令、データ構造、プログラムモジュール、またはその他のデータを、搬送波やその他のトランスポート機構などの変調データ信号に具現するものであり、任意の情報送達媒体がこれに含まれる。用語「変調データ信号」は、信号中に情報を符号化するようにその特性の１つまたは複数を設定または変更した信号を意味する。限定ではなく例として、通信媒体には、有線ネットワークや直接配線接続などのワイヤ媒体と、音響、ＲＦ、赤外線などの無線媒体およびその他のワイヤレス媒体とが含まれる。本明細書で説明したコンピュータ可読媒体という用語は、コンピュータ記憶媒体と通信媒体の両方を含む。記載の方法は、データやコンピュータ実行可能命令など任意の形態で、任意のコンピュータ可読媒体中に符号化することができる。
【００７０】
コンピューティングデバイス９００は、キーボード、マウス、ペン、音声入力デバイス、タッチ入力デバイスなどの入力デバイス９３５を有することもできる。また、表示装置、スピーカ、プリンタなどの出力デバイス９３０を含むこともできる。これらのデバイスはすべて当技術分野で周知であり、これらについて詳細に述べる必要はない。
【００７１】
本発明の好ましい実施形態について図示し、説明したが、本発明の趣旨および範囲を逸脱することなく様々な変更を加えることができることが理解されるであろう。
【図面の簡単な説明】
【００７２】
【図１】階層を考慮してウェブページをランク付けするための例示的な階層ランク付けシステムを示す図である。
【図２】２つの異なるホストに関連付けられたウェブページを表す例示的なウェブグラフを示す図である。
【図３】図２に示したウェブグラフから導出される例示的なホストグラフを示す図である。
【図４】ホストと、このホストに関連付けられたウェブページとを表す例示的な階層構造を示す図である。
【図５】ウェブページの重要性値を判定するのに使用することができる例示的なプロセスを示す図である。
【図６】ホストの重み値を判定するための例示的なプロセスを示す図である。
【図７】ウェブページに関連付けられた重み値を判定するための例示的なプロセスを示す図である。
【図８】クエリに応答するための例示的なプロセスを示す図である。
【図９】記載のシステムおよび方法を実施するための例示的なコンピュータデバイスを示す図である。
【符号の説明】
【００７３】
１００  階層ランク付けシステム
１０５  ウェブクローラ
１１０  ランク付けモジュール
１１５  ウェブページデータ
１２０  構造データ
１２５  階層ランク付けデータ
１３０  検索エンジン
１４０  クエリ
１４５  結果
１５０  ワールドワイドウェブ
２００  ウェブグラフ
２０５  ホスト
２１０  ホスト
３００  ホストグラフ
４００  階層構造
９００  コンピューティングデバイス
９０５  中央処理装置（ＣＰＵ）
９１０  メモリ
９１５  記憶装置
９３０  出力デバイス
９３５  入力デバイス
９４０  通信デバイス
【図１】
2006127529.tif 000012
【図２】
2006127529.tif 000013
【図３】
2006127529.tif 000014
【図４】
2006127529.tif 000015
【図５】
2006127529.tif 000016
【図６】
2006127529.tif 000017
【図７】
2006127529.tif 000018
【図８】
2006127529.tif 000019
【図９】
2006127529.tif 000020