リンク構造解析によるページの 価値計算とネットワーク分析

Presentation on theme: "リンク構造解析によるページの 価値計算とネットワーク分析"— Presentation transcript:

1 リンク構造解析によるページの 価値計算とネットワーク分析
知識システム構築論講座 林研究室　黄　林春

2 発表の構成 1 背景と目的 2 定義 3 アルゴリズム 4 分析方法と結果 本発表は、 まず、背景と目的を概説し、
1 背景と目的　 2 定義 3 アルゴリズム 4 分析方法と結果 本発表は、 まず、背景と目的を概説し、 次、研究で使われるいくつかの言葉の定義について、説明します。 その次は、アルゴリズムの解説、 最後に研究手法と結果および考察について説明します。 この順番でやっていきたいと思います。

3 1 研究の背景と目的 1.1 研究の背景 1.2 目的 WWWの成長。 的確な情報入手の困難さ。 情報の移動経路や流通ルートの不明瞭さ。
1 研究の背景と目的 1.1　研究の背景 WWWの成長。 的確な情報入手の困難さ。 情報の移動経路や流通ルートの不明瞭さ。 1.2　目的 リンク構造を利用して、情報の分布や流通経路と、ネットワークの形態との関連性を探す。 研究背景: 現在、インターネットの規模や構成の複雑さが拡大する一方、WWWにおいては誰でも容易に情報発信できるというオープンな性格のためにネットワークの上で情報や知識の流通と交換が頻繁に行われている。しかし、情報・知識の移動経路や流通ルートのメカニズムに関しては、まだ不明なところが多くある。また、情報資源発見の支援するために多数のサーチエンジンが提供されているが、大量の結果から適切な情報を選択することは依然として困難である。本研究では、サーチエンジンとは別のアプローチとしてネットワークにおけるリンク構造とページの価値との関連性に注目して、リンク構造を利用して、Webページのリンク価値を計算し、ネットワークにおける情報の分布とネットワーク全体の形態特徴を分析する手法を提案する。 この研究の目的： 　リンク構造を利用して、ネットワーク上の情報の分布や、ネットワークの形態と情報や知識の流通経路との関連性について検討することです。

4 2 概念と定義 リンクの重要性 リンクの分類 HubリンクとAuthorityリンク リンクの多さ ＝ページに関する価値の高さと仮定
2 概念と定義 リンクの重要性 リンクの多さ ＝ページに関する価値の高さと仮定 ページのリンク価値＝ページのリンク数（HubとAut） リンクの分類 HubリンクとAuthorityリンク Authority Link Hub Link Webページの内容の多様性がWebページをみる人にとっては、大きな楽しみとなっている。しかし、言語処理的な解析でページの内容や価値を評価しようとすると膨大な計算時間を必要とする上、評価基準にも多様なものが存在します。そこで、リンクの多さがページ内容に関する価値の高さを示していると仮定して、Webページの直接的な内容の解析は行わず、Webページのリンクに注目します。 ここで、 リンクの分類： ネットワークのリンク構造から、リンクをHubリンクとAutリンクに分類する。 Autリンクは、他のページをリンクしているほうで、Hubリンクは、他のページにリンクされるほうであります。ただし、このリンクの定義は抽象的な概念であり、絶対的なものではない。つまり、あるWebページにとってAutリンクとなるものは、リンク先のページにとってはHubリンクともなるからです。

5 3 研究手法とアルゴリズム 3.1 ネットワーク分析の手順 ① ページ（HTMLファイル）及びリンクデータの収集 ② リンク構造の解析
3 研究手法とアルゴリズム 3.1　ネットワーク分析の手順 ①　ページ（HTMLファイル）及びリンクデータの収集 ②　リンク構造の解析 ③　ページのリンク価値等，評価値の計算 ④　データのグラフ化、ネットワーク分析 本研究の手順は、 まず、 Webロボットと呼ばれるプログラムを用いて、ページデータ（HTMLファイル）及びリンクデータ（Autリンク）を収集します。 次、得られたAutリンクデータとページデータから、ネットワークのHubリンク構造を計算します。 その次、AutリンクデータとHubリンクデータを使って、すべてのページのリンク価値などネットワークの評価値を計算する。 最後、計算の結果をグラフ化して、専用ツールに表示させて、ネットワークの特徴とネットワークにおける情報の分布状況について、分析を行う。

