同配性

**同配性**（**Assortativity**）, 用作考察度值相近的頂點是否傾向於互相連接。

如果總體上度大的頂點傾向於連接度大的頂點，那麼就稱網絡的度正相關的，或者成網絡是**同配**的；如果總體上度大的頂點傾向於連接度小的頂點，那麼就稱網絡的度負相關的，或者成網絡是**異配**的。

## 同配性計算

### 聯合度分布

網絡的度分布 $P(k)={\frac {n(k)}{N}}$ 為一階度分布，**聯合度分布**可理解為二階度分布，或網絡度的聯合概率分布。

聯合度分布 $e_{jk}=P(j,k)={\frac {m(j,k)\mu (j,k)}{2M}}$ 為兩個端點的度分別為 j 和 k 的概率， $m(j,k)$ 為對應連邊數，如果 j=k， $\mu (j,k)=2$ ，否則 $\mu (j,k)=1$

余度分布 $q_{k}=P_{n}(k)=\sum _{j=k_{min}}^{k_{max}}P(j,k)$ ，即網絡度的邊緣分布，表示隨機頂點的鄰居頂點為 k 的概率。

如果二階度分布是完全隨機的，即恆有 $e_{jk}=q_{j}q_{k}$ ，則網絡**不具有度相關性**。

### 余平均度

**余平均度**是頂點 i 的鄰居頂點的平均度，記為 $<k_{nn}>_{i}={\frac {1}{k_{i}}}\sum _{j=1}^{k_{i}}k_{i_{j}}$ ，度為 k 的頂點的余平均度記為 $<k_{nn}>(k)={\frac {1}{i_{k}}}\sum _{v_{i}=1}^{i_{k}}<k_{nn}>_{v_{i}}$ 。

　
: $<k_{nn}>(k)=\sum _{k'=k_{min}}^{k_{max}}k'P_{c}(k'|k)={\frac {1}{q_{k}}}\sum _{k'=k_{min}}^{k_{max}}k'e_{kk'}$

如果 $<k_{nn}>(k)$ 是 k 的增函數，那麼就意味著平均而言，度大的頂點傾向於與度大的頂點連接，從而表明網絡是**同配**的；反之，如果 $<k_{nn}>(k)$ 是 k 的減函數，那麼就意味著平均而言，度大的頂點傾向於與度小的頂點連接，從而表明網絡是**異配**的；如果網絡不具有度相關性，那麼 $<k_{nn}>(k)$ 是一個與 k 無關的常數：

　
: $<k_{nn}>(k)={\frac {\sum _{j}je_{jk}}{\sum _{j}e_{jk}}}={\frac {\sum _{j}jq_{j}q_{k}}{q_{k}}}=\sum _{j}jq_{j}=\sum _{j}j{\frac {jp_{j}}{<k>}}={\frac {<k^{2}>}{<k>}}$

### 同配係數

網絡是度相關的就意味著 $e_{jk}$ 與 $q_{j}q_{k}$ 之間不恆等。可以考慮用兩者之間的差的大小刻畫網絡的同配或者異配程度，即如下定義的度相關函數：

　
: $<jk>-<j><k>=\sum _{j,k}jk(e_{jk}-q_{j}q_{k})$

當網絡為完全同配時， $e_{jk}=q_{k}\delta _{jk}$ ， $<jk>-<j><k>$ 達到最大值，即為余度分布 $q_{k}$ 的方差：

　
: $\sigma _{q}^{2}=\sum _{k}k^{2}q_{k}-(\sum _{k}kq_{k})^{2}$

於是得到歸一化的相關係數，即**同配係數**，記為 **r**：

　
: $r={\frac {\sum _{j,k}jk(e_{jk}-q_{j}q_{k})}{\sigma _{q}^{2}}}$

其中 r>0 代表網絡**同配**，r<0 代表網絡**異配**，|r | 的大小反映了網絡同配或異配的強弱程度。

