同配性

同配性（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 （頁面存檔備份，存於互聯網檔案館）