第Ⅰ部社会ネットワーク分析への招待第３章社会ネットワーク分析にはどんな数学が必要か Social Network Seminar 内容１．社会ネットワークを表現する根本ツールとしてのグラフ２．方向をもつグラフ –ダイグラフ３．社会ネットワークの行列表現とその演算４．特殊な諸グラフ →社会ネットワーク分析にはグラフが必要。 1 １．グラフ社会ネットワーク分析・・・技法の体系 →技術的な側面の理解が必要 →数学的な基礎・グラフ理論グラフの基礎グラフGは、pの点とqの互いに素な点の非順序対からなる集合Eをもった、空でない有限集合V=V(G)から構成される。このときGは位数p、規模qをもつという。 2 グラフの基礎 Eにおける点の対e={u,v}：Gの辺(edge) ”eはuとvを結合している” ”uとvは隣接点である” ”辺eはu,vに接続的である” (p,q)グラフ：pの点とqの辺をもったグラフ次数：ある点が隣接する他の点の数次数列：各点の次数を降順に並べたものグラフを一意的に決定するものグラフは頂点の集合Vと辺の集合Eの対として、 G=<V,E>のように表現される。また、 V(G)：グラフGの点の集合 E(G)：グラフGの辺の集合と書く。 3 隣接行列(adjacency matrix) 点同士の結合があるとき１、ないとき０と表した行列 →隣接行列図のグラフG1において、 G1の隣接行列A(G1)は、 • 次数は各行か各列の和である。 • 次数列は{4.3.2.2.1}である。 4 距離行列と連結グラフ基本用語歩道：点と辺が代わる代わる連続したもの歩道の長さ：辺の出現回数小道：同じ辺が二度以上現れない歩道道：同じ点が二度以上現れない歩道点uで始まり、vで終わる歩道をuv歩道と呼ぶ 5 距離行列と連結グラフ基本用語つづき uv歩道において、u=vであるような歩道を"閉じている“ という。閉小道：閉じた小道回路：自明でない閉小道閉路：点がすべて異なる回路無閉路グラフ：閉路を含まないグラフ 6 連結グラフグラフGにおいて、どの２点u-vの間にも道が存在するとき、Gは連結しているといわれ、そうでない場合、非連結といわれる。グラフとは、部分的グラフが連結してできたものである距離：u,v間の道の長さの最小値 →その道のことを測地線という距離行列：各点間の距離を測定し、それを行列にまとめたもの直径：行列の成分の最大値距離行列は様々なモデルにおいて利用される。 7 密度完備グラフ：グラフの各点からすべての他の点に辺が存在するグラフ規模nのグラフ Gの密度d (G )  m(G ) / m( K n ) m(G：グラフ ) Gの辺の数　m( K n ：点が ) nからなる完備グラフ 8 部分グラフ部分グラフ：一つのグラフの中に小さな部分として含まれるグラフ → V ( H )  V (G)でかつ E ( H )  E (G)であるとき、グラフ HはGの部分グラフである。 9 部分グラフ v  V (G )かつ | V (G ) | 2であるときに点集合 V (G )  {v}をもつ部分グラフを G  vと書くまた、 e  E (G )とするとき、辺集合 E (G )  {e}をもつ部分グラフを G  eと書く点や辺の添付も同様に、 G  fと書く 10 誘導部分グラフ UをV(G)の空でない点の部分集合とする ”Uによって誘導される”Gの部分グラフ<U>：点集合U をもち、かつUの二点に接続しているGの辺のすべてからなる辺集合をもつグラフ点誘導部分グラフ（単純に誘導部分グラフともいう）： Uに対して H  U  であるときの H  H  G 辺誘導部分グラフ：点誘導部分グラフと同様。 11 ２．ダイグラフ～方向をもつグラフ～ →グループ・ダイナミクスの小集団研究的な発想有向グラフ（ダイグラフ）D：グラフと同じ。 →点の対を”辺”ではなく、Dの”弧”とよぶ。方向が考慮されている。出ていく弧の数・・・出次数入ってくる弧の数・・・入次数 →隣接行列において、出次数は各行の和、入次数は列の和で求められる。 12 長さrの通路：r+1個の点が、互いに方向のある弧でつながっている系列長さrの半通路：r+1個の点が、方向を無視してつながっている系列 r-到達可能：点iから点jへ長さr以下の通路が存在する状態ダイグラフにおける距離行列の成分は、最短の通路の長さを表している。 13 連結度連結度k(D)（点-連結度）：それを除去することでダイグラフの連結性が失われてしまうような最小の点の数。通常のグラフでも同定義。辺-連結度k’(D)：その辺を除去することでダイグラフの連結性が失われてしまうような最小の辺の数。それを除くと連結が切れてしまう点・・・切断点それを除くと連結が切れてしまう辺・・・橋辺 14 ダイグラフ結合の類型到達可能の観点から、異なる種類の結合を定義できる。弱r-結合：点iと点jの間に長さr以下の半通路が存在する。（単純に"弱結合”と呼ぶ場合もある）片方r-結合：点iと点jの間に長さr以下の通路が存在する。強r-結合：点iと点jおよび点jと点iの間に長さr以下の通路が存在する。弱r-結合：点iと点jおよび点jと点i間に長さr以下の通路が存在し、それらが同じ点を使う逆の順番の通路が存在する。結合の強さ・・・弱＜片方＜強＜再帰 15 推移性点AからB、BからCに結合関係がある →AからCにも関係があるという関係を”推移的である” という。 →関係が推移的であると集団の結合はより強固になる推移度 2 ( A  A)  Tran( D)  2 2 ( A  diagA )  2 2 AはダイグラフDの隣接行列diagAはA の対角を０に置き換えてできた行列 16 推移的包括推移的包括Dt・・・間接的な結合関係を直接的な結合関係に変換する。すなわち、ダイグラフDにおいて uとvの間に長さ２の通路があるとき、そのたびに Dに存在しない弧を、できなくなるまで追加していったときに得られる最小の推移的なダイグラフのこと。 17 連結成分ダイグラフ全体が弱、片方、強、再帰的の結合で特徴づけられるとき、そのダイグラフは、それぞれ弱、片方、強、再帰的に連結したダイグラフとよばれる。またダイグラフの部分がそれ以上の規模が大きくならない結合で特徴づけられるとき、それをその結合の連結成分とよぶ。 18 ３．社会ネットワークの行列表現とその演算社会構造を一意的に記述する隣接行列グラフで表現すると、形が異なって見えるが実際は構造が同じということがあるが、隣接行列表現ではそうはならない。《図２つと行列》 cf.二部グラフグラフの隣接行列 19 行列演算～和、差、積、プール演算～行列Cの(i, j )成分を(C ) ij  cijで表すと、 ( A  B ) ij  aij  bij ( A  B ) ij  aij  bij ( A  B ) ij  aijbij Aが m  n、 Bが n  rのとき、 AB  Cつまり、 n cij  ai1b1 j  ai 2b2 j    ainbnj   aik bkj k 1 転置：行列の行と列を逆にしたもの行列Aに対しA'と表記 AA  A2は、 aij( 2)  ai1b1 j  ai 2b2 j    ainbnj A3  A 2 A 20 行列演算～和、差、積、プール演算～プール演算：整数０，１上に定義される２進法の演算。x,yを非負の整数とすると、和を(x+y)#と表記し、その和は０か１である。 2#=（1+1）=1,3#=1となる。さらに(2+3)#=1である。 21 到達可能性行列隣接行列とプール演算を利用すると、到達可能性についての計算ができるようになる。到達可能性行列：点 iが点jに到達可能であるとき、 rij  1、そうでないとき 0であるような行列　ただし rii  1 22 ここで、定理：隣接行列 Aをもった (ダイ )グラフにおいて、 Anの i, j成分は点iから jへの長さ nの歩道の数を表す。 →プール演算を利用すると、隣接行列を累乗すれば到達可能性行列が得られるかもしれないさらに定理：隣接行列 An # の i, j成分aij( n ) #はダイグラフ Dの点iから jへの長さ nの歩道が少なくとも１そのときにかぎって１本あるときには、である。 →nステップまで到達可能かどうかを表す到達可能性行列を与える。→限定到達可能性行列 23 距離行列定理各正の整数nに対して、 Rn  ( I  A  A2    An )#  ( I  An )# また、 R  ( I  A  A2    A p 1 )#  ( I  An ) p 1 # →これにより（ダイ）グラフにおける最短の通路の長さを与える、距離行列が求まる。距離グラフの求め方 (1)すべての対角、 d ii  0 (2)rij  0なら、 d ii   (3)d iiは、 An #において、 aijn #  1となっているような最小ステップ数 24 ４．特殊な諸グラフ重み付きグラフ弧にあらゆる種類の値が与えられるダイグラフを、重み付きグラフとよぶ。 →ネットワークとは、xij  vij , v  R(実数) であるようなダイグラフここで２つの終点ネットワークNはDからなり、それは２つの相異なる点s,tと、Dの弧上に負でない実数関数 cを伴う。 s・・・ネットワークの入口 t・・・ネットワークの出口他の点・・・内部点また、弧e∈N各々に対して、値c(e)で表されるeの容量が与えられる。 25 流れ（フロー）流れ（フロー）f：Nの弧に負でない実数を与えたものこのときの条件 (1)各弧の値はその容量を超えてはならない (2)s,t以外の各点に対して、入ってくる流れと出てくる流れは等しくなければならない 26 最大フロー s-tの切断集合：入口sと出口tを分離する弧の集合 ※何パターンもある集合の容量：各要素である弧の容量を総和したもの。もっとも容量が少ないものを"最小切断容量"という。 →sからtまでを流れうる最大値・・・"最大ネットワーク・フロー" 点対に関して最大ネットワークフローを求めたもの・・・最大フロー行列 27 最高到達可能性ここで A  [aij ], B  [bij ] で表される２つの重み付きグラフで表される社会ネットワークにおいて、 A  B  [aij  bij ], A  B  [aij  bij ] とする。ここで、( ) はAとBの要素のうち大きい方を、( ) はAとBの要素のうち小さい方を選ぶということを表すここでAとBの行列演算A＊Bを n A＊B  [  (aik  bkj )]  (ai1  b1 j )  (ai 2  b2 j )   (ain  bnj ) k 1 と定義する。 →まず要素ごとに最小値を選び、それからその中の最大値を選ぶという演算。 28 最高到達可能性この演算を使うと、重み付きグラフの道に関する値を与えるという操作を定義できる。定理 Wを重み付きグラフ、Aをその隣接行列とする。そのとき A＊A A  A p＊はWの各点対の間のpステップの歩道の最高レベルを与える。 →各ステップでの道の重みが求められる定理行列 T  np1 P p＊はすべての点対の間の最高到達可能レベルを与える n A → ＊を"ドレイアン・ベキ"とよぶ 29 バイグラフバイグラフ：実数値に限られない様々な”値”を扱えるように拡張されたもの定義有値ダイグラフVは、p個の点をもち、各弧に値が与えられているダイグラフであり、それは値域Q の要素である。弧のとき値は実数値でなくてもよい。 Vに対する有値行列Mの成分、mij は点iから点jまでの弧の値である。→重み付きグラフの一般化 30 一般的諸条件と諸条件を満たす演算二項演算の一般和、一般積演算、一般和の単位元、一般積の単位元が定義され、以下の条件が満たされたとき、特殊な演算について各種のr-到達度が求められる。条件１：Qがに関して閉じていること条件２：が結合的で交換的であること条件３：Qのすべてのa,b,cに関して、に対して右分配的で、条件４：Qは、そのすべての要素aに対して、を有し、条件５：Qは、そのすべての要素aに対して、を有し、条件６：Vのすべての隣接しないような点iと点jに対して、条件７：Mのすべての対角成分は、に設定される。つまり1≦i≦pに対して、条件８：Qのすべてのa,bに対して、 {min,max,∞,-∞}、{∪，∩，φ，R}という演算体系もある 31 ハイパーグラフハイパーグラフ・・・点と線の異なるモードに関する数学グラフ。点の線への接続関係によってグラフが定義される。定義：点の集合をX  {x1 , x2 ,, xn } とする場合、ハイパーグラフはXの上に定義される辺の集合H  {E1 , E2 ,, En } である。ここで、 Ei   (i  1,2,, n)で、  Ei  X ,  {X , E} i 1, 2,,n で表される。 32 ハイパーグラフ →点が辺に属している様を表現したもので、点が多重的に辺に接続している関係を表現している。接合行列：どの点がどの辺を構成するかという接続関係を行列式で表現したもの。各成分は接続があれば１、なければ０である。 33 まとめ社会ネットワーク分析に必要な数学とは１．グラフ２．ダイグラフ３．行列４．重み付きグラフ（バイグラフ）５．ハイパーグラフ 34