スポンサーサイト

上記の広告は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.幅140px高さ260pxの画像を用意する。

2.画像のURLをこのテキストボックスに入れる。


3.このリンクを右クリックしてブックマーク
学祭ミスコン ブックマークレット

4.コンテストの公式ページに行く
第6回Mr.&Ms.東北大コンテスト
http://www.festa-tohoku.org/program/contest/contest.html


5.先ほどのブックマークを開く!
5人目のミス候補が現れます。

マウスを画像にのせたときの白いオーバーレイは実装しましたが、
名前やNo.5の記述は省略しました。
以下に元のコードを載せるので、誰かやって!


var imgurl = 'ms1.jpg';
var msul = $('ul').eq(1);
msul.children().attr('style','margin-right:25px;');
var newms = $('
  • ');
    newms.css({
    'position':'relative',
    'float':'left',
    'width':'150px',
    'height':'270px',
    'background-image':'-moz-linear-gradient(top,#931f20,#f29d80 50%,#931f20)'
    });
    newms.css('background-image','-webkit-gradient(linear,left top,left bottom,from(#931f20),color-stop(0.5, #f29d80),to(#931f20))');
    var msimg = $('');
    msimg.attr('src',imgurl);
    msimg.css({
    'position':'absolute',
    'top':'5px',
    'left':'5px',
    });
    newms.append(msimg);
    var overlay = $('
    ');
    overlay.css({
    'position':'absolute',
    'top':'4px',
    'left':'4px',
    'width':'142px',
    'z-index':'100',
    'height':'262px',
    'background':'rgba(255,255,255,0.15)'
    });
    overlay.hide();
    newms.append(overlay);
    newms.hover(
    function(){
    overlay.show();
    },
    function(){
    overlay.hide();
    }
    );
    msul.append(newms);

  • コードが書けたら以下のページで適当な形に変換すれば、
    ブックマークレット化できます。
    bookmarklet maker
    http://userjs.up.seesaa.net/js/bookmarklet.html

    Wikipediaでリンクを辿って遊ぶ

    Wikipediaでリンクを辿って遊ぶのがなかなか楽しいです。

    Wikipediaのあるページから全く関係のないページに、
    記事内のリンクだけを使ってどれだけ早くつけるか競うゲームです。
    例えば「リオネル・メッシ」から「貞子3D2」とか。

    リンクを辿るごとに目的の記事に近づいたり離れたりが
    なんとなくですがわかるので結構楽しいです。
    メッシなら「アルゼンチン入った!」とか「サッカーまで来た」とか。
    色々なルートがあるのも楽しいです。

    ゴールしたらそこからスタートすると辿ってる感がでるし、
    負けた方が次のゴール決めたり、
    「戻る」禁止にしたりルール次第でかなり面白くなると思います。


    こんな感じで遊んでいるうちに
    Wikipediaのページ間の距離(?)に興味がわいてきたので、
    Page view statistics for Wikimedia projects
    http://dumps.wikimedia.org/other/pagecounts-raw/

    からデータを頂いてきてpythonでいろいろやってみたので
    近いうちに記事にしようと思います。
    上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。