6 3.2 Webロボットの動作 探索開始ページのHTMLファイルを読み込み、リンクデータをリストに記憶する。
リストからリンクデータを取り出し、リンク先のページを読み込み、リストに追加する。 設定条件が満たすまで②を繰り返す。 ネットワークの分析をするために、まずネットワークのリンク構造情報を知る必要があります。リンクデータを収集することは人間にとって大変な作業であります。今回の研究では、この機械的作業を人間の代わりにWebロボットにやらせる方法をとりました。 ●Webロボットの動作 ① Webロボットは、最初の探索開始ページのHTMLファイルを読み込んで、ドキュメントを解析して、リンクデータを抽出して、自分のインデックスリストに記憶する。 ②次に、リストから順番にリンクデータを取り出し、リンク先のドキュメントを読み込みます。読み込んだドキュメントを解析しながら、リンクデータを自分のインデックスリストに追加する。 新しいドキュメントを閲覧するたびにインデックスにリンクデータを追加していきます。 ③ユーザーが設定した条件を満たすまで、或はタイムリミットまでこの処理を繰り返します。 こうして、Webロボットはスタートポイントを中心にリンクを辿って、幅優先探索方式で次々へと自分の探索範囲を広げていきます。

7 Webロボットの並列分散処理環境の実現 プログラムを設計する際に、ロボットの仕事効率を上げるために、Java言語のマルチスレッド機能を利用して、ネットワークの通信スピードやデータの数と量に応じて、ロボットを自律的に自分自身をコントロールできるようにしました。 ロボットは、メインの制御スレッド、動作を監視する監視スレッドとリンクデータを収集する仕事スレッドからなります。この３つのスレッドは、互いに、独立に動いており、自分の役割を果たしています。さらに、ネットワークの通信スピードが許す限り、仕事スレッドは最大10個の代理（サブスレッド＝自分自身）を呼び出し、処理を分散させることができる。 この設計により、プログラムは人間の介入を受けなくても、常に効率よく仕事をすることが出来ます。

8 4 結果と考察 4.1 実験の項目 ① 実験の対象 WWW（Java、Hp…12個） 人工的ネットワーク（25個） ② 比較項目
4 結果と考察 4.1　実験の項目 ①　実験の対象 WWW（Java、Hp…12個） 人工的ネットワーク（25個） ②　比較項目 Hubリンク数（総・平均） Autリンク数（総・平均） ネットワーク開放度（後述）… 今回の実験では、 Jaistの公式ページや東京理科大学の公式ページ、個人ページなど１２個のホームページをロボットの探索開始ページとして、実験を行いました。 さらに、実際のネットワークと比較するために、人工的ネットワークを作って、ネットワークの形態やリンク構造などについて比較をしました。

9 4.2 実験の結果 4.2.1 Autリンク価値の高いページは、そのページのHubリンク価値も相対的に高い。 （Java）のリンク数の分布表
4.2　実験の結果 4.2.1　Autリンク価値の高いページは、そのページのHubリンク価値も相対的に高い。 分布図（Autリンクでソートした結果） （Java）のリンク数の分布表 実験で分ったこととして、まず。 つまり、Hubリンク価値とAutリンク価値との間に相関関係がある程度みられました。、 このグラフはページをAutリンクの数でソートしたものです。X軸はページの順番を表し、Y軸はリンクの数を表しています。また、青い線はAutリンクの数を、赤い線はHubリンクの数を表しています。 グラフを見ると、Hubリンク価値の高いページがAutリンク価値の高い区域（グラフの前半）に集中する傾向がある事がわかります。 この表は、右のグラフを数値化したものです。数値を見ると、やはり、Hubリンク価値高いページはAutリンク価値高いところに集中する傾向が見られます。

