2部グラフと、各々の集団内のネットワークの関係性
数学やグラフ理論では、すべての頂点をうまく2つの集合に分けたときに、自分の集団内に対しては枝がなく、相手の集団間に枝が存在するグラフのことを「2部グラフ」と定義しています。
現実の世界での例を挙げてみます。
世界には様々な組織(大学、企業、高校、etc)があり、その組織に所属する人間がいます。
上が5つの塾、下が所属する生徒と考えてみましょう。
このとき、塾と生徒は「所属」という枝で結ばれていますが、塾と塾、生徒と生徒間の間には枝がないです。
ここで、塾と生徒をそれぞれ枝集合AとBに分けてみましょう。
すると、集合AとBの要素間に枝は存在するものの、A内の要素同士、B内の要素同士に枝は存在しません。
こういった分割が可能なグラフの関係性を2部グラフという、と定義した訳です。
ところでこの2部グラフ、関係性という枝によって結ばれる端点同士が、異なる2つの意味合いを持つときに現れやすいです。
ここでいうと所属という関係性の元、異なる意味合いを持つ塾と生徒が結ばれていますね。
他にも最も分かりやすい例では、性交渉をした関係性は(同性愛者を除き)異なる性別である男と女が枝で結ばれます。
例えば話したことがあるという関係性の元では男同士、女同士でも話すわけですから、二部グラフにはなりません。
では、ここで同じ塾に通う生徒同士のネットワークを描きたい、と思ったらどうなるでしょうか。
上の図では6,8,9さんは同じ塾に通っているから枝を張る、という訳です。
性交渉では、いわゆる穴兄弟のネットワークを張るという意味です。
このネットワークの定義を知らないので、「同所属ネットワーク」と以下呼んでみます。
これとは違う例ではありますが、同所属ネットワークを書く機会があったため、数学的な計算法を紹介しておきます。
まず、隣接行列を作ってください。
(n,m)成分は頂点nからmに枝があるとき、その成分を1とする行列です。
ここでは、上の図の例を使います。
この隣接行列を2乗してください。
このとき、この2乗の行列の各成分は、
です。
これを使って、先ほどの2部グラフを、塾についてと生徒についての2つのグラフへ分けてみます。
1〜5の塾のネットワークと6〜15の生徒のネットワークに分かれていますね。
自分に対するループ枝は、自分の所属する塾あるいは生徒の数です。
他のノードに対する枝は、共通する塾に行く生徒同士、あるいは共通する生徒を持つ塾同士を繋いでいます。
背景にある定理は、
であり、その系として、
証明をしておきましょう。
ただし、小さなネットワークに対してスマートな計算法であっても、大きなネットワークに対しては巨大な計算量とメモリを消費することになります。
巨大なものに対しては、疎行列に対するアルゴリズムを適用することで軽量化できます。
本当に莫大な計算が必要なときは、やはり枝リストから重みなしで数え上げるのが一番速いと思われます。(重みありならば疎行列に対する積と実質同じになる。)
今回の記事でRのプログラムを使ったので、後々紹介します。
疎行列積や枝リストからの数え上げはやる気が出次第取り組んでみます。