同配性

同配性（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 （页面存档备份，存于互联网档案馆）