関連ウェブページ発見装置、関連ウェブページ発見方法および関連ウェブページ発見プログラム
【課題】、特性の類似した関連ウェブページ群を容易に発見することができる関連ウェブページ発見装置を提供する。
【解決手段】インターネット50からウェブページを収集してウェブページ情報DB102に登録するウェブページ収集手段101と、前記DB102からハイパーリンク情報を抽出してハイパーリンク情報DB104に登録する事で、ネットワークを隣接行列形式で表現するネットワーク抽出手段103と、前記ネットワークを基に、ノード毎に該ノードとその周辺ノードとのエッジの接続状態に基づいた特徴量を算出し、当該特徴量をウェブページ特徴量DB106に登録するウェブページ特徴量算出手段105と、各ページの特徴量を基に、処理対象のページと関連するウェブページを算出し、関連ウェブページ群を出力として提示する関連ウェブページ算出手段107と、を有する。
【解決手段】インターネット50からウェブページを収集してウェブページ情報DB102に登録するウェブページ収集手段101と、前記DB102からハイパーリンク情報を抽出してハイパーリンク情報DB104に登録する事で、ネットワークを隣接行列形式で表現するネットワーク抽出手段103と、前記ネットワークを基に、ノード毎に該ノードとその周辺ノードとのエッジの接続状態に基づいた特徴量を算出し、当該特徴量をウェブページ特徴量DB106に登録するウェブページ特徴量算出手段105と、各ページの特徴量を基に、処理対象のページと関連するウェブページを算出し、関連ウェブページ群を出力として提示する関連ウェブページ算出手段107と、を有する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、あるウェブページと関連するウェブページを発見する方法及び装置に係り、特に、特性が類似しているウェブページを関連ページとして発見する関連ウェブページ発見装置、方法、プログラムに関する。
【0002】
ここで、特性が類似しているとは、例えば、ウェブページの注目度やそのウェブページが議論の構造における発端なのか、何らかの情報を受けての補足なのかといった役割のような、いわば当該ウェブページの属性的な要素が類似していることを指す。また、上記の特性の例のほかにも、例えば、そのウェブページがスパムと呼ばれる、検索エンジンにおける出力順位を不正に高めようという意図の下に作られたページであるかどうかに基づいた性質や、ショッピングサイト等への誘導を主目的として作られているページであるというような性質があげられる。
【背景技術】
【0003】
現在ではインターネット上のウェブページやウェブサイトの数は膨大なものとなり、ユーザーが所望の情報を取得するための負担は非常に大きなものとなった。
【0004】
そこで、ユーザーの情報取得を支援する様々な方法が提案されてきた。中でも、あるウェブページやウェブサイトに関連する情報が欲しいといった場合のニーズに答える方法に関しては、ウェブページ中のハイパーリンクによって形成されるネットワークの解析を基にした手法が提案されてきた。
【0005】
例えば、あるウェブページに対してハイパーリンクを張っているウェブページ群を抽出し、そのウェブページ群の多くがハイパーリンクを張っている当該ページと異なるウェブページを、当該ウェブページの関連ページとして提示する方法(特許文献1参照)がある(背景技術1)。
【0006】
また、ウェブページ間のハイパーリンクによる接続情報を隣接行列で表した上で、同一のページにリンクを張っている、もしくは同一のページからリンクを張られているという情報に基づいて、ウェブページのクラスタリングを行い、同一のクラスターに存在するページ群を関連ページ群として提示するという、従来からよく用いられてきた手法(背景技術2)がある。
【0007】
ここで、上記の手法をさらに高度化し、あるページの特徴量として、隣接行列から、当該ページが近傍のページと構成するサブネットワーク構造中での位置及びどのページとそのサブネットワーク構造を構成するかの情報を求め(非特許文献1参照)、より高精度なクラスタリングを行い、関連するウェブページを提示するという方法も考えられる(背景技術3)。
【0008】
ここで、背景技術3については、サブネットワーク構造を考慮する際にどのページと当該構造を構成するかを考慮しているため、結果的に背景技術2と同様に、クラスタリングを行う際の特徴量はページ間の接続情報を考慮したものとなっている。
【特許文献1】特開2002−304393号公報
【非特許文献1】高田寛喜、山田武士、上田修功、「ノードの機能特性に基づくクラスタリング」、ネットワーク生態学2008シンポジウム予稿集、pp.120−124、2008.
【発明の開示】
【発明が解決しようとする課題】
【0009】
上記背景技術1をはじめとする、あるページにハイパーリンクを張っているページ群を利用する手法では、当該ページ群は関連するウェブページをまとめたリンク集の機能を持っているという仮定に基づいている。したがって、ユーザーが所望した特性に基づく関連ページが得られるかどうかは、当該の特性を考慮したリンク集が背後に存在するかどうかに依存しており、必ずしも所望の関連ページが得られるとは限らないといった課題があった。
【0010】
上記背景技術2および背景技術3においては、ページ間の接続情報を考慮することで、接続情報が類似しているページは内容的に関連性が近いという仮定に基づいている。
【0011】
一方で、内容ではなく、例えば、同じような手法によって作成されたスパムページを発見したいといったような、特性が類似しているページを発見する場合には、直接接続関係がなくとも特性が類似していれば、関連ページとしてまとめられるべきである。このように、内容的な関連性に重きが置かれる結果、接続先を考慮した特徴量を用いた場合には、提示可能なページが接続関係のあるページ群のみに限定されるという課題があった。
【0012】
本発明は上記課題を解決するものであり、その目的は、特性の類似した関連ウェブページ群を容易に発見することができる関連ウェブページ発見装置、関連ウェブページ発見方法および関連ウェブページ発見プログラムを提供することにある。
【課題を解決するための手段】
【0013】
本発明では、ウェブページの特性は、当該ページと特定数の近傍ページとによって構成されるサブネットワーク中での当該ページの配置に基づいて算出された特徴量によって、よく表現されるという仮定に基づくことで、特性の類似した関連ウェブページの発見を実現した。
【0014】
請求項1に記載の関連ウェブページ発見装置は、特定のウェブページと関連するページを発見する装置において、インターネットからウェブページを自動的に収集し、ウェブページ情報データベースに登録するウェブページ収集手段と、前記ウェブページ情報データベースを参照し、登録されている各ページから、リンク元とリンク先に関するハイパーリンク情報を抽出し、該情報をハイパーリンク情報データベースに登録する事で、ウェブページをノード、ハイパーリンクをエッジとしたネットワークを隣接行列形式で表現するネットワーク抽出手段と、前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、ノード毎に該ノードとその周辺ノードとのエッジの接続状態に基づいた特徴量を算出し、当該特徴量をウェブページ特徴量データベースに登録するウェブページ特徴量算出手段と、前記ウェブページ特徴量データベースを参照し、各ページの特徴量を基に、処理対象のページと関連するウェブページを算出し、関連ウェブページ群を出力として提示する関連ウェブページ算出手段と、を有することを特徴としている。
【0015】
また請求項2に記載の関連ウェブページ発見装置は、請求項1において、前記ウェブページ特徴量算出手段は、前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、各ノードに対してその周辺ノードと形成するサブネットワーク中での構造を考慮した特徴量を算出し、当該特徴量をウェブページ特徴量データベースに登録することを特徴としている。
【0016】
また請求項3に記載の関連ウェブページ発見装置は、請求項1又は2において、前記ウェブページ特徴量算出手段は、前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、各ノードに対してあらかじめ定められた数の周辺ノードと形成するサブネットワーク構造中での当該ノードの配置に基づいてウェブページの特徴量を算出し、当該特徴量をウェブページ特徴量データベースに登録することを特徴としている。
【0017】
また請求項4に記載の関連ウェブページ発見装置は、請求項1ないし3のいずれか1項において、前記ウェブページ特徴量算出手段は、前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、各ノードに対してあらかじめ定められた数の周辺ノードと形成するサブネットワーク構造中での当該ノードの配置を考慮し、かつ、当該ノードの配置が一致する同形状のサブネットワーク構造が存在する場合には、そのサブネットワーク構造を形成するノードの違いを区別しないで算出した、該ウェブページの特徴量をウェブページ特徴量データベースに登録する、ことを特徴としている。
【0018】
また請求項5に記載の関連ウェブページ発見装置は、請求項1ないし4のいずれか1項において、前記関連ウェブページ算出手段は、前記ウェブページ特徴量データベースを参照し、処理対象のページの特徴量と各ページの特徴量を基に、ユークリッド距離を算出し、距離が小さいページ群を関連ウェブページ群として出力する、ことを特徴としている。
【0019】
また、請求項6に記載の関連ウェブページ発見方法は、特定のウェブページと関連するページを発見する方法において、ウェブページ収集手段が、インターネットからウェブページを自動的に収集し、ウェブページ情報データベースに登録するウェブページ収集ステップと、ネットワーク抽出手段が、前記ウェブページ情報データベースを参照し、登録されている各ページから、リンク元とリンク先に関するハイパーリンク情報を抽出し、該情報をハイパーリンク情報データベースに登録する事で、ウェブページをノード、ハイパーリンクをエッジとしたネットワークを隣接行列形式で表現するネットワーク抽出ステップと、ウェブページ特徴量算出手段が、前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、ノード毎に該ノードとその周辺ノードとのエッジの接続状態に基づいた特徴量を算出し、当該特徴量をウェブページ特徴量データベースに登録するウェブページ特徴量算出ステップと、関連ウェブページ算出手段が、前記ウェブページ特徴量データベースを参照し、各ページの特徴量を基に、処理対象のページと関連するウェブページを算出し、関連ウェブページ群を出力として提示する関連ウェブページ算出ステップと、を有することを特徴としている。
【0020】
また請求項7に記載の関連ウェブページ発見方法は、請求項6において、前記ウェブページ特徴量算出ステップは、前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、各ノードに対してその周辺ノードと形成するサブネットワーク中での構造を考慮した特徴量を算出し、当該特徴量をウェブページ特徴量データベースに登録することを特徴としている。
【0021】
また請求項8に記載の関連ウェブページ発見方法は、請求項6又は7において、前記ウェブページ特徴量算出ステップは、前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、各ノードに対してあらかじめ定められた数の周辺ノードと形成するサブネットワーク構造中での当該ノードの配置に基づいてウェブページの特徴量を算出し、当該特徴量をウェブページ特徴量データベースに登録することを特徴としている。
【0022】
また請求項9に記載の関連ウェブページ発見方法は、請求項6ないし8のいずれか1項において、前記ウェブページ特徴量算出ステップは、前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、各ノードに対してあらかじめ定められた数の周辺ノードと形成するサブネットワーク構造中での当該ノードの配置を考慮し、かつ、当該ノードの配置が一致する同形状のサブネットワーク構造が存在する場合には、そのサブネットワーク構造を形成するノードの違いを区別しないで算出した、該ウェブページの特徴量をウェブページ特徴量データベースに登録する、ことを特徴としている。
【0023】
また、請求項10に記載の関連ウェブページ発見プログラムは、コンピュータを請求項1ないし5のいずれか1項に記載の各手段として機能させる関連ウェブページ発見プログラムである。
【発明の効果】
【0024】
(1)請求項1〜10に記載の発明によれば、ユーザーが特性の類似した関連ウェブページ群を容易に発見する事が可能となる。
(2)請求項2〜4および請求項7〜9に記載の発明によれば、サブネットワーク中での構造(局所構造)を考慮した特徴量を算出しているので、ウェブページの特性を反映した特徴量を得ることができる。このため例えばスパムであれば、そのノードのランキングを不正に向上させるための構造が浮かび上がるなど、そのノードのネットワーク中での機能や特性、ひいては表に現われてこない意図を読み取ることができる。
【発明を実施するための最良の形態】
【0025】
以下、図面を参照しながら本発明の実施の形態を説明するが、本発明は下記の実施形態例に限定されるものではない。
【0026】
図1は本発明の実施形態の一例である関連ウェブページ発見装置の構成を示す図である。本実施形態の関連ウェブページ発見装置100は、所定のプログラムに基づいて動作する一般的なコンピュータ装置からなり、インターネット50からウェブページを収集し、その結果をウェブページ情報DB(データベース)102に登録するウェブページ収集手段101と、ウェブページ情報DB102からページ毎にハイパーリンクを抽出し、リンク元およびリンク先の情報などをハイパーリンク情報DB(データベース)104に登録するネットワーク抽出手段103と、ハイパーリンク情報DB104を利用して、各ウェブページが周辺ページと形成するサブネットワーク中での配置に基づいた局所構造を考慮した特徴量を算出し、ウェブページ特徴量DB(データベース)106に登録するウェブページ特徴量算出手段105と、指定されたURLに対応するウェブページと関連するウェブページ群を算出して、当該関連ウェブページ群のURLを出力する関連ウェブページ算出手段107とから構成されている。
【0027】
本実施形態の関連ウェブページ発見装置の処理の流れについては、大きく分けて2つの異なる流れによって構成される。ひとつは、図2によって示される、ウェブページ間のハイパーリンクに基づくネットワークを構築するために、ウェブページを自動的に収集しハイパーリンク情報を収集するための処理の流れであり、もうひとつは図3によって示される、入力されたウェブページの関連ウェブページを算出し、関連ウェブページ群を出力として提示するための処理の流れである。
【0028】
まず、図2のネットワーク構築のための処理の流れについては、ウェブページ収集手段101が、ステップS1において、ウェブページ情報DB102中のステータスを参照し、まだ未収集のウェブページを特定及び収集し、当該ウェブページのHTMLをウェブページ情報DB102に登録する。また、当該ウェブページのHTML中にウェブページ情報DB102に登録されていないウェブページへのハイパーリンクが含まれている場合にはその情報もウェブページ情報DB102に登録する。次に、ネットワーク抽出手段103が、ステップS2において、ウェブページ情報DB102に直前に登録されたウェブページに関して、ハイパーリンクを抽出し、その結果としてリンク先及びリンク元の情報をハイパーリンク情報DB104に登録する。以降、ウェブページ情報DB102の中にステータスが未収集のページがなくなるまで、もしくは、明示的に収集完了と指定されるまでウェブページの収集を繰り返す(ステップS3,S1,S2,S3)。
【0029】
次に、図3の関連ウェブページ群を算出するための処理の流れについては、ウェブページ特徴量算出手段105が、ステップS11において、ハイパーリンク情報DB104によって表されるネットワークの規模の変化および前回ウェブページの特徴量を算出してから経過した時間に基づいて、ウェブページの特徴量を算出するかどうかを判断する。
【0030】
ウェブページの特徴量を算出する場合には、ステップS12において、ハイパーリンク情報DB104を利用し、ページ毎に局所構造を考慮したウェブページ特徴量を算出し、ウェブページ特徴量DB106に結果を登録する。
【0031】
以降、関連ウェブページ算出手段107が、ステップS13,S14において、処理対象のウェブページがなくなるまで、当該ページ(指定されたURLに対応するウェブページ)をユーザー等からの入力として受け取り、前記ウェブページ特徴量DB106を参照しながら、当該ウェブページと関連するウェブページ群をユークリッド距離に基づいて算出し続ける。
【0032】
以下、前記図2、図3によって示された処理の手順を基に、各手段の詳細な説明を行う。
【0033】
ウェブページ収集手段101は、一般的な検索エンジンにおけるクローラに相当し、インターネットから自動的にウェブページを収集し、収集結果及び収集の状況に関する情報はウェブページ情報DB102に登録される。
【0034】
ここで、ウェブページ情報DB102は図4に示すように、ウェブページID,URL,Status,HTML等をウェブページごとに関連付けを行った形でデータとして保持している。ここで、ウェブページIDはウェブページごとにユニークに与えられる識別子である。また、Statusは、現在の収集状況を表す。alreadyは既に収集済である事を表す。yetは、まだ収集を試みていない事を表す。最後に、errorは収集を試みた際にエラーによって収集できなかった事を示す。また、例えば、HTMLの収集に成功した時間をTimeとするような形で、様々な付加情報を加えた上で関連付けを行い、データを保持することもできる。
【0035】
ここで、ウェブページの中には日々更新されるようなページが存在する事を鑑みると、Timeの情報を利用する事で、一度収集済みのページであっても一定期間ごとに再度HTMLを取得することで、情報の更新への対応が可能である。
【0036】
また、収集結果のHTML中に、ウェブページ情報DB102に登録されていないURLへのリンクが存在する場合には、ウェブページ情報DB102にそのURLに対応する新たなIDを付与し、Statusをyetとした上でURLを登録する。
【0037】
次に、ネットワーク抽出手段103は、前記ウェブページ収集手段101によって、収集およびウェブページ情報DB102に登録されたウェブページのHTMLを解析して、ハイパーリンクを抽出し、リンク元とリンク先の情報をハイパーリンク情報DB104に登録する事で、ウェブページをノード、ハイパーリンクをエッジとしたネットワークを例えば図5に示す隣接行列形式で表現可能にする。
【0038】
ここで、ハイパーリンク情報DB104は図5に示すように、ハイパーリンクID,FromURL,FromSite,ToURL,ToSite等をハイパーリンクごとに関連付けを行った形でデータを保持している。ハイパーリンクIDは、ハイパーリンク毎にユニークに与えられる識別子である。FromURLはリンク元URLであり、FromSiteはリンク元URLから得られたリンク元サイトでのURLである。ToURL,ToSiteについてはそれぞれリンク先のURL、リンク先サイトのURLに対応する。
【0039】
本DB104に、ウェブページ単位のURLのみではなく、サイト単位のURLも記録しておく事によって、次のウェブページ特徴量算出手段105において、サイト単位でリンクをまとめ、ウェブページのネットワークではなく、ウェブサイトのネットワークを構築した上で特徴量を算出する事が可能となり、結果として本発明を関連ウェブサイト発見装置としても利用する事ができるようになる。
【0040】
本DB104においても、ウェブページ情報DB102と同様にTime等の付加的な情報を加えて関連付けを行う事で、前記ウェブページ情報DB102と同様に、例えば、Timeであればウェブページの更新への対応が可能となる。
【0041】
続いて、ウェブページ特徴量算出手段105では、前記ハイパーリンク情報DB104を参照し、前記隣接行列形式で表現されたネットワーク(例えば図5)を基に、ノード(ウェブページ)毎に該ノードとその周辺ノードとのエッジ(ハイパーリンク)の接続状態に基づいた特徴量を算出し、当該特徴量をウェブページ特徴量DB106に登録する(請求項1、6の発明の実施形態)。
【0042】
また、請求項2,7の発明の実施形態において、ウェブページ特徴量算出手段105は、前記ハイパーリンク情報DB104を参照し、前記隣接行列形式で表現されたネットワーク(例えば図5)を基に、各ノード(ウェブページ)に対してその周辺ノードと形成するサブネットワーク中での構造を考慮した特徴量を算出し、当該特徴量をウェブページ特徴量DB106に登録する。
【0043】
また、請求項3,8の発明の実施形態において、ウェブページ特徴量算出手段105は、前記ハイパーリンク情報DB104を参照し、前記隣接行列形式で表現されたネットワーク(例えば図5)を基に、各ノード(ウェブページ)に対してあらかじめ定められた数の周辺ノードと形成するサブネットワーク構造中での当該ノードの配置に基づいてウェブページの特徴量を算出し、当該特徴量をウェブページ特徴量DB106に登録する。
【0044】
すなわち、ウェブページの特性は当該ウェブページと周辺ページとで形成するサブネットワーク中での当該ウェブページの配置によってよく現されるという仮説に基づき、ハイパーリンク情報DB104を参照し、各ウェブページとその接続情報を基に、局所構造を考慮した特徴量を算出した上で、当該特徴量をウェブページ特徴量DB106に登録する。
【0045】
より具体的には、ウェブページやブログサイトなどインターネット内に構築されているネットワークは、例えばランキングを不正操作しようとするスパム、アフィリエイト収入目当ての広告サイトへの誘導、周囲にたくさんのフォロワーを形成する注目度の高いブロガー(アルファブロガー)など、複数の人の様々な意図によってその巨大な構造を形成していると考えられる。したがって、ネットワーク全体に着目すると個々の意図は薄れてしまうが、注目ノードの周辺で形成されている局所構造に着目すると、例えば、スパムであれば、そのノードのランキングを不正に向上させるための構造が浮かび上がるなど、そのノードのネットワーク中での機能や特性、ひいては表に現れてこない意図を読み取る事ができるのではないかと考えられる。ここで、ウェブページによって構成されるネットワークおいては、ノードはウェブページ、エッジはハイパーリンクの事を指す。
【0046】
局所構造を考慮した特徴量を算出する処理の詳細な流れについては図6に示され、まずウェブページ特徴量算出手段105が、ハイパーリンク情報DB104によって表されるウェブページのネットワーク構造の中からあらかじめ指定されたノード数k,例えばk=3〜6程度、のサブネットワークをすべて列挙する(ステップS21)。ここで、k=3の場合には、とりうるサブネットワークの構造は図7に示すように計13パターンあり、各パターン中でのノードの位置について対称性を考慮すると、ノードの機能は計30種類に分類される。したがって、k=3の場合、ウェブページiの特徴量、つまり特徴ベクトルはウェブページiがその周辺のウェブページと形成する3ノードサブネットワーク構造中で果たしている各機能の頻度を要素として持った30次元のベクトルとなり、以下の式(1)で表される。
【0047】
Mi=(m1,m2,m3,...,m30)…(1)
ここで、m1,m2の添え字1,2は、それぞれ図7中における機能1,2に対応している。各ウェブページの特徴ベクトルの算出(式(1)の算出)が終わったら、その結果をウェブページ特徴量DB106に登録する(ステップS22)。
【0048】
本発明における、局所構造を考慮した特徴量においては、ウェブページの特性は必ずしも人が容易に把握できるものばかりではないが、中には特定の機能が表すウェブページの定性的な特性を想像できるものもある。
【0049】
例えば、機能1および3はそれぞれ出次数・入次数を良く表すと考えられる。もちろん、他の2ノードとの間およびそれらのノード間にエッジが存在する場合には異なったパターンを形成するが、その出次数・入次数をnとすると、複雑なサブネットワーク構造は形成されにくいことを考慮すると、特徴ベクトル中でのm1,m2の頻度は、nC2程度(CはCombinatioの頭文字)になると考えられ、出次数・入次数nが大きいほど、その頻度も大きくなる。また、特に入次数の大きさはそのウェブページが注目されている度合いを表すと考えられ、重要な特性となる。
【0050】
同様に、パターンから得られる情報の例としては、図7におけるパターン(7)は16の情報を参照して発信された情報17に対し、16と17を参照した上で情報18を発信するといったように、議論を深める場合であるとか、16と17との間で起こった論争に対して、第3者が突っ込みを入れるといった際に現れてくるパターンではないかと想像され、各機能によって意味が異なる事が分かる。以上のように、局所構造を考慮する事によって、ウェブページの特性を反映した特徴量になりうると考えられる。
【0051】
ウェブページ特徴量DB106は、図8に示されるように、ウェブページIDとURL、上記特徴ベクトルにおける各次元をウェブページごとに関連付けを行った形でデータを保持している。
【0052】
また、請求項4、9の発明の実施形態例において、ウェブページ特徴量算出手段105は、前記ハイパーリンク情報DB104を参照し、前記隣接行列形式で表現されたネットワーク(例えば図5)を基に、各ノード(ウェブページ)に対してあらかじめ定められた数の周辺ノードと形成するサブネットワーク構造中での当該ノードの配置を考慮し、かつ、当該ノードの配置が一致する同形状のサブネットワーク構造が存在する場合には、そのサブネットワーク構造を形成するノードの違いを区別しないで算出した、該ウェブページの特徴量を算出し、当該特徴量をウェブページ特徴量DB106に登録する。
【0053】
ここで、本実施形態例におけるウェブページ特徴量算出の例を示す。図9のように8つのウェブページから構成されるネットワークについて、urlaおよびurleの特徴量を求める。urlaが周辺ノードと構成する3ノードサブネットワーク構造は、(a,b,c),(a,c,d),(a,b,d)の計3つである。それぞれの構造における、aの配置に基づいて、対応する要素をカウントアップすることによって、aの特徴量は30次元のベクトルにおいて、3次元目に2、22次元目に1の値を持つベクトルとなる。また、eの特徴ベクトルも同様にして求められ、aの特徴ベクトルと同一のものとなる。
【0054】
ここで、もし背景技術3のようにurlaがどのノードとサブネットワーク構造を構築するかまで考慮したうえで、特徴量を算出した場合には、urlaとurleの間には直接の接続関係がないために、同一のベクトルとはならない。したがって、次で説明する関連ウェブページ算出手段107において、ユークリッド距離が大きくなるため、urlaとurleが互いに関連ページとして提示されることはなくなる。一方で、本発明における特徴量を用いると、リンク構造が同様であることは何らかの特性が一致しているとして、urlaとurleは互いに関連ページとして提示される。
【0055】
関連ウェブページ算出手段107は、ユーザー等からの入力を受け取った上で、ウェブページ特徴量DB106を参照し、入力ページの特徴量とのユークリッド距離が小さくなる特徴量を持ったウェブページ群のURLをあらかじめ指定された数だけ、例えば10URL程度、出力として提示する。
【0056】
ここで、種々の距離指標の中でユークリッド距離を用いる理由は、本発明における局所構造を考慮した特徴ベクトルの要素の一部は、直接的に入次数および出次数を反映しているので、次数をサイトの特性を決定付ける際の重要な情報のひとつと考えると、例えば、方向性のみを考慮したコサイン距離等によって、次数の情報を無視するのは不適切だと考えられるためである。
【0057】
最後に、本発明に基づいてブログネットワークから、関連するブログを発見した結果についてデータを示す。ただし、ブログにおいては、本実施例における各ウェブページにあたる各記事中のリンクが極めて少ないので、ハイパーリンク情報DBにおけるFromSite,ToSiteを利用し、ブログサイト単位のネットワークを構築し、関連するブログサイトを発見する事とした。
【0058】
ブログネットワークを構築する際の基となったブログ記事は、2008年1月の日本語ブログ記事の595,350記事である。また、このブログネットワークにおける、ブログサイト数(ノード数)は248,225であり、エッジ数(ブログサイト間のリンク)は399,398、抽出された3ノードサブネットワーク数は48,668,680であった。
【0059】
ここでは、ブログサイト閲覧システムにおいてユーザーの利便性を阻害していた、スパムブログを取り除くため、よく現れてくるスパムの一つを関連ウェブページ算出手段107の入力とした。その結果、約60のブログについてユークリッド距離が著しく小さい値となり、関連サイトとして抽出され、また、これらのサイトは全て外見が同一のスパムブログであった。図10に、これらのブログの特徴量を、splog1を関連ウェブページ算出手段107の入力に用いたもの、splog2〜5までを、抽出された60のブログからランダムに選んだものとして示す。
【0060】
また、このスパムブログの特徴量と比較するため、関連ウェブページ算出手段107の入力に著名なブロガー(アルファブロガーと呼ばれる場合もある)のブログサイトを用いた場合の例を、図11に示す。上記と同様に、アルファ1は関連ウェブページ算出手段107の入力に用いたもの、アルファ2〜5までは、抽出された関連ブログからランダムに選んだものである。
【0061】
これらの特徴量を比較すると、スパムブログにおいては全ての特徴ベクトル中において全ての機能の頻度に値を持っていることが分かり、アルファブロガーのように機能2に大きな頻度を持つことから、入次数が非常に大きいことが分かるサイトの周辺でも出現しないような構造が多く出現している事から、これらのスパムブログは何らかの意図によって同一の手法で作成されたサイト群であると想像される。
【0062】
また、本実施形態の関連ウェブページ発見装置における各手段の一部もしくは全部の機能をコンピュータのプログラムで構成し、そのプログラムをコンピュータを用いて実行して本発明を実現することができること、本実施形態の関連ウェブページ発見方法における手順をコンピュータのプログラムで構成し、そのプログラムをコンピュータに実行させることができることは言うまでもなく、コンピュータでその機能を実現するためのプログラムを、そのコンピュータが読み取り可能な記録媒体、例えばFD(Floppy(登録商標) Disk)や、MO(Magneto−Optical disk)、ROM(Read Only Memory)、メモリカード、CD(Compact Disk)−ROM、DVD(Digital Versatile Disk)−ROM、CD−R、CD−RW、HDD、リムーバブルディスクなどに記録して、保存したり、配布したりすることが可能である。また、上記のプログラムをインターネットや電子メールなど、ネットワークを通して提供することも可能である。
【図面の簡単な説明】
【0063】
【図1】本発明の実施形態例における関連ウェブページ発見装置のブロック図。
【図2】本発明の実施形態例におけるネットワーク処理の流れを示すフローチャート。
【図3】本発明の実施形態例における関連ウェブページ算出処理の流れを示すフローチャート。
【図4】本発明の実施形態例におけるウェブページ情報DBの構造を示す説明図。
【図5】本発明の実施形態例におけるハイパーリンク情報DBの構造を示す説明図。
【図6】本発明の実施形態例におけるウェブページ特徴量算出処理の流れを示すフローチャート。
【図7】本発明の実施形態例における局所構造を考慮した3ノードサブグラフネットワーク構造を示す説明図。
【図8】本発明の実施形態例におけるウェブページ特徴量DBの構造を示す説明図。
【図9】本発明の実施形態例におけるウェブページ特徴量算出例を示す説明図。
【図10】本発明の実施形態例におけるスパムブログのウェブサイト特徴量の例を示す説明図。
【図11】本発明の実施形態例におけるアルファブロガーのウェブサイト特徴量の例を示す説明図。
【符号の説明】
【0064】
100…関連ウェブページ発見装置、101…ウェブページ収集手段、102…ウェブページ情報DB、103…ネットワーク抽出手段、104…ハイパーリンク情報DB、105…ウェブページ特徴量算出手段、106…ウェブページ特徴量DB、107…関連ウェブページ算出手段。
【技術分野】
【0001】
本発明は、あるウェブページと関連するウェブページを発見する方法及び装置に係り、特に、特性が類似しているウェブページを関連ページとして発見する関連ウェブページ発見装置、方法、プログラムに関する。
【0002】
ここで、特性が類似しているとは、例えば、ウェブページの注目度やそのウェブページが議論の構造における発端なのか、何らかの情報を受けての補足なのかといった役割のような、いわば当該ウェブページの属性的な要素が類似していることを指す。また、上記の特性の例のほかにも、例えば、そのウェブページがスパムと呼ばれる、検索エンジンにおける出力順位を不正に高めようという意図の下に作られたページであるかどうかに基づいた性質や、ショッピングサイト等への誘導を主目的として作られているページであるというような性質があげられる。
【背景技術】
【0003】
現在ではインターネット上のウェブページやウェブサイトの数は膨大なものとなり、ユーザーが所望の情報を取得するための負担は非常に大きなものとなった。
【0004】
そこで、ユーザーの情報取得を支援する様々な方法が提案されてきた。中でも、あるウェブページやウェブサイトに関連する情報が欲しいといった場合のニーズに答える方法に関しては、ウェブページ中のハイパーリンクによって形成されるネットワークの解析を基にした手法が提案されてきた。
【0005】
例えば、あるウェブページに対してハイパーリンクを張っているウェブページ群を抽出し、そのウェブページ群の多くがハイパーリンクを張っている当該ページと異なるウェブページを、当該ウェブページの関連ページとして提示する方法(特許文献1参照)がある(背景技術1)。
【0006】
また、ウェブページ間のハイパーリンクによる接続情報を隣接行列で表した上で、同一のページにリンクを張っている、もしくは同一のページからリンクを張られているという情報に基づいて、ウェブページのクラスタリングを行い、同一のクラスターに存在するページ群を関連ページ群として提示するという、従来からよく用いられてきた手法(背景技術2)がある。
【0007】
ここで、上記の手法をさらに高度化し、あるページの特徴量として、隣接行列から、当該ページが近傍のページと構成するサブネットワーク構造中での位置及びどのページとそのサブネットワーク構造を構成するかの情報を求め(非特許文献1参照)、より高精度なクラスタリングを行い、関連するウェブページを提示するという方法も考えられる(背景技術3)。
【0008】
ここで、背景技術3については、サブネットワーク構造を考慮する際にどのページと当該構造を構成するかを考慮しているため、結果的に背景技術2と同様に、クラスタリングを行う際の特徴量はページ間の接続情報を考慮したものとなっている。
【特許文献1】特開2002−304393号公報
【非特許文献1】高田寛喜、山田武士、上田修功、「ノードの機能特性に基づくクラスタリング」、ネットワーク生態学2008シンポジウム予稿集、pp.120−124、2008.
【発明の開示】
【発明が解決しようとする課題】
【0009】
上記背景技術1をはじめとする、あるページにハイパーリンクを張っているページ群を利用する手法では、当該ページ群は関連するウェブページをまとめたリンク集の機能を持っているという仮定に基づいている。したがって、ユーザーが所望した特性に基づく関連ページが得られるかどうかは、当該の特性を考慮したリンク集が背後に存在するかどうかに依存しており、必ずしも所望の関連ページが得られるとは限らないといった課題があった。
【0010】
上記背景技術2および背景技術3においては、ページ間の接続情報を考慮することで、接続情報が類似しているページは内容的に関連性が近いという仮定に基づいている。
【0011】
一方で、内容ではなく、例えば、同じような手法によって作成されたスパムページを発見したいといったような、特性が類似しているページを発見する場合には、直接接続関係がなくとも特性が類似していれば、関連ページとしてまとめられるべきである。このように、内容的な関連性に重きが置かれる結果、接続先を考慮した特徴量を用いた場合には、提示可能なページが接続関係のあるページ群のみに限定されるという課題があった。
【0012】
本発明は上記課題を解決するものであり、その目的は、特性の類似した関連ウェブページ群を容易に発見することができる関連ウェブページ発見装置、関連ウェブページ発見方法および関連ウェブページ発見プログラムを提供することにある。
【課題を解決するための手段】
【0013】
本発明では、ウェブページの特性は、当該ページと特定数の近傍ページとによって構成されるサブネットワーク中での当該ページの配置に基づいて算出された特徴量によって、よく表現されるという仮定に基づくことで、特性の類似した関連ウェブページの発見を実現した。
【0014】
請求項1に記載の関連ウェブページ発見装置は、特定のウェブページと関連するページを発見する装置において、インターネットからウェブページを自動的に収集し、ウェブページ情報データベースに登録するウェブページ収集手段と、前記ウェブページ情報データベースを参照し、登録されている各ページから、リンク元とリンク先に関するハイパーリンク情報を抽出し、該情報をハイパーリンク情報データベースに登録する事で、ウェブページをノード、ハイパーリンクをエッジとしたネットワークを隣接行列形式で表現するネットワーク抽出手段と、前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、ノード毎に該ノードとその周辺ノードとのエッジの接続状態に基づいた特徴量を算出し、当該特徴量をウェブページ特徴量データベースに登録するウェブページ特徴量算出手段と、前記ウェブページ特徴量データベースを参照し、各ページの特徴量を基に、処理対象のページと関連するウェブページを算出し、関連ウェブページ群を出力として提示する関連ウェブページ算出手段と、を有することを特徴としている。
【0015】
また請求項2に記載の関連ウェブページ発見装置は、請求項1において、前記ウェブページ特徴量算出手段は、前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、各ノードに対してその周辺ノードと形成するサブネットワーク中での構造を考慮した特徴量を算出し、当該特徴量をウェブページ特徴量データベースに登録することを特徴としている。
【0016】
また請求項3に記載の関連ウェブページ発見装置は、請求項1又は2において、前記ウェブページ特徴量算出手段は、前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、各ノードに対してあらかじめ定められた数の周辺ノードと形成するサブネットワーク構造中での当該ノードの配置に基づいてウェブページの特徴量を算出し、当該特徴量をウェブページ特徴量データベースに登録することを特徴としている。
【0017】
また請求項4に記載の関連ウェブページ発見装置は、請求項1ないし3のいずれか1項において、前記ウェブページ特徴量算出手段は、前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、各ノードに対してあらかじめ定められた数の周辺ノードと形成するサブネットワーク構造中での当該ノードの配置を考慮し、かつ、当該ノードの配置が一致する同形状のサブネットワーク構造が存在する場合には、そのサブネットワーク構造を形成するノードの違いを区別しないで算出した、該ウェブページの特徴量をウェブページ特徴量データベースに登録する、ことを特徴としている。
【0018】
また請求項5に記載の関連ウェブページ発見装置は、請求項1ないし4のいずれか1項において、前記関連ウェブページ算出手段は、前記ウェブページ特徴量データベースを参照し、処理対象のページの特徴量と各ページの特徴量を基に、ユークリッド距離を算出し、距離が小さいページ群を関連ウェブページ群として出力する、ことを特徴としている。
【0019】
また、請求項6に記載の関連ウェブページ発見方法は、特定のウェブページと関連するページを発見する方法において、ウェブページ収集手段が、インターネットからウェブページを自動的に収集し、ウェブページ情報データベースに登録するウェブページ収集ステップと、ネットワーク抽出手段が、前記ウェブページ情報データベースを参照し、登録されている各ページから、リンク元とリンク先に関するハイパーリンク情報を抽出し、該情報をハイパーリンク情報データベースに登録する事で、ウェブページをノード、ハイパーリンクをエッジとしたネットワークを隣接行列形式で表現するネットワーク抽出ステップと、ウェブページ特徴量算出手段が、前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、ノード毎に該ノードとその周辺ノードとのエッジの接続状態に基づいた特徴量を算出し、当該特徴量をウェブページ特徴量データベースに登録するウェブページ特徴量算出ステップと、関連ウェブページ算出手段が、前記ウェブページ特徴量データベースを参照し、各ページの特徴量を基に、処理対象のページと関連するウェブページを算出し、関連ウェブページ群を出力として提示する関連ウェブページ算出ステップと、を有することを特徴としている。
【0020】
また請求項7に記載の関連ウェブページ発見方法は、請求項6において、前記ウェブページ特徴量算出ステップは、前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、各ノードに対してその周辺ノードと形成するサブネットワーク中での構造を考慮した特徴量を算出し、当該特徴量をウェブページ特徴量データベースに登録することを特徴としている。
【0021】
また請求項8に記載の関連ウェブページ発見方法は、請求項6又は7において、前記ウェブページ特徴量算出ステップは、前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、各ノードに対してあらかじめ定められた数の周辺ノードと形成するサブネットワーク構造中での当該ノードの配置に基づいてウェブページの特徴量を算出し、当該特徴量をウェブページ特徴量データベースに登録することを特徴としている。
【0022】
また請求項9に記載の関連ウェブページ発見方法は、請求項6ないし8のいずれか1項において、前記ウェブページ特徴量算出ステップは、前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、各ノードに対してあらかじめ定められた数の周辺ノードと形成するサブネットワーク構造中での当該ノードの配置を考慮し、かつ、当該ノードの配置が一致する同形状のサブネットワーク構造が存在する場合には、そのサブネットワーク構造を形成するノードの違いを区別しないで算出した、該ウェブページの特徴量をウェブページ特徴量データベースに登録する、ことを特徴としている。
【0023】
また、請求項10に記載の関連ウェブページ発見プログラムは、コンピュータを請求項1ないし5のいずれか1項に記載の各手段として機能させる関連ウェブページ発見プログラムである。
【発明の効果】
【0024】
(1)請求項1〜10に記載の発明によれば、ユーザーが特性の類似した関連ウェブページ群を容易に発見する事が可能となる。
(2)請求項2〜4および請求項7〜9に記載の発明によれば、サブネットワーク中での構造(局所構造)を考慮した特徴量を算出しているので、ウェブページの特性を反映した特徴量を得ることができる。このため例えばスパムであれば、そのノードのランキングを不正に向上させるための構造が浮かび上がるなど、そのノードのネットワーク中での機能や特性、ひいては表に現われてこない意図を読み取ることができる。
【発明を実施するための最良の形態】
【0025】
以下、図面を参照しながら本発明の実施の形態を説明するが、本発明は下記の実施形態例に限定されるものではない。
【0026】
図1は本発明の実施形態の一例である関連ウェブページ発見装置の構成を示す図である。本実施形態の関連ウェブページ発見装置100は、所定のプログラムに基づいて動作する一般的なコンピュータ装置からなり、インターネット50からウェブページを収集し、その結果をウェブページ情報DB(データベース)102に登録するウェブページ収集手段101と、ウェブページ情報DB102からページ毎にハイパーリンクを抽出し、リンク元およびリンク先の情報などをハイパーリンク情報DB(データベース)104に登録するネットワーク抽出手段103と、ハイパーリンク情報DB104を利用して、各ウェブページが周辺ページと形成するサブネットワーク中での配置に基づいた局所構造を考慮した特徴量を算出し、ウェブページ特徴量DB(データベース)106に登録するウェブページ特徴量算出手段105と、指定されたURLに対応するウェブページと関連するウェブページ群を算出して、当該関連ウェブページ群のURLを出力する関連ウェブページ算出手段107とから構成されている。
【0027】
本実施形態の関連ウェブページ発見装置の処理の流れについては、大きく分けて2つの異なる流れによって構成される。ひとつは、図2によって示される、ウェブページ間のハイパーリンクに基づくネットワークを構築するために、ウェブページを自動的に収集しハイパーリンク情報を収集するための処理の流れであり、もうひとつは図3によって示される、入力されたウェブページの関連ウェブページを算出し、関連ウェブページ群を出力として提示するための処理の流れである。
【0028】
まず、図2のネットワーク構築のための処理の流れについては、ウェブページ収集手段101が、ステップS1において、ウェブページ情報DB102中のステータスを参照し、まだ未収集のウェブページを特定及び収集し、当該ウェブページのHTMLをウェブページ情報DB102に登録する。また、当該ウェブページのHTML中にウェブページ情報DB102に登録されていないウェブページへのハイパーリンクが含まれている場合にはその情報もウェブページ情報DB102に登録する。次に、ネットワーク抽出手段103が、ステップS2において、ウェブページ情報DB102に直前に登録されたウェブページに関して、ハイパーリンクを抽出し、その結果としてリンク先及びリンク元の情報をハイパーリンク情報DB104に登録する。以降、ウェブページ情報DB102の中にステータスが未収集のページがなくなるまで、もしくは、明示的に収集完了と指定されるまでウェブページの収集を繰り返す(ステップS3,S1,S2,S3)。
【0029】
次に、図3の関連ウェブページ群を算出するための処理の流れについては、ウェブページ特徴量算出手段105が、ステップS11において、ハイパーリンク情報DB104によって表されるネットワークの規模の変化および前回ウェブページの特徴量を算出してから経過した時間に基づいて、ウェブページの特徴量を算出するかどうかを判断する。
【0030】
ウェブページの特徴量を算出する場合には、ステップS12において、ハイパーリンク情報DB104を利用し、ページ毎に局所構造を考慮したウェブページ特徴量を算出し、ウェブページ特徴量DB106に結果を登録する。
【0031】
以降、関連ウェブページ算出手段107が、ステップS13,S14において、処理対象のウェブページがなくなるまで、当該ページ(指定されたURLに対応するウェブページ)をユーザー等からの入力として受け取り、前記ウェブページ特徴量DB106を参照しながら、当該ウェブページと関連するウェブページ群をユークリッド距離に基づいて算出し続ける。
【0032】
以下、前記図2、図3によって示された処理の手順を基に、各手段の詳細な説明を行う。
【0033】
ウェブページ収集手段101は、一般的な検索エンジンにおけるクローラに相当し、インターネットから自動的にウェブページを収集し、収集結果及び収集の状況に関する情報はウェブページ情報DB102に登録される。
【0034】
ここで、ウェブページ情報DB102は図4に示すように、ウェブページID,URL,Status,HTML等をウェブページごとに関連付けを行った形でデータとして保持している。ここで、ウェブページIDはウェブページごとにユニークに与えられる識別子である。また、Statusは、現在の収集状況を表す。alreadyは既に収集済である事を表す。yetは、まだ収集を試みていない事を表す。最後に、errorは収集を試みた際にエラーによって収集できなかった事を示す。また、例えば、HTMLの収集に成功した時間をTimeとするような形で、様々な付加情報を加えた上で関連付けを行い、データを保持することもできる。
【0035】
ここで、ウェブページの中には日々更新されるようなページが存在する事を鑑みると、Timeの情報を利用する事で、一度収集済みのページであっても一定期間ごとに再度HTMLを取得することで、情報の更新への対応が可能である。
【0036】
また、収集結果のHTML中に、ウェブページ情報DB102に登録されていないURLへのリンクが存在する場合には、ウェブページ情報DB102にそのURLに対応する新たなIDを付与し、Statusをyetとした上でURLを登録する。
【0037】
次に、ネットワーク抽出手段103は、前記ウェブページ収集手段101によって、収集およびウェブページ情報DB102に登録されたウェブページのHTMLを解析して、ハイパーリンクを抽出し、リンク元とリンク先の情報をハイパーリンク情報DB104に登録する事で、ウェブページをノード、ハイパーリンクをエッジとしたネットワークを例えば図5に示す隣接行列形式で表現可能にする。
【0038】
ここで、ハイパーリンク情報DB104は図5に示すように、ハイパーリンクID,FromURL,FromSite,ToURL,ToSite等をハイパーリンクごとに関連付けを行った形でデータを保持している。ハイパーリンクIDは、ハイパーリンク毎にユニークに与えられる識別子である。FromURLはリンク元URLであり、FromSiteはリンク元URLから得られたリンク元サイトでのURLである。ToURL,ToSiteについてはそれぞれリンク先のURL、リンク先サイトのURLに対応する。
【0039】
本DB104に、ウェブページ単位のURLのみではなく、サイト単位のURLも記録しておく事によって、次のウェブページ特徴量算出手段105において、サイト単位でリンクをまとめ、ウェブページのネットワークではなく、ウェブサイトのネットワークを構築した上で特徴量を算出する事が可能となり、結果として本発明を関連ウェブサイト発見装置としても利用する事ができるようになる。
【0040】
本DB104においても、ウェブページ情報DB102と同様にTime等の付加的な情報を加えて関連付けを行う事で、前記ウェブページ情報DB102と同様に、例えば、Timeであればウェブページの更新への対応が可能となる。
【0041】
続いて、ウェブページ特徴量算出手段105では、前記ハイパーリンク情報DB104を参照し、前記隣接行列形式で表現されたネットワーク(例えば図5)を基に、ノード(ウェブページ)毎に該ノードとその周辺ノードとのエッジ(ハイパーリンク)の接続状態に基づいた特徴量を算出し、当該特徴量をウェブページ特徴量DB106に登録する(請求項1、6の発明の実施形態)。
【0042】
また、請求項2,7の発明の実施形態において、ウェブページ特徴量算出手段105は、前記ハイパーリンク情報DB104を参照し、前記隣接行列形式で表現されたネットワーク(例えば図5)を基に、各ノード(ウェブページ)に対してその周辺ノードと形成するサブネットワーク中での構造を考慮した特徴量を算出し、当該特徴量をウェブページ特徴量DB106に登録する。
【0043】
また、請求項3,8の発明の実施形態において、ウェブページ特徴量算出手段105は、前記ハイパーリンク情報DB104を参照し、前記隣接行列形式で表現されたネットワーク(例えば図5)を基に、各ノード(ウェブページ)に対してあらかじめ定められた数の周辺ノードと形成するサブネットワーク構造中での当該ノードの配置に基づいてウェブページの特徴量を算出し、当該特徴量をウェブページ特徴量DB106に登録する。
【0044】
すなわち、ウェブページの特性は当該ウェブページと周辺ページとで形成するサブネットワーク中での当該ウェブページの配置によってよく現されるという仮説に基づき、ハイパーリンク情報DB104を参照し、各ウェブページとその接続情報を基に、局所構造を考慮した特徴量を算出した上で、当該特徴量をウェブページ特徴量DB106に登録する。
【0045】
より具体的には、ウェブページやブログサイトなどインターネット内に構築されているネットワークは、例えばランキングを不正操作しようとするスパム、アフィリエイト収入目当ての広告サイトへの誘導、周囲にたくさんのフォロワーを形成する注目度の高いブロガー(アルファブロガー)など、複数の人の様々な意図によってその巨大な構造を形成していると考えられる。したがって、ネットワーク全体に着目すると個々の意図は薄れてしまうが、注目ノードの周辺で形成されている局所構造に着目すると、例えば、スパムであれば、そのノードのランキングを不正に向上させるための構造が浮かび上がるなど、そのノードのネットワーク中での機能や特性、ひいては表に現れてこない意図を読み取る事ができるのではないかと考えられる。ここで、ウェブページによって構成されるネットワークおいては、ノードはウェブページ、エッジはハイパーリンクの事を指す。
【0046】
局所構造を考慮した特徴量を算出する処理の詳細な流れについては図6に示され、まずウェブページ特徴量算出手段105が、ハイパーリンク情報DB104によって表されるウェブページのネットワーク構造の中からあらかじめ指定されたノード数k,例えばk=3〜6程度、のサブネットワークをすべて列挙する(ステップS21)。ここで、k=3の場合には、とりうるサブネットワークの構造は図7に示すように計13パターンあり、各パターン中でのノードの位置について対称性を考慮すると、ノードの機能は計30種類に分類される。したがって、k=3の場合、ウェブページiの特徴量、つまり特徴ベクトルはウェブページiがその周辺のウェブページと形成する3ノードサブネットワーク構造中で果たしている各機能の頻度を要素として持った30次元のベクトルとなり、以下の式(1)で表される。
【0047】
Mi=(m1,m2,m3,...,m30)…(1)
ここで、m1,m2の添え字1,2は、それぞれ図7中における機能1,2に対応している。各ウェブページの特徴ベクトルの算出(式(1)の算出)が終わったら、その結果をウェブページ特徴量DB106に登録する(ステップS22)。
【0048】
本発明における、局所構造を考慮した特徴量においては、ウェブページの特性は必ずしも人が容易に把握できるものばかりではないが、中には特定の機能が表すウェブページの定性的な特性を想像できるものもある。
【0049】
例えば、機能1および3はそれぞれ出次数・入次数を良く表すと考えられる。もちろん、他の2ノードとの間およびそれらのノード間にエッジが存在する場合には異なったパターンを形成するが、その出次数・入次数をnとすると、複雑なサブネットワーク構造は形成されにくいことを考慮すると、特徴ベクトル中でのm1,m2の頻度は、nC2程度(CはCombinatioの頭文字)になると考えられ、出次数・入次数nが大きいほど、その頻度も大きくなる。また、特に入次数の大きさはそのウェブページが注目されている度合いを表すと考えられ、重要な特性となる。
【0050】
同様に、パターンから得られる情報の例としては、図7におけるパターン(7)は16の情報を参照して発信された情報17に対し、16と17を参照した上で情報18を発信するといったように、議論を深める場合であるとか、16と17との間で起こった論争に対して、第3者が突っ込みを入れるといった際に現れてくるパターンではないかと想像され、各機能によって意味が異なる事が分かる。以上のように、局所構造を考慮する事によって、ウェブページの特性を反映した特徴量になりうると考えられる。
【0051】
ウェブページ特徴量DB106は、図8に示されるように、ウェブページIDとURL、上記特徴ベクトルにおける各次元をウェブページごとに関連付けを行った形でデータを保持している。
【0052】
また、請求項4、9の発明の実施形態例において、ウェブページ特徴量算出手段105は、前記ハイパーリンク情報DB104を参照し、前記隣接行列形式で表現されたネットワーク(例えば図5)を基に、各ノード(ウェブページ)に対してあらかじめ定められた数の周辺ノードと形成するサブネットワーク構造中での当該ノードの配置を考慮し、かつ、当該ノードの配置が一致する同形状のサブネットワーク構造が存在する場合には、そのサブネットワーク構造を形成するノードの違いを区別しないで算出した、該ウェブページの特徴量を算出し、当該特徴量をウェブページ特徴量DB106に登録する。
【0053】
ここで、本実施形態例におけるウェブページ特徴量算出の例を示す。図9のように8つのウェブページから構成されるネットワークについて、urlaおよびurleの特徴量を求める。urlaが周辺ノードと構成する3ノードサブネットワーク構造は、(a,b,c),(a,c,d),(a,b,d)の計3つである。それぞれの構造における、aの配置に基づいて、対応する要素をカウントアップすることによって、aの特徴量は30次元のベクトルにおいて、3次元目に2、22次元目に1の値を持つベクトルとなる。また、eの特徴ベクトルも同様にして求められ、aの特徴ベクトルと同一のものとなる。
【0054】
ここで、もし背景技術3のようにurlaがどのノードとサブネットワーク構造を構築するかまで考慮したうえで、特徴量を算出した場合には、urlaとurleの間には直接の接続関係がないために、同一のベクトルとはならない。したがって、次で説明する関連ウェブページ算出手段107において、ユークリッド距離が大きくなるため、urlaとurleが互いに関連ページとして提示されることはなくなる。一方で、本発明における特徴量を用いると、リンク構造が同様であることは何らかの特性が一致しているとして、urlaとurleは互いに関連ページとして提示される。
【0055】
関連ウェブページ算出手段107は、ユーザー等からの入力を受け取った上で、ウェブページ特徴量DB106を参照し、入力ページの特徴量とのユークリッド距離が小さくなる特徴量を持ったウェブページ群のURLをあらかじめ指定された数だけ、例えば10URL程度、出力として提示する。
【0056】
ここで、種々の距離指標の中でユークリッド距離を用いる理由は、本発明における局所構造を考慮した特徴ベクトルの要素の一部は、直接的に入次数および出次数を反映しているので、次数をサイトの特性を決定付ける際の重要な情報のひとつと考えると、例えば、方向性のみを考慮したコサイン距離等によって、次数の情報を無視するのは不適切だと考えられるためである。
【0057】
最後に、本発明に基づいてブログネットワークから、関連するブログを発見した結果についてデータを示す。ただし、ブログにおいては、本実施例における各ウェブページにあたる各記事中のリンクが極めて少ないので、ハイパーリンク情報DBにおけるFromSite,ToSiteを利用し、ブログサイト単位のネットワークを構築し、関連するブログサイトを発見する事とした。
【0058】
ブログネットワークを構築する際の基となったブログ記事は、2008年1月の日本語ブログ記事の595,350記事である。また、このブログネットワークにおける、ブログサイト数(ノード数)は248,225であり、エッジ数(ブログサイト間のリンク)は399,398、抽出された3ノードサブネットワーク数は48,668,680であった。
【0059】
ここでは、ブログサイト閲覧システムにおいてユーザーの利便性を阻害していた、スパムブログを取り除くため、よく現れてくるスパムの一つを関連ウェブページ算出手段107の入力とした。その結果、約60のブログについてユークリッド距離が著しく小さい値となり、関連サイトとして抽出され、また、これらのサイトは全て外見が同一のスパムブログであった。図10に、これらのブログの特徴量を、splog1を関連ウェブページ算出手段107の入力に用いたもの、splog2〜5までを、抽出された60のブログからランダムに選んだものとして示す。
【0060】
また、このスパムブログの特徴量と比較するため、関連ウェブページ算出手段107の入力に著名なブロガー(アルファブロガーと呼ばれる場合もある)のブログサイトを用いた場合の例を、図11に示す。上記と同様に、アルファ1は関連ウェブページ算出手段107の入力に用いたもの、アルファ2〜5までは、抽出された関連ブログからランダムに選んだものである。
【0061】
これらの特徴量を比較すると、スパムブログにおいては全ての特徴ベクトル中において全ての機能の頻度に値を持っていることが分かり、アルファブロガーのように機能2に大きな頻度を持つことから、入次数が非常に大きいことが分かるサイトの周辺でも出現しないような構造が多く出現している事から、これらのスパムブログは何らかの意図によって同一の手法で作成されたサイト群であると想像される。
【0062】
また、本実施形態の関連ウェブページ発見装置における各手段の一部もしくは全部の機能をコンピュータのプログラムで構成し、そのプログラムをコンピュータを用いて実行して本発明を実現することができること、本実施形態の関連ウェブページ発見方法における手順をコンピュータのプログラムで構成し、そのプログラムをコンピュータに実行させることができることは言うまでもなく、コンピュータでその機能を実現するためのプログラムを、そのコンピュータが読み取り可能な記録媒体、例えばFD(Floppy(登録商標) Disk)や、MO(Magneto−Optical disk)、ROM(Read Only Memory)、メモリカード、CD(Compact Disk)−ROM、DVD(Digital Versatile Disk)−ROM、CD−R、CD−RW、HDD、リムーバブルディスクなどに記録して、保存したり、配布したりすることが可能である。また、上記のプログラムをインターネットや電子メールなど、ネットワークを通して提供することも可能である。
【図面の簡単な説明】
【0063】
【図1】本発明の実施形態例における関連ウェブページ発見装置のブロック図。
【図2】本発明の実施形態例におけるネットワーク処理の流れを示すフローチャート。
【図3】本発明の実施形態例における関連ウェブページ算出処理の流れを示すフローチャート。
【図4】本発明の実施形態例におけるウェブページ情報DBの構造を示す説明図。
【図5】本発明の実施形態例におけるハイパーリンク情報DBの構造を示す説明図。
【図6】本発明の実施形態例におけるウェブページ特徴量算出処理の流れを示すフローチャート。
【図7】本発明の実施形態例における局所構造を考慮した3ノードサブグラフネットワーク構造を示す説明図。
【図8】本発明の実施形態例におけるウェブページ特徴量DBの構造を示す説明図。
【図9】本発明の実施形態例におけるウェブページ特徴量算出例を示す説明図。
【図10】本発明の実施形態例におけるスパムブログのウェブサイト特徴量の例を示す説明図。
【図11】本発明の実施形態例におけるアルファブロガーのウェブサイト特徴量の例を示す説明図。
【符号の説明】
【0064】
100…関連ウェブページ発見装置、101…ウェブページ収集手段、102…ウェブページ情報DB、103…ネットワーク抽出手段、104…ハイパーリンク情報DB、105…ウェブページ特徴量算出手段、106…ウェブページ特徴量DB、107…関連ウェブページ算出手段。
【特許請求の範囲】
【請求項1】
特定のウェブページと関連するページを発見する装置において、
インターネットからウェブページを自動的に収集し、ウェブページ情報データベースに登録するウェブページ収集手段と、
前記ウェブページ情報データベースを参照し、登録されている各ページから、リンク元とリンク先に関するハイパーリンク情報を抽出し、該情報をハイパーリンク情報データベースに登録する事で、ウェブページをノード、ハイパーリンクをエッジとしたネットワークを隣接行列形式で表現するネットワーク抽出手段と、
前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、ノード毎に該ノードとその周辺ノードとのエッジの接続状態に基づいた特徴量を算出し、当該特徴量をウェブページ特徴量データベースに登録するウェブページ特徴量算出手段と、
前記ウェブページ特徴量データベースを参照し、各ページの特徴量を基に、処理対象のページと関連するウェブページを算出し、関連ウェブページ群を出力として提示する関連ウェブページ算出手段と、
を有することを特徴とする関連ウェブページ発見装置。
【請求項2】
請求項1に記載の関連ウェブページ発見装置において、前記ウェブページ特徴量算出手段は、
前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、各ノードに対してその周辺ノードと形成するサブネットワーク中での構造を考慮した特徴量を算出し、当該特徴量をウェブページ特徴量データベースに登録することを特徴とする関連ウェブページ発見装置。
【請求項3】
請求項1又は2に記載の関連ウェブページ発見装置において、前記ウェブページ特徴量算出手段は、
前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、各ノードに対してあらかじめ定められた数の周辺ノードと形成するサブネットワーク構造中での当該ノードの配置に基づいてウェブページの特徴量を算出し、当該特徴量をウェブページ特徴量データベースに登録することを特徴とする関連ウェブページ発見装置。
【請求項4】
請求項1ないし3のいずれか1項に記載の関連ウェブページ発見装置において、前記ウェブページ特徴量算出手段は、
前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、各ノードに対してあらかじめ定められた数の周辺ノードと形成するサブネットワーク構造中での当該ノードの配置を考慮し、かつ、当該ノードの配置が一致する同形状のサブネットワーク構造が存在する場合には、そのサブネットワーク構造を形成するノードの違いを区別しないで算出した、該ウェブページの特徴量をウェブページ特徴量データベースに登録する、ことを特徴とする関連ウェブページ発見装置。
【請求項5】
請求項1ないし4のいずれか1項に記載の関連ウェブページ発見装置において、前記関連ウェブページ算出手段は、
前記ウェブページ特徴量データベースを参照し、処理対象のページの特徴量と各ページの特徴量を基に、ユークリッド距離を算出し、距離が小さいページ群を関連ウェブページ群として出力する、ことを特徴とする関連ウェブページ発見装置。
【請求項6】
特定のウェブページと関連するページを発見する方法において、
ウェブページ収集手段が、インターネットからウェブページを自動的に収集し、ウェブページ情報データベースに登録するウェブページ収集ステップと、
ネットワーク抽出手段が、前記ウェブページ情報データベースを参照し、登録されている各ページから、リンク元とリンク先に関するハイパーリンク情報を抽出し、該情報をハイパーリンク情報データベースに登録する事で、ウェブページをノード、ハイパーリンクをエッジとしたネットワークを隣接行列形式で表現するネットワーク抽出ステップと、
ウェブページ特徴量算出手段が、前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、ノード毎に該ノードとその周辺ノードとのエッジの接続状態に基づいた特徴量を算出し、当該特徴量をウェブページ特徴量データベースに登録するウェブページ特徴量算出ステップと、
関連ウェブページ算出手段が、前記ウェブページ特徴量データベースを参照し、各ページの特徴量を基に、処理対象のページと関連するウェブページを算出し、関連ウェブページ群を出力として提示する関連ウェブページ算出ステップと、
を有することを特徴とする関連ウェブページ発見方法。
【請求項7】
請求項6に記載の関連ウェブページ発見方法において、前記ウェブページ特徴量算出ステップは、
前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、各ノードに対してその周辺ノードと形成するサブネットワーク中での構造を考慮した特徴量を算出し、当該特徴量をウェブページ特徴量データベースに登録することを特徴とする関連ウェブページ発見方法。
【請求項8】
請求項6又は7に記載の関連ウェブページ発見方法において、前記ウェブページ特徴量算出ステップは、
前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、各ノードに対してあらかじめ定められた数の周辺ノードと形成するサブネットワーク構造中での当該ノードの配置に基づいてウェブページの特徴量を算出し、当該特徴量をウェブページ特徴量データベースに登録することを特徴とする関連ウェブページ発見方法。
【請求項9】
請求項6ないし8のいずれか1項に記載の関連ウェブページ発見方法において、前記ウェブページ特徴量算出ステップは、
前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、各ノードに対してあらかじめ定められた数の周辺ノードと形成するサブネットワーク構造中での当該ノードの配置を考慮し、かつ、当該ノードの配置が一致する同形状のサブネットワーク構造が存在する場合には、そのサブネットワーク構造を形成するノードの違いを区別しないで算出した、該ウェブページの特徴量をウェブページ特徴量データベースに登録する、ことを特徴とする関連ウェブページ発見方法。
【請求項10】
コンピュータを請求項1ないし5のいずれか1項に記載の各手段として機能させる関連ウェブページ発見プログラム。
【請求項1】
特定のウェブページと関連するページを発見する装置において、
インターネットからウェブページを自動的に収集し、ウェブページ情報データベースに登録するウェブページ収集手段と、
前記ウェブページ情報データベースを参照し、登録されている各ページから、リンク元とリンク先に関するハイパーリンク情報を抽出し、該情報をハイパーリンク情報データベースに登録する事で、ウェブページをノード、ハイパーリンクをエッジとしたネットワークを隣接行列形式で表現するネットワーク抽出手段と、
前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、ノード毎に該ノードとその周辺ノードとのエッジの接続状態に基づいた特徴量を算出し、当該特徴量をウェブページ特徴量データベースに登録するウェブページ特徴量算出手段と、
前記ウェブページ特徴量データベースを参照し、各ページの特徴量を基に、処理対象のページと関連するウェブページを算出し、関連ウェブページ群を出力として提示する関連ウェブページ算出手段と、
を有することを特徴とする関連ウェブページ発見装置。
【請求項2】
請求項1に記載の関連ウェブページ発見装置において、前記ウェブページ特徴量算出手段は、
前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、各ノードに対してその周辺ノードと形成するサブネットワーク中での構造を考慮した特徴量を算出し、当該特徴量をウェブページ特徴量データベースに登録することを特徴とする関連ウェブページ発見装置。
【請求項3】
請求項1又は2に記載の関連ウェブページ発見装置において、前記ウェブページ特徴量算出手段は、
前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、各ノードに対してあらかじめ定められた数の周辺ノードと形成するサブネットワーク構造中での当該ノードの配置に基づいてウェブページの特徴量を算出し、当該特徴量をウェブページ特徴量データベースに登録することを特徴とする関連ウェブページ発見装置。
【請求項4】
請求項1ないし3のいずれか1項に記載の関連ウェブページ発見装置において、前記ウェブページ特徴量算出手段は、
前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、各ノードに対してあらかじめ定められた数の周辺ノードと形成するサブネットワーク構造中での当該ノードの配置を考慮し、かつ、当該ノードの配置が一致する同形状のサブネットワーク構造が存在する場合には、そのサブネットワーク構造を形成するノードの違いを区別しないで算出した、該ウェブページの特徴量をウェブページ特徴量データベースに登録する、ことを特徴とする関連ウェブページ発見装置。
【請求項5】
請求項1ないし4のいずれか1項に記載の関連ウェブページ発見装置において、前記関連ウェブページ算出手段は、
前記ウェブページ特徴量データベースを参照し、処理対象のページの特徴量と各ページの特徴量を基に、ユークリッド距離を算出し、距離が小さいページ群を関連ウェブページ群として出力する、ことを特徴とする関連ウェブページ発見装置。
【請求項6】
特定のウェブページと関連するページを発見する方法において、
ウェブページ収集手段が、インターネットからウェブページを自動的に収集し、ウェブページ情報データベースに登録するウェブページ収集ステップと、
ネットワーク抽出手段が、前記ウェブページ情報データベースを参照し、登録されている各ページから、リンク元とリンク先に関するハイパーリンク情報を抽出し、該情報をハイパーリンク情報データベースに登録する事で、ウェブページをノード、ハイパーリンクをエッジとしたネットワークを隣接行列形式で表現するネットワーク抽出ステップと、
ウェブページ特徴量算出手段が、前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、ノード毎に該ノードとその周辺ノードとのエッジの接続状態に基づいた特徴量を算出し、当該特徴量をウェブページ特徴量データベースに登録するウェブページ特徴量算出ステップと、
関連ウェブページ算出手段が、前記ウェブページ特徴量データベースを参照し、各ページの特徴量を基に、処理対象のページと関連するウェブページを算出し、関連ウェブページ群を出力として提示する関連ウェブページ算出ステップと、
を有することを特徴とする関連ウェブページ発見方法。
【請求項7】
請求項6に記載の関連ウェブページ発見方法において、前記ウェブページ特徴量算出ステップは、
前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、各ノードに対してその周辺ノードと形成するサブネットワーク中での構造を考慮した特徴量を算出し、当該特徴量をウェブページ特徴量データベースに登録することを特徴とする関連ウェブページ発見方法。
【請求項8】
請求項6又は7に記載の関連ウェブページ発見方法において、前記ウェブページ特徴量算出ステップは、
前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、各ノードに対してあらかじめ定められた数の周辺ノードと形成するサブネットワーク構造中での当該ノードの配置に基づいてウェブページの特徴量を算出し、当該特徴量をウェブページ特徴量データベースに登録することを特徴とする関連ウェブページ発見方法。
【請求項9】
請求項6ないし8のいずれか1項に記載の関連ウェブページ発見方法において、前記ウェブページ特徴量算出ステップは、
前記ハイパーリンク情報データベースを参照し、前記隣接行列形式で表現されたネットワークを基に、各ノードに対してあらかじめ定められた数の周辺ノードと形成するサブネットワーク構造中での当該ノードの配置を考慮し、かつ、当該ノードの配置が一致する同形状のサブネットワーク構造が存在する場合には、そのサブネットワーク構造を形成するノードの違いを区別しないで算出した、該ウェブページの特徴量をウェブページ特徴量データベースに登録する、ことを特徴とする関連ウェブページ発見方法。
【請求項10】
コンピュータを請求項1ないし5のいずれか1項に記載の各手段として機能させる関連ウェブページ発見プログラム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【公開番号】特開2010−123038(P2010−123038A)
【公開日】平成22年6月3日(2010.6.3)
【国際特許分類】
【出願番号】特願2008−297849(P2008−297849)
【出願日】平成20年11月21日(2008.11.21)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】
【公開日】平成22年6月3日(2010.6.3)
【国際特許分類】
【出願日】平成20年11月21日(2008.11.21)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】
[ Back to top ]