実習に用いるファイルはこちらからダウンロードして下さい．
この実習のために配布したデータは，元々は理学部情報科学科に在籍していた鶴見敏行さんが国際学会での発表のために準備したものを用いて，この実習のために一部を取り出したものです．鶴見さんの英文論文を和訳したものは，この授業のテーマの論文執筆の実習でも利用します．
まず，簡単に「大規模社会ネットワークからのクラスタ構造の抽出」と題する鶴見さんの研究の内容について紹介します．ここで社会ネットワークとは，人間関係を意味します．いまではミクシィといえば，モンスターストライクというスマートフォン向けのゲームを思い浮べるかと思います．でも，１０年前のミクシィは日本最大のソーシャルネットワーキングシステム(SNS)を運営していました．当時は誰しもがミクシィをしていた時代で，計算機演習室でも授業を聞いていない人の画面はミクシィカラーのオレンジだったので遠目でもすぐに見つけることができたくらいです．
鶴見さんが研究したのは，ミクシィがサービスを急激に拡大していた時期で，ミクシィのサービスを利用している人々の友人関係を分析することで，人々に共通する関心事を見つけられるのではないかという点に興味を持っていました．また，そのような特性を見極めて，当時のやや不安定だったミクシィのサービスの効率を改善することも隠れた目標でした．
彼の研究に先だつ数年前に，社会ネットワークのなかから濃密な人間関係を高速に見つけられる手法の研究が始まっていました．当時，もっとも注目されていたのがClausetらが提案し，鶴見さんの論文のなかでCNM手法と読んでいる方法です．それまでの提案では，数千人程度の小さな規模の社会ネットワークしか分析できなかったのですが，CNM手法を利用することで十万人規模のネットワークの分析ができ，Clausetの論文には数百万人規模のネットワークへの応用も示唆されていました．
そこで鶴見さんがCNM法のプログラムを作成し，ミクシィから取得した９０万人程度の友人関係のネットワークの分析を始めました．最初の予想では数日で結果が出るかと思っていたのですが，一週間たっても分析は全体の１０％も進みませんでした．鶴見さんはほかの勉強もしながら，そのプログラムを動かせっぱなしにしていたのですが，一月たった様子から分析には半年以上がかかることが明らかになってきました．巨大な社会ネットワークにCNM法を適用すると最初は効率がよいのですが，だんだんと非効率になる傾向があります．この様子を可視化したグラフが図２：ネットワークの解析に要した時間の時系列遷移です．
当初の予定では，分析はあっという間に終ることを期待し，分析結果からなにかを発見するつもりでした．でも，思いがけないことに分析がなかなか終らないため，予定を変更し，分析手法自体を研究することにしました．
まずは，Clausetが数百万まで応用できると書いているにも関わらず，分析がなかなか終らない原因について調べました．そこから明らかになったのは，鶴見さんの論文のなかで提案している合併比率と呼ばれる指標にかかわる問題でした．詳しい内容は鶴見さんの論文を読んでいただくことにしますが，合併比率が悪化した様子を表した結果が今回配布する図３：CNM法におけるクラスターの合併比率の推移（片対数）です．
効率悪化の原因が明らかになったので，その問題を解決する方針を立て，それを実施したのが鶴見さんの研究成果です．彼はHE法，HE’法，HN法と呼ぶ３つの高速化手法を提案しました．Clausetらが提案した既存の提案を少し改良することで，ミクシィから得た５５０万人規模の 友人関係まで分析することができました．この結果は，図６：スケーラビリティのHN手法として示されています．このグラフは縦軸が処理時間です．HN法はあまりに短時間で終了するため，グラフでは横軸とほぼ重なっています．
実習のために提供するデータは鶴見さんが国際学会の準備のために用意したデータの一部です．論文では，CNM法とそれを改善したHE法，HE’法，HN法についてのいくつかの比較実験をしています．
| 手法 | データ数 | データのサイズ |
|---|---|---|
| CNM | 16 | 36.1 MB |
| HE | 20 | 14.2 MB |
| HE’ | 13 | 14.4 MB |
| HN | 17 | 13.6 MB |
| 合計 | 66 | 78.3 MB |
実際にはこれだけのデータを作成したのですが，論文のなかで用いたデータはその一部だけです． でも，論文に使わなかったデータが無駄になったわけではありません．紙面の都合上，論文には掲載しなかったデータが多かったのですが，発表資料スライドには論文には掲載しなかった図表も提示しためので，結局，無駄になったデータはほとんどなかったと思います．
みなさんに学んで欲しいのは，研究発表をするときには事前にかなりの分量のデータを用意するという点です．鶴見さんの研究で用いたデータは６６個，総量78.3 MBでした．
このように数量ともに多くのファイルをどのように管理すればよいのかという点は，この実習の隠れたテーマのひとつです．
研究で用いたデータセットに含まれる６６個のデータは，分析した４つの手法ごとのフォルダに整理しました．それぞれのデータのファイルはデータの属性名と実験条件を列挙して命名されています．また，各フォルダには，そのフォルダに含まれるデータの内容を説明したファイルを保存してあります．
cnm/: CNM手法のデータを保存したフォルダ．詳細は省略．he1/: HE手法のデータを保存したフォルダ．詳細は省略．he2/: HE’手法のデータを保存したフォルダ．詳細は省略．hn/: HN手法のデータを保存したフォルダ．
etime-join-500K.data: time-join-500K.data のデータを積み上げたもの。\((n, t)\) という形式で、最初の \(n\) 回の合併に \(t\) 秒を要したことを示している。etime-size.data: 分析対象の社会ネットワークの規模を変化させ、解析にかかった時間を計測した結果。\((N, t)\) という形式で大きさが \(N\) のネットワークの解析に \(t\) 秒要したことを示している。modularity-etime-500K.data: ネットワークの規模を変化させ、モジュール性の変化を調べた結果。\((t, Q)\)という形式で、ノード数 \(N\) の大きさのサブセットの解析でモジュール性 \(Q\) が得られたときの解析時間がt．modularity-size.data: ネットワークの規模を変化させ、モジュール性の変化を調べた結果。\((N, Q)\)という形式で、ノード数 \(N\) の大きさのサブセットの解析でモジュール性 \(Q\) が得られたことを示している。ratio-join.data: 分析中にはクラスタを合併していくが，その合併比率のデータ．\((x, r)\)という形式で，\(x\)番目の合併における合併比率がrだったことを記録している．さまざまな大きさの社会ネットワークに対して同様に実験を実施した結果を記録した．time-join-100K.data, time-join-200K.data, …: 10,000回ごとの合併に要した時間を社会ネットワークの大きさを記録した結果．分析対象の社会ネットワークを変化させて実験したので，実験対象の大きさが100K, 200K, …と表されている．time-size.data: ミクシィの友人関係から切り出したデータの大きさを10万人，20万人，…と変化させて分析したときの，データの大きさ(size)と処理時間(time)の関係を表したもの．READNE.md: このフォルダに含まれるデータについての簡単な説明．cnm/: CNM手法のデータを保存したフォルダ．
etime-size.data 分析対象の社会ネットワークの規模を変化させ、解析にかかった時間を計測した結果。\((N, t)\) という形式で大きさが \(N\) のネットワークの解析に \(t\) 秒要したことを示している。
図５の元データ（図５は他の解析手法に対する etime-size.data と併せて作成しました）
ratio-join.data: 分析中にはクラスタを合併していくが，その合併比率のデータ．\((x, r)\)という形式で，\(x\)番目の合併における合併比率が\(r\)だったことを記録している．500Kの大きさの社会ネットワークに対する結果だけを配布する．
図３の元データ
time-join-100K.data, time-join-200K.data, …: 10,000回ごとの合併に要した時間を社会ネットワークの大きさを記録した結果．分析対象の社会ネットワークを変化させて実験したので，実験対象の大きさが100K, 200K, …と表されている．
図２の元データ群
he1/: HE手法のデータを保存したフォルダ．
etime-size.data: 分析対象の社会ネットワークの規模を変化させ、解析にかかった時間を計測した結果。\((N, t)\) という形式で大きさが \(N\) のネットワークの解析に \(t\) 秒要したことを示している。
図５の元データ（図５は他の解析手法に対する etime-size.data と併せて作成しました）
etime-size-M.data: etime-size.dataと同様の実験をミクシィから切り出した550万人の友人関係のデータについて適用した結果．実験では，分析を完了できなかったため，合併数=400万までのデータしか入手できていない．
図６の元データ（図６は他の解析手法に対する etime-size.data と併せて作成しました）
he2/: HE’手法のデータを保存したフォルダ．
etime-size.data: 分析対象の社会ネットワークの規模を変化させ、解析にかかった時間を計測した結果。\((N, t)\) という形式で大きさが \(N\) のネットワークの解析に \(t\) 秒要したことを示している。
etime-size.data と併せて作成しました）etime-size-M.data: etime-size.dataと同様の実験をミクシィから切り出した550万人の友人関係のデータについて適用した結果．
図６の元データ（図６は他の解析手法に対する etime-size.data と併せて作成しました）
hn/: HN手法のデータを保存したフォルダ．
etime-size.data: 分析対象の社会ネットワークの規模を変化させ、解析にかかった時間を計測した結果。\((N, t)\) という形式で大きさが \(N\) のネットワークの解析に \(t\) 秒要したことを示している。
図５の元データ（図５は他の解析手法に対する etime-size.data と併せて作成しました）
etime-size-M.data: etime-size.dataと同様の実験をミクシィから切り出した550万人の友人関係のデータについて適用した結果．
図６の元データ（図６は他の解析手法に対する etime-size.data と併せて作成しました）
ratio-join-500K.data: 分析中にはクラスタを合併していくが，その合併比率のデータ．\((x, r)\)という形式で，\(x\)番目の合併における合併比率がrだったことを記録している．500Kの大きさの社会ネットワークに対する結果だけを配布する．
図７の元データ