04-社会网络分析与算法研究

社会网络分析与算法研究 2n   随机网络的特征       ① 节点的度分布：遵循泊松分布          ② 平均距离：         ③ 聚类系数：  回顾 3n 小世界模型的特征       ① 节点的度分布： WS小世界模型是所有节点的度都近似               相等的均匀网络。        ② 平均距离：较小        小世界网络的平均距离下降的原因        在于两个节点间出现了最短路径       （捷径）。        ③ 聚类系数：较高  第四章  幂律分布与无标度网络 4n  流行度是一种极端不平衡的现象: Ø  绝大部分人一生只在与他/她们直接相关的社会圈子里被认知，少数人有广泛的知名度，而极少数人具有全球范围的知名度。 Ø  同样，书籍、电影或者是任何有受众的事物都存在这种现象。 Ø  如何量化这种不平衡？为什么会产生这样的不平衡？它们是否在某种程度上反映出流行现象本身特有的内在特性？ n  以万维网为例，测量每个网页的流行度。定义指向某个网页的所有链接为该网页的链入集合，就可以利用一个网页的链入数来测量该网页的流行度。 流行度现象 5n  正态分布: 平均值和标准方差。 Ø 观察到一个偏离均值c倍于标准差的值的概率随c以指数率递减。 Ø  正态分布是一种很自然的猜测，因为它在自然科学领域普遍存在。 Ø  中心极限定理对正态分布的大量出现提供了基本解释：粗略的说，中心极限定理表明，如果考虑任何独立的小的随机量集合，在极限情况下，这些随机量的和结果将服从正态分布。 n  以万维网为例，假定每个网页独立的随机决定是否连接到一个给定的网页，那么给定网页的链入数等于多个独立的随机量值之和，我们希望它服从正态分布：那么，拥有k个链入链接数的网页当k增大时，应该以指数形式减少。 流行度现象 6n  实际发现，拥有k个链入数的网页数量比例近似的与1/k²成正比。 n   函数1/k²当k增加时，降低得比较缓慢，也就是说实际拥有很大链入数量的网页相当普遍，超出预期的正态分布。 n  其他领域也有类似流行度的幂律分布。 7n  正态分布广泛应用于自然科学领域。 n  幂律分布成为复杂网络（社会网络）中的一种规范。 n  如何检测一个数据集是否服从幂律分布： Ø     设f(k)表示某个整体中属性值为k的那部分所在份额，希望证明方程                         成立或者近似成立，其中指数c和系数a均为常数。 Ø     如果将方程写成                     ，对等式两边去对数得到：      logf(k)=loga–clogk如果存在一个幂律关系，那么以logk作为变量的函数logf(k)将是一条直线，斜率为-c，loga为直线与y轴的相交点。对数图可以验证一组数据是否呈现近似幂律的关系。 流行度现象 ()/cfkak=()cfkak−=8幂律分布 910幂律分布 11幂律分布 12幂律分布 1314151617181920214.2无标度网络 ¢ 4.2.1Price模型¢ 4.2.2BA模型¢ 4.2.3BA无标度网络的度分布和度相关¢ 4.2.4BA无标度网络的平均距离和集聚系数224.2.1PRICE模型 ¢ Price主要对论文间的引用关系网络及其入度进行了研究，其思想是：一篇论文被引用的比率与它已经被引用的次数成比例。从定性角度来看，如果某篇文章被引用的次数越多，你碰到该论文的概率越大。于是，Price和Simon提出了一个简单的假设“论文的引用概率与它以前的引用数量之间存在严格的线性关系”。¢ 考虑一个包含N个节点的有向图构成的论文引用关系网络，假定P（k）是节点中入度为k的节点所占比例。新的节点不断地加入到网络中，每个新加入的节点都有一定的出度，该出度在节点一经产生后便保持不变，平均出度为234.2.1PRICE模型 ¢ 在网络不断增长的过程中，新边连接到旧节点的概率与旧节点的入度成比例。然而，因每个节点开始时入度均为0，这便使得该节点获取新边的概率为0。为了解决这一问题，新边连接到节点的概率与k＋k0成比例，其中k0＝1，即认为论文首次出版时的引用次数为1（自己引用自己）。一条新边连接到任何度为k的节点的概率为其度分布为244.2.2BA模型 ¢ Barabási和Albert指出现实中的网络有两个方面在以前的网络模型中未包含进去。¢ 首先，没有考虑现实网络的增长特性（网络的规模是不断扩大的）。在ER、WS和NW模型中，均假设网络从固定的节点数N开始，然后随机连接（ER模型）或者重连（WS模型）或者加边（NW模型），没有修改节点数N。相比而言，大部分现实网络是开放的，即它们由不断加进系统中的新节点组成，因此节点数目N的增长伴随网络的终生。254.2.2BA模型 ¢ 其次，没有考虑现实网络的优先连接特征（新的节点更倾向于与那些具有较高度的“大”节点相连接）。随机网络模型假设两个节点被连接的概率是随机的或统一的。相比之下，大部分现实网络展现出择优连接的性质。这种现象也称为“富者更富”或“马太效应”。¢ Barabási等人证明了在这两个基本假定的基础上，网络必然最终发展成无标度网络，即BA网络模型。¢ 基于网络的增长和优先连接特征，BA无标度网络模型的构造算法如下：①增长：从一个具有m0个节点的网络开始，每次引入一个新的节点，与m个已存在的节点相连，这里m≤m0。264.2.2BA模型 ②优先连接：一个新节点与一个已经存在的节点vi相连接的概率Πi与节点vi的度ki成正比，即在经过t步后，这种算法产生一个有N＝t＋m0个节点，mt条边的网络。下图举例说明了当m＝m0＝2时，初始网络为孤立节点的BA网络的演化过程。初始网络有两个节点，每次新增加的一个节点按优先连接机制与网络中已经存在的两个节点相连。274.2.2BA模型 ¢ 根据增长性和择优选择，网络将最终演化成一个标度不变的状态，即网络的度分布不随时间而改变（同样也就是不随网络节点数N而改变），经计算得到度值为k的节点的概率正比于幂次项k-3。下面对该结论作适当的证明。¢ 在BA模型中，从网络中某一节点vi的度值ki随时间变化的角度出发，假设其度值连续，有如下方程（1）由于每一时间步，我们加入m条边，即网络总度值增加2m，于是第t步的总度值为（2）284.2.2BA模型 将式（2）代入式（1），可以得到（3）解方程得（4）由初始条件，节点vi在时刻ti以ki（ti）＝m加入到系统中，可以得到（5）因此，将式（5）代入式（4）可得（6）294.2.2BA模型 由（6）式可以得到节点连接度ki（t）小于某定值k的概率为（7）假设我们等时间间隔地向网络中增加节点，则ti值就有一个常数概率密度（8）由式（7）和式（8）可以得到（9）所以度值的分布P(k)为（10）当t→∞时，P(k)=2m2k-3，完全符合幂律分布。304.2.2BA模型 【例】用Matlab程序绘制BA网络，并给出具体程序代码。解：（1）程序代码如下：314.2.2BA模型 324.2.2BA模型 334.2.2BA模型 （2）当m0=2、m=2、N=20且从孤立节点开始（pp=1）的程序运行结果如下图所示。344.2.2BA模型 n 复杂系统中的竞争：在竞争环境中，每个节点都有特定的适应性。n 适应性模型中，适应性高的节点链接较多：将适应性加入到无标度网络中，假设优先连接受到节点的适应性和链接数目的共同影响的乘积。354.2.3BA无标度网络的度分布和度相关 1.度分布对BA无标度网络的度分布的理论研究主要有三种方法：连续场理论（前面已介绍），主方程法和速率方程法。①速率方程法②主方程法364.2.3BA无标度网络的度分布和度相关 主方程法和速率方程法是等价的，而在渐进极限下，也和连续场理论得到的结果一致。因此，在计算度分布标度行为时，它们可以相互转化。BA模型标度γ＝－3与m无关。度分布渐进地与时间无关，进而也与系统尺度N＝m0＋t无关。这就意味着，尽管网络在不断增长，最后都能达到一个稳定的无标度状态，而且幂律分布的系数与m2成正比。2.度相关考虑有边连接的所有度值为k和l的节点对，不失一般性，设度值为k的节点是新近加入系统的节点。为简化起见，令m＝1，用符号Nkl（t）表示t时刻连接度为k的和度为l的节点对的数量，则374.2.3BA无标度网络的度分布和度相关 右边第一项表示由于增添了一条边到度为k－1或度为k的节点，并把它连接到度值为l的节点，在Nkl中产生的变化。由于增添的新边使节点的度数加1，分子中的第一项对应着Nkl的增加，而第二项对应损失。右边第二项用于其它节点，与第一项有相同的效果。最后一项为k＝l时的概率。因此，添加到了度为l－1的节点的边是连接这两个节点的同一条边。该式中可用和转换成与时间无关的递归关系，求得384.2.3BA无标度网络的度分布和度相关 对一个具有任意度分布的网络，若边随机连接，则。而上式最重要的特性是联合度分布不能进行因子分解，即。这表明连通节点度之间的相关性自然产生。仅当1kl，nkl才可以简化为因子分解表达式，。正如所期望的那样，若网络缺少相关性，在这种情况下都与nkl＝k-3l-3不同。该结果首次证明了产生无标度网络的动态过程建立了节点间的非平凡相关。394.2.4BA无标度网络的平均距离和集聚系数 1.平均距离下图给出了平均度＜k＞＝4的BA模型平均距离LBA随网络规模N的变化曲线，跟它比较的是相同规模和相同平均度条件下的随机图的平均距离Lrand。404.2.4BA无标度网络的平均距离和集聚系数 从图中可以看出，对任意N，BA网络中的平均距离比随机图中的要小得多，这说明异质性无标度网络拓扑比同质性随机图拓扑在“拉拢节点”方面效率更高。从模拟结果上看，BA模型网络中的平均距离是随N按指数增长的，它很好地符合下式LBA＝Aln（N＋B）＋C式中，A，B和C为常数。然而这是有争议的，因为大多数学者提出的BA网络的平均距离随N按指数增长关系为LBA∝lnN／ln（lnN）由此可见BA网络的平均距离比较小，表明该网络具有小世界特性。414.2.4BA无标度网络的平均距离和集聚系数 2.集聚系数下图给出了平均度＜k＞＝4的BA模型集聚系数CBA随网络规模N的变化曲线，跟它比较的是相同规模和相同平均度条件下的随机图的集聚系数Crand。424.2.4BA无标度网络的平均距离和集聚系数 ¢ 从图中可以看出：①无标度网络的集聚系数几乎是随机图的5倍，随节点数的增加，这个倍率还会稍微地随着增加；②BA模型网络的集聚系数是随着网络尺度N的增加而减小的，其大概遵循幂指数规律，即CBA～N-0.75；③BA模型网络的集聚系数比随机图Crand的衰减要慢；④由于无标度网络的集聚系数依赖于N，因此它的行为与小世界模型（集聚系数与N无关）不同。¢ 因此，BA模型不仅平均距离很小，集聚系数也很小，但比同规模随机图的集聚系数要大，不过当网络趋于无穷大时，这两种网络的集聚系数均近似为零。目前，学者们已经给出了BA无标度网络集聚系数的解析公式为43