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

《复杂网络度相关性与社团结构ppt.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章度相关性与社团结构4.1引言度分布尽管是网络的一个重要拓扑特征，但是不能由它唯一的刻画一个网络，因为具有相同度分布的两个网络可能具有非常不同的其他性质或行为。为进一步刻画网络的拓扑结构，需考虑包含更多结构信息的高阶拓扑特征。本章介绍刻画网络的二阶度分布特性（也称度相关性）的几种不同方法，包括最为一般但较为复杂的联合概率分布、更为简洁但不宜比较的条件概率和余平均度以及可以定量刻画度相关性但过于粗略的相关系数。即使是联合概率分布也仍然不能完全刻画网络拓扑。一个典型例子就是复杂网络的社团结构；实际网络往往可以视为是由若干个社

2、团构成，每个社团内部的节点之间的连接相对较为紧密，但是各个社团的连接相对比较稀疏。本章将介绍大规模网络社团结构分析所面临的挑战以及几个有代表性的算法。4.2度相关性与同配性4.21高阶度分布的引入网络的0阶度分布特性：平均度=2M/N只告诉我们网络中有多少条边，并没有给出这些边是如何安置在网络中。给定网络的节点数N和边数M，那么任一与该网络具有相同节点数和边数的网络模型也具有相同的平均度。网络的1阶度分布特性：度分布P(k)=n(k)/N其中n(k)是网络中度为k的节点数；度分布刻画了网络中不同度的节点各自所占的比例。

3、显然度分布中已经包含了平均度的信息具有相同度分布的两个网络可能具有非常不同的其他性质或行为。eg:P121为进一步刻画网络的拓扑结构，考虑包含更多结构信息的高阶拓扑特性。4.2联合概率分布（2阶度分布特性）联合概率：网络中随机选取的一条边的两个端点的度分别为j和k的概率，即为网络中度为j的节点和度为k的节点之间存在的边数占网络总数的比例。其中，m(j,k)是度为j的节点和度为k的节点之间的连边数。联合概率分布的性质：（1）对称性，即（2）归一性，即（3）余度分布，即表示网络中随机选取的一个节点随机选取的一个邻居节点的度为k的

4、概率。也就是说，在网络中随机选取一个节点，然后再从该节点出发随机地沿着一条边到达一个邻居节点，该邻居节点的度为k的概率即为一般而言，与度分布P(k)是不同的。例如，我们无法从一个节点出发到达网络中的孤立节点。因此，在网络中存在孤立节点的情形：记下式表明网络的二阶度分布特性包含了1阶度分布特性：如果网络中两个节点之间是否有边相连与这两个节点的度值无关，也就是说，网络中随机选择的一条边的两个端点的度是完全随机的，即有那么就称网络不具有度相关性，或者称网络是中性的；否则就称网络具有度相关性。对于度相关的网络，如果总体上度大的节点倾

5、向于连接度大的节点，就称网络是度正相关的，或称网络是同配的；如果总体上度大的节点倾向于连接度大小的节点，就称网络是度负相关的，或称网络是异配的。具有相同度序列/度分布的网络可以具有完全不同的度相关性（P122图4-2）。4.2.3余平均度条件概率：网络中随机选取的一个度为k的节点的一个邻居的度为j的概率，记为.它与联合概率之间具有如下关系：如果条件概率与k相关，那么就说明节点度之间具有相关性，且网络结构具有层次结构；反之，说明网络没有度相关性。考虑到任一条边与某个节点相连的概率与该节点的度成正比，度不相关网络的条件概率为判断

6、度相关性的更为简洁的方法：计算度为k的节点的邻居节点的平均度，也称度为k的节点的余平均度，记为假设节点i的个邻居节点的度为我们可以计算节点i的余平均度，即节点i的个邻居节点的平均度如下：（egP124图4-4）假设网络中度为k的节点为那么度为k的节点的余平均度可计算如下：与条件概率和联合概率之间具有如下关系：如果是k的增函数，那么就意味着平均而言，度大的节点倾向于与度大的节点连接，从而表明网络是同配的；反之，那么就意味着平均而言，度大的节点倾向于与度小的节点连接，从而表明网络是异配的；如果网络不具有度相关性，那么是一个与k无

7、关的常数：网络是度相关的就意味着和之间不恒等。用二者的差刻画网络的同配或者异配程度，即：（4-15）当网络完全同配时，（4-17）达到最大，即为余度分布：（4-16）4.2.4同配系数于是得到归一化系数（同配系数）：（4-17）r>0，网络是同配的；r<0，网络异配。r的数值大小反应了网络的同配或异配强弱程度。蛋白质交互网络和神经网络以及交互互联网和WWW等技术都是异配的；科研人员合作和电影演员合作等许多现实网络呈现同配性质；不同的在线网络呈现不同的性质。度同配起源的解释1、社会学2、心理学近些年的社会网络发展冲破了社会阶层

8、之间的无形壁垒。（P127）4.2.5实际网络的同配性质4.2.6同配概念的一般化同配就是指属性相近的节点倾向于互相连接。这里的属性可以是度也可以是其他特性，例如社会网络中个体的职业、年龄、种族、信仰等。社会网络同质性的两种基本解释：1、选择，即人们倾向于和相似的人成为朋友；2、影响，即人