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

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

同配性计算

联合度分布

网络的度分布 为一阶度分布,联合度分布可理解为二阶度分布,或网络度的联合概率分布

联合度分布 为两个端点的度分别为j和k的概率, 为对应连边数,如果j=k, ,否则 

余度分布 ,即网络度的边缘分布,表示随机顶点的邻居顶点为k的概率。

如果二阶度分布是完全随机的,即恒有 ,则网络不具有度相关性[1]

余平均度

余平均度顶点i的邻居顶点的平均度,记为 ,度为k的顶点的余平均度记为 

 

如果 是k的增函数,那么就意味着平均而言,度大的顶点倾向于与度大的顶点连接,从而表明网络是同配的;反之,如果 是k的减函数,那么就意味着平均而言,度大的顶点倾向于与度小的顶点连接,从而表明网络是异配的;如果网络不具有度相关性,那么 是一个与k无关的常数

 [1]

同配系数

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

 

当网络为完全同配时,  达到最大值,即为余度分布 的方差:

 

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

 

其中r>0代表网络同配,r<0代表网络异配,|r|的大小反映了网络同配或异配的强弱程度。

令属性值 为度值 ,可从皮尔逊积矩相关系数计算同配系数:

 
 

对于有向图,也可以利用皮尔逊积矩相关系数 计算,即 [1][2][3]

例子

N点星型网络,其中包括度为N-1的1个点,度为1的N-1个点

 

 

 

 

 

所以星型网络是异配的。

用另外一个公式会得到一样的值。

 

 

 


算法

参考资料

  1. ^ 1.0 1.1 1.2 1.3 汪小帆 陈关荣. 网络科学导论. 
  2. ^ M. E. J. Newman. Assortative mixing in networks (PDF). [2014-05-02]. (原始内容 (PDF)存档于2019-12-07). 
  3. ^ M. E. J. Newman. Mixing patterns in networks.