二部グラフ（海外ドラマ「ナンバーズ」に出てくるネットワーク分析）

キース・デブリン／ゲーリー・ローデン（山形浩生／守岡桜訳）『数学で犯罪を解決する』（ダイアモンド社）は海外ドラマ「ナンバーズ」に出てくる数学の話題を扱った本ですが、第10章で社会ネットワーク分析が紹介されています。

数学で犯罪を解決する

ということでシーズン2　Vol.8の「追憶」という回を見てみました。

ナンバーズ 天才数学者の事件ファイル シーズン2 コンプリートDVD-BOX

あらすじ：米軍の事務所近くで爆弾事件が発生。手口と犯行声明は35年前のベトナム反戦運動の中でおきた爆弾事件に酷似。35年前の事件の容疑者スターリングは失踪しており、FBIは彼の関与を疑う。FBIの数学コンサルタントとして兄ドンの捜査に協力する数学者チャーリーは社会ネットワーク分析を使って運動団体の人間関係を分析することを提案。しかし、2人の父がスターリングとともに反戦運動に参加していたことが分かって...。

実際にネットワーク分析の話題が出てくるのはこんな感じ。

チャーリー「昔の事件の資料を基にソーシャル・ネットワーク分析を使えば集団の構造が分かる。団体での彼の立場や協力者が分かるかも」（7分55秒　以下同様におおよその再生時間を示す）

チャーリー「人はネットワークを作ります。趣味や教会、大学や政府の機関などです。その構造を数学的に分析すれば真のリーダーが分かる。71年の複数の反戦団体もネットワークの一種です。二部ネットワークの分析でつなぎ役が分かります」（14分18秒）*1

二部ネットワーク（bipartite network）という言葉がいきなり出てきて、その後説明もされませんので、ここでは二部グラフ（二部ネットワークより一般的な呼び方と思いますので、これを使います）についてちょっと書こうと思います。

普通、ソーシャルネットワークというと次のような人と人とのつながりを思い浮かべるでしょう。

しかし、FBIがテロの容疑者について調べていくとき、必ずしも「誰と誰が仲間」というような人間関係についての直接的な情報が手に入るわけではないでしょう。例えば、「○○はAというグループの集会に参加した」とか「○○はBというグループの機関誌に投稿した」「○○はCというグループのパーティで撮られた写真に写っている」といった断片的な情報が集まるのではないでしょうか。1人の人についてそのような情報を集めると、グループと個人について下の図のようにまとめることができます。

これだけでは、個人とグループとの間の関係は分かっても、個人と個人との間の関係は分かりません。そこで、このような個人とグループとの関係を何人分も合わせてみると、次のように複数のグループと複数の個人の間の関係を表すことができます。

この図ではネットワークがグループと個人という2つの部分に分かれています。そしてグループどうしや個人どうしのように、それぞれの部分の内部には関係を表す線がなく、異なる部分の要素間にのみ線が引かれています。
このようなネットワークの表し方を二部グラフといいます。

では、どのように二部グラフを分析すれば個人間のつながりが分かるのでしょうか。それは、グループを介したつながりの可能性をさぐることによってできます。

例えば、ある人とまた別のある人が同じ集会に参加していたとしたら、2人はそこで会っているかもしれませんし、何かのつながりがあるかもしれません。そのようなつながりの可能性を探していくのです。

まずグループAに注目すると、1番・2番・3番がグループAと関係をもっていますので、この3人には関係があるかもしれません。

次にグループBを見ると、2番と4番とのつながりがありますので、この2人は関係があるかもしれません。

グループCには4番しか関係していませんので、そこから個人間の関係を導くことはできません。

こうして得られた個人間のつながり（の可能性）をまとめてみると次のように個人と個人の関係のネットワークを得ることができます。

グループとの関係を加えて示すと次のようになります。

これでチャーリーの言った「二部ネットワークの分析でつなぎ役が分かります」の意味が分かるでしょう。
上の図では2番が人間関係あるいはグループ間の関係の「つなぎ役」である可能性が高いと思われます。「つなぎ役」をもう少し数学的に探すには媒介中心性（betweenness）を使うのですが、それは別の機会に扱いたいと思います。

