スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Wikipediaのアクセス上位10000ページの距離を計算した話

先日の記事の続きです。

Wikipediaでリンクを辿って遊ぶ
http://zaburoapp.blog.fc2.com/blog-entry-24.html


今回探したのはWikipediaに存在する記事のうち
最も距離のはなれている記事の組み合わせです。

ここで言う距離とは、ある記事から記事内のリンクのみを辿って行く時
何回リンクを踏めばその記事に辿り着くかを表した数字です。
複数あるルートのうち最も短いものをその組の距離としました。

さて、Wikipediaについてですが、
Wikipedia:全言語版の統計
http://ja.wikipedia.org/wiki/Wikipedia:%E5%85%A8%E8%A8%80%E8%AA%9E%E7%89%88%E3%81%AE%E7%B5%B1%E8%A8%88

によれば、2014年10月17日現在
純記事数は全言語総計でなんと33,448,472もあるそうです。
日本語のものだけで930,619もあるので
これをすべて解析するとなると人生が終わるまでに
計算し終わるかという問題が出てきます。

というわけで今回は、日本語版Wikipediaの記事のうち
ある日の閲覧数が上位の記事を一定数とって来て
その記事のみを対象にページ間距離を計算しました。

技術的なことは後日記事にするとして
早速結果を書いていきたいと思います。

まず2014年9月1日の閲覧数上位1000位に限定した場合の結果。
上位20位のみを抜粋しました。
---------------------------------------------------------

List of longest distance between Wikipedia pages
20140901 : Page view Top 1000

1: 8 続柄 -> 近江友里恵
2: 8 続柄 -> たちかぜ自衛官いじめ自殺事件
3: 8 国鉄105系電車 -> たちかぜ自衛官いじめ自殺事件
4: 8 七草 -> 近江友里恵
5: 8 七草 -> たちかぜ自衛官いじめ自殺事件
6: 8 カルトの集団自殺 -> 近江友里恵
7: 8 カルトの集団自殺 -> たちかぜ自衛官いじめ自殺事件
8: 8 特別:最近の更新 -> 近江友里恵
9: 8 特別:最近の更新 -> たちかぜ自衛官いじめ自殺事件
10: 8 カツオノカンムリ -> 近江友里恵
11: 8 カツオノカンムリ -> たちかぜ自衛官いじめ自殺事件
12: 8 城井鎮房 -> たちかぜ自衛官いじめ自殺事件
13: 8 奇皇后 -> 近江友里恵
14: 8 奇皇后 -> たちかぜ自衛官いじめ自殺事件
15: 8 標準偏差 -> 近江友里恵
16: 8 標準偏差 -> たちかぜ自衛官いじめ自殺事件
17: 8 青春18きっぷ -> たちかぜ自衛官いじめ自殺事件
18: 8 特別:検索 -> 近江友里恵
19: 8 特別:検索 -> たちかぜ自衛官いじめ自殺事件
20: 8 龍虎 -> たちかぜ自衛官いじめ自殺事件

---------------------------------------------------------

たちかぜ自衛官いじめ自殺事件の存在感が半端ないですね。
8回リンク踏むだけでいけちゃうということで
案外短くてがっかりしました。
105位まで距離8がありその後2500位くらいまで距離7が続きます。

思った以上に大したことが無い結果が出てしまったので
上位10000ページでもやりたいところですが、
上位1000ページでさえ20分程度時間がかかっていて、
最短距離の計算につかったアルゴリズムの計算量がO(n^3)なので
約1000倍の時間がかかることになります。

終わるまでの時間を計算してみた結果、
まあ現実的な時間で終わるだろうという数字が出たので
ここ数日ずっとパソコンをフル稼働させて計算していました。

そして、その結果が今日、出ました!
利用したデータは2014年10月1日の閲覧数上位10000ページ。
要した時間なんと261時間!
その結果は!

保存できませんでした!

というのも使ったパソコンには4GBしかメモリが積まれていないので
ターミナルの出力をコピーしようとした瞬間
ターミナルがフリーズして永遠の眠りについてしまいました。
何とかログの復旧を試みたのですが
89129689位以降というまったく意味のないデータしか復元できませんでした。

最も離れている距離は6だったのは確認しました。
1000ページの時より小さい結果となりましたが、
ページが増える事で新しいより短いルートが生まれたのだと思います。

結果が公開できないのは大変残念ですが、
そもそもいけないページを除けば、
6回リンクを踏むだけで大体のページ同士はいけてしまうというのは
10000ページに限られてるとはいえなかなか面白い結果だと思います。
普段みるようなページは大体10000ページの中に含まれていますしね。

250時間以上ずっと電源をつけて、ファンがまわるほど計算させていたので
使ったMacbook Airのバッテリーが心配になりました。
二度とやりません!

詳しい方法等はソースコードとともに後日記事にしたいと思います。
スポンサーサイト
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。