時間発展するグラフ（ネットワーク）においてコミュニティがどのように時間発展するかを可視化したいことは多い。
例えば、SNSなどのネットワークにおいて各時刻におけるネットワークのコミュニティを検出し、それらのコミュニティ内のノードのメンバーがどのように時間変化するかを可視化したいということはよくあるだろう。
ここではそのようなコミュニティ構造の時間発展を可視化する方法の一つalluvial plotを作成する方法についてまとめておく。
今回、図の作成に使うツールはこちらのオンラインのツール Alluvial Generator。
こちらのツールを使うと例えばこんな感じのかっこいい図が作成できる。
しかも、インタラクティブに、階層的なコミュニティ構造を表示できたり、特定のノードやモジュールに色をつけたりでき、作成した図はsvgやpngなどのフォーマットに保存することができる。
また、可視化時の設定なども含めてjsonにエクスポートすることが可能である。
しかし、このツールは便利な反面、入力ファイルのフォーマットがあまりわかりやすくないので、今回はここでその手法をまとめておく。
このツールの入力のファイルのフォーマットとしては、infomapで出力される形式のファイルを想定している。
infomap以外のツールで検出したコミュニティ構造を可視化したい場合にはこれらのファイル形式に変換する必要がある。
.clu, .map, .tree, .ftree などのフォーマットがあるが、ここでは階層的なコミュニティ構造を表現でき、かつシンプルなフォーマットであるtreeフォーマットでデータを指定することにする。
treeフォーマットのドキュメントはこちらにある。
https://www.mapequation.org/code_old.html#Tree-format
treeは次のようなファイルの形式である。
1:1:1 0.0384615 "7" 6
1:1:2 0.0384615 "8" 7
1:1:3 0.0384615 "9" 8
1:2:1 0.0384615 "4" 3
1:2:2 0.0384615 "5" 4
...
各行がノード一つ一つを表している。
まず最も左の列にあるコロンで区切られた数字が、モジュールのIDである。階層的なコミュニティ構造を表現しており、一番左の数字がトップレベルモジュール（もっとも粗視化したコミュニティ）のID、次の数字がそれよりも階層が下のモジュールのID、さらに下のモジュールのID、、、と続いていき、最後に各モジュール内でのノードのIDというように番号付けされている。
infomapでは1から始まる連番を使うことが一般的なようなので、その慣習に習っておくのがよいだろう。（０から始めるとどうなるのかはよくわからない。）
２列目の不動小数点はtotal flow(Page Rank)という数字となる。どれくらい中心性があるかという数値になるが、今回の可視化には特に必要ないので任意の数字を入れておけば良いだろう。
３列目はノードの名前。４つ目がノードの（グローバルな）IDとなる。
一つのtreeファイルが一つの時点でのコミュニティ構造を表しており、alluvial plotでは複数のtreeファイルを読み込んで図を作成する。その際に、異なる時点でどのノードとどのノードが対応しているのかを判定するのにノードの名前が使われる。
このように複数の時点に対応するtreeファイルを複数用意したらデータを読み込めば可視化することができる。
作画できたら画面右のほうに可視化のオプションを指定する箇所があるので、色などを指定するときれいな図が作れるだろう。
最後に
こちらの方法はネットワークのコミュニティの時間発展を可視化するために提案されたものだが、実は一般的に複数の時点での集合関係がどのように発展しているかを可視化するのにも利用することができる。