复杂网络(度相关性与社团结构)ppt

第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）余度分布，即,记下式表明网络的二阶度分布特性包含了1阶度分布特性：,如果网络中两个节点之间是否有边相连与这两个节点的度值无关，也就是说，网络中随机选择的一条边的两个端点的度是完全随机的，即有那么就称网络不具有度相关性，或者称网络是中性的；否则就称网络具有度相关性。对于度相关的网络，如果总体上度大的节点倾向于连接度大的节点，就称网络是度正相关的，或称网络是同配的；如果总体上度大的节点倾向于连接度大小的节点，就称网络是度负相关的，或称网络是异配的。具有相同度序列/度分布的网络可以具有完全不同的度相关性（P122图4-2）。,与条件概率和联合概率之间具有如下关系：如果是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、选择，即人们倾向于和相似的人