二部グラフの分析は他には、企業の重役の兼任関係の分析に使われます。いくつもの企業の重役を兼任しているような経営者がいますが、そういう人たちがどの企業で重役を務めているかという情報から、経営者間の関係や企業間の関係を導くことができます*2。

エクセルでの計算

ここまでは二部グラフについて図で考えてきましたが、グループと個人の関係を表す二部グラフから個人間のネットワークを導くのに行列の積を用いることもできます。

まずエクセルに二部グラフの隣接行列を入力します。最初に行に個人のラベル、列にグループのラベルをつけるように入力しておきます。

入力する範囲を選択して、行列の要素を={1,0,0;1,1,0;1,0,0;0,1,1}と入力します。入力順は行ごとで、要素の区切りにはカンマ、改行にはセミコロンを使います。

入力したらCtrl + Shift + Enter（そうしないと行列にならない）

これで隣接行列入力完了。

次に今入力した隣接行列の転置行列（行と列を入れ換えた行列）を作りたいので、さっきとは行と列を入れ換えてラベルを入力。

転置行列の入力範囲を選択して、関数TRANSPOSEで先ほど入力した隣接行列の範囲を指定。

ここでもCtrl + Shift + Enter（そうしないと行列にならない）

転置行列ができた。

今度は個人間の隣接行列を作るために適当なところに行と列のラベルを入力

入力する範囲を選択して、関数MMULTで配列1に二部グラフの隣接行列、配列2に二部グラフの隣接行列の転置行列の範囲を指定。

ここでもCtrl + Shift + Enter（そうしないと行列にならない）

個人間の隣接行列ができた。

この隣接行列ですが、その要素は個人間で共通に関係のあるグループ数を表しています。例えば1行2列目の「1」は1番と2番が共通に関係をもっているグループが1つあることを表しています。対角要素はその個人が関係をもつグループ数です。例えば2行2列目の「2」は2番が2つのグループと関係があることを表しています。

しかし、エクセルで行列積を出すのは面倒ですね。Rなら A %*% t(A)で済むのに...。

応用例

さて、『数学で犯罪を解決する』ではソーシャルネットワーク分析の適用例として9.11テロの容疑者のネットワークの分析が出てきます。
紹介されているのはValdis E. KrebsのUncloaking Terrorist Networksという論文。

この論文で、どうやってテロ容疑者どうしのネットワークを作成しているかというと、新聞記事から「いつ、誰が何をしたか」という情報を集めて、いっしょに何かした人どうしをつないでいるのです。例えばワシントンポストがそういう情報をまとめた図表があります。

Suspected Hijackers

このリンク先で「VIEW THE TIME LINE」というボタンを押して表を展開させると、「誰と誰が飛行機の訓練校を尋ねた」とか「誰と誰がなんとかというお店に来た」という情報が出てきます。これは出来事と個人を結びつけた情報になっているので、ここから出来事と個人の二部グラフを作成し、さらにその二部グラフから個人間のネットワークを作ることができるのです*3。

NodeXLで可視化した例。

*1:これを受けてかつて反戦運動を捜査した捜査官が「私の時代には大学教授の力など借りなかった。信用できなくてね」と言うのは、科学的捜査への不信というより大学人に反戦運動の支持者が多かったことを指しているのでしょうね。

*2:これは経営学におけるソーシャルネットワーク分析の活用の一例です。ところで、「ナンバーズ」のこの回では登場人物の1人が自分の息子を紹介して「賢い息子だ。経営学の学位を取った。私は社会学をやっただけだ」（9分39秒）と言うのですが、アメリカにおける経営学と社会学の関係がなんとなく分かり、社会学者としては切ないです。

*3:ワシントンポストの表では個々の出来事と関係している個人が赤い線で結ばれています。個人を点、出来事を辺と考えると一種のハイパーグラフになっています。