同配性(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.