10 4.2.2 リンク価値の分布について ネットワーク区域ごとにリンク価値の平均値とパタンが大きく異なる
4.2.2 リンク価値の分布について 実験により、各ネットワーク区域において、その区域の平均リンク価値（Autリンク、Hubリンク両方含む）は大きく違い、分布パターンも異なることがわかった。 ネットワーク区域とは、ネットワークの中に、探索の開始ページをはじめ、Webロボットがリンクを辿って、探索できた部分のことです。 右側のグラフの平均リンク価値は左側より、Autリンクでは４倍、Hubリンクでは２倍も高いことが分かります。それは、ネットワークにおける知識と情報の分布はランダムではなく、人の嗜好や趣味など主観的要素と集団や組織の構造など物理的要素と非常に関係していることを示していると考えられる。 ネットワーク区域ごとにリンク価値の平均値とパタンが大きく異なる

11 4.2.3 明確な目的を持って作ったページはそうでないページよりページのリンク価値が高い
4.2.3　明確な目的を持って作ったページはそうでないページよりページのリンク価値が高い ネットワーク 平均Hubリンク価値 平均Autリンク価値 Shino（個人サイト） 2.89 6.47 Java（Java言語サイト） 7.61 24.87 この表で表している数字は、ある人の個人ページを探索開始ページとしたネットワークと、Java言語という共通な話題を持つページを探索開始ページとしたネットワークの平均HubリンクとAutリンク価値です。二つのネットワークを比較すると、個人ページのほうのリンク（HubリンクとAutリンク）価値の平均値が全般的に低く、それに対して、JavaのぺーじのほうのAutリンク価値とHub価値が両方とも高いことが分ります。明らかに、後者の場合、知識と情報の流通が活発に行われていると思われる。 リンク数の比較（平均）

12 リンク数の比較（分布） あるJavaのサイト ある個人のサイト これはさき説明した、二つのネットワークのグラフの比較です。
これでもまた、リンク価値の分布パターンが大きく異なることが分ります。

13 4.3 考察 4.3.1 ネットワークの開放度と開放型ネットワーク 探索できた範囲 Network ネットワーク開放度のイメージ
4.3　考察 4.3.1　ネットワークの開放度と開放型ネットワーク Network 回収されないリンク ここでいうネットワーク開放度とは、Webロボットの探索できた範囲の中のページから、外のページへのリンクの割合のことです。 リンクが収束していくか、それとも開放していくか 探索できた範囲 ネットワーク開放度のイメージ

14 開放度の意義 ネットワークの開放度が高ければ高いほど、情報や知識の交流も行いやすいと考えられる。 各ネットワークの開放度 Network
Hp Huang Jaist Java Ks Test Yy Tkd SUT 開放度 0.76 0.56 0.54 0.69 0.53 0.45 0.82 0.79 0.77 ネットワークの開放度が高ければ高いほど、外部の世界（ネットワーク）との連結経路が多くなり、情報や知識の交流も行いやすいから、ネットワークの開放度はネットワーク構造を評価する時に一つ重要な参考値となると考えられる。 実験データに用いて、それぞれのネットワークの開放度を計算するとスタートページがYY、TKD、SUT、HPであるネットワークは開放度が高く、これらのネットワークは開放的ネットワークであることを示唆（しさ）しています。 各ネットワークの開放度

