| 本アーティクルは The Mathematica Journal (volume 15, 2013) で発表されたもので、著作権は Wolfram Research, Inc. に属します。 |
| "This article was previously published in The Mathematica Journal (volume 15, 2013) and the copyright holder is Wolfram Research, Inc." |
本アーティクルでは World Wide Web 上でランダムウォークを実行し、結果のデータを視覚化するために開発されたパッケージである RandomWalkWeb を紹介します。パッケージの機能を使って、35,616 個のユニークな URL (おおよそ 133,500 ステップ) から成り立つ経験的なネットワークデータを収集しました。解析はドメインレベルで行われ、web のいくつかの特徴を評価しました。とりわけ、入次数と出次数の分布のためのべき乗則の指数 γ を推定し、それぞれ 2.10±0.09 と 2.36±0.1 を得ました。これらの値は以前に公表された結果とよく一致することが分かりました。
一般には単に web と呼ばれる World Wide Web (WWW) は、インターネットを介してアクセスできる広大な情報ネットワークです。web は、1989年に初めて提案され [1]、CERN（欧州原子核研究機構）の Tim Berners-Lee の仕事から生まれました。
web の中心となる二つのソフトウェア技術は Hyper Text Markup Language (HTML) と Hypertext Transfer Protocol (HTTP) です。web ページの HTML (もしくはソース) はドキュメントの内容を記述する要素であるタグを含んでいます。例えば、アンカー <a> タグは他のドキュメントへのハイパーリンクもしくはリンクとして定義されています。web 上のそれぞれのファイル (もしくはリソース) は Uniform Resource Locator (URL) によって識別されます。ブラウザもしくは他のユーザーエージェントはその URL を指定することによって、HTTP を介してファイルを要求します。応答、つまり要求されたファイル、は web サーバーからクライアントへ HTTP によって再び送信されます。
Web のような大規模で複雑なネットワークのトポロジーは、グラフ理論の方法を使うことで求めることができます ([2] とそのリファレンスをご覧ください)。具体的に言えば、web を有向グラフとして考えることができ、web ページが頂点、ハイパーリンクが辺に対応します。あいにく、web の本質に起因する２つの問題があります。(1) 全体をインデックス化 (もしくはマップ) することはできないことと、(2) 対応するグラフを分析することは非常に計算が大変であることです。実際に、最近の発表 [3] では、web は少なくとも 1012 個のユニークな URL が存在すると言われています。
その規模のサイズと複雑さにもかかわらず、web の構造を定量化するために使うことのできる有益な基準を求めることができます。ランダムウォークの方法を用いて、ネットワークをサンプリングし、web の部分グラフを調べることができます。
この方法では、ある URL から始めます。クライアントはその URL で web ページを要求し、サーバーはドキュメントの HTML で応答します。次に、クライアントはその web ページから全ての URL を抽出し、ランダムにそれらの一つを選択します。再度、クライアントは選択された URL のドキュメントを要求します。サーバーに到達できないか、その web ページが見つからない場合、クライアントはまた別の URL をランダムに選択します。全体のプロセスはその後、有限回数繰り返されます。
この記事の焦点は World Wide Web の研究のためにランダムウォークを利用することにあります。第２節では、web 上でランダムウォークを実行し、結果を可視化するパッケージである RandomWalkWeb の概要を述べます。次に、第３節では、パッケージの機能を利用して、ランダムウォークを実行し、ウェブをサンプリングします。収集された経験的なネットワークデータを分析し、web のいくつかの特徴を推定します。最後に、第４節では、結果の概略を示し、結論を述べます。
この節では RandomWalkWeb パッケージの概要について述べ、その機能を説明します。
RandomWalkWeb パッケージ (www.mathematica-journal.com/data/uploads/2013/09/RandomWalkWeb.zip) は Mathematica 8 で導入されたグラフやネットワーク機能に基づいて構築されています。web への接続は .NET/Link を介して提供されるため .NET Framewok 2.0 (もしくはそれ以降) が必要です。
パッケージには次の４つの領域をカバーする 28 のパブリックシンボルで構成されています: (1) データの収集と可視、(2) web ページコンポーネント、(3) URL の操作、(4)メッセージログ。それぞれのシンボルについてドキュメントが整備されていますので、Mathematica のヘルプシステムを通して簡単にアクセスすることができます。
パッケージの読み込みから始めます。
第１節で述べたように、web 上のシングルランダムウォークは、パッケージと同名の RandomWalkWeb 関数を使うことで実行できます。スタート (もしくは原点) の URL を、ステップの最大数 ns とともに指定します。
RandomWalkWeb 関数は訪れることに成功した URL のリストを返し、ここでは列で表示します。関数がノートブックベースのフロントエンドから評価された場合、ウォークの進行状況がウインドウのステータス領域に表示されます。有効な外部リンクを持たない URL に到達した場合には、RandomWalkWeb 関数は１ステップだけバックトラックを試みます。この関数は、途中で終了するかもしれません;
つまり、全てのハイパーリンクを試しても、返されるステップの数は ns より少ないかもしれません。
同じ URL から複数のランダムウォークを実行したい場合があります。これはPerformRandomWalks 関数を使うことによって実行できます。RandowWalkWeb 関数と同様に、開始する URL とステップの最大数を指定します。さらに、関数の２番目の引数として実行するランダムウォークの数 nw を指定します。
返される値は正常に出力されたデータファイルの数を示します。
データファイルを格納するために使用されるルートディレクトリは $BaseDataDirectory で指定されます。デフォルトでは、これは現在の作業ディレクトリに設定されています。
PerformRandomWalks 関数に渡されるユニークな URL ごとに、ルートデータディレクトリに、URL の 16 進形式の MD5 ハッシュ 32 文字の名称のフォルダが作成されます。それぞれのウォークの訪れることができた URL を、人間が読めるテキストファイルとして別にエクスポートします。それぞれのファイルの名前は $DataFilePrefix によって指定されたラベルとウォークナンバーの組み合わせです。
次の例では以前に収集されたネットワークデータ
(www.mathematica-journal.com/data/uploads/2013/09/RW_Data_1.zip から入手できます) を考察します。$BaseDataDirectory と $DataFilePrefix を指定することから始めます。
データは RandomWalkGraph 関数を使って簡単にインポートし、可視化することができます。ここでは、２つ目のランダムウォークから抽出された最初の７つのステップに興味を持っています。
最初の部分はグラフオブジェクトを返し、最後の部分は列挙された頂点のリストを含んでいます。RandomWalkGraph 関数が返す全てのグラフは単純有向グラフです。つまり、ループや複数の辺は含まれていません。
同様に、複数のデータファイルからグラフを作成することができます。ここでは、１つ目と３つ目のランダムウォークから全てのステップを組み合わせます。
グラフは VertexIcon オプションを使うことで視覚的に向上させることができます。VertexIcon を True にすると、RandomWalkGraph 関数は favorite アイコンをダウンロードし、デフォルトの頂点の形をそれに置き換えます。RandomWalkGraph 関数には組み込み関数の Graph と同じオプションを利用することができます。
この節では、RandomWalkWeb パッケージの機能を構築し、それをランダムウォークを実行するために利用して、web をサンプリングします。収集された経験的なネットワークデータを分析し、web のいくつかの特性を推定します。
この節で報告される時間は、組み込み関数 AbsoluteTiming を使い、カスタムワークステーション PC 上で測定しました。システムは Intel Core i7 CPU950@4GHz と 12GB の DDR3 メモリで構成されています。OS には Microsoft Windows™ 7 Professional (64-bit) を利用し、 MathematicaMark8 ベンチマークパッケージで 1.23 のスコアを出しました。
3.1.1 ランダムウォークとジャンプ
RandomWalkWithJumps という新しい関数を定義してみましょう。
RandomWalkWithJumps 関数は、スタートの URL へ戻る代わりにウォークの履歴のなかからランダムに選択された URL に "ジャンプする" という点を除き、PerformRandomWalks 関数（第２節を参照）と同様に機能します。ジャンプした先から、この関数はさらに追加の ns 個のステップを実行しようとし、そのプロセスが繰り返されます。最終的なウォークの数は nw = nj + 1 となります。ここで nj は指定されたジャンプの数です。
RandomWalkWithJumps 関数を使って経験的なネットワークデータを収集する前に、いくつかのパッケージパラメータを設定します。
次に、ログファイルの場所を変更します。(Appendix を参照)
最後に、一般的なユーザエージェント文字列を指定します (Appendix を参照)。
このウォークのゴールは合計 150,000 ステップを実行することです。
RandomWalkWithJumps 関数を評価します。
web 上で約26時間後に関数が終了しました。得られたリストには、要求されたステップ数の約89%が完了したことを示されています。さらに、35,616 のユニークな URL を訪れたことが分かります。
3.2.1 データ入力と可視化
RandomWalkGraph 関数を使って、収集した経験的なネットワークデータ
(www.mathematica-journal.com/data/uploads/2013/09/RW_Data_2.zip からダウンロードできます)をインポートします。組み込み関数 Range はファイル番号の一覧を生成するために使われます。
関数が Graph オブジェクトと頂点のリストを返すまでに、約68秒かかります。
同時に、それらはドメインレベルの分析を実行するために必要な情報を含んでいます。
3.2.2 基本的な基準
Mathematica の組み込み関数を使って、データからいくつかの基本的なグラフの基準を抽出します。
n をグラフの頂点の数 (すなわちドメイン名) とします。
同様に m を辺の数 (すなわちリンク) とします。
一般に、頂点 i の次数 ki はその頂点に接続されている辺の総数です。例えば、VertexDegree 関数を使って、指定したドメイン名に接続されているリンクの数を取得することができます。
グラフの平均次数 c は
で与えられます。
頂点が指定されていない場合、VertexDegree 関数はグラフのすべての頂点の次数のリストを返します。経験的なネットワークデータから c を計算すると、その後は簡単です。
ここで、c から平均絶対偏差を求めます。
3.2.3 入次数と出次数の分布
有向グラフの場合、頂点は入ってくる辺と出ていく辺の数それぞれと等しい入次数と出次数があります。
pkin を入次数 k を持つ有向グラフの頂点の割合とします。同様に pkout を出次数 k を持つ頂点の割合とします。これらを計算するために二つの関数を定義します。
pkin と pkout はランダムに選ばれた頂点が入次数と出次数 k を持つ確率と見なすことができます。たとえば、経験的ネットワークデータを用いて、7つの入力リンクを持つドメイン名をランダムに選ぶ確率を計算することができます。
次数の分布を可視化するために組み込み関数 Histogram を用います。
3.2.4 べき乗則次数分布
web の入次数と出次数の分布が、べき乗則に従うことが知られています [4] 。ここでは、収集した経験的ネットワークデータを用いて、それらの結果を再現してみます。入次数の累積分布関数 (CDF) を定義します。
ここで kmax(i) はグラフの入次数の最大値で、pjin は前に定義した入次数 j の割合です。出次数の CDF Pkout についても同様に表現することができます。
次に、全ての次数ドメインにわたるデータを生成するため、両方の関数を使います。
得られた CDF データを、組み込み関数 ListLogLogPlot を使って可視化します。
log-log プロットは web の次数分布がべき乗則に概ね従うことを示します。
次数分布が k ≥ kmin のとき k -γに比例していると仮定してみましょう。kmin はべき乗側が成り立つ最小の次数です。[5] に従って、最尤推定量 (MLE) 
を用いてべき乗指数を推定します。
N は k ≥ kmin となる頂点の数です。この近似は kmin ≳ 6 のとき正確です。 の標準誤差は
で与えられます。式 (3) と (4) を次の関数に取り込みます。
PLExponentEstimated 関数を評価すると、べき指数の推定値が得られます。
ここで、kmin の最小値が使われています。web の入次数と出次数の分布はそれぞれ γin = 2.10 ± 0.09 、γout = 2.36 ± 0.1 となることが分かります。これらの値は [4] で報告されたものとよく一致しています。
3.2.5 トップレベルドメインの分布
データの中のトップレベルドメイン (TLD) の分布について考察します。TLD の例としては、com、net、org などがあります。
はじめに、列挙された頂点のリストからドメイン名を抽出します。それからドメイン名の最後の部分を取り出し、EffectiveTLDNAmeQ 関数 (Appendix を参照) を用いて結果をフィルタします。
次に、TLD の総数を求め、リストを集計します。
TLD の相対的な頻度を計算し、相対頻度と TLD のアルファベットの順にデータをソートします。
最後に組み込み関数 BarChart を使って結果を可視化します。
ここでは、TLD の top15 の相対的な頻度が比較されます。
この記事では、World Wide Web上でランダムウォークを実行し、結果のデータを可視化するために開発された RandomWalkWeb パッケージについて述べました。パッケージの関数を利用して、35,616 のユニークな URL を含む経験的ネットワークデータを収集しました。ドメインレベルの分析を行い、いくつかの web の構造上の特徴を評価しました。入次数と出次数の分布を考察し、それらがべき乗則で近似できることを検証しました。べき乗則の指数は γin = 2.10 ± 0.09 と γout = 2.36 ± 0.1 と推定され、以前に公開された結果とよく一致しました。
RandomWalkWeb パッケージは Mathematica 8 で導入されたグラフやネットワーク機能に依存しています。またパッケージは .NET Framework によって提供されるクライアント-サーバー通信機能を利用するように設計されています。.NET/Link を使うという選択は、パッケージの機能にはあまり影響を与えませんので、例えば J/Link のような他の技術を利用するために関数を再実装することも、おそらく簡単な作業でしょう。
RandomWalkWeb パッケージは様々な方法で改善や拡張できます。例えば、コードを RandomWalkWeb 関数のように関数を並列サブカーネルで評価するように変更できます。別の可能性としては、さらに入念に web の構造を探索することのできるフル機能の Mathematica ベースのクローラーを構築することもできるでしょう。
最後に、Mathematica は Wolfram|Alpha の基盤となっているので、World Wide Web に関するユーザのクエリにグラフ理論的な答えを返す web ベースの計算知識エンジンを容易に想像することができるでしょう。
この Appendix では、RandomWalkWeb パッケージの設計と実装に関するいくつかの詳細について述べます。完全にドキュメント化されたソースコードを確認することを強くお勧めします。
GetSource
web 上でランダムウォークを行うための最初の操作は、web ページの HTML (もしくはソース) を要求し、取得することです。これを実現する最も簡単な方法は組み込み関数 Import を使うことです。
しかしながら、この方法には少なくとも一つの欠点があります。ウェブサイトは異なるデバイス (例えばモバイルとデスクトップ) に異なるコンテンツを提供するように構成することができます。リクエストを行うデバイスのタイプを検出するために様々な方法があります。
具体的には、クライアントによって送信された User-Agent HTTP ヘッダーを解析するサーバーもこのような技術の一つです。クライアントソフトウェアは要求時に、サーバーがクライアントを識別できるようにこのヘッダーを使います。例えば、Mathematica 8 を使い、Import 関数に URL を渡すと、サーバーはユーザエージェント文字列として “Mathematica /8.0.4.0.0 PM/1.3.1” を取得します。残念ながら、この文字列は変えることができません。
この制約を回避するために、RandomWalkWeb パッケージは GetSource 関数という独自の HTML インポート機能を実装しています。この関数は .NET ランタイムと通信するために .NET/Link を用います。HTTP 要求時に、GetSource は $UserAgent に割り当てられた文字列を送信します。
GetSource 関数を用いて、Web ページの HTML を要求し、取得することができます。
返されたリストの最初の部分が応答アドレスです。通常、このアドレスは、要求した URL と同じです。しかし、1つまたはそれ以上のリダイレクトが原因で異なる場合があります。最後の部分は Web ページの HTML を含んでいます。
一般的なモバイルデバイスをまねる $UserAgent を設定してみましょう。
今回は GetSource 関数に URL のリストを渡し、応答側アドレスを調査します。
ここでは、GetSource 関数がリダイレクトに従い、モバイル固有のアドレスから HTML を取得していることが分かります。ユーザエージェント文字列を変更する機能を持つことで、いわゆる "mobile web" 上でランダムウォークを実行することを可能にします。
DomainName
RandomWalkWeb パッケージは URL に関して役立つ操作を実行するいくつかの機能を含んでいます。 例えば、DomainName 関数はスタンドアロン形式と RandomWalkGraph 関数や関連する関数で内部的に使われます。 その名前が示唆するように、指定した URL からドメイン名を抽出します。
DomainName 関数の中心に、データファイルからインポートされ、初期化中にメモリに格納される既知の有効な TLD、または公開されたサフィックスのリストがあります。有効な TLD の例には、com、co.uk および nj.us があります。ファイルはパッケージのルートディレクトリの下の Data フォルダにあります。それはユーザ指定の追加によって増強された基本リストから構成されています [6]。
$ETLDNInfo を評価し、返されたリストの最後の部分を調べることで、データファイルの中の有効な TLD 名の数を確認することができます。
DomainName 関数は最初にホスト名をコンポーネントのリストに分割することによって動作します。
次に、この関数は返されるリストの最後の部分を取得して、EffectiveTLDNameQ 関数を使って、既知の有効なトップレベルドメインであるかどうかを確認します。そうであれば、リストの最後から2番目の部分が文字列の先頭に追加され、ドット (ピリオド) で結合します。再び、文字列がテストされます。文字列を増やして検証するプロセスは、EffectiveTLDNameQ 関数が False を返すまで続けられます。
有効な TLD が決定できない場合、DomainName 関数は Hostname と同じものを返します。
メッセージロギングが有効になっている場合 (この Appendix の後述参照)、DomainName 関数は後のレビューのためにエラーとホスト名を記録します。 その後、ユーザはデータファイルの適切なセクションに、欠けている有効な TLD を追加するかどうかを決めることができます。
LogMessage
コード開発中は、詳細なエラーメッセージ (例えば .NET exceptions) を調査したり、関数の実行経路を追跡することがしばしば必要です。これは関数が数百や数千回繰り返し呼び出される場合には特に困難になります。これらの理由から、RandomWalkWeb パッケージのいくつかの関数は、プレーンテキストファイルにエラー、情報およびデバッグレベルメッセージを書き込むように設計されています。
デフォルトでは、メッセージは $TemporaryDirectory によって指定されたディレクトリに書き込まれます。$LogFileName を評価すると、ログファイルのフルパスが表示されます。
ファイルの名前や場所を変更することは自由にできます。またメッセージロギングは $LogFileName に空の文字列を割り当てることによって、無効にすることができます。
重要性のレベルを指定し、ログファイルにメッセージを書き込むために LogMessage 関数を使います。
メッセージがファイルに追加されたことを確認することができます。
家族のゆるぎない忍耐とサポートに感謝します。
T. Silvestri, "Random Walks on the World Wide Web," The Mathematica Journal, 2013. doi:10.3888/tmj.15-9.