Pymnetで多層ネットワークを扱う

はじめに

Sansan Advent Calendar 2018の15日目の記事です。
今回は、ネットワーク科学で流行している「多層ネットワーク」という考え方と、それを扱うためのPythonライブラリの1つであるPymnetについて紹介したいと思います。

多層ネットワークとは

• ふつう、「ネットワーク」と呼ばれるのは**単一ネットワーク(monoplex network)**のことが多いです。
• ネットワークは「ノード」と「エッジ」から構成されますが、ここに「レイヤ」という次元を追加したのが**多層ネットワーク(multilayer network)**です。
  • 多層ネットワークはアスペクト(aspect)を持ちます(e.g.「関係の種類」と「時点」)
  • それぞれのアスペクトは、$L_{type} = \{友人関係,仕事関係,親戚関係\}$、$L_{time} = \{2016,2017,2018\}$のように、要素レイヤ(elementary layer)を持ちます。
  • $V$をノードの集合、$d$をアスペクト数とした時、単層のネットワークは$|V|×|V|$の隣接行列で表現されます。一方、多層ネットワークの場合は要素数$|V|×|V|×|L_1|×|L_1|×…×|L_d|×|L_d|$で$2(d+1)$階の隣接テンソルとして表現されます。
  • ただ、実際にはアスペクト$d=1$の4階の隣接テンソルを扱う場合がほとんどだと思います。この記事も主にアスペクトが1の多層ネットワークを扱います。
• 下位概念として**多重ネットワーク(multiplex network)**というものがあります。
  • これは(厳密には違うようですが)全てのレイヤの間でノードを1つでも共有している場合の多層ネットワークを指します。
  • あるネットワークの時系列的なシーケンス等を扱う場合は多重ネットワークになります。
• 多層ネットワークの例：
  • 「航空会社」をレイヤとした航空機の運行ネットワーク(Cardillo et al. 2013)
  • 「友達関係・同一グループの所属関係・同じ写真に写っている関係」をレイヤとしたFacebookのネットワーク(Lewis et al. 2008)
  • 「年」をレイヤとした世界貿易のネットワーク(Bader et al. 2007)
• 最近のネットワーク科学では、より複雑なメカニズムをするために、様々なネットワークレイヤーを複合的に考慮して分析するのが流行となっています。
  • Kivelä et al.(2014)の包括的なレビュー論文が有名です。この論文で用語の統一が図られました。
  • 社会学でもDickison et al.(2016)など解説書が登場しています。

多層ネットワークを扱うためのライブラリ

