SATソルバーを使ってBrainfuckのプログラムを実行するというネタのLTです。

[全画面/表示されない場合]

詳しくはgithubのリポジトリへ。

巨大なグラフ1を階層的に纏め上げてくれるLouvain Method(Blondel, et al. [2008])というアルゴリズムの論文と、これをリアルタイム可視化に用いている(Praneenararat et al.[2011])論文を発見して、面白そうだなぁと思ったので（小学生並みの感想）、ニコニコデータセットに適応してやってみました。

明日、日曜日（4/26）に「ニコニコ超会議」内の「ニコつく」でサークルの一つとして展示します。I19です。

デモサイトはこちら

(2018/04/24: メモリの圧がキツいので終了しました）

ネットワーク・クラスタリング

ニコニコ動画へのタグって、ふつう「アニメ, 遊戯王, この虫野郎」みたいな感じで相互に関連するタグが付けられますよね。

このタグ同士の関連をネットワークとして可視化したら、ニコニコ動画の中でどんな概念同士がリンクしてるのかなー、とか、詳しくないジャンル2でどんなワードが流行っているのかなー、とかが一目で把握できそうです。

というわけで、今回はタグを頂点、辺を 「同じ動画に付けられている回数（共起回数）」としたグラフ（ネットワーク図）を作り、可視化してみました。

それだけ？って感じかもしれませんが、実はグラフをそのまま表示しただけでは頂点も辺も数が多すぎて人間には解釈不能な「Hair-ball graph（髪の毛もじゃもじゃグラフ）」になってしまいます。たとえば、ノードが1万4000のグラフを可視化した結果がこんな感じだそうです。

うーむ、とてもじゃないけど、人間には読めない図です。今回は15万タグを対象としたので、この10倍ほどの頂点とエッジがあります。

この問題に対処するために、可視化する前にタグを階層的にまとめるクラスタリングを行います。たとえば、「ぽいぽい教」や「金剛」タグをまとめて「艦隊これくしょん」クラスタを作り、さらに「艦隊これくしょん」と「ご注文はうさぎですか？」や「きんいろモザイク」とまとめて「アニメ」クラスタを作るわけです。その状態で可視化を行えば、先ほどの図のように「ゲーム」「音楽」「アニメ」みたいなざっくりとした関係の図が出来上がります。

もちろん、その纏めた「アニメ」クラスターの中身もダブルクリックすれば見ることができます。ニコニコデータセットはそこまで最近のデータはないので、例として2011年データから「IS（インフィニットストラトス）」のクラスタを持ってきました。

わたし自身はこのアニメを見てないのであまり詳しくないのですが、一時期エースコンバットとのMADが流行っていたのと、（キャラ名）党っていうタグでお気に入りのキャラクタを示す文化があるのがわかります。

今回の売りは、この集計を「その場」で行っていることです。従来でもさいころ [2013], tasukuchan [2009]など可視化は行われているのですが、基本的には「事前に」集計しておいて、それを可視化しています。しかし今回のシステムでは、表示するたびに毎回、15万ノード＋200万エッジの大規模なグラフを、クラスタリングしつつその場で可視化してしまいます。かかる時間はさくらのVPS2Gのような非力なマシン１台でも2秒以下です。

今回これをやった本心としては「データの分析をして知識をマイニングしたい！」とかよりは「この超高速なクラスタリングアルゴリズムを使ってみたかった」という感じなので、実際にこのソフトウェアから有益な知識が得られるかどうかは微妙です。客観的評価とかもとくにしてないし、まぁそのへんはご愛嬌。

タグネットワークで時間旅行

今回のシステムのもう一つの売りは、高速性を活かしてインタラクティブに集計期間を変更して好きな時期のデータをその場で可視化できることです。

上のバーを左右に動かすことで、時間を行き来しながらネットワークの様子を可視化できます3。

初音ミクの居ない頃のニコニコ動画

たとえば、初音ミクはニコニコ動画文化を象徴するものだと言っていいと思うのですが、できた当時の2007年すぐには初音ミクはありません。なので、2007年の最初期のデータで可視化すると初音ミクがなかったころのニコニコ動画が見えます。

最近はもう見なくなったものもちらほらありますが4、今でも人気な作品も多いですね。「涼宮ハルヒの憂鬱」はアニメなのにアニメクラスタに入っていませんが、このような人気な作品はそれ自体が大きなコミュニティを形成しているので、独立して一個のクラスタになることがよくあります。また「ヘタリア」みたいな腐女子向け作品がちょくちょく独立してますが、腐女子向け作品は「アニメ」「ゲーム」タグと同時につかない動画が多いのが原因みたいです。

2011年3月

時間を行き来しながら見ると、時事ニュースによるその時の流行タグも自然と浮上してきます。たとえば、2011年４月の画面を見てみましょう。

右下のほうに「東北地方太平洋沖地震」とありますね。一ヶ月弱前にあった地震を扱った動画がたくさん投稿されていたことがわかります。ちなみに中はほとんど政治的な動画で、みんな大好き「あいさつの魔法。」は「エンターテインメント」の中に入ってます。ただいマンボウ。

昔の流行の思い出に浸るもよし、新規ジャンル開拓に使うもよし、まぁなんか暇つぶしにご活用ください。

「超大規模なグラフをその場で可視化して仮説発見に役立てる」というのはPraneenararat et al.[2011]. が元ネタです。彼らはバイオインフォマティクスで日々生まれる膨大なデータを素早く可視化するために使っていますが、これをニコニコ動画に適応したらどうなるかなーと考えた所、こんな感じになりました。

ソースコード

ソースコードはこちらに置いてあります。

• ledyba/NicoGraph

結果を再現するためのプログラムが全部置いてあるので、あなたも自分のサーバで動かすことができます。データはNIIのサイトからダウンロードしてきてください。

また、クラスタリングアルゴリズムであるLouvain Methodの実装はゼロから書き起こした物を使っています。元の実装よりも少し制限がキツい（エッジの重みがintのみ）いのですが、その分だけ頑張って高速化して、だいたい３倍ぐらい速いです。

• ledyba/cpp-louvain-fast

現状の問題点

• 多くのタグを一度にまとめてしまって、部分的に一部のクラスタ以下がHair-ballになって破綻することが稀によくあります。
• 実装がマルチスレッドになってないので本当に何人も同時にアクセスするとサーバが沈黙します。優しくしてあげてください。
• 
  ！データがいまいち古い！
  ドワンゴ氏〜〜〜〜
  最新のデータくだされ〜〜〜〜〜〜〜〜〜

他のデータでもやってみたい？

もしも、「ニコニコデータセットじゃなくてウチのデータセットでもやってみたいんだけど…」という方が居た場合はご相談ください。本当に有益な情報をマイニングしようとするとここから更に何段階か努力しないといけないとおもいますが…。

1. 頂点と辺からなる方 [↩]
2. わたしは鉄道とか全くわからない [↩]
3. 集計に使う長さは約二週間分 [↩]
4. ひぐらしのなく頃にとかね… [↩]

大昔に作った「ソーシャル地球儀」っていうWebアプリを公開してないことに気がついたので記事を書いておきます。Twitterの位置情報付きのPublicStreamをリアルタイムでGoogleMaps上に表示するWebアプリです。

大したことはないソフトウェアですが、リアルタイムで「いま世界中で呟かれているさま」を眺めていると「おお、地球上にはたくさんのニンゲンおり、皆それぞれに生きておるのじゃなぁ」というまるで10万10歳のロリババアかなにかのような達観を得られるのでオススメです（？）

もうちょっと人間くさいことをいうと、アフリカはやっぱりあんまりツイートないんだなとか、やっぱり今昼の時間帯のところで活発にツイートされてるんだなとか、色々気づきがあります。疲れたときの暇つぶしにどうぞ。

フレームワークにはScalatraを、JSとの連携にはAtmosphereを使っています。ユーザーごとの状態とかはとくに持ってないのでそんなに複雑なソースではないです。

ソースはこちらです。

• ledyba/twitter-globe