同配性(Assortativity), 用作考察度值相近的頂點是否傾向於互相連接。
如果總體上度大的頂點傾向於連接度大的頂點,那麼就稱網絡的度正相關的,或者成網絡是同配的;如果總體上度大的頂點傾向於連接度小的頂點,那麼就稱網絡的度負相關的,或者成網絡是異配的。[1]
同配性計算[編輯]
聯合度分布[編輯]
網絡的度分布
為一階度分布,聯合度分布可理解為二階度分布,或網絡度的聯合概率分布。
聯合度分布
為兩個端點的度分別為j和k的概率,
為對應連邊數,如果j=k,
,否則
余度分布
,即網絡度的邊緣分布,表示隨機頂點的鄰居頂點為k的概率。
如果二階度分布是完全隨機的,即恆有
,則網絡不具有度相關性。[1]
余平均度[編輯]
余平均度是頂點i的鄰居頂點的平均度,記為
,度為k的頂點的余平均度記為
。
![{\displaystyle <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'}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5f4caa788ac40db2e14b510b2d348d7489437e56)
如果
是k的增函數,那麼就意味著平均而言,度大的頂點傾向於與度大的頂點連接,從而表明網絡是同配的;反之,如果
是k的減函數,那麼就意味著平均而言,度大的頂點傾向於與度小的頂點連接,從而表明網絡是異配的;如果網絡不具有度相關性,那麼
是一個與k無關的常數:
[1]
同配係數[編輯]
網絡是度相關的就意味著
與
之間不恆等。可以考慮用兩者之間的差的大小刻畫網絡的同配或者異配程度,即如下定義的度相關函數:
![{\displaystyle <jk>-<j><k>=\sum _{j,k}jk(e_{jk}-q_{j}q_{k})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d8b0b34c7ed62c0a2164add0c8bdd35f18d71fdf)
當網絡為完全同配時,
,
達到最大值,即為余度分布
的方差:
![{\displaystyle \sigma _{q}^{2}=\sum _{k}k^{2}q_{k}-(\sum _{k}kq_{k})^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0cc0aecbc0de7a79f03998b9d030c4a125d75a9e)
於是得到歸一化的相關係數,即同配係數,記為r:
![{\displaystyle r={\frac {\sum _{j,k}jk(e_{jk}-q_{j}q_{k})}{\sigma _{q}^{2}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5439f60c628f03ef7462fc9853bf4535c8f1e2a9)
其中r>0代表網絡同配,r<0代表網絡異配,|r|的大小反映了網絡同配或異配的強弱程度。
令屬性值
為度值
,可從皮爾遜積矩相關係數計算同配係數:
![{\displaystyle \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}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8dd1694626293bb10dae443e381f1cfa6464ae34)
![{\displaystyle \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}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cc50e33a20e59b300d23b95e57ac4d5a38ba4fde)
對於有向圖,也可以利用皮爾遜積矩相關係數
計算,即
[1][2][3]
N點星型網絡,其中包括度為N-1的1個點,度為1的N-1個點
所以星型網絡是異配的。
用另外一個公式會得到一樣的值。
參考資料[編輯]
- ^ 1.0 1.1 1.2 1.3 汪小帆 陳關榮. 网络科学导论.
- ^ M. E. J. Newman. Assortative mixing in networks (PDF). [2014-05-02]. (原始內容 (PDF)存檔於2019-12-07).
- ^ M. E. J. Newman. Mixing patterns in networks.