|
Broder, Andrei.1, Kumar Ravi.2, Maghoul Farzin.1, Raghavan, Prabhakar.2, Rajagopalan, Sridhar.2, Stata Raymie.3, Tomkins, Andrew.2, Wiener, Janet.3 "Graph structure in the Web". Proceedings of the 9th World Wide Web Conference. (2000)
1: AltaVista Company, San Mateo, CA., 2: IBM Almaden Research Center, San Jose, CA., 3: Compaq Systems Research Center, Palo Alto, CA.
※図表、注・引用文献は原文献をご参照下さい。
1. はじめに
Webを有向グラフ（directed graph）と捉え、その様々な特性を理解することには以下のような誘因が存在する。
①Webにおけるクローリング戦略の設計のため、②Web上のコンテンツの社会学的な理解のため、③リンク情報を活用するアルゴリズムの振る舞いを分析するため、④Web構造の進化を予測し、より良いアルゴリズムを開発するため、⑤Webグラフ上の新たな現象の発生を予測するため。
1.1 主要な結果（→以下の内容と重複するため割愛）
1.2 関連する先行研究
本研究と関連する先行研究は、（1）Webにおける指数分布の特定、（2）Webに対するグラフ理論の手法の適用、といった二つの領域に大別される。
これまで、指数法則は、Pareto、Yule、Zipfらによって、様々な社会現象の中に見出されてきたが、Web上では、利用者の振る舞いやアクセス・ログの集中度、もしくは、Webグラフの次数（degree）の分布に当てはめられている。
一方、グラフ理論は、Webにおける情報探索等のために応用されており、すでに、その有効性が示されていると言える。
本研究におけるWebグラフでは、ページ内のテキストや他のコンテンツは無視し、ページ間のリンク関係にのみ注目する。
1.3 用語解説
BFS（breadth-fast-search）とは、頂点vに隣接する全てのページを訪れてから、より深い階層のページをトラバースしていくというアルゴリズムであり、DFS（depth-fast-search）と対をなすものである。
2. 実験と結果
2.1 装置
全ての実験はConnectivity Server 2（CS2）を用いて行われた。
CS2は12GBのRAMを持つ465MHz Compaq Alpha Server 4100であり、約4分間で1億ページに到達することが出来る。
また、ここでは、AltaVistaのクローリングの結果もたらされたデータを使用している。
AltaVistaのクローリングでは、特定のサーバに負荷をかけすぎないような工夫が施されている。
実験は1999年3月に行われ、CS2のデータベースには、2億URL、14億リンク（合計9.5GB）が保存された。
実験のうち幾つかは、1999年10月に再度繰り返された（2億URL、21億リンク）。
2.2 実験データ
実験のために、BFSを基本とした三種類の基本的なアルゴリズム（BFS, WCC, SCC）がCS2に実装され、それぞれの目的のために使用された。
実験結果を以下に示す。
次数の分布（Degree distributions）．
Webにおける入次数（in-degree）と出次数（out-degree）の分布については、指数法則が見出されるとする先行研究の結果を改めて支持した。
対数線形回帰によって推定された入次数の指数である「2.09」は、同じく「2.1」としたKumerらの二年以上前の結果と驚くほど一致している。
同様に、対数線形回帰を行った出次数については、その指数が「2.72」と推定されたが、出次数の少ないページ群においてはあまり当てはまりが良いとは言えないため、今後、他の分布型の適用を試みることが望まれる。また、1999年3月と10月の結果はいずれも極めて似通っていた（→図1, 図2, 図3, 図4）。
無向連結部分（Undirected connected component）．
次に、Webを無向グラフとして扱い、その規模を把握することを試みた。
その結果、リンクが正逆双方向にたどれる場合、全体の91％に当る1億8600万のページが到達可能であることが明らかになった。
これは極めて入次数の多い一部のページ群の存在のみによってもたらされたものではないと考えることが妥当である（→表1）。
したがって、よく連結されたWebグラフの一部にPageRankの高い、もしくは、hubやauthorityとなるようなページ群が含まれているに過ぎないのだと言える。
これはHITSのようなアルゴリズムで、なぜ早く収束し得るのかという説明にもなっている。
強連結部分（Strongly connected components）．
同様に、有向グラフとして扱った場合、全体の約28％にあたる5600万ページが到達可能であった。
無作為な始点．
無作為に選択された570のページから、BFSアルゴリズムによって、リンクを正逆それぞれの方向にたどっていった。
その結果、90ページ程度の小さな集合に到達した後に消滅したもの、もしくは、1億ページ程度まで到達するものという二極に分かれた。訪れたページの累積分布が図7に示されている。
Zipfの法則と指数法則．
入次数の分布は、指数法則だけでなく、順位（ここでは、逆順位）を用いたZipfの法則にも適合する。図8は、両者を同一のグラフ上にプロットしたものである。
3. 解釈
以上の結果から、Webグラフにおける強連結部分（SCC：56,463,993ノード）以外の部位とそのサイズを明らかにする。
リンクを正順にたどってSCCへと繋がる部分（IN：43,343,168ノード）、及び、リンクを逆順にたどってSCCへと繋がる部分（OUT：43,166,185ノード）、INやOUTにぶら下がっている「つる（TENDRIL：43,797,944ノード）」などが存在する（→図9、表）。
3.1 TENDRILとDISCONNECTED
われわれのサンプルには172のTENDRILとDISCONNECTEDが含まれていたが、両者を弁別することは出来なかった。
また、ここからout-linkをたどっていくと、到達可能な全てのページを訪れ尽くすまでに平均20ページ、in-linkをたどった場合は平均52ページを訪れる。
3.2 INとOUT
同様に、OUTからout-linkをたどった場合は平均3093ページ、また、INからin-linkをたどった場合は平均171ページを訪れている。
3.3 SCC
SCCからin-linkをたどっていった場合のリンクの深さは（Min.475, Avr.482, Max.503）であり、同様に、out-linkをたどっていった場合は（Min.430, Avr.434, Max.444）であった。
3.4 直径と平均連結距離（Diameter and average connected distance）
Webグラフにおける「任意の2頂点間の距離（＝2頂点間の最短経路）の最大値（＝グラフの直径）」は少なくとも503であるが、実際には、SCCを介さないで、INから直接OUTに繋がる「チューブ（TUBE）」が存在するため、その値は905（＝475+430）に近い値となるだろう。
また、570のサンプルページからの平均連結距離は、それぞれ、in-link（16.12）、out-link（16.18）であり、無向グラフの場合6.83であった。
これは、平均距離が19であるとしたAlbert & Barabasiの結論を支持している。
|