(57)【特許請求の範囲】
【請求項１】
複数の文書をスコアリングする情報処理システムであって、
前記複数の文書間の接続関係を表すデータに基づき、少なくとも弱連結関係にある文書群で構成される文書ネットワークを１つ以上特定する特定部と、
前記１つ以上の文書ネットワークのそれぞれについて、対応する文書ネットワークの始点に位置する文書である始点文書を判別する判別部と、
前記対応する文書ネットワークにおいて、出次数がゼロの文書に入次数１及び出次数０の仮想的なダミー文書を接続することにより、前記１つ以上の文書ネットワークのそれぞれについて、前記ダミー文書を含む仮想文書ネットワークを設定する設定部と、
前記１つ以上の文書ネットワークに対応する１つ以上の仮想文書ネットワークのそれぞれについて、特殊エルミート隣接行列を定義する定義部であって、前記特殊エルミート隣接行列は、対応する仮想文書ネットワークを構成する文書Ｄ［ｍ］（１≦ｍ（整数）≦Ｎ）間の接続関係に基づくＮ行Ｎ列のエルミート隣接行列の変形であり、前記エルミート隣接行列は、第ｐ行第ｑ列の成分ｈ（ｐ，ｑ）が、文書Ｄ［ｐ］から文書Ｄ［ｑ］へのリンクが存在し且つ文書Ｄ［ｑ］から文書Ｄ［ｐ］へのリンクが存在するとき、値１を示し、文書Ｄ［ｐ］から文書Ｄ［ｑ］へのリンク及び文書Ｄ［ｑ］から文書Ｄ［ｐ］へのリンクのいずれも存在しないとき、値０を示し、文書Ｄ［ｐ］から文書Ｄ［ｑ］へのリンクが存在するが文書Ｄ［ｑ］から文書Ｄ［ｐ］へのリンクが存在しないとき、値＋ｉ（ｉは虚数単位）を示し、文書Ｄ［ｐ］から文書Ｄ［ｑ］へのリンクが存在しないが文書Ｄ［ｑ］から文書Ｄ［ｐ］へのリンクが存在するとき、値−ｉを示す、対角成分がゼロのエルミート行列である定義部と、
前記特殊エルミート隣接行列の絶対値最大の固有値に対応する固有ベクトルであって、前記文書Ｄ［ｍ］（１≦ｍ≦Ｎ）のそれぞれに対応する成分を有する固有ベクトルを算出する固有ベクトル算出部と、
前記１つ以上の仮想文書ネットワークのそれぞれについて、前記始点文書に対応する成分を基準に、前記固有ベクトルの各成分を複素平面上に配置したときの、前記文書Ｄ［ｍ］（１≦ｍ≦Ｎ）間の前記複素平面上の位置関係に基づき、前記文書Ｄ［ｍ］（１≦ｍ≦Ｎ）のそれぞれのスコアを算出するスコア算出部と、
を備え、前記定義部は、前記固有ベクトルの各成分を前記複素平面上に配置したときに、全ての成分が前記複素平面においてπ／２ラジアンの角度範囲内に収まるように、前記エルミート隣接行列を変形して、前記特殊エルミート隣接行列を定義する情報処理システム。
【請求項２】
請求項１記載の情報処理システムであって、
前記特殊エルミート隣接行列は、第一の補正量Ｃ１及び第二の補正量Ｃ２に基づき、前記エルミート隣接行列において値＋ｉを示す成分を値Ｃ１（Ｃ２＋ｉ）に置換し、値−ｉを示す成分を値Ｃ１（Ｃ２−ｉ）に置換し、当該置換後のエルミート隣接行列における各行の成分の値Ｃ１（Ｃ２＋ｉ）を、同じ行において値Ｃ１（Ｃ２＋ｉ）及び値１を示す成分の数Ｗで除算した値｛Ｃ１（Ｃ２＋ｉ）／Ｗ｝に変更し、更に、前記｛Ｃ１（Ｃ２＋ｉ）／Ｗ｝に変更された成分と対角成分を挟んで対称的な位置関係にある成分の値Ｃ１（Ｃ２−ｉ）を、前記値｛Ｃ１（Ｃ２＋ｉ）／Ｗ｝の複素共役｛Ｃ１（Ｃ２−ｉ）／Ｗ｝に変更することによって定義されるエルミート行列に対応し、
前記第一の補正量Ｃ１及び前記第二の補正量Ｃ２は、パラメータｎを用いて次のように定められ、
【数１】
0006502592.tif 000007
前記パラメータｎは、前記１つ以上の仮想文書ネットワークの中で、文書数Ｎが最大の仮想文書ネットワークにおける文書数ｍａｘ｛Ｎ｝に基づいて、前記全ての成分が前記複素平面においてπ／２ラジアンの角度範囲内に収まるように定められる情報処理システム。
【請求項３】
請求項１記載の情報処理システムであって、
前記特殊エルミート隣接行列は、第一の補正量Ｃ１及び第二の補正量Ｃ２に基づき、前記エルミート隣接行列において値＋ｉを示す成分を値Ｃ１（Ｃ２＋ｉ）に置換し、値−ｉを示す成分を値Ｃ１（Ｃ２−ｉ）に置換し、当該置換後のエルミート隣接行列における各行の成分の値Ｃ１（Ｃ２＋ｉ）を、同じ行において値Ｃ１（Ｃ２＋ｉ）及び値１を示す成分の数Ｗで除算した値｛Ｃ１（Ｃ２＋ｉ）／Ｗ｝に変更し、更に、前記値｛Ｃ１（Ｃ２＋ｉ）／Ｗ｝に変更された成分と対角成分を挟んで対称的な位置関係にある成分の値Ｃ１（Ｃ２−ｉ）を、前記値｛Ｃ１（Ｃ２＋ｉ）／Ｗ｝の複素共役｛Ｃ１（Ｃ２−ｉ）／Ｗ｝に変更し、変更後のエルミート隣接行列Ｈにおける各行の成分の値｛Ｃ１（Ｃ２−ｉ）／Ｗ｝を、前記変更の前において同じ行でＣ１（Ｃ２−ｉ）及び値１を示していた成分の数Ｚで乗算した値｛Ｃ１（Ｃ２−ｉ）Ｚ／Ｗ｝に変更し、更に、前記値｛Ｃ１（Ｃ２−ｉ）Ｚ／Ｗ｝に変更された成分と対角成分を挟んで対称的な位置関係にある成分の値｛Ｃ１（Ｃ２＋ｉ）／Ｗ｝を、前記値｛Ｃ１（Ｃ２−ｉ）Ｚ／Ｗ｝の複素共役｛Ｃ１（Ｃ２＋ｉ）Ｚ／Ｗ｝に変更することによって定義されるエルミート行列に対応し、
前記第一の補正量Ｃ１及び前記第二の補正量Ｃ２は、パラメータｎを用いて次のように定められ、
【数２】
0006502592.tif 000008
前記パラメータｎは、前記１つ以上の仮想文書ネットワークの中で、文書数Ｎが最大の仮想文書ネットワークにおける文書数ｍａｘ｛Ｎ｝に基づいて、前記全ての成分が前記複素平面においてπ／２ラジアンの角度範囲内に収まるように定められる情報処理システム。
【請求項４】
請求項１記載の情報処理システムであって、
前記特殊エルミート隣接行列は、補正量Ｃに基づき、前記エルミート隣接行列において値＋ｉを示す成分を値Ｃ＋ｉに置換し、当該置換後のエルミート隣接行列における各行の値Ｃ＋ｉを示す成分の値を、同じ行において値Ｃ＋ｉを示す成分の数Ｒで除算した値｛（Ｃ＋ｉ）／Ｒ｝に変更し、更に、値−ｉを示す成分の値を、対角成分を挟んで対称的な位置関係にある成分の複素共役｛（Ｃ−ｉ）／Ｒ｝に変更することによって定義されるエルミート行列に対応し、
前記補正量Ｃは、パラメータｎを用いて次のように定められ、
【数３】
0006502592.tif 000009
前記パラメータｎは、前記１つ以上の仮想文書ネットワークの中で、文書数Ｎが最大の仮想文書ネットワークにおける文書数ｍａｘ｛Ｎ｝に基づいて、前記全ての成分が前記複素平面においてπ／２ラジアンの角度範囲内に収まるように定められる情報処理システム。
【請求項５】
請求項１〜請求項４のいずれか一項記載の情報処理システムであって、
前記スコア算出部は、前記１つ以上の仮想文書ネットワークのそれぞれについて、前記固有ベクトルの各成分の値Ｖ［ｍ］（１≦ｍ≦Ｎ）を、前記始点文書に対応する成分が前記複素平面における特定位置に配置されるように回転変換し、前記文書Ｄ［ｍ］（１≦ｍ≦Ｎ）のそれぞれのスコアを、対応する文書Ｄ［ｍ］の前記回転変換後の値Ｖｃ［ｍ］に基づき算出する情報処理システム。
【請求項６】
請求項５記載の情報処理システムであって、
前記スコア算出部は、前記始点文書に対応する成分が、前記特定位置として、前記複素平面における前記一つの象限の境界に位置する特定軸からゼロではない所定角度の位置に配置されるように、前記固有ベクトルの各成分の値Ｖ［ｍ］（１≦ｍ≦Ｎ）を回転変換する情報処理システム。
【請求項７】
請求項５又は請求項６記載の情報処理システムであって、
前記スコア算出部は、前記文書Ｄ［ｍ］（１≦ｍ≦Ｎ）のそれぞれのスコアとして、対応する文書Ｄ［ｍ］の前記回転変換後の値Ｖｃ［ｍ］に基づき、前記複素平面における特定軸からの前記値Ｖｃ［ｍ］の角度θ［ｍ］と前記値Ｖｃ［ｍ］の絶対値Ｌ［ｍ］との積（θ［ｍ］・Ｌ［ｍ］）に対応する値を算出する情報処理システム。
【請求項８】
請求項１〜請求項４のいずれか一項記載の情報処理システムであって、
前記スコア算出部は、前記１つ以上の仮想文書ネットワークのそれぞれについて、前記固有ベクトルの各成分の値Ｖ［ｍ］（１≦ｍ≦Ｎ）を、前記始点文書に対応する成分の値Ｖ［ｓ］に基づいた特定値Ｅで除算することにより、前記始点文書に対応する成分を複素平面の特定軸上に配置し、その後、前記始点文書に対応する成分を前記特定軸からゼロではない所定角度の位置まで回転させるように、前記固有ベクトルの各成分の値Ｖ［ｍ］／Ｅ（１≦ｍ≦Ｎ）を回転変換し、前記文書Ｄ［ｍ］（１≦ｍ≦Ｎ）のそれぞれのスコアとして、対応する文書Ｄ［ｍ］の前記回転変換後の値Ｖｃ［ｍ］に基づき、前記複素平面における前記特定軸からの前記値Ｖｃ［ｍ］の角度θ［ｍ］と前記値Ｖｃ［ｍ］の絶対値Ｌ［ｍ］との積（θ［ｍ］・Ｌ［ｍ］）に対応する値を算出する情報処理システム。
【請求項９】
請求項８記載の情報処理システムであって、
前記スコア算出部は、前記固有ベクトルの各成分の値Ｖ［ｍ］（１≦ｍ≦Ｎ）を前記特定値Ｅで除算したときに、前記複素平面において、前記特定軸よりも前記回転変換による回転方向の上流に位置する成分が存在する場合には、最も上流に位置する成分を、前記特定軸からゼロではない所定角度の位置まで回転させるように、前記固有ベクトルの各成分の値Ｖ［ｍ］／Ｅ（１≦ｍ≦Ｎ）を回転変換する情報処理システム。
【請求項１０】
請求項７〜請求項９のいずれか一項記載の情報処理システムであって、
前記文書Ｄ［ｍ］（１≦ｍ≦Ｎ）のそれぞれのスコアを、前記文書Ｄ［ｍ］（１≦ｍ≦Ｎ）の全ての前記スコアの最小値がゼロとなるように前記積（θ［ｍ］・Ｌ［ｍ］）を減算した値として算出する情報処理システム。
【請求項１１】
請求項１〜請求項４のいずれか一項記載の情報処理システムであって、
前記スコア算出部は、前記１つ以上の仮想文書ネットワークのそれぞれについて、前記固有ベクトルの各成分の値Ｖ［ｍ］（１≦ｍ≦Ｎ）を、前記始点文書に対応する成分の値Ｖ［ｓ］に基づいた特定値Ｅで除算することにより、前記始点文書に対応する成分を複素平面の特定軸上に配置し、前記文書Ｄ［ｍ］（１≦ｍ≦Ｎ）のそれぞれのスコアとして、対応する文書Ｄ［ｍ］の成分の値Ｖ［ｍ］／Ｅの前記特定軸からの角度θ［ｍ］と前記値Ｖ［ｍ］／Ｅの絶対値Ｌ［ｍ］との積（θ［ｍ］・Ｌ［ｍ］）に対応する値を算出する情報処理システム。
【請求項１２】
請求項８、請求項９、及び請求項１１のいずれか一項記載の情報処理システムであって、
前記スコア算出部は、前記特定値Ｅとして、前記固有ベクトルの各成分の値Ｖ［ｍ］を前記始点文書に対応する成分の値Ｖ［ｓ］で除算することにより、前記始点文書に対応する成分を複素平面の実軸上に配置する情報処理システム。
【請求項１３】
請求項１〜請求項１２のいずれか一項記載の情報処理システムであって、
前記判別部は、前記対応する文書ネットワークにおいて、最も長い経路の始点に位置する文書を前記始点文書に判別する情報処理システム。
【請求項１４】
請求項１３記載の情報処理システムであって、
前記判別部は、前記対応する文書ネットワークにおいて複数の経路が前記最も長い経路に該当する場合には、前記複数の経路の始点に位置する文書の内、出次数が最も多い文書及び出次数が最も少ない文書の一方を、前記始点文書に判別する情報処理システム。
【請求項１５】
請求項１３記載の情報処理システムであって、
前記判別部は、前記対応する文書ネットワークにおいて複数の経路が前記最も長い経路に該当する場合には、前記複数の経路の始点に位置する文書に接続される入次数がゼロの仮想的なダミー文書を配置し、配置した仮想的なダミー文書を前記始点文書として判別する情報処理システム。
【請求項１６】
請求項１〜請求項１５のいずれか一項記載の情報処理システムであって、
前記スコア算出部により算出された前記複数の文書のスコアに基づき、検索クエリに対応する文書のリストにおける文書の配列を決定する配列決定部を備える情報処理システム。
【請求項１７】
複数の文書をスコアリングする情報処理方法であって、コンピュータが、
前記複数の文書間の接続関係を表すデータに基づき、少なくとも弱連結関係にある文書群で構成される文書ネットワークを１つ以上特定することと、
前記特定された１つ以上の文書ネットワークのそれぞれについて、対応する文書ネットワークの始点に位置する文書である始点文書を判別することと、
前記対応する文書ネットワークにおいて、出次数がゼロの文書に入次数１及び出次数０の仮想的なダミー文書を接続することにより、前記１つ以上の文書ネットワークのそれぞれについて、前記ダミー文書を含む仮想文書ネットワークを設定することと、
前記１つ以上の文書ネットワークに対応する１つ以上の仮想文書ネットワークのそれぞれについて、特殊エルミート隣接行列を定義することであって、前記特殊エルミート隣接行列は、対応する仮想文書ネットワークを構成する文書Ｄ［ｍ］（１≦ｍ（整数）≦Ｎ）間の接続関係に基づくＮ行Ｎ列のエルミート隣接行列の変形であり、前記エルミート隣接行列は、第ｐ行第ｑ列の成分ｈ（ｐ，ｑ）が、文書Ｄ［ｐ］から文書Ｄ［ｑ］へのリンクが存在し且つ文書Ｄ［ｑ］から文書Ｄ［ｐ］へのリンクが存在するとき、値１を示し、文書Ｄ［ｐ］から文書Ｄ［ｑ］へのリンク及び文書Ｄ［ｑ］から文書Ｄ［ｐ］へのリンクのいずれも存在しないとき、値０を示し、文書Ｄ［ｐ］から文書Ｄ［ｑ］へのリンクが存在するが文書Ｄ［ｑ］から文書Ｄ［ｐ］へのリンクが存在しないとき、値＋ｉ（ｉは虚数単位）を示し、文書Ｄ［ｐ］から文書Ｄ［ｑ］へのリンクが存在しないが文書Ｄ［ｑ］から文書Ｄ［ｐ］へのリンクが存在するとき、値−ｉを示す、対角成分がゼロのエルミート行列である、前記定義することと、
前記特殊エルミート隣接行列の絶対値最大の固有値に対応する固有ベクトルであって、前記文書Ｄ［ｍ］（１≦ｍ≦Ｎ）のそれぞれに対応する成分を有する固有ベクトルを算出することと、
前記１つ以上の仮想文書ネットワークのそれぞれについて、前記始点文書に対応する成分を基準に、前記固有ベクトルの各成分を複素平面上に配置したときの、前記文書Ｄ［ｍ］（１≦ｍ≦Ｎ）間の前記複素平面上の位置関係に基づき、前記文書Ｄ［ｍ］（１≦ｍ≦Ｎ）のそれぞれのスコアを算出することと
を含み、
前記固有ベクトルの各成分を前記複素平面上に配置したときに、全ての成分が前記複素平面においてπ／２ラジアンの角度範囲内に収まるように、前記エルミート隣接行列を変形することによって、前記特殊エルミート隣接行列を定義する情報処理方法。
【請求項１８】
請求項１７記載の情報処理方法をコンピュータに実行させるためのコンピュータプログラム。
【発明の詳細な説明】
【関連出願の相互参照】
【０００１】
本国際出願は、２０１７年１１月２８日に日本国特許庁に出願された日本国特許出願第２０１７−２２７９３６号に基づく優先権を主張するものであり、日本国特許出願第２０１７−２２７９３６号の全内容を参照により本国際出願に援用する。
【技術分野】
【０００２】
本開示は、情報処理システム、情報処理方法、及びコンピュータプログラムに関する。
【背景技術】
【０００３】
ウェブページのスコアリング／ランク付けを行う技術が既に知られている（特許文献１参照）。この技術の単純な例では、ページランクを、多くのウェブページからリンクされるウェブページほど高く判定する。ページランクの計算には、ウェブページ間の接続関係を値０，１で二値表現した隣接行列、及び、隣接行列の各成分を変更した、値０，１と他の実数とを成分に含む行列が用いられる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１７−１０２７１２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上述の隣接行列に基づきページランクを判定する従来方法では、ウェブページ間の実際の接続関係に加え、全てのウェブページから全てのウェブページへの仮想的な接続関係を措定する必要がある。このため、ウェブページの良好なランク付けを行うことが難しい。【０００６】
そこで、本開示の一側面によれば、新規な隣接行列に基づいて、従来よりも適切に複数文書のスコアリング／ランク付けを行うことが可能な技術を提供できることが望ましい。
【課題を解決するための手段】
【０００７】
本開示の一側面によれば、複数の文書をスコアリングする情報処理システムが提供される。情報処理システムは、特定部と、判別部と、設定部と、定義部と、固有ベクトル算出部と、スコア算出部と、を備える。【０００８】
特定部は、複数の文書間の接続関係を表すデータに基づき、少なくとも弱連結関係にある文書群で構成される文書ネットワークを１つ以上特定する。判別部は、１つ以上の文書ネットワークのそれぞれについて、対応する文書ネットワークの始点に位置する文書である始点文書を判別する。【０００９】
設定部は、対応する文書ネットワークにおいて、出次数がゼロの文書に、入次数１及び出次数０の仮想的なダミー文書を接続することにより、１つ以上の文書ネットワークのそれぞれについて、ダミー文書を含む仮想文書ネットワークを設定する。【００１０】
定義部は、１つ以上の文書ネットワークに対応する１つ以上の仮想文書ネットワークのそれぞれについて、特殊エルミート隣接行列を定義する。特殊エルミート隣接行列は、対応する仮想文書ネットワークを構成する文書Ｄ［ｍ］（１≦ｍ≦Ｎ）間の接続関係に基づくＮ行Ｎ列のエルミート隣接行列の変形である。ここで、ｍは、整数である。【００１１】
エルミート隣接行列は、対角成分がゼロのエルミート行列である。エルミート隣接行列において、第ｐ行第ｑ列の成分ｈ（ｐ，ｑ）は、文書Ｄ［ｐ］から文書Ｄ［ｑ］へのリンクが存在し且つ文書Ｄ［ｑ］から文書Ｄ［ｐ］へのリンクが存在するとき、値１を示し、文書Ｄ［ｐ］から文書Ｄ［ｑ］へのリンク及び文書Ｄ［ｑ］から文書Ｄ［ｐ］へのリンクのいずれも存在しないとき、値０を示し、文書Ｄ［ｐ］から文書Ｄ［ｑ］へのリンクが存在するが文書Ｄ［ｑ］から文書Ｄ［ｐ］へのリンクが存在しないとき、値＋ｉ（ｉは虚数単位）を示し、文書Ｄ［ｐ］から文書Ｄ［ｑ］へのリンクが存在しないが文書Ｄ［ｑ］から文書Ｄ［ｐ］へのリンクが存在するとき、値−ｉを示す。【００１２】
固有ベクトル算出部は、特殊エルミート隣接行列の絶対値最大の固有値に対応する固有ベクトルを算出する。固有ベクトルは、文書Ｄ［ｍ］（１≦ｍ≦Ｎ）のそれぞれに対応する成分を有する。本開示の一側面によれば、固有ベクトル算出部は、絶対値最大の固有値として正の固有値と負の固有値が存在する場合、正の固有値に対応する固有ベクトルを算出することができる。【００１３】
スコア算出部は、１つ以上の仮想文書ネットワークのそれぞれについて、始点文書に対応する成分を基準に、固有ベクトルの各成分を複素平面上に配置したときの、文書Ｄ［ｍ］（１≦ｍ≦Ｎ）間の複素平面上の位置関係に基づき、文書Ｄ［ｍ］（１≦ｍ≦Ｎ）のそれぞれのスコアを算出する。【００１４】
この情報処理システムによれば、文書間の接続関係を１，０，＋ｉ，−ｉの４値で表現可能なエルミート隣接行列に対応する特殊エルミート隣接行列を用いて複数の文書をスコアリングする。このため、全文書から全文書への仮想的な接続関係を措定する必要がなく、文書間の接続関係に基づく各文書のスコアリング／ランク付けを従来よりも適切に実現することができる。【００１５】
本開示の一側面では、定義部は、固有ベクトルの各成分を複素平面上に配置したときに、全ての成分が複素平面においてπ／２ラジアン（即ち９０度）の角度範囲内に収まるように、エルミート隣接行列を変形して、特殊エルミート隣接行列を定義するように構成されてもよい。【００１６】
この情報処理システムでは、複素平面上で各文書に対応する固有ベクトルの成分が１回転以上しないように、特には、各成分が複素平面上で１象限に対応するサイズの領域に収まるように、エルミート隣接行列を変形して、スコアを算出するので、複素平面上での回転方向の距離情報を用いて、各文書を適切にスコアリングすることができる。【００１７】
本開示の一側面では、特殊エルミート隣接行列は、第一の補正量Ｃ１及び第二の補正量Ｃ２に基づき、エルミート隣接行列において値＋ｉを示す成分を値Ｃ１（Ｃ２＋ｉ）に置換し、値−ｉを示す成分を値Ｃ１（Ｃ２−ｉ）に置換し、当該置換後のエルミート隣接行列における各行の成分の値Ｃ１（Ｃ２＋ｉ）を、同じ行において値Ｃ１（Ｃ２＋ｉ）及び値１を示す成分の数Ｗで除算した値｛Ｃ１（Ｃ２＋ｉ）／Ｗ｝に変更し、更に、値｛Ｃ１（Ｃ２＋ｉ）／Ｗ｝に変更された成分と対角成分を挟んで対称的な位置関係にある成分の値Ｃ１（Ｃ２−ｉ）を、値｛Ｃ１（Ｃ２＋ｉ）／Ｗ｝の複素共役｛Ｃ１（Ｃ２−ｉ）／Ｗ｝に変更することによって定義されるエルミート行列に対応し得る。第一の補正量Ｃ１及び第二の補正量Ｃ２は、パラメータｎを用いて次のように定められ得る。【００１８】
【数１】
0006502592.tif 000002
パラメータｎは、上記１つ以上の仮想文書ネットワークの中で、文書数Ｎが最大の仮想文書ネットワークにおける文書数ｍａｘ｛Ｎ｝に基づいて、上記全ての成分が複素平面においてπ／２ラジアンの角度範囲内に収まるように定められ得る。【００１９】
第一の補正量Ｃ１及び第二の補正量Ｃ２は、固有ベクトルの各成分の関係を保持しながら、全ての成分が複素平面においてπ／２ラジアンの角度範囲内に収まるように、特殊エルミート隣接行列を定義することに役立つ。【００２０】
本開示の一側面では、特殊エルミート隣接行列は、エルミート隣接行列において値＋ｉを示す成分を値Ｃ１（Ｃ２＋ｉ）に置換し、値−ｉを示す成分を値Ｃ１（Ｃ２−ｉ）に置換し、当該置換後のエルミート隣接行列における各行の成分の値Ｃ１（Ｃ２＋ｉ）を、同じ行において値Ｃ１（Ｃ２＋ｉ）及び値１を示す成分の数Ｗで除算した値｛Ｃ１（Ｃ２＋ｉ）／Ｗ｝に変更し、更に、値｛Ｃ１（Ｃ２＋ｉ）／Ｗ｝に変更された成分と対角成分を挟んで対称的な位置関係にある成分の値Ｃ１（Ｃ２−ｉ）を、値｛Ｃ１（Ｃ２＋ｉ）／Ｗ｝の複素共役｛Ｃ１（Ｃ２−ｉ）／Ｗ｝に変更し、変更後のエルミート隣接行列Ｈにおける各行の成分の値｛Ｃ１（Ｃ２−ｉ）／Ｗ｝を、変更前において同じ行でＣ１（Ｃ２−ｉ）及び値１を示していた成分の数Ｚで乗算した値｛Ｃ１（Ｃ２−ｉ）Ｚ／Ｗ｝に変更し、更に、値｛Ｃ１（Ｃ２−ｉ）Ｚ／Ｗ｝に変更された成分と対角成分を挟んで対称的な位置関係にある成分の値｛Ｃ１（Ｃ２＋ｉ）／Ｗ｝を、値｛Ｃ１（Ｃ２−ｉ）Ｚ／Ｗ｝の複素共役｛Ｃ１（Ｃ２＋ｉ）Ｚ／Ｗ｝に変更することによって定義されるエルミート行列に対応してもよい。【００２１】
本開示の一側面では、特殊エルミート隣接行列は、補正量Ｃに基づき、エルミート隣接行列において値＋ｉを示す成分を値Ｃ＋ｉに置換し、当該置換後のエルミート隣接行列における各行の値Ｃ＋ｉを示す成分の値を、同じ行において値Ｃ＋ｉを示す成分の数Ｒで除算した値｛（Ｃ＋ｉ）／Ｒ｝に変更し、更に、値−ｉを示す成分の値を、対角成分を挟んで対称的な位置関係にある成分の複素共役｛（Ｃ−ｉ）／Ｒ｝に変更することによって定義されるエルミート行列に対応してもよい。補正量Ｃは、パラメータｎを用いて次のように定められてもよい。【００２２】
【数２】
0006502592.tif 000003
補正量Ｃは、固有ベクトルの全ての成分が複素平面においてπ／２ラジアンの角度範囲内に収まるように、特殊エルミート隣接行列を定義することに役立つ。【００２３】
本開示の一側面では、スコア算出部は、１つ以上の仮想文書ネットワークのそれぞれについて、固有ベクトルの各成分の値Ｖ［ｍ］（１≦ｍ≦Ｎ）を、始点文書に対応する成分が複素平面における特定位置に配置されるように回転変換してもよい。スコア算出部は、文書Ｄ［ｍ］（１≦ｍ≦Ｎ）のそれぞれのスコアを、対応する文書Ｄ［ｍ］の回転変換後の値Ｖｃ［ｍ］に基づき算出してもよい。【００２４】
このようにスコアを算出すれば、複数の文書ネットワークのそれぞれの始点文書を、複素平面上において同じ位置に配置することができ、複数の文書ネットワークのそれぞれに属する文書を、同じ評価基準で適切にスコアリングすることができる。【００２５】
本開示の一側面では、スコア算出部は、始点文書に対応する成分が、特定位置として、複素平面における一つの象限の境界に位置する特定軸からゼロではない所定角度の位置に配置されるように、固有ベクトルの各成分の値Ｖ［ｍ］（１≦ｍ≦Ｎ）を回転変換してもよい。【００２６】
本開示の一側面では、スコア算出部は、文書Ｄ［ｍ］（１≦ｍ≦Ｎ）のそれぞれのスコアとして、対応する文書Ｄ［ｍ］の回転変換後の値Ｖｃ［ｍ］に基づき、複素平面における特定軸からの値Ｖｃ［ｍ］の角度θ［ｍ］と値Ｖｃ［ｍ］の絶対値Ｌ［ｍ］との積（θ［ｍ］・Ｌ［ｍ］）に対応する値を算出してもよい。【００２７】
本開示の一側面では、スコア算出部は、１つ以上の仮想文書ネットワークのそれぞれについて、固有ベクトルの各成分の値Ｖ［ｍ］（１≦ｍ≦Ｎ）を、始点文書に対応する成分の値Ｖ［ｓ］に基づいた特定値Ｅで除算することにより、始点文書に対応する成分を複素平面の特定軸上に配置してもよい。スコア算出部は、その後、始点文書に対応する成分を特定軸からゼロではない所定角度の位置まで回転させるように、固有ベクトルの各成分の値Ｖ［ｍ］／Ｅ（１≦ｍ≦Ｎ）を回転変換してもよい。【００２８】
本開示の一側面では、スコア算出部は、固有ベクトルの各成分の値Ｖ［ｍ］（１≦ｍ≦Ｎ）を特定値Ｅで除算したときに、複素平面において、特定軸よりも回転変換による回転方向の上流に位置する成分が存在する場合には、最も上流に位置する成分を、特定軸からゼロではない所定角度の位置まで回転させるように、固有ベクトルの各成分の値Ｖ［ｍ］／Ｅ（１≦ｍ≦Ｎ）を回転変換してもよい。【００２９】
本開示の一側面では、文書Ｄ［ｍ］（１≦ｍ≦Ｎ）のそれぞれのスコアを、文書Ｄ［ｍ］（１≦ｍ≦Ｎ）の全てのスコアの最小値がゼロとなるように積（θ［ｍ］・Ｌ［ｍ］）を減算した値として算出してもよい。【００３０】
本開示の一側面では、スコア算出部は、１つ以上の仮想文書ネットワークのそれぞれについて、固有ベクトルの各成分の値Ｖ［ｍ］（１≦ｍ≦Ｎ）を、始点文書に対応する成分の値Ｖ［ｓ］に基づいた特定値Ｅで除算することにより、始点文書に対応する成分を複素平面の特定軸上に配置し、文書Ｄ［ｍ］（１≦ｍ≦Ｎ）のそれぞれのスコアとして、対応する文書Ｄ［ｍ］の成分の値Ｖ［ｍ］／Ｅの特定軸からの角度θ［ｍ］と値Ｖ［ｍ］／Ｅの絶対値Ｌ［ｍ］との積（θ［ｍ］・Ｌ［ｍ］）に対応する値を算出してもよい。【００３１】
本開示の一側面では、特定軸は、複素平面における実軸であってもよい。スコア算出部は、特定値Ｅとして、固有ベクトルの各成分の値Ｖ［ｍ］を始点文書に対応する成分の値Ｖ［ｓ］で除算することにより、始点文書に対応する成分を複素平面の実軸上に配置することができる。【００３２】
本開示の一側面では、判別部は、対応する文書ネットワークにおいて、最も長い経路の始点に位置する文書を始点文書に判別してもよい。
本開示の一側面では、判別部は、対応する文書ネットワークにおいて複数の経路が最も長い経路に該当する場合には、複数の経路の始点に位置する文書の内、出次数が最も多い文書又は出次数が最も少ない文書を、始点文書に判別してもよい。【００３３】
本開示の一側面では、判別部は、対応する文書ネットワークにおいて複数の経路が最も長い経路に該当する場合には、複数の経路の始点に位置する文書に接続される入次数がゼロの仮想的なダミー文書を配置し、配置した仮想的なダミー文書を始点文書として判別してもよい。本開示の一側面では、判別部は、対応する文書ネットワークにおいて複数の経路が最も長い経路に該当し、さらに、これら複数の経路の始点に位置する複数の文書において出次数が最も多い文書又は出次数が最も少ない文書が複数存在する場合には、複数の経路の始点に位置する出次数が最も多い又は出次数が最も少ない複数の文書に接続される入次数がゼロの仮想的なダミー文書を配置し、配置した仮想的なダミー文書を始点文書として判別してもよい。【００３４】
本開示の一側面では、スコア算出部により算出された複数の文書のスコアに基づき、検索クエリに対応する文書のリストにおける文書の配列を決定する配列決定部を備えてもよい。本開示の一側面では、配列決定部は、検索クエリに対応する文書のリストを、スコアが高い文書ほどリストにおいて対応する文書が上位に配置されるように生成してもよい。【００３５】
この情報処理システムによれば、検索クエリに対応する複数の文書を、重要度に応じた順序で配列したリストを生成することができ、適切な検索結果を出力することができる。
本開示の一側面では、上述の情報処理システムが実行する手順を含む情報処理方法が提供されてもよい。即ち、本開示の一側面では、複数の文書をスコアリングする情報処理方法が提供されてもよい。【００３６】
本開示の一側面に係る情報処理方法は、複数の文書間の接続関係を表すデータに基づき、少なくとも弱連結関係にある文書群で構成される文書ネットワークを１つ以上特定することと、特定された１つ以上の文書ネットワークのそれぞれについて、対応する文書ネットワークの始点に位置する文書である始点文書を判別することと、対応する文書ネットワークにおいて、出次数がゼロの文書に入次数１及び出次数０の仮想的なダミー文書を接続することにより、１つ以上の文書ネットワークのそれぞれについて、ダミー文書を含む仮想文書ネットワークを設定することと、１つ以上の文書ネットワークに対応する１つ以上の仮想文書ネットワークのそれぞれについて、特殊エルミート隣接行列を定義することと、特殊エルミート隣接行列の絶対値最大の固有値に対応する固有ベクトルであって、文書Ｄ［ｍ］（１≦ｍ≦Ｎ）のそれぞれに対応する成分を有する固有ベクトルを算出することと、１つ以上の仮想文書ネットワークのそれぞれについて、始点文書に対応する成分を基準に、固有ベクトルの各成分を複素平面上に配置したときの、文書Ｄ［ｍ］（１≦ｍ≦Ｎ）間の複素平面上の位置関係に基づき、文書Ｄ［ｍ］（１≦ｍ≦Ｎ）のそれぞれのスコアを算出することと、を含んでいてもよい。【００３７】
特殊エルミート隣接行列は、固有ベクトルの各成分を複素平面上に配置したときに、全ての成分が複素平面においてπ／２ラジアンの角度範囲内に収まるように、エルミート隣接行列を変形することによって定義されてもよい。【００３８】
本開示の一側面では、上述した情報処理方法をコンピュータに実行させるためのコンピュータプログラムが提供されてもよい。本開示の一側面によれば、このコンピュータプログラムを格納した非遷移的実体的記録媒体が提供されてもよい。本開示の一側面では、プロセッサと、プロセッサに複数の文書をスコアリングするための処理を実行させるためのコンピュータプログラムを記憶するメモリと、を備える情報処理システムが提供されてもよい。
【図面の簡単な説明】
【００３９】
【図１】情報処理システムの構成を表すブロック図である。
【図２】情報処理システムに関する機能ブロック図である。
【図３】クエリ応答部の詳細を表す機能ブロック図である。
【図４】第２スコアリング部が実行する処理を表すフローチャートである。
【図５】図５Ａは、連結文書ネットワークの例を示す図であり、図５Ｂは、対応する仮想文書ネットワークを示す図である。
【図６】図６Ａは、連結文書ネットワークの例を示す図であり、図６Ｂは、対応する仮想文書ネットワークを示す図である。
【図７】図７Ａは、連結文書ネットワークの例を示す図であり、図７Ｂは、対応する仮想文書ネットワークを示す図である。
【図８】図８Ａは、連結文書ネットワークの例を示す図であり、図８Ｂは、対応する仮想文書ネットワークを示す図である。
【図９】図９Ａは、連結文書ネットワークの例を示す図であり、図９Ｂは、対応する仮想文書ネットワークを示す図である。
【図１０】図１０Ａは、連結文書ネットワークの例を示す図であり、図１０Ｂは、対応する仮想文書ネットワークを示す図である。
【図１１】連結文書ネットワークの例を示す図である。
【図１２】第２スコアリング部が始点ページを設定するために実行する処理を表すフローチャートである。
【図１３】特殊エルミート隣接行列の生成方法を説明した図である。
【図１４】第２スコアリング部が回転変換のために実行する処理を表すフローチャートである。
【図１５】図１５Ａは、複数成分の複素平面上の配置に関する説明図であり、図１５Ｂは、スコアの算出方法を説明した図である。
【図１６】特殊エルミート隣接行列の変形例を示す図である。
【図１７】別の変形例において、第２スコアリング部が実行する処理を表すフローチャートである。
【図１８】特殊エルミート隣接行列の別の変形例を示す図である。
【図１９】別の変形例におけるスコアの算出方法を説明した図である。
【符号の説明】
【００４０】
１…情報処理システム、５…ユーザ端末、１０…演算部、１１…プロセッサ、１５…メモリ、２０…記憶部、３０…通信部、１１０…クローラ、１２０…インデクサ、１３０…クエリ処理部、１４０…クエリ応答部、１４１…第１スコアリング部、１４３…第２スコアリング部、１４５…ランク付け部、１４７…出力部、２１０…ページリポジトリ、２２０…インデックス記憶部、ＳＰ…始点ページ、ＥＰ…終点ページ、ＤＰ…ダミーページ。
【発明を実施するための形態】
【００４１】
本開示の例示的実施形態を、以下に図面を参照しながら説明する。
図１に示す本実施形態の情報処理システム１は、ユーザ端末５から入力される検索クエリに応答して、ユーザ端末５に、検索クエリに対応する文書のリストを提供するように構成される。文書は、ウェブ文書、具体的にはウェブページである。即ち、情報処理システム１は、通信ネットワークを通じてユーザ端末５から利用可能な検索エンジンとして機能する。通信ネットワークは、例えば、インターネットである。
【００４２】
この情報処理システム１は、演算部１０と、記憶部２０と、通信部３０と、を備える。演算部１０は、プロセッサ１１及びメモリ１５を備える。記憶部２０は、プロセッサにより実行されるコンピュータプログラム及びデータを記憶する。記憶部２０は、ハードディスクドライブ及びソリッドステートドライブの一方を備えることができる。
【００４３】
通信部３０は、ユーザ端末５と通信可能に構成される。演算部１０は、記憶部２０に記憶されたコンピュータプログラムに従う処理を実行することにより、検索機能、即ち検索エンジンとしての機能を実現する。この検索機能を実現するための処理は、具体的には、プロセッサ１１により実行される。図１に簡略的に示される情報処理システム１は、具体的には、一つ以上の協働するサーバ装置群で構成され得る。
【００４４】
検索機能は、演算部１０が、図２に示すクローラ１１０、インデクサ１２０、クエリ処理部１３０、及び、クエリ応答部１４０として機能し、記憶部２０が、ページリポジトリ２１０、及びインデックス記憶部２２０として機能することにより実現される。
【００４５】
クローラ１１０は、周知のクローラと同様に、通信ネットワークに存在するウェブページを収集するように構成される。クローラ１１０により収集されたウェブページは、ページリポジトリ２１０に蓄積される。
【００４６】
インデクサ１２０は、ページリポジトリ２１０に蓄積されたウェブページを解析してインデックス化するように構成される。インデックス化により、ウェブページから、検索に価値のある情報が抽出され、ウェブページに対応するインデックスデータが生成される。
【００４７】
インデックスデータは、ウェブページから抽出された検索に価値のある情報を含む。具体的に、インデックスデータは、内容インデックス、構造インデックス、及び特殊用途インデックスを含む。内容インデックスは、ウェブページのキーワード、タイトル、キーとなる文章の情報を含む。構造インデックスは、ウェブページのハイパーリンク構造を表す情報を含む。特殊用途インデックスは、画像インデックス及びｐｄｆインデックスなどの特殊なクエリ処理に役立つ情報を保持する。インデクサ１２０により生成されたウェブページ毎のインデックスデータは、インデックス記憶部２２０に記憶される。インデックスデータの一群は、ウェブページ間の接続関係を表す。
【００４８】
クエリ処理部１３０は、ユーザからの検索クエリを受け付け、検索クエリに対応するウェブページの集合である関連ページ群を、全ウェブページの中から抽出する。ここでいう全ウェブページは、クローラ１１０により通信ネットワーク内で見つけられ、インデックス記憶部２２０にインデックスデータが登録されたウェブページ群に対応する。
【００４９】
具体的に、クエリ処理部１３０は、インデックス記憶部２２０が記憶する各ウェブページの内容インデックスに基づき、検索クエリに対応する語彙を含むウェブページの集合を関連ページ群として、全ウェブページの中から抽出する。そして、この関連ページ群の情報をクエリ応答部１４０に提供する。
【００５０】
クエリ応答部１４０は、クエリ処理部１３０から提供される関連ページ群の情報に基づき、関連ページ群をページランク順に配列した検索結果リストを、検索クエリに対する応答データとして、ユーザ端末５に送信する。関連ページの夫々は、検索クエリとの関連度及び重要度が高いウェブページほど上位にランク付けされ、検索結果リストの上位に配置される。検索結果リストは、従来の検索エンジンからの応答データと同様に、リストアップされた関連ページへのリンクを有したウェブページとして構成される。ここで言うリンクは、所謂ハイパーリンクである。
【００５１】
詳述すると、クエリ応答部１４０は、図３に示すように、第１スコアリング部１４１と、第２スコアリング部１４３と、ランク付け部１４５と、出力部１４７と、を備える。
第１スコアリング部１４１は、検索クエリに対応する関連ページ群について、関連ページの夫々を、ページコンテンツの検索クエリとの関連度に基づいてスコアリングし、関連ページの夫々に、第１スコアとして、内容得点を与えるように構成される。
【００５２】
第２スコアリング部１４３は、検索クエリとは独立して動作し、クローラ１１０により収集されたウェブページの夫々に、第２スコアとして、ウェブページ間の接続関係に基づく重要得点を与えるように構成される。
【００５３】
第２スコアは、ウェブページ間の接続関係から重要度が高いと推定されるウェブページほど大きな値を示すように算出され、各ウェブページに付与される。具体的には、多くのリンクが集まるウェブページほど、高い重要得点を持つウェブページからリンクされるウェブページほど、他のウェブページへのリンクの少ないウェブページからのリンクを持つウェブページほど大きな値を示すように算出され、各ウェブページに付与される。
【００５４】
ランク付け部１４５は、第１スコアリング部１４１が関連ページの夫々に対して算出した第１スコアと、第２スコアリング部１４３が関連ページの夫々に対して算出した第２スコアとに基づき、関連ページの夫々のページランクを算出するように構成される。
【００５５】
簡単な例によれば、関連ページの夫々のページランクは、第１スコアと第２スコアとの重み付け和に対応する。例えば、第１スコアＸ１、第２スコアＸ２、及び、０から１の間の値を採る重み付け係数αを用いて、各関連ページのページランクＹは、式Ｙ＝α・Ｘ１＋（１−α）・Ｘ２に従って算出され得る。各関連ページのページランクは、検索クエリに基づく内容得点とウェブページ間の接続関係に基づく重要得点とを成分に含む全体得点として理解されてもよい。
【００５６】
出力部１４７は、検索クエリに対応する関連ページ群を、ランク付け部１４５により算出された各関連ページのページランクに基づき、ページランクが高い関連ページから順に並べるように、リストアップしたページリストを、検索結果リストとして検索クエリ送信元のユーザ端末５に送信する。
【００５７】
続いて、第２スコアリング部１４３が実行する処理の詳細と共に、本実施形態に特徴的な第２スコアの算出技術の詳細を、以下に説明する。
従来では、ウェブページ間の接続関係に基づくウェブページのスコアリングを、各成分が値１，０の二値（実数）で表される隣接行列を用いて行っていた。これに対し、本実施形態では、値１，０，＋ｉ，−ｉの四値（複素数）で表されるエルミート隣接行列Ｈを用いて、ウェブページのスコアリングを行う。ここでｉは、虚数単位を表す。
【００５８】
エルミート隣接行列Ｈは、弱連結関係にあるウェブページ群毎に生成される。周知のように弱連結関係にあるノード群から構成されるネットワークは、ノード間のリンクの接続方向を無視したときに、そのネットワークに属するノード群の任意の一つのノードから、残りのノードにリンクをたどって到達可能なネットワークに対応する。同様に、弱連結関係にあるウェブページ群から構成される文書ネットワークは、その文書ネットワークに属するウェブページの任意の一つが、リンクの接続方向を無視したときに、残りのウェブページと少なくとも間接的な接続関係を有するウェブページ群から構成される。
【００５９】
第２スコアリング部１４３は、図４に示すフローチャートを定期的に実行することにより、インデックス記憶部２２０が記憶する最新のインデックスデータに基づき、弱連結関係にあるウェブページ群毎に、対応するウェブページ群に属する各ウェブページの第２スコアを算出する。
【００６０】
図４に示す処理を開始すると、第２スコアリング部１４３は、全ウェブページの中から、一つ以上の連結文書ネットワークを抽出する（Ｓ１１０）。具体的には、インデックス記憶部２２０が記憶するインデックスデータを参照することにより、全ウェブページの中で、弱連結関係を有するウェブページ群のそれぞれを、一つの連結文書ネットワークとして抽出する（Ｓ１１０）。一つの連結文書ネットワークは、弱連結関係を有するウェブページ群から構成される。
【００６１】
図５Ａ、図６Ａ、図７Ａ、図８Ａ、図９Ａ、図１０Ａ、及び図１１は、連結文書ネットワークの例を示す。図５Ａ、図６Ａ、図７Ａ、図８Ａ、図９Ａ、図１０Ａ、及び図１１における一つの円は、一つのノード、換言すれば一つのウェブページに対応する。
【００６２】
同図における矢印は、矢印の始点に対応するウェブページに、矢印の終点に対応するウェブページへのリンク（ハイパーリンク）が形成されていることを示す。即ち、矢印の始点に対応するウェブページから矢印の終点に対応するウェブページにリンクを介して移動可能であることを意味する。両方向の矢印は、矢印に接続された二つのウェブページにおいて互いへのリンクが形成され、双方向に移動可能であることを意味する。
【００６３】
同図に示される文書ネットワーク内の各ウェブページは、その図から明らかに、矢印の方向を無視したとき、他のウェブページと少なくとも間接的に接続されている。以下では、これらのウェブページを、図において円内に示される数字ｋを用いて、第ｋウェブページと表現する。
【００６４】
Ｓ１１０に続くＳ１２０において、第２スコアリング部１４３は、連結文書ネットワークの夫々について、始点ページＳＰを設定する。具体的には、第２スコアリング部１４３は、連結文書ネットワークの夫々について、図１２に示す処理を実行して、始点ページＳＰを設定する。
【００６５】
図１２に示す処理を開始すると、第２スコアリング部１４３は、対応する連結文書ネットワークにおいて、最長経路に該当する一つ以上の経路を探索する（Ｓ１２１）。第２スコアリング部１４３は、対応する連結文書ネットワーク内のノード（ウェブページ）のそれぞれに関して、対応するノードから、矢印に従って隣接するノードに、同じノードに複数回移動することができないという規則を守って、移動先がなくなるまで移動したときの、その経路を構成するノード数を算出し、ノード数が最大の経路を、最長経路として探索することができる。
【００６６】
その後、第２スコアリング部１４３は、最長経路として複数の経路が見つかったか否かを判断する（Ｓ１２２）。最長経路として一つの経路のみが見つかった場合（Ｓ１２２でＮｏ）、第２スコアリング部１４３は、最長経路として見つかった経路の始点に対応するウェブページを、始点ページＳＰに設定する（Ｓ１２３）。
【００６７】
例えば、図５Ａ、図６Ａ、図７Ａ、図８Ａ、図９Ａに示す連結文書ネットワークに対しては、最長経路の始点に位置する入次数がゼロの第１ウェブページが始点ページＳＰに設定される。
【００６８】
第２スコアリング部１４３は、最長経路として複数の経路が見つかった場合（Ｓ１２２でＹｅｓ）、上記最長経路に該当する複数の経路の中で、始点からの出次数が最小又は最大である特定経路に該当する一つ以上の経路を探索する（Ｓ１２４）。特定経路を「始点からの出次数が最小の経路」及び「始点からの出次数が最大の経路」のいずれに定義するかは、システムの設計者が任意に決定することができる。図１０Ａ、及び、図１１に例示される連結文書ネットワークには、最長経路に該当する経路が複数存在する。
【００６９】
ここで、用語「出次数」及び「入次数」について説明する。一つの連結文書ネットワーク内で、一つのウェブページからＵ１個のウェブページへのリンクが存在するとき、一つのウェブページの出次数はＵ１である。一方、一つのウェブページにＵ２個のウェブページからのリンクが存在するとき、一つのウェブページの入次数はＵ２である。
【００７０】
Ｓ１２４での探索を終えると、第２スコアリング部１４３は、上記特定経路に該当する複数の経路が見つかったか否かを判断する（Ｓ１２５）。複数の経路が見つかったと判断すると（Ｓ１２５でＹｅｓ）、第２スコアリング部１４３は、特定経路に該当する複数の経路の上流に、複数の経路の始点に接続する入次数がゼロの一つのダミーページを配置して、このダミーページを始点ページＳＰに設定する（Ｓ１２６）。
【００７１】
ここで言うダミーページは、仮想的なウェブページのことを意味する。図１０Ｂによれば、第１ウェブページ及び第３ウェブページの上流に、第１ウェブページ及び第３ウェブページへのリンクを有する一つのダミーページが、始点ページＳＰとして設けられる。
【００７２】
一方、第２スコアリング部１４３は、上記特定経路として一つの経路のみが見つかったと判断すると（Ｓ１２５でＮｏ）、この経路の始点に位置するウェブページを始点ページＳＰに設定する（Ｓ１２７）。図１１に示す連結文書ネットワークは、最長経路として、第１、第２、第３、第４、第５、第６、第７、及び第１０ウェブページを始点とする複数の経路を含む。始点の出次数が最小である経路は、第１０ウェブページを始点とする経路である。従って、上記特定経路が始点からの出次数が最小の経路に定義されている場合、第１０ウェブページが始点ページＳＰに設定される。
【００７３】
このようにして、第２スコアリング部１４３は、連結文書ネットワークの夫々に関し、そのネットワーク構造に応じた始点ページＳＰを設定する（Ｓ１２０）。その後、第２スコアリング部１４３は、連結文書ネットワークの夫々に対応する仮想文書ネットワークを設定する（Ｓ１３０）。一つの仮想文書ネットワークは、一つの連結文書ネットワークに対応する。
【００７４】
Ｓ１３０において、第２スコアリング部１４３は、連結文書ネットワークの夫々に関して、対応する連結文書ネットワーク内に存在する出次数がゼロのウェブページを終点ページＥＰとして探索し、見つかった終点ページＥＰに、入次数１及び出次数０のダミーページＤＰを付加して、仮想文書ネットワークを設定する。
【００７５】
終点ページＥＰに接続されるダミーページＤＰは、対応する仮想文書ネットワークにおいて、終点ページＥＰからダミーページＤＰへのリンクが存在し、ダミーページＤＰから他のウェブページへのリンクが存在しない仮想的なウェブページである。
【００７６】
対応する連結文書ネットワーク内に複数の終点ページＥＰが見つかった場合、第２スコアリング部１４３は、終点ページＥＰのそれぞれに、ダミーページＤＰを付加して、仮想文書ネットワークを設定する。
【００７７】
図５Ｂ、図６Ｂ、図７Ｂ、図８Ｂ、図９Ｂ、図１０Ｂ、及び図１１には、図５Ａ、図６Ａ、図７Ａ、図８Ａ、図９Ａ、図１０Ａ、及び図１１に示される連結文書ネットワークのそれぞれに対応する仮想文書ネットワークを示す。図１１に示す連結文書ネットワークに対応する仮想文書ネットワークは、連結文書ネットワークに出次数がゼロのウェブページが存在しないため、連結文書ネットワークと同じである。
【００７８】
ここで終点ページＥＰにダミーページＤＰを付加することによって仮想文書ネットワークを設定するのは、次の理由からである。
仮にダミーページＤＰなしの連結文書ネットワークに基づいて、エルミート隣接行列Ｈを用いたスコアリングを行う場合には、出次数がゼロの終点ページＥＰのスコアが、終点ページＥＰへのリンクを有する隣接ページのスコアに対して下がる傾向を示す。しかしながら、ウェブページ間の接続方向の終端に対応する終点ページＥＰは、重要度の高いウェブページということができ、高いスコアが算出されるべきウェブページである。
【００７９】
このため、本実施形態では、ダミーページＤＰを導入して、終点ページＥＰに高いスコア（第２スコア）が算出されるように工夫している。
Ｓ１３０において、仮想文書ネットワークを設定し終えると、第２スコアリング部１４３は、仮想文書ネットワークが有する要素数Ｎの最大値ｍａｘ{Ｎ}を特定する（Ｓ１４０）。一つの仮想文書ネットワークの要素数Ｎは、その仮想文書ネットワークに属するウェブページとダミーページとの合計数に対応する。例えば、図６Ｂに示す仮想文書ネットワークの要素数Ｎは、１４である（Ｎ＝１４）。例えば、図８Ｂに示す仮想文書ネットワークの要素数Ｎは、７である（Ｎ＝７）。最大値ｍａｘ{Ｎ}は、全ての仮想文書ネットワークの内、要素数Ｎが最大の仮想文書ネットワークの当該要素数Ｎに対応する。
【００８０】
続くＳ１５０において、第２スコアリング部１４３は、仮想文書ネットワークの一つを処理対象に選択する。ここで選択した仮想文書ネットワークを、以下では、選択文書ネットワークと表現する。
【００８１】
その後、第２スコアリング部１４３は、選択文書ネットワークのエルミート隣接行列Ｈに基づき、選択文書ネットワークを構成するウェブページの夫々に対する第２スコアを算出する（Ｓ１６０〜Ｓ２２０）。以下では、選択文書ネットワークを構成するウェブページの一つを、ウェブページＤ［ｍ］と表現する。変数ｍは、値１からＮまでの整数値を採り（１≦ｍ≦Ｎ）、ウェブページＤ［ｍ］は、選択文書ネットワークにおける第ｍウェブページに対応する。Ｎは、選択文書ネットワークの要素数Ｎである。
【００８２】
Ｓ１６０において、第２スコアリング部１４３は、選択文書ネットワーク内のウェブページの接続関係を、値１，０，＋ｉ，−ｉで表すエルミート隣接行列Ｈを生成する。エルミート隣接行列Ｈは、選択文書ネットワークの要素数Ｎに対応したＮ行Ｎ列（ＮｘＮ）の行列であり、各成分が、値１，０，＋ｉ，−ｉのいずれかの値を採る行列である。以下における表現「成分ｈ（ｐ，ｑ）」は、エルミート隣接行列Ｈにおける第ｐ行第ｑ列の成分を示す。
【００８３】
第２スコアリング部１４３は、ウェブページＤ［ｐ］からウェブページＤ［ｑ］へのリンクが存在し且つウェブページＤ［ｑ］からウェブページＤ［ｐ］へのリンクが存在するとき、対応する成分ｈ（ｐ，ｑ）を、値１に設定する。
【００８４】
ウェブページＤ［ｐ］からウェブページＤ［ｑ］へのリンク及びウェブページＤ［ｑ］からウェブページＤ［ｐ］へのリンクのいずれもが存在しないとき、対応する成分ｈ（ｐ，ｑ）を、値０に設定する。従って、第２スコアリング部１４３は、エルミート隣接行列Ｈの対角成分ｈ（ｐ，ｐ）を値ゼロに設定する。
【００８５】
第２スコアリング部１４３は更に、ウェブページＤ［ｐ］からウェブページＤ［ｑ］へのリンクが存在するがウェブページＤ［ｑ］からウェブページＤ［ｐ］へのリンクが存在しないとき、対応する成分ｈ（ｐ，ｑ）を、値＋ｉを設定する。ウェブページＤ［ｐ］からウェブページＤ［ｑ］へのリンクが存在しないがウェブページＤ［ｑ］からウェブページＤ［ｐ］へのリンクが存在するとき、対応する成分ｈ（ｐ，ｑ）を、値−ｉを設定する。
【００８６】
このようにして、第２スコアリング部１４３は、各成分ｈ（ｐ，ｑ）の値を設定し、エルミート隣接行列Ｈを生成する。
【００８７】
【数３】
0006502592.tif 000004
上述の規則に従って各成分ｈ（ｐ，ｑ）の値を設定した場合、第ｐ行第ｑ列の成分ｈ（ｐ，ｑ）と対角成分を挟んで対称的な位置関係にある第ｑ行第ｐ列の成分ｈ（ｑ，ｐ）は、成分ｈ（ｐ，ｑ）の複素共役に設定される。従って、エルミート隣接行列Ｈは、エルミート行列である。
【００８８】
その後、第２スコアリング部１４３は、このエルミート隣接行列Ｈを変形した特殊エルミート隣接行列Ｈ１を生成する（Ｓ１７０）。変形は、特殊エルミート隣接行列Ｈ１の固有ベクトルＶの各成分を、複素ベクトルとして複素平面に配置したときに、成分の全てがπ／２ラジアンの角度範囲に収まるように行われる。
【００８９】
変形に際して、第２スコアリング部１４３は、Ｓ１４０で算出した最大値ｍａｘ｛Ｎ｝に基づいて次式に従う第一補正量Ｃ１及び第二補正量Ｃ２を算出する。
【００９０】
【数４】
0006502592.tif 000005
ここで、パラメータｎは、Ｓ１４０で特定された最大値ｍａｘ｛Ｎ｝以上の自然数である。
【００９１】
上記成分の全てをπ／２ラジアンの角度範囲に収めるためには、ｎ＝ｍａｘ｛Ｎ｝に設定すれば十分である。パラメータｎの値を、最大値ｍａｘ｛Ｎ｝より大きくするほど、成分の全ては、π／２ラジアンの角度範囲より小さい角度範囲内に収まる。成分の全てをπ／２ラジアンの角度範囲に収めることの目的は、成分の全てが複素平面上の一つの象限内に収まるようにするためである。この目的が達成できる範囲で、パラメータｎは任意の値に定められ得る。しかしながら、第２スコアの良好な算出のために、パラメータｎは、目的が達成可能な範囲で、なるべく小さい値に設定されるのが好ましい。
【００９２】
第二補正量Ｃ２は、角度範囲の調整に寄与し、第一補正量Ｃ１は、第二補正量Ｃ２によって行列成分の絶対値が変化するのを回避するのに役立つ。
第２スコアリング部１４３は、第一補正量Ｃ１及び第二補正量Ｃ２の算出後、エルミート隣接行列Ｈにおける値＋ｉの成分を、値Ｃ１（Ｃ２＋ｉ）に置換し、値−ｉを示す成分を値Ｃ１（Ｃ２−ｉ）に置換する。第２スコアリング部１４３は更に、当該置換後のエルミート隣接行列Ｈにおける各行の成分の値Ｃ１（Ｃ２＋ｉ）を、同じ行において値Ｃ１（Ｃ２＋ｉ）を示す成分の数及び値１を示す成分の数の和Ｗで除算した値｛Ｃ１（Ｃ２＋ｉ）／Ｗ｝に変更する。第２スコアリング部１４３は更に、値｛Ｃ１（Ｃ２＋ｉ）／Ｗ｝に変更された成分と対角成分を挟んで対称的な位置関係にある成分の値Ｃ１（Ｃ２−ｉ）を、値｛Ｃ１（Ｃ２＋ｉ）／Ｗ｝の複素共役｛Ｃ１（Ｃ２−ｉ）／Ｗ｝に変更する。このような置換及び変更によって定義されるエルミート行列を、特殊エルミート隣接行列Ｈ１として生成する。
【００９３】
エルミート隣接行列Ｈから特殊エルミート隣接行列Ｈ１への変形手順の具体例を図１３に示す。例えば、第ｐ１行における合計Ｎ個の成分ｈ（ｐ１，１），ｈ（ｐ１，２），…，ｈ（ｐ１，Ｎ）の内、値＋ｉを採る成分及び値１を採る成分が合計Ｗ１個である場合には、エルミート隣接行列Ｈにおける第ｐ１行の値＋ｉを示す各成分を、値{Ｃ１（Ｃ２＋ｉ）／Ｗ１}に変更する。第ｐ２行における合計Ｎ個の成分ｈ（ｐ２，１），ｈ（ｐ２，２），…，ｈ（ｐ２，Ｎ）の内、値＋ｉを採る成分及び値１を採る成分が合計Ｗ２個である場合には、エルミート隣接行列Ｈにおける第ｐ２行の値＋ｉを示す各成分を、値{Ｃ１（Ｃ２＋ｉ）／Ｗ２}に変更する。
【００９４】
更に、値−ｉを示す成分の値を、対角成分を挟んで対称的な位置関係にある成分の複素共役に変更する。例えば、値｛Ｃ１（Ｃ２＋ｉ）／Ｗ１｝を示す成分ｈ（ｐ１，ｑ１）と対角成分を挟んで対称的な位置関係にある成分ｈ（ｑ１，ｐ１）の値を、{Ｃ１（Ｃ２−ｉ）／Ｗ１}に変更する。同様に、値｛Ｃ１（Ｃ２＋ｉ）／Ｗ２｝を示す成分ｈ（ｐ２，ｑ２）と対角成分を挟んで対称的な位置関係にある成分ｈ（ｑ２，ｐ２）の値を、{Ｃ１（Ｃ２−ｉ）／Ｗ２}に変更する。
【００９５】
続くＳ１８０において、第２スコアリング部１４３は、Ｓ１７０で生成した特殊エルミート隣接行列Ｈ１の固有値及び固有ベクトルを算出する。特殊エルミート隣接行列Ｈ１がＮｘＮの行列であることから、固有ベクトルは、Ｎ個の成分を含むＮ次元ベクトルである。以下では、絶対値最大の固有値に対応する固有ベクトルＶの各成分をＶ［ｍ］を用いて表す。変数ｍは値１から値Ｎまでの整数値を採る。即ち、固有ベクトルは、Ｖ＝｛Ｖ［１］，Ｖ［２］，…，Ｖ［Ｎ］｝である。固有ベクトルＶの各成分Ｖ［ｍ］（１≦ｍ≦Ｎ）は、選択文書ネットワークを構成する各ウェブページＤ［ｍ］（１≦ｍ≦Ｎ）に対応する。
【００９６】
続くＳ１９０において、第２スコアリング部１４３は、特殊エルミート隣接行列Ｈ１の絶対値最大の固有値に対応する固有ベクトルＶの各成分Ｖ［ｍ］（１≦ｍ≦Ｎ）を、選択文書ネットワークの始点ページＳＰに対応する成分Ｅで除算する。ここで、始点ページＳＰは、選択文書ネットワークに関してＳ１２０で設定された始点ページＳＰに対応する。始点ページＳＰが第ｓウェブページＤ［ｓ］であるとき、成分Ｅは、固有ベクトルＶの第ｓ成分Ｖ［ｓ］に対応する（Ｅ＝Ｖ［ｓ］）。
【００９７】
固有ベクトルＶの各成分Ｖ［ｍ］（１≦ｍ≦Ｎ）を成分Ｅで除算すると、始点ページＳＰに対応する固有ベクトルＶの成分は、値１に変換される。以下では、除算後の固有ベクトルＶを、固有ベクトルＶ１と表現する。固有ベクトルＶ１は、Ｖ１＝｛Ｖ［１］／Ｅ，Ｖ［２］／Ｅ，…，Ｖ［ｓ］／Ｅ＝１，…，Ｖ［Ｎ］／Ｅ｝である。除算により、始点ページＳＰに対応する固有ベクトルＶ１の成分は、複素平面において、実軸上に配置される。
【００９８】
Ｓ１９０での処理を終えると、第２スコアリング部１４３は、除算後の固有ベクトルＶ１の各成分Ｖ［ｍ］／Ｅ（１≦ｍ≦Ｎ）を回転変換する（Ｓ２００）。Ｓ２００において、第２スコアリング部１４３は、図１４に示す処理を実行することができる。
【００９９】
図１４に示す処理を開始すると、第２スコアリング部１４３は、固有ベクトルＶ１の各成分を複素平面に配置したときに、複素平面において実軸より第一象限側に位置する成分が存在するか否かを判断する（Ｓ２０１）。ここでいう実軸より第一象限側に位置する成分には、実軸に位置する成分は含まれない。
【０１００】
多くの場合、実軸に位置する始点ページＳＰの成分よりも第一象限側に位置する成分は、存在しない。しかしながら、対応する仮想文書ネットワークに環式構造が存在する場合には、始点ページＳＰよりも第一象限側に位置する成分が存在する場合がある。Ｓ２０１の処理は、低い確率で発生するこのような成分の存在を判別するために行われる。
【０１０１】
実軸より第一象限側に位置する成分が存在しないと判断すると（Ｓ２０１でＮｏ）、第２スコアリング部１４３は、固有ベクトルＶ１の各成分を、第４象限側に所定角度θ１だけ回転させるように回転変換する（Ｓ２０３）。このようにして、第２スコアリング部１４３は、始点ページＳＰに対応する成分を、複素平面上において、実軸から角度θ１だけ離れた特定位置に配置するように、固有ベクトルＶ１の各成分を回転変換する。
【０１０２】
図１５Ａは、回転変換前の各成分の複素平面上の配置を例示する。図１５Ａにおいて黒丸及び白丸の夫々は、固有ベクトルＶ１の成分の一つに対応し、黒丸は、特に、始点ページＳＰの成分に対応する。図１５Ｂは、回転変換後の各成分の複素平面上の配置を例示する。
【０１０３】
角度θ１は、例えば、π／１８０ラジアンである。角度θ１は、固有ベクトルＶ１の各成分が、全て第４象限に収まる範囲内で、始点ページＳＰに対応する成分が実軸から離れるような角度であれば十分であり、π／１８０ラジアンに限定されない。始点ページＳＰに対応する成分を実軸から離す理由については、後述する。
【０１０４】
実軸より第一象限側に位置する成分が存在すると判断すると（Ｓ２０１でＹｅｓ）、第２スコアリング部１４３は、Ｓ２０５に移行する。Ｓ２０５において、第２スコアリング部１４３は、実軸から第１象限側に最も離れた成分の実軸からの角度θ２を特定する。その後、第２スコアリング部１４３は、固有ベクトルＶ１の各成分を、第４象限側に角度θ１＋θ２だけ回転させるように回転変換する（Ｓ２０７）。
【０１０５】
角度θ１は、Ｓ２０３の処理に関して上述した通りである。角度θ１＋θ２の回転変換により、第２スコアリング部１４３は、固有ベクトルＶ１の各成分を、始点ページＳＰより第１象限側に位置する成分を含めて、全て複素平面の第４象限に収める。以下では、回転変換後の固有ベクトルＶ１のことを、固有ベクトルＶｃ＝｛Ｖｃ［１］，Ｖｃ［２］，…，Ｖｃ［ｓ］，…，Ｖｃ［Ｎ］｝と表現する。
【０１０６】
Ｓ２００において、このように回転変換を行うと、第２スコアリング部１４３は、固有ベクトルＶｃの各成分Ｖｃ［ｍ］（１≦ｍ≦Ｎ）を、複素ベクトルとして複素平面に配置したときの各成分Ｖｃ［ｍ］（１≦ｍ≦Ｎ）の実軸からの距離に対応する値Ｚ［ｍ］＝Ｌ［ｍ］・θ［ｍ］（１≦ｍ≦Ｎ）を算出する（Ｓ２１０）。図１５Ｂには、値Ｚ［ｍ］を概念的に示す。
【０１０７】
ここで値Ｌ［ｍ］は、成分Ｖｃ［ｍ］の絶対値｜Ｖｃ［ｍ］｜に対応する。値θ［ｍ］は、成分Ｖｃ［ｍ］と実軸との間の角度、換言すれば、成分Ｖｃ［ｍ］の実軸からの時計回り方向の角度に対応する。
【０１０８】
その後、第２スコアリング部１４３は、各ウェブページＤ［ｍ］（１≦ｍ≦Ｎ）の第２スコアを、値Ｚ［ｍ］に基づいて算出し、算出した第２スコアを記憶部２０に記憶する（Ｓ２２０）。
【０１０９】
ウェブページＤ［ｍ］に対応する第２スコアＸ２は、Ｘ２＝Ｚ［ｍ］−ｍｉｎ｛Ｚ［ｍ］｝に従って算出される。ｍｉｎ｛Ｚ［ｍ］｝は、Ｚ［ｍ］（１≦ｍ≦Ｎ）の一群のうちの最小値を意味する。即ち、最も小さいＺ［ｍ］を示すウェブページＤ［ｍ］の第２スコアが値ゼロとなるように、各ウェブページＤ［ｍ］（１≦ｍ≦Ｎ）の第２スコアＸ２として、Ｚ［ｍ］から最小値ｍｉｎ｛Ｚ［ｍ］｝を減算した値を算出する。但し、ダミーページＤＰに対応する成分についての第２スコアＸ２を算出する必要はない。実際には存在しないダミーページＤＰは、第２スコアＸ２を算出しても意味がないためである。
【０１１０】
このようにして、第２スコアリング部１４３は、第２スコアとして、固有ベクトルＶの成分が実軸から離れているウェブページほど、及び、成分の絶対値が大きいウェブページほど、高いスコアを算出する。
【０１１１】
多くの場合には、始点ページＳＰに対応する成分が実軸に最も近い特定位置にあり、始点ページＳＰに対応する第２スコアは、ゼロである。従って、本実施形態によれば、始点ページＳＰから離れているウェブページほど高い第２スコアが算出される。具体的には、複素平面において、固有ベクトルＶの成分が始点ページＳＰに対応する固有ベクトルの成分から大きく回転しているウェブページほど、及び、成分の絶対値が大きいウェブページほど、高い第２スコアが算出される。上述したＳ２０１の処理で肯定判断してＳ２０５の処理に移行したケースにおいても、角度θ２は大きくないため、多くのウェブページの第２スコアは、始点ページＳＰから離れているほど高い値として算出される。
【０１１２】
特殊エルミート隣接行列Ｈ１に基づけば、第２補正量Ｃ２のおかげで、固有ベクトルＶｃの各成分が、複素平面上を１回転することなく、かならず複素平面のπ／２ラジアンの角度範囲内に、具体的には第４象限内に配置される。また、回転変換により、始点ページＳＰに対応する成分は、複素平面上の特定位置（角度θ１を有する位置）に配置される。そして、第２スコアが、特定位置と一定の対応関係にある実軸を基準とした値Ｚ［ｍ］＝Ｌ［ｍ］・θ［ｍ］（１≦ｍ≦Ｎ）に従って算出される。このようにして、始点ページＳＰに対応する成分との位置関係に応じた、各ウェブページＤ［ｍ］の値Ｚ［ｍ］及び第２スコアが算出される。
【０１１３】
従って、本実施形態によれば、始点ページＳＰを基準としたウェブページ間の接続関係に従う重要得点（第２スコア）を、容易かつ適切に算出可能である。
本実施形態において、始点ページＳＰに対応する成分を実軸からずらして配置するように回転変換を行っているのは、Ｚ［ｍ］が式Ｚ［ｍ］＝Ｌ［ｍ］・θ［ｍ］に従って算出されるためである。この式によれば、実軸上に配置される成分は、θ［ｍ］＝０であることから、全てＺ［ｍ］＝０となり、値Ｌ［ｍ］が第２スコアに反映されない。各成分Ｖｃ［ｍ］のいずれもが実軸から離れるように回転変換することは、θ［ｍ］が非ゼロになるように固有ベクトルＶ１の各成分を回転変換することに対応する。この回転変換により、第２スコアを、特には双方向リンクを有するウェブページの第２スコアを、Ｌ［ｍ］に基づき良好に算出することができる。
【０１１４】
本実施形態によれば、ダミーページＤＰのおかげで、終点ページＥＰに対応する第２スコアが高くなるように、各ウェブページの第２スコアを算出可能であることも有意義である。従って、本実施形態によれば、選択文書ネットワークにおけるウェブページの接続関係に応じた適切なスコアを、第２スコアとして算出することができる。
【０１１５】
第２スコアリング部１４３は、Ｓ２２０で選択文書ネットワークにおける各ウェブページＤ［ｍ］の第２スコアを算出すると、Ｓ２３０に移行し、全ての仮想文書ネットワークについてＳ１６０〜Ｓ２２０の処理を実行して、ウェブページに対する第２スコアを算出したか否かを判断する。そして、未処理の仮想文書ネットワークが存在する場合には（Ｓ２３０でＮｏ）、処理をＳ１５０に戻して、未処理の仮想文書ネットワークの一つを、新たな処理対象の仮想文書ネットワークに選択する。即ち、選択文書ネットワークを変更する。その後、新たな選択文書ネットワークについて、Ｓ１６０〜Ｓ２２０の処理を実行し、選択文書ネットワークにおける各ウェブページの第２スコアを算出及び記憶する。
【０１１６】
そして、全ての仮想文書ネットワークについて、Ｓ１６０〜Ｓ２２０の処理を実行すると、第２スコアリング部１４３は、図４に示す処理を終了する。第２スコアリング部１４３は、この処理によって記憶部２０内に記憶した各ウェブページの第２スコアを、必要に応じ、記憶部２０から読み出すことができる。例えば、第２スコアリング部１４３は、検索クエリが発生したときに、検索クエリに対応する関連ページのそれぞれの第２スコアを記憶部２０から読み出して、ランク付け部１４５に提供することができる。
【０１１７】
本実施形態によれば、図４に示す処理によって、各ウェブページに対応する成分を第４象限に配置し、更には始点ページＳＰに対応する成分を特定位置に配置して、値Ｚ［ｍ」を算出するので、異なる連結文書ネットワークのウェブページに対して、共通の尺度で、第２スコアを算出することができる。
【０１１８】
従って、ランク付け部１４５は、異なる連結文書ネットワークのウェブページが関連ページ群に含まれる場合であっても、第２スコアに基づいて、各関連ページの全体得点、即ち、ページランクを適切に算出することができる。
【０１１９】
即ち、ランク付け部１４５は、各ウェブページの第２スコアに基づき、検索結果リストにおけるウェブページの配列を、第１スコア及び第２スコアに基づくページランクＹという形態で、第２スコアが高い程、対応するウェブページが上位に配置されるように決定することができる。
【０１２０】
出力部１４７は、このようなウェブページ間の接続関係に基づいた適切な検索結果リストを、ユーザ端末５に提供することができる。具体的には、高い第２スコアが算出される、始点ページから離れたリンクの集まるウェブページほど、上位に位置する検索結果リストを、ユーザ端末５に提供することができる。従って、本実施形態によれば、従来よりも適切に接続関係に従う複数のウェブページのスコアリング／ランク付けを行って、適切な検索結果をユーザ端末５に提供することができる。
【０１２１】
ここで、図５Ａ、図７Ａ、図８Ａ、図９Ａ、及び図１１に示す連結文書ネットワークのそれぞれに関して、本実施形態の技術を適用して算出される第２スコアに基づく、ウェブページのランク付けを説明する。図５Ａに示される連結文書ネットワークのウェブページ群は、従来手法によれば、「５」「４」「３」「２」「１」の順序でランク付けされる。ここで示される数字は、対応する図において円内に記載される数字に対応する。即ち、「５」は、図５Ａにおける「５」と記載されたノードに対応するウェブページを指し示す。ここでの数字の配列は、「５」のウェブページの第２スコアが最も高く、従ってランクが最も高く、「１」のウェブページの第２スコアが最も小さく、従ってランクが最も低いことを意味する。
【０１２２】
本実施形態によれば、図５Ａの連結文書ネットワーク内のウェブページ群は、従来手法と同様に、「５」「４」「３」「２」「１」の順序でランク付けされる。
図７Ａの連結文書ネットワーク内のウェブページ群は、従来手法によれば、「４」「３」「７」「８」「６」「２」「５」「１」の順序でランク付けされ、本実施形態によれば、「４」「３」「２」「５」「６」「７」「８」「１」の順序でランク付けされる。
【０１２３】
図８Ａの連結文書ネットワーク内のウェブページ群は、従来手法によれば、「５」「４」「２」「３」「１」の順序でランク付けされ、本実施形態によれば、「５」「４」「３」「２」「１」の順序でランク付けされる。
【０１２４】
図９Ａの連結文書ネットワーク内のウェブページ群は、従来手法によれば、「４」「３」「２」「１」の順序でランク付けされ、本実施形態によれば、従来手法と同様に、「４」「３」「２」「１」の順序でランク付けされる。
【０１２５】
図１１の連結文書ネットワーク内のウェブページ群は、従来手法によれば、「４」「６」「７」「１」「２」「８」「９」「３」「５」「１０」の順序でランク付けされ、本実施形態によれば、「４」「６」「７」「２」「１」「３」「５」「８」「９」「１０」の順序でランク付けされる。
【０１２６】
このことから理解できるように、特殊エルミート隣接行列Ｈ１によれば、第２スコアは、始点ページＳＰから離れたリンクの集まるウェブページほど大きな値を示すように算出される。第２スコアは、多くのリンクが集まるウェブページほど、大きな値を示すように算出される。第２スコアは、高い重要得点を持つウェブページからリンクされるウェブページほど大きな値を示すように算出される。第２スコアは、他のウェブページへのリンクの少ないウェブページからのリンクを持つウェブページほど大きな値を示すように算出される。
【０１２７】
第２スコアは更に、他のウェブページへのリンクが多いウェブページほど、大きな値を示すように算出される。第２スコアは更に、高い重要得点を持つウェブページへのリンクを有するウェブページほど大きな値を示すように算出される。この点が特に、特殊エルミート隣接行列Ｈ１の特徴である。従って、本実施形態によれば、ウェブページの良好なスコアリングを実現することができる。
【０１２８】
続いて、上述した情報処理システム１の変形例について説明する。以下に説明する変形例は、第２スコアリング部１４３が実行する処理の一部が、上述した情報処理システム１と異なるだけである。変形例のその他の構成は、上述した情報処理システム１と同一である。従って、以下では、変形例に特徴的な第２スコアリング部１４３の処理の内容を選択的に説明する。
【０１２９】
［第一変形例］
第２スコアリング部１４３は、Ｓ２１０（図４参照）において、角度θ［ｍ］として、実軸からの角度ではなく、始点ページＳＰに対応する成分からの角度を用いて、値Ｚ［ｍ］＝Ｌ［ｍ］・θ［ｍ］を算出する。第一変形例によれば、角度θ［ｍ］の算出が、上述した実施形態より複雑になるが、多くの場合、適切に第２スコアを算出することができる。
【０１３０】
［第二変形例］
第２スコアリング部１４３は、Ｓ２００の処理を実行することなく、Ｓ１９０で固有ベクトルＶ１を生成した後、Ｓ２１０の処理を実行する。Ｓ２１０において、第２スコアリング部１４３は、上述した固有ベクトルＶｃに代えて、固有ベクトルＶ１を用いて、値Ｚ［ｍ］を算出する。即ち、値Ｚ［ｍ］を、固有ベクトルＶ１の成分Ｖ［ｍ］／Ｅに対応する値Ｌ［ｍ］及びθ［ｍ］に基づいて、式Ｚ［ｍ］＝Ｌ［ｍ］・θ［ｍ］に従って算出する。この例は、双方向リンクが存在しない連結文書ネットワークであって、始点ページＳＰよりも第１象限側に配置されるウェブページが現れない連結文書ネットワークに適用することができる。
【０１３１】
あるいは、第二変形例のＳ２１０では、式Ｚ［ｍ］＝Ｌ［ｍ］・（θ［ｍ］＋β）に従って、値Ｚ［ｍ］が算出されてもよい。βは、θ［ｍ］＋βがπ／２ラジアンを超えないように、π／１８０ラジアンなどの微小な値に定められ得る。この例によれば、連結文書ネットワークに双方向リンクが存在する場合にも、値Ｌ［ｍ］の情報を含む非ゼロの値Ｚ［ｍ］を算出することができ、適切な第２スコアを算出することができる。
【０１３２】
［第三変形例］
第２スコアリング部１４３は、Ｓ１７０において、上述の特殊エルミート隣接行列Ｈ１に代えて、別の特殊エルミート隣接行列Ｈ２を生成する。Ｓ１８０では、この特殊エルミート隣接行列Ｈ２の固有値及び固有ベクトルを算出する（Ｓ１８０）。ここで算出された絶対値最大の固有値に対応する固有ベクトルＶを用いて、Ｓ１９０以降の処理を実行する。即ち、第三変形例の第２スコアリング部１４３は、特殊エルミート隣接行列Ｈ１に代えて、別の特殊エルミート隣接行列Ｈ２を用いて、上述した実施形態と同様の処理を実行する。
【０１３３】
図１６に示される特殊エルミート隣接行列Ｈ２は、図１３上段に示すエルミート隣接行列Ｈに対応する特殊エルミート隣接行列Ｈ２の例である。第２スコアリング部１４３は、Ｓ１７０において、エルミート隣接行列Ｈにおける値＋ｉの成分を、値Ｃ１（Ｃ２＋ｉ）に置換し、値−ｉを示す成分を値Ｃ１（Ｃ２−ｉ）に置換する。第２スコアリング部１４３は更に、次の処理Ａ及び処理Ｂを行う。
【０１３４】
（処理Ａ）
第２スコアリング部１４３は、置換後のエルミート隣接行列Ｈにおける各行の成分内の値Ｃ１（Ｃ２＋ｉ）を、同じ行において値Ｃ１（Ｃ２＋ｉ）及び値１を示す成分の数Ｗで除算した値｛Ｃ１（Ｃ２＋ｉ）／Ｗ｝に変更し、更に、値｛Ｃ１（Ｃ２＋ｉ）／Ｗ｝に変更された成分と対角成分を挟んで対称的な位置関係にある成分内の値Ｃ１（Ｃ２−ｉ）を、値｛Ｃ１（Ｃ２＋ｉ）／Ｗ｝の複素共役｛Ｃ１（Ｃ２−ｉ）／Ｗ｝に変更する。
【０１３５】
（処理Ｂ）
第２スコアリング部１４３は、置換後のエルミート隣接行列Ｈにおける各行の成分内の値Ｃ１（Ｃ２−ｉ）を、同じ行においてＣ１（Ｃ２−ｉ）及び値１を示す成分の数Ｚで乗算した値｛Ｃ１（Ｃ２−ｉ）Ｚ｝に変更し、更に、値｛Ｃ１（Ｃ２−ｉ）Ｚ｝に変更された成分と対角成分を挟んで対称的な位置関係にある成分内の値Ｃ１（Ｃ２＋ｉ）を、値｛Ｃ１（Ｃ２−ｉ）Ｚ｝の複素共役｛Ｃ１（Ｃ２＋ｉ）Ｚ｝に変更する。
【０１３６】
このような置換及び変更によって、特殊エルミート隣接行列Ｈ２は生成される。第２スコアリング部１４３は、処理Ａの実行後、処理Ｂを実行してもよいし、処理Ｂの実行後、処理Ａを実行してもよいし、処理Ａ及び処理Ｂを同時並行的に実行してもよい。いずれの態様で処理Ａ及び処理Ｂを実行しても、同じ特殊エルミート隣接行列Ｈ２が生成される。
【０１３７】
正しい理解のために、ここで、処理Ａの実行後、処理Ｂを実行する場合の処理手順について再度説明する。第２スコアリング部１４３は、置換後のエルミート隣接行列Ｈにおける各行の成分の値Ｃ１（Ｃ２＋ｉ）を、同じ行において値Ｃ１（Ｃ２＋ｉ）及び値１を示す成分の数Ｗで除算した値｛Ｃ１（Ｃ２＋ｉ）／Ｗ｝に変更し、更に、値｛Ｃ１（Ｃ２＋ｉ）／Ｗ｝に変更された成分と対角成分を挟んで対称的な位置関係にある成分の値Ｃ１（Ｃ２−ｉ）を、値｛Ｃ１（Ｃ２＋ｉ）／Ｗ｝の複素共役｛Ｃ１（Ｃ２−ｉ）／Ｗ｝に変更する。第２スコアリング部１４３は、上記変更後のエルミート隣接行列Ｈにおける各行の成分の値｛Ｃ１（Ｃ２−ｉ）／Ｗ｝を、上記変更前において同じ行でＣ１（Ｃ２−ｉ）及び値１を示していた成分の数Ｚで乗算した値｛Ｃ１（Ｃ２−ｉ）Ｚ／Ｗ｝に変更し、更に、値｛Ｃ１（Ｃ２−ｉ）Ｚ／Ｗ｝に変更された成分と対角成分を挟んで対称的な位置関係にある成分の値｛Ｃ１（Ｃ２＋ｉ）／Ｗ｝を、値｛Ｃ１（Ｃ２−ｉ）Ｚ／Ｗ｝の複素共役｛Ｃ１（Ｃ２＋ｉ）Ｚ／Ｗ｝に変更する。上記置換後の処理Ａによって、まず特殊エルミート隣接行列Ｈ１が生成され、その後の処理Ｂによって、本変形例の特殊エルミート隣接行列Ｈ２が生成される。
【０１３８】
図１６に示される特殊エルミート隣接行列Ｈ２における値Ｚ１は、第ｐ３行における成分ｈ（ｐ３，１），ｈ（ｐ３，２），…，ｈ（ｐ３，Ｎ）の内、値−ｉを採る成分及び値１を採る成分の数に対応する。値Ｚ２は、第ｐ４行における合計Ｎ個の成分ｈ（ｐ４，１），ｈ（ｐ４，２），…，ｈ（ｐ４，Ｎ）の内、値−ｉを採る成分及び値１を採る成分の数に対応する。第ｐ３行は、図１６において値｛Ｃ１（Ｃ２−ｉ）Ｚ１／Ｗ１｝が示される行と理解されてよい。第ｐ４行は、図１６において値｛Ｃ１（Ｃ２−ｉ）Ｚ２／Ｗ２｝が示される行と理解されてよい。
【０１３９】
第２スコアリング部１４３は、このように算出した特殊エルミート隣接行列Ｈ２を、特殊エルミート隣接行列Ｈ１に代えて用いて、Ｓ１８０−Ｓ２２０の処理を実行する。
図５Ａ、図７Ａ、図８Ａ、図９Ａ、及び図１１に示す連結文書ネットワークのそれぞれに関して、第三変形例を適用して算出される第２スコアに基づく、ウェブページのランク付けを、上述した実施形態での記述方式と同様の記述方式で説明する。
【０１４０】
第三変形例によれば、図５Ａの連結文書ネットワーク内のウェブページ群は、「５」「４」「３」「２」「１」の順序でランク付けされる。図７Ａの連結文書ネットワーク内のウェブページ群は、「３」「４」「２」「５」「６」「７」「８」「１」の順序でランク付けされる。
【０１４１】
図８Ａの連結文書ネットワーク内のウェブページ群は、「５」「４」「３」「２」「１」の順序でランク付けされる。図９Ａの連結文書ネットワーク内のウェブページ群は、本「４」「３」「１」「２」の順序でランク付けされる。図１１の連結文書ネットワーク内のウェブページ群は、「４」「６」「７」「２」「１」「３」「５」「８」「９」「１０」の順序でランク付けされる。
【０１４２】
特殊エルミート隣接行列Ｈ２は、第２スコアが、他のウェブページからのリンクが多いウェブページへのリンクを持つウェブページほど、大きな値を示すように算出される点で、特殊エルミート隣接行列Ｈ１とは異なる。この点が特に、特殊エルミート隣接行列Ｈ２の特徴である。
【０１４３】
特殊エルミート隣接行列Ｈ２は、その他の点で特殊エルミート隣接行列Ｈ１と同様の特徴を示すが、第２スコアが、高い重要得点を持つウェブページへのリンクを有するウェブページほど大きな値を示すように算出される特徴は、特殊エルミート隣接行列Ｈ１に特有である。第三変形例によっても、ウェブページの良好なスコアリングを実現することができる。
【０１４４】
［第四変形例］
第四変形例では、連結文書ネットワークが、入次数ゼロのウェブページ及び出次数ゼロのウェブページを含むことを前提とする。更に言えば、一つの始点ページＳＰから一つの終点ページＥＰへ複数の経路が存在する環式構造を有する連結文書ネットワーク、及び、相互リンクが存在する連結文書ネットワークを取り扱わない。これらを前提に、第２スコアリング部１４３は、図４に示す処理に代えて、図１７に示す処理を実行するように構成される。図１７に示す処理は、図４に示す処理と同じ部分も多い。従って、以下では、同じ部分に関しての説明を簡略化する。
【０１４５】
図１７に示す処理を開始すると、第２スコアリング部１４３は、Ｓ１１０と同様に、全ウェブページの中から、一つ以上の連結文書ネットワークを抽出する（Ｓ３１０）。その後、第２スコアリング部１４３は、連結文書ネットワークの夫々について、始点ページＳＰを設定する（Ｓ３２０）。連結文書ネットワークに含まれる入次数がゼロのウェブページが一つのみであるとき、対応する連結文書ネットワークの始点ページＳＰは、入次数がゼロのウェブページに設定される。対応する連結文書ネットワークに入次数がゼロのウェブページが複数含まれる場合、始点ページＳＰは、経路長に基づいて設定される。
【０１４６】
具体的に、第２スコアリング部１４３は、入次数がゼロのウェブページから出次数がゼロのウェブページまでのリンクの向きに従う経路のうち、経路長が最大の経路を探索する。第２スコアリング部１４３は、経路長が最大の経路において、入次数がゼロのウェブページを、始点ページＳＰに設定する。経路長が最大の経路が複数存在するとき、第２スコアリング部１４３は、図１０Ａ及び図１０Ｂに示すように、複数の経路の始点に接続する入次数ゼロのダミーページを配置して、このダミーページを始点ページＳＰに設定することができる。具体的に、第２スコアリング部１４３は、経路長が最大の経路が複数存在し、これら複数の経路の始点において出次数が最小（又は最大）の始点が複数存在するとき、第２スコアリング部１４３は、図１０Ａ及び図１０Ｂに示すように、複数の経路の始点に接続する入次数ゼロのダミーページを配置して、このダミーページを始点ページＳＰに設定することができる。第２スコアリング部１４３は、経路長が最大の経路が複数存在するが、これら複数の経路の始点において出次数が最小（又は最大）の始点が一つのみであるとき、その最小（又は最大）の出次数の始点を、始点ページＳＰに設定することができる。
【０１４７】
Ｓ３２０での処理を終えると、第２スコアリング部１４３は、Ｓ１３０の処理と同様に、連結文書ネットワークの夫々に関して、仮想文書ネットワークを設定する（Ｓ３３０）。即ち、対応する連結文書ネットワーク内に存在する出次数がゼロのウェブページを終点ページＥＰとして探索し、終点ページＥＰにダミーページＤＰを付加して、仮想文書ネットワークを設定する。
【０１４８】
その後、第２スコアリング部１４３は、Ｓ１４０と同様に、仮想文書ネットワークが有する要素数Ｎの最大値ｍａｘ{Ｎ}を特定する（Ｓ３４０）。続くＳ３５０において、第２スコアリング部１４３は、仮想文書ネットワークの一つを処理対象に選択する。
【０１４９】
続くＳ３６０において、第２スコアリング部１４３は、Ｓ１６０と同様に、選択文書ネットワークに対応するエルミート隣接行列Ｈを生成する。更に、第２スコアリング部１４３は、エルミート隣接行列Ｈの変形により、特殊エルミート隣接行列Ｈ３を生成する（Ｓ３７０）。変形に際して、第２スコアリング部１４３は、Ｓ３４０で算出した最大値ｍａｘ｛Ｎ｝に基づいて次式に従う補正量Ｃを算出する。
【０１５０】
【数５】
0006502592.tif 000006
上式におけるパラメータｎは、特殊エルミート隣接行列Ｈ３の固有ベクトルの各成分を、複素ベクトルとして複素平面に配置したときに、成分の全てがπ／２ラジアンの角度範囲に収まるように予め決定される。パラメータｎは、Ｓ３４０で特定された最大値ｍａｘ｛Ｎ｝以上の自然数で定められ得る。パラメータｎは、例えば、ｎ＝ｍａｘ｛Ｎ｝であってもよいし、ｎ＝２（ｍａｘ｛Ｎ｝−１）であってもよい。第四変形例の場合には、始点ページＳＰに対応する成分が複素平面において実軸上に配置されるので、理論上はｎ＝ｍａｘ｛Ｎ｝−１に設定しても成分の全てを複素空間の第４象限に収めることができる。
【０１５１】
第２スコアリング部１４３は、補正量Ｃの算出後、エルミート隣接行列Ｈにおける値＋ｉの成分を、値（Ｃ＋ｉ）に置換し、更に、当該置換後のエルミート隣接行列Ｈにおける各行の値（Ｃ＋ｉ）を示す成分を、同じ行において値（Ｃ＋ｉ）を示す成分の数Ｒで除算した値｛（Ｃ＋ｉ）／Ｒ｝に変更し、更に、値−ｉを示す成分の値を、対角成分を挟んで対称的な位置関係にある成分の複素共役｛（Ｃ−ｉ）／Ｒ｝に変更する。
【０１５２】
第２スコアリング部１４３は、このような置換及び変更によって定義されるエルミート行列を、特殊エルミート隣接行列Ｈ３として生成する。図１８に示される特殊エルミート隣接行列Ｈ３は、図１３上段に示すエルミート隣接行列Ｈに対応する特殊エルミート隣接行列Ｈ３の例である。
【０１５３】
エルミート隣接行列Ｈにおいて、第ｐ１行における合計Ｎ個の成分ｈ（ｐ１，１），ｈ（ｐ１，２），…，ｈ（ｐ１，Ｎ）の内、値＋ｉを採る成分がＲ１個である場合には、第ｐ１行の値＋ｉを示す各成分が、値{（Ｃ＋ｉ）／Ｒ１}に変更される。第ｐ２行における合計Ｎ個の成分ｈ（ｐ２，１），ｈ（ｐ２，２），…，ｈ（ｐ２，Ｎ）の内、値＋ｉを採る成分がＲ２個である場合には、エルミート隣接行列Ｈにおける第ｐ２行の値＋ｉを示す各成分が、値{（Ｃ＋ｉ）／Ｒ２}に変更される。
【０１５４】
更に値｛（Ｃ＋ｉ）／Ｒ１｝を示す成分ｈ（ｐ１，ｑ１）と対角成分を挟んで対称的な位置関係にある成分ｈ（ｑ１，ｐ１）の値が、{（Ｃ−ｉ）／Ｒ１}に変更される。同様に、値｛（Ｃ＋ｉ）／Ｒ２｝を示す成分ｈ（ｐ２，ｑ２）と対角成分を挟んで対称的な位置関係にある成分ｈ（ｑ２，ｐ２）の値が、{（Ｃ−ｉ）／Ｒ２}に変更される。このようにして特殊エルミート隣接行列Ｈ３は生成される。
【０１５５】
第四変形例によれば、双方向リンクが存在する連結文書ネットワークを取扱わない。このため、エルミート隣接行列Ｈには値１の成分が含まれない。このことから理解できるように、数Ｒは、上記実施形態の数Ｗに対応する。
【０１５６】
続くＳ３８０において、第２スコアリング部１４３は、Ｓ１８０の処理と同様に、Ｓ３７０で生成した特殊エルミート隣接行列Ｈ３の固有値及び固有ベクトルを算出する。続くＳ３９０において、第２スコアリング部１４３は、Ｓ１９０の処理と同様に、特殊エルミート隣接行列Ｈ３の絶対値最大の固有値に対応する固有ベクトルＶの各成分Ｖ［ｍ］（１≦ｍ≦Ｎ）を、選択文書ネットワークの始点ページＳＰに対応する成分Ｅで除算する。絶対値最大の固有値が正の固有値と負の固有値を含む場合、正の固有値に対応する固有ベクトルＶの各成分Ｖ［ｍ］（１≦ｍ≦Ｎ）を、選択文書ネットワークの始点ページＳＰに対応する成分Ｅで除算することができる。この除算により、始点ページＳＰに対応する固有ベクトルＶの成分は、複素平面において、実軸上に配置される。
【０１５７】
Ｓ４００において、第２スコアリング部１４３は、除算後の固有ベクトルＶ１の各成分Ｖ［ｍ］／Ｅ（１≦ｍ≦Ｎ）を複素ベクトルとして複素平面上に配置したときの、各成分Ｖ［ｍ］／Ｅ（１≦ｍ≦Ｎ）の始点ページＳＰに対応する成分（実軸）からの回転方向の距離に対応する値Ｚ［ｍ］＝Ｌ［ｍ］・θ［ｍ］（１≦ｍ≦Ｎ）を、対応するウェブページＤ［ｍ］（１≦ｍ≦Ｎ）の第２スコアＸ２＝Ｚ［ｍ］（１≦ｍ≦Ｎ）として算出する。ダミーページＤＰに対応する成分についての第２スコアＸ２の算出は不要である。そして、算出した第２スコアＸ２を記憶部２０に記憶する。
【０１５８】
第四変形例における値θ［ｍ］は、図１９に示すように、成分Ｖ［ｍ］／Ｅの実軸からの時計回り方向の角度に対応する。始点ページＳＰは、実軸上に配置される。このため、値θ［ｍ］は、始点ページＳＰに対応する成分を基準とした時計回り方向の角度ということもできる。即ち、値θ［ｍ］は、成分Ｖ［ｍ］／Ｅと始点ページＳＰに対応する成分Ｖ［ｓ］／Ｅとのなす角度に対応する。値Ｌ［ｍ］は、成分Ｖ［ｍ］／Ｅの絶対値｜Ｖ［ｍ］／Ｅ｜に対応する。図１９に示す白丸及び黒丸の意味は、図１５Ａに関連して説明した通りである。
【０１５９】
このようにして、第２スコアリング部１４３は、第２スコアとして、固有ベクトルＶの成分が始点ページＳＰから離れているウェブページほど高いスコアを、特殊エルミート隣接行列Ｈ３に基づき算出する。
【０１６０】
特殊エルミート隣接行列Ｈ３に基づけば、補正量Ｃのおかげで、固有ベクトルＶ１の各成分Ｖ［ｍ］／Ｅ（１≦ｍ≦Ｎ）が、複素平面上を１回転することなく、かならず複素平面の１象限内に配置される。特には、始点ページＳＰが複素平面上において値１に対応する実軸上に固定され、固有ベクトルＶ１の各成分Ｖ［ｍ］／Ｅは、第４象限に配置される。従って、第四変形例によれば、始点ページを基準としたウェブページ間の接続関係に従う重要得点（第２スコア）を、容易かつ適切に算出することができる。
【０１６１】
第２スコアリング部１４３は、Ｓ４００で選択文書ネットワークにおける各ウェブページの第２スコアを算出すると、Ｓ４１０に移行し、全ての仮想文書ネットワークについてＳ３６０〜Ｓ４００の処理を実行して、ウェブページに対する第２スコアを算出したか否かを判断する。
【０１６２】
第２スコアリング部１４３は、未処理の仮想文書ネットワークが存在すると判断した場合（Ｓ４１０でＮｏ）、処理をＳ３５０に戻して、未処理の仮想文書ネットワークの一つを、新たな処理対象の仮想文書ネットワークに選択する。その後、新たな選択文書ネットワークについて、Ｓ３６０〜Ｓ４００の処理を実行し、選択文書ネットワークにおける各ウェブページの第２スコアを算出及び記憶する。そして、全ての仮想文書ネットワークについて、Ｓ３６０〜Ｓ４００の処理を実行すると、図１７に示す処理を終了する。第四変形例によれば、第２スコアの算出にかかる計算量を抑えることができるという技術的利点がある。
【０１６３】
以上、変形例を含む本開示の例示的実施形態を説明したが、本開示の技術は、上述の通り、特殊エルミート隣接行列を用いることが特徴的である。エルミート隣接行列および特殊エルミート隣接行列を含むエルミート行列においては、固有値は必ず実数となることが数学的に証明されている。
【０１６４】
更に、エルミート隣接行列および特殊エルミート隣接行列は、文書（ウェブページ）間の接続関係が少なくとも弱連結であれば、概して絶対値最大の固有値について、絶対値最大の固有値が正の固有値のみでありその重複度が１であるか、絶対値最大の固有値が負の固有値のみでありその重複度が１であるか、もしくは、絶対値最大の固有値が正および負の固有値でありそれぞれの重複度が１であることが複数の例において実証されている。
【０１６５】
従って、絶対値最大の固有値が正および負の固有値である場合は正の固有値を採用するという単純な規則を指定することによって、絶対値最大の固有値に対応する固有ベクトルが一意であることを保証することができる。絶対値最大の固有値が正および負の固有値を含む場合、概して、負の固有値の固有ベクトルの各成分の複素数は、実部の正負の符号及び虚部の正負の符号のそれぞれを保持あるいは変更すると、正の固有値の固有ベクトルの対応する各成分と一致する。
【０１６６】
複素数の実部の符号の変更は、複素平面において複素数を虚軸に関して対称となる位置に移動させることに相当し、複素数の虚部の符号の変更は、複素平面において複素数を実軸に関して対称となる位置へと移動させることに相当する。つまり、絶対値最大の固有値が正および負の固有値を含む場合には、負の固有値の固有ベクトルの各成分の複素平面上の位置関係と、正の固有値の固有ベクトルの各成分の複素平面上の位置関係と、が実軸に関する対称関係及び虚軸に関する対称関係を通した対応関係を有する。そこで、絶対値最大の固有値が正および負の固有値である場合は、負の固有値を採用するという単純な規則を指定し、正の固有値を採用した場合と同じ結果を生じさせる操作を行うことも可能である。
【０１６７】
本開示によれば、弱連結を形成する文書ネットワークのそれぞれに対応する特殊エルミート隣接行列を、全ての文書ネットワークの中で最大の文書数を持つ文書ネットワークの文書数という共通項を用いて定義する。従って、各文書ネットワークにおいて各文書に付与されるスコアは、同じ文書ネットワークの中だけなく、異なる文書ネットワーク間で有意義に比較／ランク付け可能である。
【０１６８】
文書間の接続関係を０，１で二値表現する従来の隣接行列において、絶対値が最大の固有値の内で実数である固有値の重複度が１であることを数学的に保証し、対応する固有ベクトルが一意であることをすることを確保するためには、１つの方法として、各文書から他の各文書への実際の接続関係に加え、全文書から全文書への仮想的な接続関係を措定し、一定の確率で前者が用いられ、残りの一定の確率で後者が用いられると想定しなければならない。そのため、文書間の比較／ランクにおいては、前者の確率を変化させると各文書のランクが変化してしまい一貫性がないこと、前者の確率を何にすれば適切な比較／ランクが得られるかは主に経験的に探る他なかったこと、前者の確率の設定が恣意的なランク付けに用いられる余地があったこと、等の難点があった。前者の確率はダンピング・ファクターと呼ばれ、代表的な数値は０．８５とされているが、実際の接続関係が０．８５という確率でしか用いられないという前提は現実からかけ離れている。さらに、後者の確率について、全文書から全文書への仮想的な接続関係において、ある文書から各文書への仮想的な接続関係が用いられる確率は全て等しいという前提も現実から大きく乖離している。
【０１６９】
本開示の特殊エルミート隣接行列は、全文書から全文書への仮想的な接続関係を措定する必要がない。そして、本開示の特殊エルミート隣接行列は、文書間の接続関係に基づく各文書のスコアリング／ランク付けについて、従来の隣接行列による方法においてダンピング・ファクターを０．８５とした場合と同じ傾向が高い結果を与える。
【０１７０】
更に、本開示によれば、これとは異なる結果の実現が望ましい場合には、ダンピング・ファクターを変化させ必要な値を経験的に探るのではなく、スコアを変化させる必要のある文書に出次数ダミーまたは入次数ダミーを必要な数だけ加えることによって、より体系的、系統的、理論的であるという点で適切なスコアリング／ランク付けを実現することができる。
【０１７１】
更に、スコアを変化させる必要のある文書について、必要なスコアの変化に対応した長さ（即ち、向きを守った連続する矢印の数）の経路を構成する複数のダミー文書とダミー文書の間の複数の接続関係を、スコアを変化させる必要のある文書から出発するように加える、もしくは、到着するように加えることによっても、より体系的、系統的、理論的であるという点で適切なスコアリング／ランク付けを実現することができる。
【０１７２】
加えて、本開示の特殊エルミート隣接行列は、スコアを変化させる必要がある文書と他の一つの文書との接続関係を表す二箇所の成分をエルミート行列の性質を保持しつつ必要な変化に応じて変更することによっても、より体系的、系統的、理論的であるという点においてより適切にスコアリング／ランク付けを実現することができる。
【０１７３】
特殊エルミート隣接行列Ｈ２は、特殊エルミート隣接行列Ｈ１を体系的、系統的、理論的に発展させたものである。以上で述べた特殊エルミート隣接行列Ｈ１の利点は、特殊エルミート隣接行列Ｈ２についても成り立つ。この意味で、本開示は、従来技術に対する有意義な技術的改良をもたらす。
【０１７４】
本開示は、上記実施形態及び変形例に限定されることなく、種々の態様を採ることができることは言うまでもない。例えば、第２スコアリング部１４３は、Ｓ１９０，Ｓ３９０において、固有ベクトルＶの各成分Ｖ［ｍ］を、始点ページＳＰの成分Ｖ［ｓ］で除算することにより、複素平面上において始点ページＳＰを、実軸上の値１の点に配置した。
【０１７５】
しかしながら、Ｓ１９０，Ｓ３９０において、固有ベクトルＶの各成分Ｖ［ｍ］は、−Ｖ［ｓ］で除算されてもよいし、＋Ｖ［ｓ］・ｉで除算されてもよいし、−Ｖ［ｓ］・ｉで除算されてもよいし、その所定倍（実数倍）で除算されてもよい。例えば、固有ベクトルＶの各成分Ｖ［ｍ］を、−Ｖ［ｓ］で除算した場合、始点ページＳＰは、複素平面において実軸上の−１の地点に配置され、除算後の固有ベクトルＶ１の各成分は、複素平面において第２象限に配置される。この場合にも、適切に第２スコアを算出することが可能である。
【０１７６】
この他、第２スコアリング部１４３は、図１２に示すＳ１２４において、最長経路に該当する複数の経路の中で、始点からの出次数が最大である特定経路に該当する一つ以上の経路を探索してもよい。本開示は、ウェブ文書に限定されないリンク/引用関係を持つ文書のスコアリングに適用されてもよい。
【０１７７】
上記実施形態における１つの構成要素が有する機能は、複数の構成要素に分散して設けられてもよい。複数の構成要素が有する機能は、１つの構成要素に統合されてもよい。上記実施形態の構成の一部は、省略されてもよい。請求の範囲に記載の文言から特定される技術思想に含まれるあらゆる態様が本開示の実施形態である。
【０１７８】
最後に用語間の対応関係について説明する。第２スコアリング部１４３が実行するＳ１１０，Ｓ３１０の処理は、特定部により実現される処理の一例に対応する。Ｓ１２０，Ｓ３２０の処理は、判別部により実現される処理の一例に対応する。Ｓ１３０，Ｓ３３０の処理は、設定部により実現される処理の一例に対応する。Ｓ１６０，Ｓ１７０，Ｓ３６０，Ｓ３７０の処理は、定義部により実現される処理の一例に対応する。Ｓ１８０，Ｓ３８０の処理は、固有ベクトル算出部により実現される処理の一例に対応する。Ｓ１９０〜Ｓ２２０，Ｓ３９０〜Ｓ４００の処理は、スコア算出部により実現される処理の一例に対応する。ランク付け部１４５及び出力部１４７が実行する処理は、配列決定部により実現される処理の一例に対応する。
【要約】
本開示のシステムは、１つ以上の文書ネットワークに対応する１つ以上の仮想文書ネットワークのそれぞれについて、特殊エルミート隣接行列の固有ベクトルを算出する。特殊エルミート隣接行列は、対応する仮想文書ネットワークを構成する文書Ｄ［ｍ］（１≦ｍ≦Ｎ）間の接続関係に基づくＮ行Ｎ列のエルミート隣接行列の変形である。算出される固有ベクトルは、絶対値最大の固有値に対応する。固有ベクトルは、文書Ｄ［ｍ］（１≦ｍ≦Ｎ）のそれぞれに対応する成分を有する。システムは、始点文書に対応する成分を基準に、固有ベクトルの各成分を複素平面上に配置したときの、文書Ｄ［ｍ］（１≦ｍ≦Ｎ）間の複素平面上の位置関係に基づき、文書Ｄ［ｍ］（１≦ｍ≦Ｎ）のそれぞれのスコアを算出する。【図１】
0006502592.tif 000010
【図２】
0006502592.tif 000011
【図３】
0006502592.tif 000012
【図４】
0006502592.tif 000013
【図５】
0006502592.tif 000014
【図６】
0006502592.tif 000015
【図７】
0006502592.tif 000016
【図８】
0006502592.tif 000017
【図９】
0006502592.tif 000018
【図１０】
0006502592.tif 000019
【図１１】
0006502592.tif 000020
【図１２】
0006502592.tif 000021
【図１３】
0006502592.tif 000022
【図１４】
0006502592.tif 000023
【図１５】
0006502592.tif 000024
【図１６】
0006502592.tif 000025
【図１７】
0006502592.tif 000026
【図１８】
0006502592.tif 000027
【図１９】
0006502592.tif 000028