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