スポンサードリンク
前回の続きでグラフ構造の評価方法について述べていきます。
相互性
有向グラフにおいて、頂点間の関係のうち有向辺がお互いに向いているものの割合です。言い換えると両思いの割合です。
以下の図に示すように、頂点には４パターンの関係が考えられます。
そして上の図で言えば、相互性は次のように定義されます。
\begin{eqnarray}
\mathrm{reciprocity} = \frac{a}{a+c+d}
\end{eqnarray}
しかし上記の定義は一部である。上の定義式の分子にbを加えた場合の定義も存在する。
両者の区別は、分析の目的に応じて異なる。企業間の株式のネットワークにおいてはaとbは全く別の状態であるが、集団における贈与のネットワークにおいて、互酬性の規範がどの程度守られているかを知りたいときには、aとbは同等のものとして扱うべきである。
なぜなら、互酬性の規範に反するのは、贈与が一方向に行われている場合（図のcとd）であり、お互いに無関係（b）の場合は、規範に反していない。一応その場合の定義を以下に示す。
\begin{eqnarray}
\mathrm{reciprocity} = \frac{a+b}{a+b+c+d}
\end{eqnarray}
階層的構造
出-木構造の必要十分条件として以下の4つが定義されている。
連結性、階層性、効率性、最小上界性である。これらに違反している程度からある有向グラフが階層的構造を持っているかどうかを評価する。
連結性
辺の方向を無視した時グラフ全体で相互に到達可能な頂点の組みがどれくらいあるかによって連結性を定義できる。辺の方向を無視しても相互に到達不可能な頂点の組の数をVとすると、全ての頂点間の組みの数に対するその比率を１から引くことで求める。
\begin{eqnarray}
\mathrm{connectedness} &=& 1 – \frac{V}{\frac{n(n-1)}{2}}
&=& 1 – \frac{2V}{n(n-1)}
\end{eqnarray}
階層性
上の図のように、上から下へ一方向ではなく、相互に到達可能な関係があるとすれば、それは上下関係とは呼べず、階層性に違反していることになる。
よって、双方向に到達可能な頂点の組みの数V、少なくとも一方から他方へ到達可能な頂点の組数でをMaxVとすると以下の式で表現できる。
\begin{eqnarray}
\mathrm{hierarchy} &=& 1 – \frac{V}{\mathrm{Max}V}
&=& 1 – \frac{2V}{n(n-1)}
\end{eqnarray}
上の図の場合、双方向に到達可能な組みがないので、階層性は0になる。
スポンサードリンク
弱連結
上のグラフでいうと頂点1,2,3,のような関係。
離散数学的な定義
- • 任意の頂点u, v間が、弧ではつながっている
図で示すと
みたいな感じである。
効率性
出-木構造は上位の頂点から下位の頂点へと必ず一つの経路を通って到達できるという意味で効率的である。しかしそのような経路が複数ある場合それは無駄であるため、そのような効率がどの程度実現しているかを表す指標が効率性である。
今、n個の頂点とm個の有向辺からなる弱連結の有向グラフを考える。もしこの有向グラフが出-木構造なら有向辺の数は、m = n -1 となる。
よって出-木構造でない実際の有向グラフに含まれる冗長な有向辺の数はm-(n-1)となる。
mの理論的な最大値はn(n-1)となるから、冗長な有向辺の数の理論的最大値はn(n-1)-(n-1)である。
これらを用いて、効率性は次のように定義できる。ただしVは冗長な有向辺の数、MaxVは冗長な有向辺の理論的最大値である。
\begin{eqnarray}
\mathrm efficiensy &=& 1 – \frac{V}{\mathrm{Max}V}\\
&=& 1 – \frac{m-(n-1)}{n(n-1)-(n-1)}\\
&=& 1 – \frac{m-(n-1)}{(n-1)^2}
\end{eqnarray}
弱連結でない場合（すいませんがここからよく理解できていません）
文章も砕けた感じになります。
私が参考にしている本では
「この場合は、いくつかの連結成分に分かれている場合がある。この場合、それぞれの連結成分が出- 木構造となっているのがもっとも効率的である。」と書いてあります。
？？？？
まず言葉の定義から
連結成分
以下の図を考えます。
連結成分とは同値関係におけるグラフGの部分グラフである。
{1,2,3},{4},{5,6,7}は連結成分を誘導するという。
でこの連結成分が、上の{1,2,3}のように閉ループを構成するのではなく、
こんな感じになってれば、良いと言っています。
要は、全体で」見たと時に弱連結でなくとも、部分グラフ単体で見た時に、出-木構造になっている時に、もっとも効率が良いということだろう。
弱連結でない時の定義
直感的に十分理解できる。別れている部分グラフのごとに先ほどの定義式を使うだけである。そしてシグマを取れば良い。
有向グラフがN個の連結成分に別れている時、i番目の連結成分に含まれる頂点の数をniとすると、効率性は以下のように定義できる。
\begin{eqnarray}
\mathrm{efficiensy} &=& 1 – \frac{m-\sum^{N}_{i=1}(n_{i}-1)}{\sum^{N}_{i=1}n_{i}(n_{i}-1)-(n_{i}-1)}\\
&=& 1 – \frac{m-\sum_{i=1}^{N}(n_{i}-1)}{\sum_{i=1}^{N}(n_{i}-1)^2}
\end{eqnarray}
実際に計算してみる
階層構造の４つの指標について実際に計算してみることにする。
計算する有向グラフを以下に示す。
計算の簡便化のために以下のような表を作成する。条件に当てはまるものが1、当てはまらないものが0である。
| 頂点のペア | 一方向に到達可能 | 双方向に到達可能 | 最小上界をもつ |
| 1-2 | 0 | 0 | 0 |
| 1-3 | 1 | 0 | 1 |
| 1-4 | 1 | 0 | 1 |
| 1-5 | 0 | 0 | 0 |
| 2-3 | 0 | 0 | 0 |
| 2-4 | 1 | 0 | 1 |
| 2-5 | 1 | 1 | 1 |
| 3-4 | 1 | 0 | 1 |
| 3-5 | 0 | 0 | 0 |
| 4-5 | 1 | 0 | 1 |
連結性
この有向グラフは弱連結であるので、全ての頂点間で到達可能であるため連結性は1である。
階層性
有向辺を辿って少なくとも一方向に到達可能なペアに対する双方向に到達可能なペアの比率を1から引いて求めるられる。一方向に到達可能なペアは6つ、両方向に到達可能なペアは1つなので
\begin{eqnarray}
1-\frac{1}{6} = 0.833333
\end{eqnarray}
効率性
効率性は「階層性のうち冗長な経路の数の多さ」を評価しているので、上の表は関係ない。頂点の数と有向辺の数に依存するので、
\begin{eqnarray}
1-\frac{6-(5-1)}{(5-1)^2} = 0.875
\end{eqnarray}
最小上界性
上の表より最小上界を持たないペアの数は4ペア。最小上界性を求める式を用いて計算すると
\begin{eqnarray}
1-\frac{2 \times 4}{(5-1) \times (5-2)} = 0.33333
\end{eqnarray}
となる。
以上でネットワーク構造の評価法の相互性と階層構造について述べてきた。
次は、前回と前々回にやったColemanの高校生の友人ネットワークのデータを用いて、これまで述べてきた指標について計算し、その結果とそこから導かれる背景について論じていこうと思う。
スポンサードリンク