15 4.3.2 人工的ネットワークとの比較 規則正しい（ρ=0） 中間的な領域（0＜ρ＜1） 無秩序（ρ=1）
4.3.2　人工的ネットワークとの比較 本研究では、ネットワークの結合形態を説明するために、比較の対象として、人工的ネットワークをこのように作りました。 リンクのランダム性とリンクの結合率という二つのパラメータを調節するで、規則正しい（ρ：ロー）、無秩序（ちつじょ）、とさまざまな中間的な領域（0＜ρ＜1）のネットワークを作り出すことができます。ランダム性とは、リンクの並び方で、結合率とは、リンクの本数（つまり密度）のことであります。図のように、ρが０の時、ネットワーク内のリンクが規則正しく並んでいる、ρが１に近づくにつれ、ネットワーク内のリンクの並ぶ方がランダムになる。 こうして、作られた人工的ネットワークはWebロボットやネットワーク分析ツールなどプログラムの動作確認にも用いられました。 注： リンクのランダム性は、あるノードから出ているリンクの方向を決めるパラメータである。 リンクの密度とは、ネットワーク内のリンク数とノード数の比例値のことである。 規則正しい（ρ=0） 中間的な領域（0＜ρ＜1） 無秩序（ρ=1）

16 4.3.2 WWWと人工ネットワークとの比較 人工的ネットワーク 実際のネットワーク リンク価値 リンク価値 ↑ ↑ → ページ（探索順）
ここで、人工ネットワークと実際のネットワークと比較すると、図のように、実際のネットワークのリンク価値の分布パターンと非常に似ている人工的ネットワークが存在していることが分かった。 故に、前述の二つのパラメータ（ランダムRと結合率L）が実際のネットワークの形態を決定する要素だと考えることが出来ます。 →　ページ（探索順） →　ページ（探索順）

17 4.3.3 リンク価値の高いページの分布状況 最大Hubリンク価値と平均価値との比較 極端にHubリンク価値が高いページの存在
4.3.3　リンク価値の高いページの分布状況 Start Point 平均Hub価値 最大Hub価値 倍率（最大/平均） HP 17.29 721 41.7 YY 22.07 1683 76.26 TEST 9.3 936 100.65 HUANG 5.85 829 141.71 最大Hubリンク価値と平均価値との比較 極端にHubリンク価値が高いページの存在 実験では、人工的ネットワークを生成する際に、リンクの結合率においては、一様分布をとりました。 しかし、実際のネットワークを分析したところ、ページHubリンク価値が極端に高いページがあることが分かった。このような現象はリンクの結合率を一様分布で決める人工ネットワークには発生していない。 図と表のように、個別のページに複数のページからのリンクが集中している現象はポアソン分布に相当すると考えられる。Hubリンクが集中するネットワークに近い人工ネットワークを作成する際に、リンクの結合率をポアソン分布で決めるような手法が考えられる。これは今後の課題の一つとして、研究を続けていく予定である。

18 4.3.4 まとめ ネットワークの分類 ① 高Hub価値、開放型ネットワーク。
4.3.4　まとめ ネットワークの分類 ①　高Hub価値、開放型ネットワーク。 　実用的なページが多く含まれ、ページとページの間にもリンクが積極的に張られている。実用性と便利性とも高い。 ②　高Aut価値、開放型ネットワーク。 　リンク集の多いページが多く含まれ、ページとページの間にもリンクが積極的に張られている。便利性の高いネットワーク。 ③　高Hub価値、閉鎖型ネットワーク。 　実用的なページが多く含まれてるが、ネットワーク外のページへのリンクが相対的に少ない。実用性高いが、便利性低い。 ④　高Aut価値、閉鎖型ネットワーク。 　ネットワーク内部ではリンクが多く張られているが、ネットワーク外のページへのリンクが相対的に少ない。実用性と便利性とも高くない。 これまでの結果をまとめるてみると、ネットワークの形態を主に以下の４タイプに分類できることが分かった。 ①高Hub価値、開放型ネットワーク。このタイプのネットワークは、Hubリンクの平均値が高く、ネットワークの開放度も高い。実用的なページが多く含まれており、ページとページの間にもリンクが積極的に張られている。実用性も便利性も高いネットワークです。 ②高Aut価値、開放型ネットワーク。このタイプのネットワークは、 Autリンクの平均値が高く、ネットワークの開放度の値も高いネットワーク。リンク集の多いページが多く含まれており、ページとページの間にもリンクが積極的に張られている。便利性が高いネットワークです。 ③高Hub価値、閉鎖型ネットワーク。このタイプのネットワークは、 Hubリンクの平均値が高いが、ネットワークの開放度は低い。実用的なページは多く含まれてるが、ネットワーク外のページへのリンクが相対的にすくない。企業や組織団体の内部ネットワークなどが、それの例である。 ④高Aut価値、閉鎖型ネットワーク。Autリンクの平均値が高いが、ネットワークの開放度が低いネットワーク。ネットワーク内部ではリンクが多く張られているが、ネットワーク外のページへのリンクが相対的にすくない。