令屬性值 $x_{i}$ 為度值 $k_{i}$ ，可從皮爾遜積矩相關係數計算同配係數：

　
: $\displaystyle r={\frac {cov(x_{i},x_{j})}{\sigma _{x}^{2}}}={\frac {\displaystyle \sum _{i,j}(a_{ij}-{\frac {k_{i}k_{j}}{2M}})x_{i}x_{j}}{\displaystyle \sum _{i,j}(k_{i}\delta _{ij}-{\frac {k_{i}k_{j}}{2M}})x_{i}x_{j}}}={\frac {\displaystyle \sum _{i,j}(a_{ij}-{\frac {k_{i}k_{j}}{2M}})k_{i}k_{j}}{\displaystyle \sum _{i,j}(k_{i}\delta _{ij}-{\frac {k_{i}k_{j}}{2M}})k_{i}k_{j}}}$

　
: $\displaystyle ={\frac {S_{1}S_{e}-S_{2}^{2}}{S_{1}S_{3}-S_{2}^{2}}}={\frac {\displaystyle (\sum _{i}k_{i})(2\sum _{(i,j)\in E}k_{i}k_{j})-(\sum _{i}k_{i}^{2})^{2}}{\displaystyle (\sum _{i}k_{i})(\sum _{i}k_{i}^{3})-(\sum _{i}k_{i}^{2})^{2}}}$

對於有向圖，也可以利用皮爾遜積矩相關係數 $r={\frac {\sum _{xy}xy(e_{xy}-a_{x}b_{y})}{\sigma _{a}\sigma _{b}}}$ 計算，即 $r={\frac {\sum _{j,k}jk(e_{jk}-q_{j}^{in}q_{k}^{out})}{\sigma _{in}\sigma _{out}}}$

### 例子

N 點星型網絡，其中包括度為 N-1 的 1 個點，度為 1 的 N-1 個點

$$
P(N-1,1)=P(1,N-1)={\dfrac {1}{2}}
$$

$$
q_{1}={\dfrac {1}{2}},q_{N-1}={\dfrac {1}{2}}
$$

$$
\displaystyle \sum _{j,k}jk(e_{jk}-q_{j}q_{k})=(1)^{2}(-{\frac {1}{4}})+2(1)(N-1)({\frac {1}{4}})+(N-1)^{2}(-{\frac {1}{4}})={\frac {-(N-2)^{2}}{4}}
$$

$$
\displaystyle \sigma _{q}^{2}=\sum _{k}k^{2}q_{k}-(\sum _{k}kq_{k})^{2}=(1)^{2}({\frac {1}{2}})+(N-1)^{2}({\frac {1}{2}})-({\frac {N}{2}})^{2}={\frac {(N-2)^{2}}{4}}
$$

$$
r={\frac {\sum _{j,k}jk(e_{jk}-q_{j}q_{k})}{\sigma _{q}^{2}}}=-1
$$

所以星型網絡是異配的。

用另外一個公式會得到一樣的值。

$$
S_{1}=2(N-1),S_{2}=N(N-1),S_{3}=(N-1)[(N-1)^{2}+1],S_{e}=2(N-1)^{2}
$$

$$
r={\dfrac {S_{1}S_{e}-S_{2}^{2}}{S_{1}S_{3}-S_{2}^{2}}}={\dfrac {4(N-1)^{3}-N^{2}(N-1)^{2}}{2(N-1)^{2}[(N-1)^{2}+1]-N^{2}(N-1)^{2}}}
$$

$$
={\dfrac {4(N-1)-N^{2}}{2[(N-1)^{2}+1]-N^{2}}}={\dfrac {-(N-2)^{2}}{(N-2)^{2}}}=-1
$$

 

## 算法

* 同配係數的算法：get\_assortative\_coefficient （頁面存檔備份，存於網際網路檔案館）

## 參考資料