2部グラフと、各々の集団内のネットワークの関係

数学やグラフ理論では、すべての頂点をうまく2つの集合に分けたときに、自分の集団内に対しては枝がなく、相手の集団間に枝が存在するグラフのことを「2部グラフ」と定義しています。

現実の世界での例を挙げてみます。
世界には様々な組織（大学、企業、高校、etc）があり、その組織に所属する人間がいます。
f:id:alstd:20150115182438p:plain
上が5つの塾、下が所属する生徒と考えてみましょう。
このとき、塾と生徒は「所属」という枝で結ばれていますが、塾と塾、生徒と生徒間の間には枝がないです。
ここで、塾と生徒をそれぞれ枝集合AとBに分けてみましょう。
すると、集合AとBの要素間に枝は存在するものの、A内の要素同士、B内の要素同士に枝は存在しません。
こういった分割が可能なグラフの関係性を2部グラフという、と定義した訳です。

 

ところでこの2部グラフ、関係性という枝によって結ばれる端点同士が、異なる2つの意味合いを持つときに現れやすいです。
ここでいうと所属という関係性の元、異なる意味合いを持つ塾と生徒が結ばれていますね。
他にも最も分かりやすい例では、性交渉をした関係性は（同性愛者を除き）異なる性別である男と女が枝で結ばれます。
例えば話したことがあるという関係性の元では男同士、女同士でも話すわけですから、二部グラフにはなりません。

 

では、ここで同じ塾に通う生徒同士のネットワークを描きたい、と思ったらどうなるでしょうか。
上の図では6,8,9さんは同じ塾に通っているから枝を張る、という訳です。
性交渉では、いわゆる穴兄弟のネットワークを張るという意味です。
このネットワークの定義を知らないので、「同所属ネットワーク」と以下呼んでみます。

 

これとは違う例ではありますが、同所属ネットワークを書く機会があったため、数学的な計算法を紹介しておきます。

まず、隣接行列を作ってください。
(n,m)成分は頂点nからmに枝があるとき、その成分を1とする行列です。
ここでは、上の図の例を使います。


{\displaystyle A = \left( \begin{array}{ccccccccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \end{array} \right) }

この隣接行列を2乗してください。

{\displaystyle A^2 = \left( \begin{array}{ccccccccccccccc} 3 & 0 & 2 & 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 3 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 2 & 1 & 4 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 2 & 0 & 1 & 4 & 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 2 & 3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 2 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 1 & 2 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 2 & 1 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 2 & 1 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 3 & 1 & 2 & 0 & 2 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 2 & 0 & 2 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 2 & 1 & 1 & 0 & 2 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ \end{array} \right) }

このとき、この2乗の行列の各成分は、

(n,m) = \begin{cases} n(さん/塾)がm(さん/塾)と共有する(塾/生徒)数 & (n\neq{m}) \\ n(さん/塾)が所属(する/される)(塾/生徒)数 & (n=m) \end{cases}


です。

 

これを使って、先ほどの2部グラフを、塾についてと生徒についての2つのグラフへ分けてみます。
f:id:alstd:20150115195214p:plain
1〜5の塾のネットワークと6〜15の生徒のネットワークに分かれていますね。
自分に対するループ枝は、自分の所属する塾あるいは生徒の数です。
他のノードに対する枝は、共通する塾に行く生徒同士、あるいは共通する生徒を持つ塾同士を繋いでいます。

 

背景にある定理は、

あるネットワークに対する隣接行列Aのl乗であるA^lの(n,m)成分は、\\ nからmを長さlで繋ぐパスの数となる。


であり、その系として、

2部グラフに対する隣接行列Aの2乗であるA^2の(n,m)成分は、\\ nからmを2の長さで繋ぐパスの数となる。\\ 特に2部グラフの定義における頂点の2つの集合X,Yを考えたとき、\\ Xのある頂点から長さ1で到達しうる点はYに属し、更にそのような\\ Yの点から長さ1で到達しうる点はXに属する。\\ 従って、A^2の隣接行列によって与えられるネットワークは、\\ X,Yの（少なくとも）2つのネットワークである。

 

証明をしておきましょう。

{\displaystyle 数学的帰納法によって証明する。\\ l=1のとき、A^1は隣接行列であり、定義より(n,m)成分はn-mを長さ1で繋ぐパスの数である。\\ l=pのとき、A^pの(n,m)成分がnからmを長さpで結ぶパス数であると仮定すると、\\ l=p+1のとき、\\ 隣接行列のp乗をA^p=B=[b_{ij}]とおく。\\ A^{p+1}=A^{p}A=\sum_{k=1}^nb_{ik}a_{kj}=b_{i1}a_{1j}+b_{i2}a_{2j}+\cdots+b_{in}a_{nj}……(1)\\ ここで帰納法の仮定より、\alphaをi-jを長さpで繋ぐパスの数として、b_{ij}=\alpha\\ 更に、隣接行列の定義より、\\ a_{ij} = \begin{cases} 1 & (i-j間に枝がある) \\ 0 & (i-j間に枝がない) \end{cases}\\ だから、\\ b_{ik}a_{kj} = \begin{cases} \alpha & (i-k間に枝 かつ k-j間に枝) \\ 0 & (それ以外) \end{cases}\\ (1)のkについての総和を取ることで、i-(pの長さのパス)-k-jという結びつきの数が\\ 数えあげられ、即ちこれは長さがp+1のパスを数え上げていることになっている。\\ よってl=p+1のときも成立するため、一般のlについても成立。\\ }

ただし、小さなネットワークに対してスマートな計算法であっても、大きなネットワークに対しては巨大な計算量とメモリを消費することになります。
巨大なものに対しては、疎行列に対するアルゴリズムを適用することで軽量化できます。
本当に莫大な計算が必要なときは、やはり枝リストから重みなしで数え上げるのが一番速いと思われます。（重みありならば疎行列に対する積と実質同じになる。）

今回の記事でRのプログラムを使ったので、後々紹介します。
疎行列積や枝リストからの数え上げはやる気が出次第取り組んでみます。