同配性

维基百科,自由的百科全书
跳转至: 导航搜索

同配性Assortativity), 用作考察值相近的节点是否倾向于互相连接。

如果总体上度大的节点倾向于连接度大的节点,那么就称网络的度正相关的,或者成网络是同配的;如果总体上度大的节点倾向于连接度小的节点,那么就称网络的度负相关的,或者成网络是异配的。[1]

同配性计算[编辑]

联合度分布[编辑]

网络的度分布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_jq_k,则网络不具有度相关性[1]

余平均度[编辑]

余平均度是节点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_jq_k}{q_k}=\sum_j jq_j=\sum_j j\frac{jp_j}{<k>}=\frac{<k^2>}{<k>}[1]

同配系数[编辑]

网络是度相关的就意味着e_{jk}q_jq_k之间不恒等。可以考虑用两者之间的差的大小刻画网络的同配或者异配程度,即如下定义的度相关函数:

<jk>-<j><k>=\sum_{j,k} jk(e_{jk}-q_jq_k)

当网络为完全同配时,e_{jk}=q_k\delta_{jk}<jk>-<j><k>达到最大值,即为余度分布q_k的方差:

\sigma_q^2=\sum_k k^2q_k-[\sum_k kq_k]^2

于是得到归一化的相关系数,即同配系数,记为r

r=\frac{\sum_{j,k} jk(e_{jk}-q_jq_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_ik_j}{2M})x_ix_j}{\displaystyle\sum_{i,j}(k_i\delta_{ij}-\frac{k_ik_j}{2M})x_ix_j}=\frac{\displaystyle\sum_{i,j}(a_{ij}-\frac{k_ik_j}{2M})k_ik_j}{\displaystyle\sum_{i,j}(k_i\delta_{ij}-\frac{k_ik_j}{2M})k_ik_j}
\displaystyle =\frac{S_1S_e-S_2^2}{S_1S_3-S_2^2}=\frac{\displaystyle(\sum_ik_i)(2\sum_{(i,j)\in E}k_ik_j)-(\sum_ik_i^2)^2}{\displaystyle(\sum_ik_i)(\sum_ik_i^3)-(\sum_ik_i^2)^2}

对于有向图,也可以利用皮尔逊积矩相关系数r=\frac{\sum_{xy} xy(e_{xy}-a_xb_y)}{\sigma_a \sigma_b}计算,即r=\frac{\sum_{j,k} jk(e_{jk}-q_j^{in}q_k^{out})}{\sigma_{in}\sigma_{out}}[1][2][3]

算法[编辑]

参考资料[编辑]

  1. ^ 1.0 1.1 1.2 1.3 汪小帆 陈关荣. 网络科学导论. 
  2. ^ M. E. J. Newman. Assortative mixing in networks. 
  3. ^ M. E. J. Newman. Mixing patterns in networks.