第4章 度相关性与社团结构,4.1 引言,度分布尽管是网络的一个重要拓扑特征，但是不能由它唯一的刻画一个网络，因为具有相同度分布的两个网络可能具有非常不同的其他性质或行为。为进一步刻画网络的拓扑结构，需考虑包含更多结构信息的高阶拓扑特征。本章介绍刻画网络的二阶度分布特性（也称度相关性）的几种不同方法，包括最为一般但较为复杂的联合概率分布、更为简洁但不宜比较的条件概率和余平均度以及可以定量刻画度相关性但过于粗略的相关系数。 即使是联合概率分布也仍然不能完全刻画网络拓扑。一个典型例子就是复杂网络的社团结构；实际网络往往可以视为是由若干个社团构成，每个社团内部的节点之间的连接相对较为紧密，但是各个社团的连接相对比较稀疏。本章将介绍大规模网络社团结构分析所面临的挑战以及几个有代表性的算法。,4.2 度相关性与同配性,4.21 高阶度分布的引入 网络的0阶度分布特性：平均度=2M/N 只告诉我们网络中有多少条边，并没有给出这些边是如何安置在网络中。给定网络的节点数N和边数M，那么任一与该网络具有相同节点数和边数的网络模型也具有相同的平均度。 网络的1阶度分布特性：度分布P(k)=n(k)/N 其中n(k)是网络中度为k的节点数；度分布刻画了网络中不同度的节点各自所占的比例。显然度分布中已经包含了平均度的信息 具有相同度分布的两个网络可能具有非常不同的其他性质或行为。eg:P121 为进一步刻画网络的拓扑结构，考虑包含更多结构信息的高阶拓扑特性。,4.2 联合概率分布（2阶度分布特性）,联合概率：网络中随机选取的一条边的两个端点的度分别为j和k的概率，即为网络中度为j的节点和度为k的节点之间存在的边数占网络总数的比例。 其中，m(j,k)是度为j的节点和度为k的节点之间的连边数。,联合概率分布的性质： （1）对称性，即 （2）归一性，即 （3）余度分布，即,表示网络中随机选取的一个节点随机选取的一个邻居节点的度为k的概率。也就是说，在网络中随机选取一个节点，然后再从该节点出发随机地沿着一条边到达一个邻居节点，该邻居节点的度为k的概率即为 一般而言， 与度分布P(k)是不同的。例如，我们无法从一个节点出发到达网络中的孤立节点。因此，在网络中存在孤立节点的情形：,记 下式表明网络的二阶度分布特性包含了1阶度分布特性：,如果网络中两个节点之间是否有边相连与这两个节点的度值无关，也就是说，网络中随机选择的一条边的两个端点的度是完全随机的，即有 那么就称网络不具有度相关性，或者称网络是中性的；否则就称网络具有度相关性。 对于度相关的网络，如果总体上度大的节点倾向于连接度大的节点，就称网络是度正相关的，或称网络是同配的；如果总体上度大的节点倾向于连接度大小的节点，就称网络是度负相关的，或称网络是异配的。具有相同度序列/度分布的网络可以具有完全不同的度相关性（P122图4-2）。,判断度相关性的更为简洁的方法：计算度为k的节点的邻居节点的平均度，也称度为k的节点的余平均度，记为 假设节点i的 个邻居节点的度为 我们可以计算节点i 的余平均度，即节点i的 个邻居节点的平均度 如下： （egP124图4-4） 假设网络中度为k的节点为 那么度为k的节点的余平均度可计算如下：,与条件概率和联合概率之间具有如下关系： 如果 是k的增函数，那么就意味着平均而言，度大的节点倾向于与度大的节点连接，从而表明网络是同配的；反之， 那么就意味着平均而言，度大的节点倾向于与度小的节点连接，从而表明网络是异配的；如果网络不具有度相关性，那么 是一个与k无关的常数：,网络是度相关的就意味着 和 之间不恒等。 用二者的差刻画网络的同配或者异配程度，即： （4-15） 当网络完全同配时，（4-17）达到最大，即为余度分布： （4-16）,4.2.4 同配系数,于是得到归一化系数（同配系数）： （4-17） r0，网络是同配的； r0，网络异配。 r的数值大小反应了网络的同配或异配强弱程度。,蛋白质交互网络和神经网络以及交互互联网和WWW等技术都是异配的； 科研人员合作和电影演员合作等许多现实网络呈现同配性质； 不同的在线网络呈现不同的性质。 度同配起源的解释 1、社会学 2、心理学 近些年的社会网络发展冲破了社会阶层之间的无形壁垒。 （P127）,4.2.5 实际网络的同配性质,4.2.6 同配概念的一般化,同配就是指属性相近的节点倾向于互相连接。这里的属性可以是度也可以是其他特性，例如社会网络中个体的职业、年龄、种族、信仰等。 社会网络同质性的两种基本解释： 1、选择，即人们倾向于和相似的人成为朋友； 2、影响，即人们由于成为朋友而相互影响，从而变得更相为似。 社会网络面临的重大挑战：区分选择和影响这两个因素以及如何判断哪一个因素的作用更大。 （P128）,4.2.6 同配概念的一般化,关于度同配性的一些方法也可以推广到判断其他特征的同配性质： 社会网络中社会年龄性质的同配性。定义条件概率 为网络中随机选取的一个年龄为t的个体的一个邻居的年龄为 的概率。P128的图48给出了t=20、30、40、50、60时Facebook网络的条件概率分布。 可以看到，每一天曲线都是以t=t为峰值的。 度同配性也可以推广到其他属性的情形。我们用标量参数 表示节点的某个属性。假设一个无向网络中有M条边， 为网络的邻接矩阵。每条边有两个端点，对所有M条边的2M个端点的属性取平均值，得到：,4.2.6 同配概念的一般化,（P129） 考虑网络中每条边的两个端点i和j所对应的 ，他们的协方差为：,4.2.6 同配概念的一般化,4.2.6 同配概念的一般化,令 ，得到 的方差如下： 同配系数的定义就是归一化的协方差：,4.2.6 同配概念的一般化,令 ，得到 的方差如下： 同配系数的定义就是归一化的协方差：,