(57)【要約】  リンクされた文書の集合に相対的品質スコアを割り当てるための方法が提示される。該方法は、リンクデータベースの接続性グラフにしたがってバネネットワークを構築すること、およびネットワークのリンク構造と端ノードにおける変位とに基づいてノード間バネの強さを決定することを含む。方法は、更に、反復プロセスを通じてバネネットワーク内においてノードの変位を計算すること、および収束後のノードの変位をもとに文書の品質スコアを得ることを含んでよい。方法は、また、文書グループの相対的品質スコアを得ることも含んでよい。方法は、更に、リンクデータベースの中の文書にトピック固有の品質スコアを割り当てることを含んでよい。
2008525896.tif 000002
【特許請求の範囲】
【請求項１】
リンクされた複数の文書にスコアを割り当てるための、コンピュータに実装された方法であって、前記文書の少なくとも一部は、ハイパーメディア文書であり、前記方法は、
文書の集合の接続性グラフと、該文書間のリンクとにしたがって、バネネットワークを構築するステップと、
複数のノードを参照ノードとして識別すると共に、他のノードを通常ノードとして識別するステップと、
前記参照ノードに所定量の変位を加えるステップと、
前記バネネットワーク内において前記通常ノードの変位を計算するステップと、
前記文書に対応する前記ノードの変位に基づいて、文書へのスコアの割り当てを行うステップと、
を備える、リンクされた複数の文書にスコアを割り当てるための方法。
【請求項２】
請求項１に記載の方法であって、
前記構築するステップは、
前記集合内の各文書に１つずつノードを加えることと、
各ノードに１つずつ追加バネを加えることと、
前記集合内の前記文書のリンク構造にしたがって、弾性バネによるノードの接続を行うことと、
を含む、リンクされた複数の文書にスコアを割り当てるための方法。
【請求項３】
請求項２に記載の方法であって、
前記追加バネの強さは、均一であると共に、前記ノード間バネの全体の強さに比例する、リンクされた複数の文書にスコアを割り当てるための方法。
【請求項４】
請求項２に記載の方法であって、
前記追加バネの強さは、対応する文書の分類に基づいて、ノードごとに異なる、リンクされた複数の文書にスコアを割り当てるための方法。
【請求項５】
請求項１に記載の方法であって、
前記参照ノードに加えられる変位の量は、均一である、リンクされた複数の文書にスコアを割り当てるための方法。
【請求項６】
請求項１に記載の方法であって、
前記参照ノードに加えられる変位の量は、前記関連付けられた文書の種類に依存する、リンクされた複数の文書にスコアを割り当てるための方法。
【請求項７】
請求項１に記載の方法であって、
前記計算するステップは、
入力変位ベクトルを初期化することと、
ステップａ）〜ｄ）を、すなわち、
ａ）ノード間バネの強さを調整するステップと、
ｂ）出力変位ベクトルを計算するステップと、
ｃ）収束判定のために、前記出力変位ベクトルを前記入力変位ベクトルと比較し、もし収束されたならば、手順を終了させるステップと、
ｄ）もし収束されていないならば、前記入力変位ベクトルと前記出力変位ベクトルとを組み合わせ、新しい入力変位ベクトルを生成するステップと、
を繰り返すことと、
を含む、リンクされた複数の文書にスコアを割り当てるための方法。
【請求項８】
請求項７に記載の方法であって、
前記ノード間バネの強さは、２つの端ノードの変位の現行値と、該２つの端ノード間のリンクの重み係数とに基づいて調整される、リンクされた複数の文書にスコアを割り当てるための方法。
【請求項９】
請求項８に記載の方法であって、
前記リンクの重み係数は、所定の定値を有する、リンクされた複数の文書にスコアを割り当てるための方法。
【請求項１０】
請求項８に記載の方法であって、
前記リンクの重み係数は、起点の文書からアウトバウンドされるリンクの総数の逆数に対応する均一な値を有する、リンクされた複数の文書にスコアを割り当てるための方法。
【請求項１１】
請求項８に記載の方法であって、
前記リンクの重み係数は、アウトバウンドリンクの数と、該リンクの相対位置と、該リンクがある段落の大きさと、該リンクが指し示すリンクが同一サイト内または異なるサイト内のいずれにあるかということとに依存する可変値を有する、リンクされた複数の文書にスコアを割り当てるための方法。
【請求項１２】
請求項７に記載の方法であって、
前記出力変位ベクトルを計算するステップは、各ノードにかかる力の合計をバランスさせることを含む、リンクされた複数の文書にスコアを割り当てるための方法。
【請求項１３】
請求項７に記載の方法であって、
前記出力変位ベクトルを計算するステップは、前記バネネットワークのひずみエネルギの合計を最小化することを含む、リンクされた複数の文書にスコアを割り当てるための方法。
【請求項１４】
リンクされた複数の文書グループにスコアを割り当てるための、コンピュータに実装された方法であって、前記文書の少なくとも一部は、ハイパーメディア文書であり、前記方法は、
文書グループの集合の接続性グラフと、該文書間のリンクとにしたがって、バネネットワークを構築するステップと、
複数のノードを参照ノードとして識別すると共に、他のノードを通常ノードとして識別するステップと、
前記参照ノードに所定量の変位を加えるステップと、
前記バネネットワーク内において前記通常ノードの変位を計算するステップと、
前記文書に対応する前記ノードの変位に基づいて、文書グループへのスコアの割り当てを行うステップと、
を備える、リンクされた複数の文書グループにスコアを割り当てるための方法。
【請求項１５】
請求項１４に記載の方法であって、
前記構築するステップは、
集合内の文書をグループに分けることと、
前記集合内の各グループに１つずつノードを加えることと、
各ノードに１つずつ追加バネを加えることと、
前記集合内の前記文書グループのリンク構造にしたがって、弾性バネによるノードの接続を行うことと、
少なくとも１つの参照文書を含む各グループに、１つずつ追加ノードを加えることと
、
前記グループ内の参照ページの数に対応する強さを有する弾性バネによって、各ノードをそれに関連付けられた追加ノードに接続することと、
を含む、リンクされた複数の文書グループにスコアを割り当てるための方法。
【請求項１６】
請求項１５に記載の方法であって、
前記追加バネの強さは、均一であると共に、ノード間バネの全体の強さに比例する、リンクされた複数の文書グループにスコアを割り当てるための方法。
【請求項１７】
請求項１５に記載の方法であって、
前記追加バネの強さは、前記グループの分類に基づいて、グループごとに異なる、リンクされた複数の文書グループにスコアを割り当てるための方法。
【請求項１８】
請求項１４に記載の方法であって、
前記参照ノードに加えられる変位の量は、均一である、リンクされた複数の文書グループにスコアを割り当てるための方法。
【請求項１９】
請求項１４に記載の方法であって、
前記参照ノードに加えられる変位の量は、前記関連付けられたグループの種類に依存する、リンクされた複数の文書グループにスコアを割り当てるための方法。
【請求項２０】
請求項１４に記載の方法であって、
前記計算するステップは、
入力変位ベクトルを初期化することと、
ステップａ）〜ｄ）を、すなわち、
ａ）ノード間バネの強さを調整するステップと、
ｂ）出力変位ベクトルを計算するステップと、
ｃ）収束判定のために、前記出力変位ベクトルを前記入力変位ベクトルと比較し、もし収束されたならば、手順を終了させるステップと、
ｄ）もし収束されていないならば、前記入力変位ベクトルと前記出力変位ベクトルとを組み合わせ、新しい入力変位ベクトルを生成するステップと、
を繰り返すことと、
を含む、リンクされた複数の文書グループにスコアを割り当てるための方法。
【請求項２１】
請求項２０に記載の方法であって、
前記ノード間バネの強さは、２つの端ノードの変位と、該２つの端ノード間の前記リンクの重み係数とに基づいて調整される、リンクされた複数の文書グループにスコアを割り当てるための方法。
【請求項２２】
請求項２１に記載の方法であって、
前記インバウンドリンクの重み係数は、所定の定値を有する、リンクされた複数の文書グループにスコアを割り当てるための方法。
【請求項２３】
請求項２１に記載の方法であって、
前記インバウンドリンクの重み係数は、起点の文書グループからアウトバウンドされるリンクの総数の逆数に対応する均一な値を有する、リンクされた複数の文書グループにスコアを割り当てるための方法。
【請求項２４】
請求項２０に記載の方法であって、
前記出力変位ベクトルを計算するステップは、各ノードにかかる力の合計をバランスさ
せることを含む、リンクされた複数の文書グループにスコアを割り当てるための方法。
【請求項２５】
請求項２０に記載の方法であって、
前記出力変位ベクトルを計算するステップは、前記バネネットワークのひずみエネルギの合計を最小化することを含む、リンクされた複数の文書グループにスコアを割り当てるための方法。
【請求項２６】
請求項１に記載の方法であって、
前記複数のノードを参照ノードとして識別するステップは、特定のトピックにおいて権威を有する文書に対応するノードを識別することを含む、リンクされた複数の文書にスコアを割り当てるための方法。
【請求項２７】
リンクされた複数の文書にスコアを割り当てるための、コンピュータに実装された方法であって、前記文書の少なくとも一部は、ハイパーメディア文書であり、前記方法は、
文書の集合の接続性グラフと、該文書間のリンクとにしたがって、バネネットワークを構築するステップと、
複数のノードを第１組の参照ノードとして識別すると共に、他のノードを第１組の通常ノードとして識別するステップと、
前記第１組の参照ノードに所定量の変位を加えるステップと、
前記バネネットワーク内において前記第１組の通常ノードの変位を計算するステップと、
複数のノードを第１組と異なる第２組の参照ノードとして識別すると共に、他のノードを第２組の通常ノードとして識別するステップと、
前記第２組の参照ノードに所定量の変位を加えるステップと、
前記バネネットワーク内において前記第２組の通常ノードの変位を計算するステップと、
前記文書に対応する前記ノードの第２組の変位に基づいて、文書へのスコアの割り当てを行うステップと、
を備える、リンクされた複数の文書にスコアを割り当てるための方法。
【請求項２８】
請求項２７に記載の方法であって、
前記第２組の変位を計算するステップは、
入力変位ベクトルを初期化することと、
２つの端ノード間の第１組の変位と、該２つの端ノード間の前記リンクの重み係数とに基づいて、ノード間バネの強さを設定することと、
ステップａ）〜ｃ）を、すなわち、
ａ）出力変位ベクトルを計算するステップと、
ｂ）収束判定のために、前記出力変位ベクトルを前記入力変位ベクトルと比較し、もし収束されたならば、手順を終了させるステップと、
ｃ）もし収束されていないならば、前記入力変位ベクトルと前記出力変位ベクトルとを組み合わせ、新しい入力変位ベクトルを生成するステップと、
を繰り返すことと、
を含む、リンクされた複数の文書にスコアを割り当てるための方法。
【発明の詳細な説明】
【技術分野】
【０００１】
＜関連出願の相互参照＞
本出願は、２００４年１２月２３日付けで出願された米国暫定特許出願６０／６３８，９５２であって、「Ｗｅｂ  Ａｆｆｉｎｉｔｙ  Ｉｎｄｅｘ  Ｒａｎｋｉｎｇ  Ｓｙｓｔｅｍ（Ｗｅｂ類似性索引ランキングシステム）」である出願に基づく優先権を主張する。当該出願は、引用によって本明細書に組み込まれる。
＜技術分野＞
【０００２】
本発明の実施形態は、概して、リンクされた文書の集合に相対的品質スコアを割り当てるための方法に関する。より具体的には、本発明は、ワールドワイドウェブまたは他の任意のハイパーメディアデータベースの中のウェブページなど、リンクデータベースの中のノードに相対的品質スコアを割り当てるための方法に関する。
＜背景技術＞
【０００３】
ワールドワイドウェブ（以下、「Ｗｅｂ」という。）は、インターネットにおいて急速に成長している部分である。ある団体の推測によると、２０００年の始まりの時点で、Ｗｅｂは、毎日７百万を超えるウェブページを生み出すことによって、既に巨大な情報体を増大させ続けているという。しかしながら、Ｗｅｂの急速な成長と、中心的な組織の欠如とから、何百万というユーザが、特定の情報を効率良く見つけ出せないでいる。ここ１０年間では、ＢＥＣＯＭＥ．ｃｏｍなどのサーチエンジンが、インターネット上において、何十億ものウェブページを索引付けした最も重要な情報検索手段の１つになった。しかしながら、サーチエンジンは、その対象範囲の拡大と共に、既存の問題を悪化させる。サーチエンジンは、検索基準を満たす全ての文書を引き出して、検索者を何百万もの無関係の文書で圧倒する可能性がある。検索結果が出ると、検索者は、関連する文書を見つけだすために、１つ１つの文書に目を通さなければならない。たとえ多くの文書をダウンロードできるとしても、平均的な検索者であれば、必ずしも検索結果表示の１ページ目より多くに目を通したいとは思わない。したがって、最も関連性の高い文書をリストの一番上（例えば上位１０個の結果）に提示することが、極めて重要である。
【０００４】
表面的には、何百万もの文書が検索基準に一致するので、主要なサーチエンジンは、例えばタイトル、メタタグ、または文書の冒頭など特定の位置に特定のキーワードを有する文書を上位にランク付けするランキングアルゴリズムを有している。しかしながら、これは、通常、最も関連性の高い文書をリストの上位に持ってくるものではない。すなわち、他の文書と比べた場合の文書の重要性をよく評価するものではない。
【０００５】
更に、表示時には現れないメタタグを含む、文書それ自体の内容のみに依存して文書をランク付けすることは、サーチエンジンにとって大きな問題となりうる。ウェブの開発者は、スパミングと呼ばれるように、「ホットな」キーワードを（例えばタイトルまたはメタタグなどの中で）多数繰り返し使用することによって、所定の文書の関連性を擬似的に誇張することができる。このため、今日最も作動しているインターネットサーチエンジンは、リンク構造解析のヴァリエーションの１つを使用している。例えば、Ｇｏｏｇｌｅによって使用されているＰａｇｅＲａｎｋアルゴリズムは、従来のキーワードベースのスパミング技術に対抗する有効な手段であることが判明した。しかしながら、最近では、ＰａｇｅＲａｎｋですら、Ｗｅｂのリンク構造を操作するより巧妙な次世代のスパミング技術の脅威に曝されていることがわかってきた。ウェブマスタおよびいわゆる「サーチエンジン最適化エンジニア」と呼ばれる者たちは、長年に渡って、ＰａｇｅＲａｎｋがどのように機能するかを学び、そのアルゴリズムを操作する方法を見つけだした。このような技術
の１つが、いわゆる「Ｇｏｏｇｌｅ爆弾」であり、Ｇｏｏｇｌｅは、このため、たびたび好ましくない注目を浴びてきた。
【０００６】
もう１つ、あまり知られていないがより有害な恐れのある技術は、「擬似Ｗｅｂ」と呼ばれるものである。スパマーは、適度な投資によって、いくつかのＩＰアドレスおよび大量のディスクストレージスペースを購入することができる。スパマーは、スクリプトの記述によって、宣伝したいいくつかのウェブサイトへのリンクを含む何百万またはひいては何十億もの簡単なウェブページを容易に作成することができる。これらの擬似的なウェブページの数は、本物のＷｅｂの主要部分の数に匹敵しうるので、スパマーは、Ｗｅｂ全体のリンク構造の操作に不当な影響を与え、ＰａｇｅＲａｎｋの計算に悪影響を及ぼすことができる。
【０００７】
擬似Ｗｅｂに対する脆弱性は、ＰａｇｅＲａｎｋなどの従来のリンク解析アルゴリズムの根本的な限界を露呈する。これらのアルゴリズムの欠陥の主要因の１つは、これらの方法が、全ての文書を平等にカウントする点にある。Ｙａｈｏｏ．ｃｏｍのホームページは、小学校４年生の管理する無名のウェブサイトのホームページと同じく１つの文書としてカウントされる。このため、擬似Ｗｅｂは、本物のＷｅｂからかなりの量の重み係数を吸い上げることが可能である。
【０００８】
したがって、互いに相対的な品質スコアをウェブページに割り当てるための方法で、これらの高度に巧妙化されたスパミング技術の脅威に曝されないような方法を提供することが望まれている。
＜発明の概要＞
【０００９】
本発明は、概して、ワールドワイドウェブの中のウェブページなどのリンクされた文書の集合に相対的品質スコアを割り当てるための方法に関する。代表的な一実施形態において、本発明は、対象となっているリンクデータベースの接続性グラフにしたがって、バネネットワークの構造解析を実施することによって、相対的品質スコアを割り当てる方法である。該方法は、集合内の各文書に１つずつノードを追加し、これらのノードを、集合内の文書のリンク構造にしたがって弾性バネによって接続する。更に、全てのノードは、個々のアンカーバネに結合され、それぞれの場所に保持される。
【００１０】
代表的な一実施形態では、権威として知られる参照文書または高品質である参照文書に対応するいくつかのノードが、参照ノードとして選択される。該方法は、次いで、参照ノードに所定量の変位を加え、この操作の結果として残りのノードに生じる変位を測定する。新しい変位が得られると、ノード間バネは、変位が大きいほど良いという（接続性に関する）ノードの「意見」を反映する形でその強さを調整される。この変化は、すると、ノードの変位に更なる変化をもたらす。この手順は、変位が収束して大きく変化しなくなるまで繰り返される。次いで、文書に関連付けられたノードにおける最終的な変位に比例する量として、その文書の相対的品質スコアが定められる。本発明の実施形態は、擬似Ｗｅｂによって作成されたなどの非合法な文書グループをデータベースの主要部分に結びつける弱いハイパーリンクを識別し、それらを、強固で且つ効率良い方法で適切に罰する。
＜発明の詳細な説明＞
【００１１】
以下の詳細な説明は、例示のために多くの細目を含んでいるが、当業者ならば誰でも、以下の詳細に対する多くの変更および代替が発明の範囲内であることがわかるであろう。したがって、以下に説明される発明の実施形態は、特許請求の範囲に定められた発明の一般性を一切損なうことなく尚且つ特許請求の範囲に定められた発明にいかなる制限を課することもなく示されるものである。
【００１２】
サーチエンジンのアーキテクチャ
簡潔化のため、本発明の実施形態は、ウェブページの集合に対し、検索照会に応答して品質スコアの収集、格納、索引付け、および割り当てを行うサーチエンジンの一部として説明される。しかしながら、当業者ならば、本明細書を見直した後、本発明があらゆるリンクデータベース構造に使用可能であることを理解できるであろう。
【００１３】
図１は、Ｗｅｂ１０１からウェブページを取り出すクローラ１０２を含むサーチエンジン１００の一実施形態を例示している。一実施形態では、サーチエンジン１００は、Ｊａｖａ（登録商標）でプログラムされ、Ｌｉｎｕｘ（登録商標）オペレーティングシステムで動作し、好ましくは、適切なＩｎｔｅｌ  Ｐｅｎｔｉｕｍ（登録商標）プロセッサを並行して使用している。しかしながら、これらのハードウェアおよびオペレーティングシステムの使用は、発明にとって不可欠ではなく、ＵＮＩＸ（登録商標）またはＭｉｃｒｏｓｏｆｔ  Ｗｉｎｄｏｗｓ（登録商標）  ＸＰ（登録商標）など、他のハードウェアおよびオペレーティングシステムが使用可能であることは明らかである。代表的な一実施形態では、Ｗｅｂ１０１上のウェブページなどのハイパーテキスト文書の集合を検索する能力を増大させるために、複数インスタンスのクローラ１０２が稼動している。クローラ１０２は、検索されたウェブページを、高速アクセス用に最適化されたデータ構造を含むリンクデータベース１０３に格納する。
【００１４】
サーチエンジン１００は、以下の手順で索引付けの機能を提供する。インデクサ１０４は、リンクデータベース１０３内の各文書に、固有の文書識別番号（ＤＩＤ）を割り当てる。インデクサ１０４は、文書からのキーワードを解析し、キーワードとＤＩＤとのペアからなるリストを生成する。インデクサ１０４は、次いで、キーワードごとに、そのキーワードを含む全ての文書の文書識別番号のリストを収集し、高速検索用の索引データベース１０５を構築する。
【００１５】
サーチエンジン１００は、全ての文書に相対的品質スコアを割り当てる品質スコアジェネレータ１０６を含む。品質スコアジェネレータ１０６は、リンクデータベース１０３からリンク構造を読み出し、図６に関連して後ほど詳述されるように、本発明の一実施形態を用いて、リンクデータベースの中の文書の品質スコアを計算する。品質スコアジェネレータ１０６は、結果を、照会サーバ１０８によって使用される品質スコアデータベース１０７に格納する。
【００１６】
サーチエンジンの目的の１つは、検索照会に応答し、関連性の高い順に検索結果を返すことである。照会サーバ１０８は、サーチエンジンのユーザ１０９からの照会を受信すると、その与えられた照会に関連する全ての文書を索引データベース１０５から収集する。代表的な照会サーバ１０８は、照会された用語が文書中に現れる頻度、フォントサイズ、および照会された用語の位置などの固有な内容情報に基づいて、各文書の内容スコアを生成する。一実施形態では、照会された用語が文書のタイトルに含まれる場合に、より高い内容スコアが付与される。照会サーバ１０８は、内容スコアと品質スコアとを組み合わせることによって、与えられた照会に対する各文書の関連性スコアを決定する。代表的な一実施形態では、照会に対する文書の関連性スコアは、内容スコアと品質スコアとの相乗平均をとることによって算出される。
【数１】
2008525896.tif 000003
ここで、Ｃ（ｉ，ｑ）は、照会ｑに対する文書ｉの内容スコアであり、Ｑ（ｉ）は、文書ｉの品質スコアである。
【００１７】
照会サーバ１０８は、次いで、関連性スコアにしたがって、結果の順位付けおよび分類を行い、最も関連性の高い文書を一度に（例えば１０ずつ）サーチエンジンユーザ１０９に対して提示する。
【００１８】
代表的な一実施形態では、照会サーバ１０８の応答時間を短縮するために、関連性スコアを評価するためのステップの一部が事前に実施される。例えば、単一用語照会用の関連性スコア一式を、事前に処理しておいてよい。照会サーバ１０８は、格納された関連性スコアを、単一用語照会に直ちに応答するためのみならず、それらを系統的に組み合わせて複数用語照会用の関連性スコアを構築するためにも使用する。
【００１９】
リンクデータベースのバネネットワーク表示
本発明の実施形態は、リンクされた文書の集合に相対的品質スコアを割り当てるための方法に関する。本発明の代表的な一実施形態において、第１のステップは、リンクデータベースのバネネットワーク表現を構築するステップである。
【００２０】
図２は、Ｗｅｂまたは他のハイパーメディアアーカイブなどのリンクデータベース１０３（図１）の有向グラフ表現２００を例示している。各ノード（すなわち丸）は、ハイパーリンクされた文書に対応し、ノード間の有向接続（すなわち矢印）は、１つの文書から別の文書へのハイパーリンクに対応する。２つのノード間のリンクは、単方向または双方向であってよい。
【００２１】
図３は、２つの文書およびそれらの間のハイパーリンクをグラフ表現している。ノードｉ（オブジェクト３０１）およびノードｊ（オブジェクト３０２）は、文書識別番号ｉおよびｊを有する文書を表している。本発明の代表的な一実施形態では、後述される手続きにしたがって、２つのノード間のリンクを、更に単一の接続に低減させることができる。
【００２２】
図４は、２つの文書およびそれらの間のハイパーリンクを、文書用のアンカーバネを含めてバネネットワーク表現している。一実施形態では、この接続を、２点間を物理的構成で接続する単純な弾性バネとして説明することができる。ノード間バネ４０１は、ノード間のハイパーリンクによって確立された、ノードｉとノードｊとの間の接続を表している。一実施形態では、ハイパーリンクを表すために、単純な弾性バネが使用される。
【００２３】
代表的な一実施形態では、一部または全部のノードが、図４のアンカーバネ４０２，４０３によってそれぞれの場所に保持される。一実施形態では、全部のアンカーバネが同じ強さを有する。他の実施形態では、アンカーバネが互いに異なる強さを有してよい。例えば、（１）個々の文書としてでなく１つのまとまりとしてウェブサイトが解析される場合、および（２）所定のウェブサイト内において文書が解析される場合などに、異なるアンカー方式が使用されてよい。
【００２４】
代表的な一実施形態では、品質スコアジェネレータ１０６（図１）に関連して説明されるように、図５に示されるバネネットワーク５０１によってリンクデータベース１０３(図１）が表される。各文書はノードによって表され、ウェブ文書間のハイパーリンクは単純な弾性バネによって表される。図を簡略化するため、図５において、アンカーバネは不図示である。
【００２５】
代表的な一実施形態では、ＣＮＥＴ．ｃｏｍのホームページ（ｗｗｗ．ｃｎｅｔ．ｃｏｍ）などの、権威的でありまたは高品質であるものとして知られるいくつかの文書が参照
文書として選択され、それらに対応するノードが参照ノードとして指定される。参照文書から多くのハイパーリンクを貼られている文書に対応するノードは、参照ノードに強く接続されていると考えられる。本発明の代表的な一実施形態では、参照ノードに特定の変位が加えられ、この操作の結果として残りのノード（すなわち通常ノード）に生じる変位が測定される。参照ノードに強く接続されている（通常）ノードは、参照ノードにあまり接続されていない（通常）ノードよりも、大きな変位を経験するであろう。したがって、相対的品質スコアは、参照ノードが移動を強いられたときにバネネットワーク５０１内のノードに生じる変位に比例する量として定められる。
【００２６】
単純なバネで接続されているノードの変位は、各ノードにかかる正味の力の合計をバランスさせることによって得ることができる。
【数２】
2008525896.tif 000004
ノード間力ｆijは、ノードｊによってノードｉに及ぼされる力であり、この力は、フックの法則によって得られる。
【数３】
2008525896.tif 000005
ここで、ｋijは、ノードｉとノードｊとの間のバネ４０１（図４）のバネ定数であり、ｄiは、ノードｉの変位であり、ｄjは、ノードｊの変位である。アンカー力は、次式によって与えられる。
【数４】
2008525896.tif 000006
ここで、ｋiaは、図４のアンカーバネ４０２のバネ定数である。
【００２７】
一実施形態では、バネ定数ｋijは、２つの端ノードの変位、すなわちバネの両端に取り付けられたノードの変位によって得られる。
【数５】
2008525896.tif 000007
ここで、ｋ0は、バネネットワーク５０１内のノード間バネのバネ定数の全体の値を表す定数である。量Ｌi→jは、リンクｉ→ｊの重み係数を表している。
【００２８】
ハイパーリンクの重み係数は、ハイパーリンクの重要度を測る。一実施形態では、もしリンクｉ→ｊが存在するならばＬi→j＝１であり、もしリンクｉ→ｊが存在しないならばＬi→j＝０である。別の一実施形態では、リンクの相対位置（すなわち文書上における位置）およびリンクがある段落の大きさなど、いくつかの要因に応じて各リンクに異なる重
み係数を与えることが可能である。別の一実施形態では、文書の読み込み時に容易に見えるリンクが、スクロールダウンしないと見えないリンクよりも高い重み係数を有することとすることができる。更に別の一実施形態では、外部リンク、すなわち異なるサイト内の文書を指し示すリンクと、内部リンク、すなわち同一サイト内の文書を指し示すリンクとに、それぞれ異なる重み係数を割り当てることができる。もし、ある文書から別の文書へのリンクがない場合は、対応する重み係数はゼロである。
【００２９】
代表的な一実施形態において、スケーリング関数ｇ（ｘ）は、その引数の単調増加関数であり、以下の特性を有する。
【数６】
2008525896.tif 000008
このような関数の最も簡単な例の１つが、いわゆるフェルミ・ディラック分布関数である。
【数７】
2008525896.tif 000009
ここで、σは、遷移領域の幅を調整する定数パラメータである。別の実施形態では、単純なステップ関数を使用することができる。
【数８】
2008525896.tif 000010
【００３０】
別の一実施形態では、各ノードにかかる力をバランスさせる代わりに、バネネットワークのひずみエネルギの合計を最小化することによって、同じ変位ベクトルを得ることができる。バネネットワークのひずみエネルギの合計Ｕは、次式によって与えられる。
【数９】
2008525896.tif 000011
【００３１】
変位の計算
物理学または構造工学で観察され研究されている物理的なバネネットワークは、３次元空間に存在する。代表的な一実施形態では、１次元のバネネットワークを考えれば十分である。更には、アンカーを含む全てのノードを、通常は原点である同一の位置に配置し、
バネネットワーク全体を一点と幾何学的に等しくすることができる。そして、バネネットワーク５０１のリンク構造にしたがって、ノード間に長さゼロのバネを配置することができる。ノードの最終的な位置は、単純に、原点からの変位である。
【００３２】
バネネットワーク５０１は、システムに外力が作用しない場合に自明な解を有する。すなわち、全ての変位はゼロである。非自明な解は、ノードの一部に非自明な境界条件が加えられた場合に生じる。代表的な一実施形態では、いくつかの参照ノードの変位が特定の固定値に設定される。後続の解析を単純化するため、ここでは、ノード０と称される１つの参照ノードのみを選択し、その変位を所定の値ｄ0に設定した場合を考える。ノード０がその本来の位置から移動されると、弾性バネによってノード０に接続された全てのノードは、同じ方向に移動して、ノード間バネの張力を低減させようとする。これらのノードは、しかしながら、自身のアンカーバネによってそれぞれの場所に保持されている。更に、これらのノードは、弾性バネによって隣接するノードに取り付けられており、これが上記の移動に対抗する。したがって、これらのノードは、対抗するこれらの力どうしの折り合いをつけて、全体のひずみエネルギを最小化することとなる。
【００３３】
物理的または機械的なバネネットワークにおいて、ノード間バネの強さは、与えられた材料の特性であり、たとえひずみを加えられた場合でも、弾性状態から塑性変形状態に移行するのに十分な大きさのひずみでない限り、変化を生じることはない。本実施形態では、しかしながら、ノード間バネの強さは、式（４）に示されるように、端ノードにおける相対的な変位に依存する。したがって、支配方程式（１）は、行列方程式を使用して確定的に解くことが不可能である。換言すると、式（１）は、循環的に定められており、すなわち問題｛ｋij｝が解｛ｄi｝に依存しており、したがって、自己矛盾無く解かれなければならない。
【００３４】
図６は、本発明の一実装形態のフローチャートを示している。代表的な実施形態では、図６の方法は、図１の品質スコアジェネレータ１０６によって実施される。代表的な一実施形態では、ステップ６０１において、リンクデータベースに対応するバネネットワークが構築される。代表的な実施形態では、ネットワークの構築は、リンクデータベース１０３(図１）からのデータに基づく。ステップ６０２において、品質スコアジェネレータ１０６は、参照ノードを変位させ、入力変位ベクトルＸ＝｛ｄi｝(0)をゼロなどの定値に設定して初期化する。品質スコアジェネレータ１０６は、以下の手順で式（１）を反復的に解く。
１．反復ステップｎについて、ステップ６０３において、式（４）を使用し、入力変位ベクトルＸ＝｛ｄi｝(n-1)に基づいてノード間バネの強さ｛ｋij｝(n)を調整する。
２．ステップ６０４において、全てのノードにつき式（２）および式（３）を使用し、ノード間力およびノードに作用するアンカー力をそれぞれ計算し、式（１）を解いて、出力変位ベクトルＹ＝｛ｄ~i｝(n)を得る。
３．ステップ６０５において、入力変位ベクトルおよび出力変位ベクトル（ＸおよびＹ）を比較する。もし両者が収束しているならば、反復を停止する。
４．もし両者が収束していないならば、ステップ６０６において、入力変位ベクトル｛ｄi｝(n-1)と出力変位ベクトル｛ｄi｝(n)とを組み合わせ、新しい入力変位ベクトルＸ＝｛ｄi｝(n)を構築する。プロセスは、次いで、ステップ６０３に進み、両者が収束されるまで繰り返される。
【００３５】
ステップ６０５の一実施形態では、収束を測るために正規化誤差関数が使用される。
【数１０】
2008525896.tif 000012
ここで、ｘiおよびｙiは、入力変位ベクトルＸおよび出力変位ベクトルＹの成分を表す。ステップ６０６の一実施形態では、品質スコアジェネレータ１０６は、平均化または次式で表されるいわゆる単純混合などの単純な方法を使用して、入力変位ベクトルと出力変位ベクトルとを組み合わせる。
【数１１】
2008525896.tif 000013
ここで、αは、０と１との間の定数パラメータである。別の一実施形態では、ステップ６０６において、品質スコアジェネレータ１０６は、Ｖ．Ｅｙｅｒｔによる「Ａ  Ｃｏｍｐａｒａｔｉｖｅ  Ｓｔｕｄｙ  ｏｎ  Ｍｅｔｈｏｄｓ  ｆｏｒ  Ｃｏｎｖｅｒｇｅｎｃｅ  Ａｃｃｅｌｅｒａｔｉｏｎ  ｏｆ  Ｉｔｅｒａｔｉｖｅ  Ｖｅｃｔｏｒ  Ｓｅｑｕｅｎｃｅ（反復ベクトル列の収束加速のための方法に関する比較研究）」（Ｊ．Ｃｏｍｐ．Ｐｈｙｓ．１２４，２７１−２８５（１９９６）に記載されるような拡張Ａｎｄｅｒｓｏｎ混合方法などの、より精巧な方法を使用する。本文献は、引用によって本明細書に組み込まれる。
【００３６】
品質スコア
全てのノードについて最終的な変位が決定されると、品質スコアジェネレータ１０６は、ステップ６０７において、これらの値を使用して文書の品質スコアを決定する。参照ノードに強いられた変位の結果として生じるこれらの変位は、参照文書に対する文書の接続の度合いを明確に反映する。一実施形態では、文書の品質スコアは、その文書に対応するノードの変位として定められる。
【数１２】
2008525896.tif 000014
結果は、次いで、品質スコアデータベース１０７（図１）に格納されてよい。
【００３７】
グループ品質スコア
グループ品質スコアは、ウェブサイトなどの文書グループのための相対的品質スコアであって、文書をグループ分けし、各グループを計算単位として扱うことによって計算される。これは、個々の文書の品質スコアに使用されるのと同様のアルゴリズムによって算出される。代表的な一実施形態では、バネネットワーク内において、各グループに１つずつノードが作成される。次いで、グループ間の全てのハイパーリンク、すなわちグループに属する全ての文書間の全てのリンクが、グループ間の個々のバネの強さの合計に対応する強さを有する単一のバネに低減される。更には、１つまたは２つ以上の参照文書を含む各
グループに、追加の参照ノードが１つずつ作成され、この参照ノードは、それに関連付けられたグループのノードに、その関連グループに含まれる参照文書の数に対応する強さを有するバネによって接続される。新しいバネネットワークが構築されたならば、個々の文書の品質スコアについて上述されたのと同様の手順にしたがって、グループ品質スコアを得ることができる。好ましい一実施形態では、文書グループのグループ品質スコアは、その文書グループに対応するグループノードの変位として定められる。
【数１３】
2008525896.tif 000015
【００３８】
トピック固有の品質スコア
本発明の実施形態は、リンクデータベース内の文書に、汎用ではなくトピック固有の品質スコアを割り当てるために使用することができる。一実施形態では、所定のトピックにおいて高く評価されている権威ある一群の文書が、参照文書として選択される。次いで、汎用の品質スコアに使用されたのと同じ手順にしたがって、トピック固有の品質スコアが得られる。例えば、ＢＥＣＯＭＥ．ｃｏｍなどショッピングに特化されたサーチエンジンは、本発明を使用して、リンクデータベースの中の文書に「ショッピング品質スコア」を割り当てることができる。この場合は、ｗｗｗ．ａｍａｚｏｎ．ｃｏｍまたはｒｅｖｉｅｗ．ｃｎｅｔ．ｃｏｍなどのウェブサイトが参照文書として機能するであろう。本発明は、医薬、スポーツ、ニュース、科学、歴史、旅行等などの多くの異なるトピック分野に適用することができる。
【００３９】
スパミングスコア
本発明の実施形態は、他の多くの目的にも使用することができる。例えば、本発明は、スパミング技術を用いている文書およびその仲間を積極的に識別して罰するために使用することができる。スパミング（または負の品質の）スコアは、以下の手順で得ることができる。１）上述された手順にしたがって、リンクデータベースに対応するバネネットワーク用に、汎用の品質スコアおよびそれらに伴う変位を取得する。２）最終ステップにおける変位に基づいて、式（４）にしたがって、ノード間バネの強さを設定する。３）周知の一群のスパミングサイトを識別し、それらに対応するノードを参照ノードとして選択し、それらの変位を所定の値に設定する。４）ノード間バネの強さをこれ以上調整することなく残りのノードの変位を取得する。
【００４０】
既知のスパミングサイトのノードに変位が生じると、それらのスパミングサイトに密接に接続された全てのサイトおよびウェブページも追従するであろう。今日のインターネットにおいて一般に見られるように、これらのスパミングサイトは、結束の強いコミュニティを形成する傾向があり、何千または何百万ものリンクによって互いに非常に密接に接続されている。
【００４１】
以上では、接続された、または接続を有するノードを使用して本発明の実施形態が説明されているが、留意すべきは、これらのノードが互いに結合されてもよい点である。
【００４２】
当業者ならば、上記の実施形態が本発明の範囲から逸脱することなく様々に変更されてよいことが明らかであろう。したがって、本発明の範囲は、以下の特許請求の範囲およびそれらの法的均等物によって決定されるべきである。
【図面の簡単な説明】
【００４３】
【図１】サーチエンジンのアーキテクチャの一実施形態を示した図である。
【図２】リンクされた文書の集合をグラフ表現した図である。
【図３】２つの文書およびそれらの間のハイパーリンクをグラフ表現した図である。
【図４】２つの文書およびそれらの間のハイパーリンクを、文書のアンカーバネを含めてバネネットワーク表現した図である。
【図５】リンクされた文書の集合をバネネットワーク表現した図である。
【図６】サーチエンジンの品質スコアジェネレータによって品質スコアを生成するための方法を示した代表的なフローチャートである。
【図１】
2008525896.tif 000016
【図２】
2008525896.tif 000017
【図３】
2008525896.tif 000018
【図４】
2008525896.tif 000019
【図５】
2008525896.tif 000020
【図６】
2008525896.tif 000021