プログラミング無しで「つながり」ネットワーク解析（2部グラフの隣接行列の計算）

こんにちは。データ分析チーム(仮)の花井です。最近は、社内に蓄積されたデータを分析し可視化する方法を模索しています。過去の記事では協調フィルタリングによるレシピ類似の可視化があります。 oishi-kenko.hatenablog.com

「つながり」を解き明かすネットワーク科学は、これまで薬品設計・代謝工学などの分野で研究者の間で応用されてきましたが、最近では人事に関わる「ピープルアナリティクス」*1といった分野が急速に発展しています。弊社では、ホットなネットワーク科学を食と医療に応用して様々な「つながり」を分析・活用していこうとしています。

今回は、弊社のSlackデータを例にして、スプレッドシートを使ったネットワークの解析を説明します。BigQueryやPythonを題材にしようと思ったのですが、エンジニアに限らず誰でもネットワークの解析ができるよう、ノンプログラミングできる表計算ソフト（MicrosoftエクセルやGoogle スプレッドシート）を使った解析方法について扱います。また、どのような見方でネットワーク構造を捉えているか解説します。

一言でいうと、メンバー集合およびチャンネル集合で構成される2部グラフの隣接行列の二乗をスプレッドシートで計算し、メンバーネットワークおよびチャンネルネットワークを隣接行列から考察します。

問題設定
アプローチと用語説明
隣接行列の表示
隣接行列の2乗を計算
ネットワークの可視化
データ分析チームを募集しています

問題設定

「ほぼ全員が参加しているチャンネルは除いて、発言が活発なSlackチャンネルにどのメンバーが所属しているか」という情報をリスト形式のデータを持っていると仮定します。このとき、どのメンバー同士が会話可能か、チャンネル同士の共通メンバー数を一覧で見る方法を考えます。

持っているデータは下記のような2つのリスト形式です。

リスト1(チャンネルとメンバーの所属関係)

チャンネル	メンバー
A	1
A	2
A	5
A	10
...	....
E	45

リスト2(メンバー一覧)

メンバー
1
2
3
4
...
46

記事執筆時点では46名の社員がSlackに参加しています。ほぼ全員が参加しているチャンネルは除いて、発言が活発なSlackチャンネル上位5つにジョインしているメンバーを（Slack APIを使って無理やり）抽出しました。

アプローチと用語説明

今回ようなリスト1を見たとき「これは2部グラフの枝だな」と思いました。

なぜそのように思ったのか説明していきます。

まず、メンバーとチャンネルをそれぞれノードとして配置してみましょう。

f:id:oishi-kenko:20190823154022p:plain

「Aチャンネルにメンバー5が所属している」という所属関係を下記のように線を結んで枝を作成します。

f:id:oishi-kenko:20190821175946p:plain

リスト1に基づいて、枝を追加していくと下記のようなグラフができます。

f:id:oishi-kenko:20190822235403p:plain

リスト1は、所属関係を示しているのでチャンネルとメンバーの要素間に枝が生成され、チャンネル同士やメンバー同士の枝はありません。

このように、要素間に枝がないノード集合が2つできるグラフを2部グラフと言います。

チャンネル集合を ${C}$ , メンバー集合を ${M}$ とすると、頂点が ${U \cup M}$ に属し、枝が ${(v, u), v \in C, u \in M }$ となる無向グラフになっています。

隣接行列の表示

ここで、隣接行列を作ります。表計算ソフト（MicrosoftエクセルやGoogle スプレッドシート）ではピボットテーブルの作成により行います。

隣接行列とは、頂点uからvに枝があるとき(u, v)成分を1とし、枝がなければ0とする行列です。

隣接行列を作るために下記操作をしてリスト3を作ります。

リスト1をそのままノード1、ノード2に追加。リンクは1にする。
リスト1の左右を入れ替えてノード1、ノード2に追加。リンクは1にする。
各メンバーをノード1、ノード2に追加。リンクは0にする。
各チャンネルをノード1、ノード2に追加。リンクは0にする。

リスト3（隣接行列の準備）

ノード1	ノード2	リンク
A	1	1
A	2	1
A	5	1
A	10	1
...	....	...
E	45	1
1	A	1
2	A	1
...	...	...
45	E	1
1	1	0
2	2	0
3	3	0
...	...	...
46	46	0
A	A	0
...	...	...
E	E	0

このリスト3を選択してピボットテーブルを作成すると次のようになります。

f:id:oishi-kenko:20190822235246p:plain

このピボットテーブルを別シートにコピーして、空白を0に置換し、1を緑色で塗る書式設定をすると次のような見やすい表になります。

f:id:oishi-kenko:20190822235259p:plain

この大きな表から行がメンバー・列がチャンネルの部分だけ取り出して並び替えてみましょう。

f:id:oishi-kenko:20190823003203p:plain

色々なことが分かります。

5つのチャンネルすべてに所属しているハブとなるメンバーがいる
5つチャンネルは3つのグループに分かれている
- (1) A,D (2) C, E (3) B
- チャンネルA, Dは共通メンバーが多い
- チャンネルC, Eは共通メンバーが多い

隣接行列の2乗を計算

さて、今回は次のことを明らかにしようとしています。

どのメンバー同士が5つのチャンネル内だけで会話可能か知りたい
チャンネル同士の共通メンバー数を一覧で見たい

言い換えると*2

ある2人のメンバー ${m_1, m_2 \in M}$ と任意のチャンネル ${c \in C}$ に対して ${m_1 c m_2 }$ となるパスが存在するか知りたい
ある2つチャンネル ${c_1, c_2 \in C}$ と任意のメンバー ${ m \in M}$ に対してパス ${c_1 m c_2}$ の数を知りたい

これを解くためにグラフ理論の定理を利用します！

あるネットワークに対する隣接行列 ${A}$ の ${n}$ 乗 ${ {A}^n }$ の ${(i,j)}$ 成分は点 ${i}$ から点 ${j}$ への長さ ${n}$ のパスの数となる

今回のケースに置き換えると次のようになります！

リスト3のピボットテーブルで生成した隣接行列 ${A}$ の2乗 ${ {A}^2 }$ の ${(i,j)}$ 成分はメンバー ${i}$ からメンバー ${j}$ もしくはチャンネル ${i}$ からチャンネル ${j}$ への長さ2のパスの数となる

隣接行列の二乗を計算には MMULT 関数を使います。*3

=MMULT(行列の範囲,行列の範囲)

隣接行列の隣に MMULT 関数を使った隣接行列の2乗を表示します。カラースケールで書式設定して見やすくしています。

f:id:oishi-kenko:20190823001317p:plain

それぞれの数字をどのように見ればいいのか説明します。

行と列が同一メンバーのとき、所属しているチャンネル数を示しています。
- メンバー '2' は2つのチャンネルに所属している
- メンバー '3' は2つのチャンネルに所属している
- メンバー '5' はすべてのチャンネルに所属している
- メンバー '6' はどのチャンネルに所属していない
行と列が異なるメンバーのとき、共通の所属チャンネル数を示しています。
- メンバー '2', '3' で共通しているチャンネルはない
- メンバー '2', '5' で2つ共通して所属しているチャンネルがある
行と列が同一チャンネルのとき、所属メンバー数を示しています。
- チャンネルAは19人が所属している
行と列が異なるチャンネルのとき、共通の所属メンバー数を示しています。
- チャンネルA, B で5人のメンバー共通して所属している。