• 色々あります。
  • Pymnet (http://www.mkivela.com/pymnet/index.html)
  • multiNetX (https://github.com/nkoub/multinetx)
  • Py3plex (https://github.com/SkBlaz/Py3plex)
• 今回はKiveläによる実装であるPymnetを使用してみます。
  • 特徴 (http://www.mkivela.com/pymnet/index.htmlを日本語訳)
    • 純粋なPython実装である
    • 一般的な多層ネットワークを扱える
    • 多層ネットワークと多重ネットワークのためのデータ構造
    • 疎なネットワークのためのスケーラブルな実装。メモリー使用量はエッジ数とノード数によって線形に増加。
      • レイヤ数と比例しないのがいいですね。
    • カップリングエッジのルールベース生成と遅延評価
    • 様々なネットワーク分析手法、変形、ネットワークやネットワークモデルの読み書き
    • ビジュアライゼーション (バックエンドとしてMatplotlibやD3を使用)
    • 単一ネットワーク分析のためのNetworkXとの統合

Pymnetのインストール

• bitbucketからソースを.zipファイルでダウンロードします。

$ wget https://bitbucket.org/bolozna/multilayer-networks-library/get/fdd96eef61dd.zip

• もしくはMercurialを使ってもよいですね(公式ではこちらの方法が紹介されています)。

$ hg clone https://bitbucket.org/bolozna/multilayer-networks-library

• .zipを解凍したら、ファイル一式をPythonのライブラリのあるディレクトリに置きます。
  • pymnetフォルダ以外は不要かもしれません。

2層のネットワークを手動で作る

MultilayerNetworkクラスのインスタンスを作成します。aspects でアスペクトの数を指定できます。

from pymnet import *

mnet = MultilayerNetwork(aspects=1)

佐藤、田中、鈴木、山田の4人から構成される会社を考えてみましょう。
アスペクトが1の場合、mnet[from_node,to_node_2,layer_1,layer_2] = 1のようにして書くと、エッジが形成されます。

mnet['sato','tanaka','work','work'] = 1
mnet['sato','suzuki','friendship','friendship'] = 1
mnet['sato','yamada','friendship','friendship'] = 1
mnet['sato','yamada','work','work'] = 1
mnet['sato','sato','work','friendship'] = 1
mnet['tanaka','tanaka','work','friendship'] = 1
mnet['suzuki','suzuki','work','friendship'] = 1
mnet['yamada','yamada','work','friendship'] = 1

この場合、レイヤー間のエッジはカップリングエッジと呼ばれ、これによって結合したノードはレイヤー間で同じエンティティである、ということを表現しています。

次に、多層ネットワークを描画してみます。

• Pymnetのdraw関数はmatplotlibがベースとなっていて、.pdfで画像を保存することができます。
• draw(mnet,show=True) のように書くと、jupyternotebook上で画像のプレビューが確認できます。

※2018年12月14日時点ではアスペクトが2以上の多層ネットワークの描画には対応していないようです。

fig = draw(mnet)
fig.savefig("net.pdf",layout='spring')

【net.pdf】

多重ネットワークを作る

先程のネットワークは実はレイヤ間でノードを共有しているため、多重ネットワークのクラスに属するネットワークでした。Pymnetには多重ネットワーク専用のクラスである MultiplexNetworkが用意されており、こちらを使うとレイヤー間でのカップリングエッジなどがルールベースで生成され、メモリ使用量も抑えられるそうです。
先程と同じ構造のネットワークは以下のスクリプトで生成できます。カップリングエッジはインスタンス作成時に自動的に形成されます。

mnet = MultiplexNetwork(couplings="categorical")
mnet['sato','tanaka','work','work'] = 1
mnet['sato','suzuki','friendship','friendship'] = 1
mnet['sato','yamada','friendship','friendship'] = 1

ランダムな多重ネットワークを生成する

ランダムグラフモデルから多重ネットワークを生成することもできます。
生成モデルをErdos-Renyiモデル、ノード数を10、レイヤ数を3、エッジ形成確率をすべてのレイヤで0.2としてみましょう。

rand_mnet = er(10,[0.2,0.2,0.2])

多層ネットワークの場合はer_multilayerを使います。

ネットワーク指標を計算する

multiplex_degs()で、各レイヤでの次数を計算できます。

multiplex_degs(mnet,degstype='nodes')

{'work': {'yamada': 0, 'sato': 1, 'tanaka': 1, 'suzuki': 0}, 'friendship': {'yamada': 1, 'sato': 2, 'tanaka': 0, 'suzuki': 1}}

複数のレイヤを集約する

aggregate()を使うと、多層ネットワークを単層ネットワークに集約できます。どれか1つのレイヤにエッジが存在すると、集約後のネットワークにもエッジが張られます。なお、この時、集約後のエッジの重みは1になります。

agg_net = aggregate(mnet,aspects=1)

集約したネットワークの次数を見てみましょう。

degs(agg_net,degstype='nodes')

{'sato': 3, 'yamada': 1, 'tanaka': 1, 'suzuki': 1}

全ての関係性を考慮すると、satoさんが特に中心的な人物であることが分かります。

※aggregate後のネットワークも描画したかったのですが、うまくいかず…。

まとめ

• 普段の分析用にゴリゴリ使える、というわけではないですが、多層ネットワークの考え方に触れるには良いライブラリだと思いました。
• 2019年1月23日に「Sansan Advent Calendar - 2018年を振り返る -」というイベントをやるらしいです。
  • LTでは実世界でのネットワークデータを使って分析したものを発表する…かも。

参考文献

• Bader B. W., Harshman R. A., Kolda T. G.. Temporal analysis of semantic graphs using ASALSAN, Seventh IEEE International Conference on Data Mining (ICDM 2007) , 2007(pg. 33-42) IEEE
• Cardillo A., Gómez-Gardeñes J., Zanin M., Romance M., Papo D., del Pozo F., Boccaletti S.. Emergence of network features from multiplexity, Sci. Rep. , 2013, vol. 3 pg. 1344
• Dickison, M. E., Magnani, M., & Rossi, L. (2016). Multilayer social networks. Cambridge University Press.
• Kivelä, M., Arenas, A., Barthelemy, M., Gleeson, J. P., Moreno, Y., & Porter, M. A. (2014). Multilayer networks. Journal of complex networks, 2(3), 203-271.
• Lewis K., Kaufman J., Gonzalez M., Wimmer M., Christakis N. A.. Tastes, ties, and time: a new (cultural, multiplex, and longitudinal) social network dataset using Facebook.com, Soc. Netw. , 2008, vol. 30 (pg. 330-342)