19 5 課題 更なる各種のネットワークの分析 リンクデータの収集におけるデータベース方式の導入
5　課題 更なる各種のネットワークの分析 リンクデータの収集におけるデータベース方式の導入 情報や知識の分布とネットワークを構成する主客観的要素との関係の定量的分析 今後の課題として、このようにまとめました。 今回は、一回の実験における平均実験周期（約20時間）が長いため、実験で分析したネットワークの数が相対的に少ない。しかし、現実のネットワークの範囲は広く、もっとさまざまな形態のネットワークが存在することが考えられるので、もっと沢山のネットワークを分析する必要がある。 ページデータとリンクデータを収集する際に、それらのデータをテキストファイルに保存する方式をとっていた。この方法では、プログラムの構成がシンプルになり、プログラムの作成にかかる時間が少なくなるというメリットがあるが、テキストデータの計算処理時間がかかり、ハードディスクとメモリの容量が無駄になるというデメリットもある。解決策として、データベース方式を使うことが考えられる。 本研究では、対象のネットワークに対して、リンクの結合形態に関する分析を行った。今後、さらに、ネットワークにおける情報や知識の分布とネットワークを構成する主客観的要素との関係をさらに定量的に分析することで、両者の間の関係を明らかにして行きたい。

20 以上です。

21

22 4.3.4 実際への応用 ぺージ・ユーザーのグループ化 検索結果のランキング ツールの転用 ページ価値の数値化計算
4.3.4　実際への応用 ページ価値の数値化計算 ぺージ・ユーザーのグループ化 検索結果のランキング ツールの転用 　　ここでは、本研究で提案したネットワーク分析手法とそれに基づいて、開発されたツールの実際への応用について検討する。 (1)　ページ価値の計算： リンク価値計算により、各ページの価値を数量化することができるという点からページのリンク価値はページの分類をする時に一つの参考値となる。 (2)　ぺージ・ユーザーのグループ化： 趣味、嗜好でネットワーク内のページ・ユーザーをリンク構造によってグループ化することによって、新しいコミュニティの形成を支援する。 (3)　検索結果のランキング： ページ価値とリンク価値によって、ページ現有の検索エージェントを使って、得た膨大な量の結果を自動的にリコメンデーションすることができる。 (4)　ツールの転用： 本研究に使われたWebロボットや分析プログラムなどのツールはインターネットやネットワークのリンク構造を対象とするユーザーやコミュニティのグループ化などに関する他の課題に使うことができる。

23 2.2 Webページの価値とリンク価値 ページの価値 リンクの重要性 ページの価値とリンク価値の関係
2.1.1　現在、WWW上にある膨大な量のページは、さまざまな人々によって作られているため、ページの表現形式は当然異なり、その内容もそれぞれ違う。Webページの多様性がWebページをみる人にとっては、大きな楽しみとなっている。しかし、ページ価値を評価しようとすると大きな難問に直面する。なぜなら、言語処理的な解析でページ内容や価値を評価しようとすると膨大な計算時間を必要とするのみならず、評価基準にも多様なものが存在するからである。そこで、リンクの多さがページ内容に関する価値の高さを示していると仮定して、Webページの直接的な内容の解析は行わず、Webページのリンクに注目する。 2.1.2　WebページのLinkは、人間が自分の価値観と努力を基に作られたものなので、その人の価値観とその人が持っている情報や知識を（何らかの形で）含んでいると考えられる。実際、面白い、有用だと思われるWebページは沢山のページにリンクされている。また、あるページが沢山のページへリンクしているのであれば、そのページが便利なページだと思われる。故に、ページのリンク価値をページの価値の一部だと考えることができる。

