同配性

同配性（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^{\prime }=k_{min}}^{k_{max}}{k}^{\prime }{P}_c(k^{\prime }|k)=\frac{1}{q_k}\sum _{k^{\prime }=k_{min}}^{k_{max}}{k}^{\prime }{e}_{k{k}^{\prime }}$

如果$<k_{nn}>(k)$是k的增函数，那么就意味着平均而言，度大的顶点倾向于与度大的顶点连接，从而表明网络是同配的；反之，如果$<k_{nn}>(k)$是k的减函数，那么就意味着平均而言，度大的顶点倾向于与度小的顶点连接，从而表明网络是异配的；如果网络不具有度相关性，那么$<k_{nn}>(k)$是一个与k无关的常数：

$<k_{nn}>(k)=\frac{\sum _{j}j{e}_{jk}}{\sum _j{e}_{jk}}=\frac{\sum _{j}j{q}_j{q}_k}{q_k}=\sum _{j}j{q}_j=\sum _{j}j\frac{j{p}_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}k{q}_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$，可从皮尔逊积矩相关系数计算同配系数：

$r=\frac{cov(x_i,x_j)}{{\sigma }_x^2}=\frac{\sum _{i,j}(a_{ij}-\frac{k_i{k}_j}{2M})x_i{x}_j}{\sum _{i,j}(k_i{\delta }_{ij}-\frac{k_i{k}_j}{2M})x_i{x}_j}=\frac{\sum _{i,j}(a_{ij}-\frac{k_i{k}_j}{2M})k_i{k}_j}{\sum _{i,j}(k_i{\delta }_{ij}-\frac{k_i{k}_j}{2M})k_i{k}_j}$

$=\frac{S_1{S}_e-S_2^2}{S_1{S}_3-S_2^2}=\frac{(\sum _i{k}_i)(2\sum _{(i,j)\in E}{k}_i{k}_j)-(\sum _i{k}_i^2{)}^2}{(\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)=\frac{1}{2}$

$q_1=\frac{1}{2},q_{N-1}=\frac{1}{2}$

$\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}$

${\sigma }_q^2=\sum _k{k}^2{q}_k-(\sum _{k}k{q}_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=\frac{S_1{S}_e-S_2^2}{S_1{S}_3-S_2^2}=\frac{4(N-1{)}^3-N^2(N-1{)}^2}{2(N-1{)}^2[(N-1{)}^2+1]-N^2(N-1{)}^2}$

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

算法

• 同配系数的算法：get_assortative_coefficient Template:Wayback