リンク構造解析によるページの価値計算とネットワーク分析知識システム構築論講座林研究室黄林春発表の構成 1 2 3 4 背景と目的定義アルゴリズム分析方法と結果 1 研究の背景と目的 1.1 研究の背景 • WWWの成長。 • 的確な情報入手の困難さ。 • 情報の移動経路や流通ルートの不明瞭さ。 1.2 目的 • リンク構造を利用して、情報の分布や流通経路と、ネットワークの形態との関連性を探す。 2 概念と定義 • リンクの重要性リンクの多さ＝ページに関する価値の高さと仮定ページのリンク価値＝ページのリンク数（HubとAut） • リンクの分類 HubリンクとAuthorityリンク Authority Link Hub Link 3 研究手法とアルゴリズム 3.1 ネットワーク分析の手順 ① ページ（HTMLファイル）及びリンクデータの収集 ② リンク構造の解析 ③ ページのリンク価値等，評価値の計算 ④ データのグラフ化、ネットワーク分析 3.2 Webロボットの動作 ① 探索開始ページの HTMLファイルを読み込み、リンクデータをリストに記憶する。 ② リストからリンクデータを取り出し、リンク先のページを読み込み、リストに追加する。 ③ 設定条件が満たすまで②を繰り返す。 Webロボットの並列分散処理環境の実現 4 結果と考察 4.1 実験の項目 ① 実験の対象 • WWW（Java、Hp…12個） • 人工的ネットワーク（25個） ② 比較項目 • Hubリンク数（総・平均） • Autリンク数（総・平均） • ネットワーク開放度（後述）… 4.2 実験の結果 4.2.1 Autリンク価値の高いページは、そのページの Hubリンク価値も相対的に高い。 SP java 前半の平均Aut数 42.38 前半の平均Hub数 13.15 後半の平均Aut数 7.36 後半の平均Hub数 2.07 全体の平均Aut数 24.87 全体の平均Huｂ数 7.61 （Java）のリンク数の分布表分布図（Autリンクでソートした結果） 4.2.2 リンク価値の分布について Start Point Page数 A-Links A-Links 平均 H-Links H-Links 平均 Huang Yy 1460 609 7800 13441 5.34 22.07 3495 2474 2.39 4.06 ネットワーク区域ごとにリンク価値の平均値とパタンが大きく異なる 4.2.3 明確な目的を持って作ったページはそうでないページよりページのリンク価値が高いネットワーク平均Hubリンク価値平均Autリンク価値 Shino（個人サイト） 2.89 6.47 Java（Java言語サイト） 7.61 24.87 リンク数の比較（平均）リンク数の比較（分布）ある個人のサイトあるJavaのサイト 4.3 考察 4.3.1 ネットワークの開放度と開放型ネットワーク回収されないリンク Network ネットワーク開放度のイメージ探索できた範囲開放度の意義 • ネットワークの開放度が高ければ高いほど、情報や知識の交流も行いやすいと考えられる。 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 各ネットワークの開放度 4.3.2 人工的ネットワークとの比較 Regular Small　World  0 Random  1 Increasing randomness 規則正しい（ρ=0）中間的な領域（0＜ρ＜ 1）無秩序（ρ=1） 4.3.2 WWWと人工ネットワークとの比較実際のネットワーク人工的ネットワークリンク価値リンク価値 ↑ ↑ → ページ（探索順） → ページ（探索順） 4.3.3 リンク価値の高いページの分布状況 Start Point HP YY TEST HUANG 平均Hub価値 17.29 22.07 9.3 5.85 最大Hub価値 721 1683 936 829 倍率（最大/平均） 41.7 76.26 100.65 141.71 最大Hubリンク価値と平均価値との比較極端にHubリンク価値が高いページの存在 4.3.4 まとめ •ネットワークの分類 ① 高Hub価値、開放型ネットワーク。実用的なページが多く含まれ、ページとページの間にもリンクが積極的に張られている。実用性と便利性とも高い。 ② 高Aut価値、開放型ネットワーク。リンク集の多いページが多く含まれ、ページとページの間にもリンクが積極的に張られている。便利性の高いネットワーク。 ③ 高Hub価値、閉鎖型ネットワーク。実用的なページが多く含まれてるが、ネットワーク外のページへのリンクが相対的に少ない。実用性高いが、便利性低い。 ④ 高Aut価値、閉鎖型ネットワーク。ネットワーク内部ではリンクが多く張られているが、ネットワーク外のページへのリンクが相対的に少ない。実用性と便利性とも高くない。 5 課題 • 更なる各種のネットワークの分析 • リンクデータの収集におけるデータベース方式の導入 • 情報や知識の分布とネットワークを構成する主客観的要素との関係の定量的分析以上です。 4.3.4 実際への応用 (1) ページ価値の数値化計算 (2) ぺージ・ユーザーのグループ化 (3) 検索結果のランキング (4) ツールの転用 2.2 Webページの価値とリンク価値 • ページの価値 • リンクの重要性 • ページの価値とリンク価値の関係 2.2 Webページのリンク価値 • ページのリンク価値を次の式で表す。 Vi  {Hub( Lh ), Aut( La )} V：リンク価値 Hub（Ln）：Hub Link数、 Aut（La）：Authority Link数 2.3 リンクに関する仮説 • ネットワーク世界においての人間の知識（価値観、趣味・嗜好を含む）はWebのリンク構造に強く依存して伝播する。 • 人間が自分の価値観（趣味・嗜好を含む）に合うリンクをWebページに追加することは、 Web世界における知識の流通につながる。 3.3 Hubリンクの解析４実験 4.1 実験の流れ 4.4 （結果からの）Suggestion • ネットワークの形状はネットワーク内の個体（Webページ）の特徴の表れであり、主・客観的な要素によって、ネットワークの特徴が決められる。