24 2.2 Webページのリンク価値 ページのリンク価値を次の式で表す。 V： リンク価値 Hub（Ln）：Hub Link数、
V： リンク価値 Hub（Ln）：Hub Link数、 Aut（La）：Authority Link数 前述のリンクの重要性から、ここでは、Webページのリンク価値を以下のように定義する。 任意のページ i において、i のリンク価値は、i のHubリンク数とAutリンク数によって決まられると考えることができる。

25 2.3 リンクに関する仮説 ネットワーク世界においての人間の知識（価値観、趣味・嗜好を含む）はWebのリンク構造に強く依存して伝播する。
2.3　リンクに関する仮説 ネットワーク世界においての人間の知識（価値観、趣味・嗜好を含む）はWebのリンク構造に強く依存して伝播する。 人間が自分の価値観（趣味・嗜好を含む）に合うリンクをWebページに追加することは、Web世界における知識の流通につながる。 ページのリンク価値を前述のように定義すると、以下の仮説が立てられる。

26 3.3　Hubリンクの解析 WEBページのリンク解析を分析する際に、各ページに対して、Aut リンクは簡単にわかるのに対し、Hubリンクは普通に見えない構造となっている。目に見えないHubリンクの構造を解析するため、以下のようなアルゴリズムを考えた。 ページの集合をP、Lとし、a,b,c,d,e,fはそれぞれのページとし、 ( a , d ) , ( b , e ) , ( c , e ) , ( c , f ) , ( d , b )はそれぞれのAutリンクとする。 ①すべてのページのAut Linkから、Aut Link 集合Aを作成する。 ②任意の２つのページa , dに対して、a のAuthority Link ( a , d )は、dにとって Hub Link ともなるので、Authority LinkペアからHub Linkペアをつくる。 ③すべてのAuthority Linkペアがなくなるまで、②を繰り返す。 こうして、Autリンクペアの集合からHubリンクペアを作ることができる。

27 ４ 実験 4.1 実験の流れ ここで、実験の全体の流れについて説明する。
４　実験 4.1　実験の流れ ここで、実験の全体の流れについて説明する。 まず、Webロボットを使って、WWWからページデータ（つまり、HTMLファイル）を読みこみながら、HTMLファイルを解析して、リンクデータ抽出する。この作業は、あらかじめ設定した条件（ハードディスクの容量や時間など）が満たされるまで、ロボットが自動的にやりつづける。 次に、リンクデータを用いて、ネットワーク全体のリンク構造、ページのリンク価値などについて計算を行う。 最後、得られたリンク構造のデータをグラフ表示ツールに表示し、グラフと数字結果を使って、分析を行う。 次は、実験の結果について述べる。

28 4.4　（結果からの）Suggestion ネットワークの形状はネットワーク内の個体（Webページ）の特徴の表れであり、主・客観的な要素によって、ネットワークの特徴が決められる。 本研究では、対象のネットワークに対して、リンク構造の特徴についての分析を行い、以下のような結論が得られた。ネットワークの形状はネットワーク内の個体（Webページ）の特徴の表れであり、主・客観的な要素によって、ネットワークの特徴が決められると考えられる。ここでいう主・客観的な要素とは、人の嗜好、趣味、知識、情報及び人の所属団体、グループの構造やインターネットへの接続状況などのことである。われわれが得た実験結果は、ネットワークにおける情報・知識の分布及びネットワーク形態がこれらの要因と密接に関係する可能性を示した。さらなる定量的な分析をすることによって、その具体な関係を発見できるものと期待している。