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

社会网络分析与算法研究 2n   社会网络的研究大致可以描述为以下密切相关但又依次深入的方面：       ① 大量的真实网络的实证研究，分析真实网络的统计特性；       ② 构建符合真实网络统计性质的网络演化模型，研究网络的形成机制和内在机理；       ③ 研究网络上的动力学行为，如网络上的信息传播机制等。       ④ 研究预测网络性质的模型：采用机器学习算法研究网络节点的分类与聚类，预测网络链接及拓扑结构的发展趋势等。  n   本章针对第二个方面，研究网络演化的机制与模型。第三章 规则网络与随机网络模型 3.1  规则网络 n  全局耦合网络：全局耦合网络是指任意两个节点之间都有边相连的网络，也称完全图。对于无向网络来说，节点数为N的全局耦合网络拥有N（N－1）／2条边，如下图所示；而对于有向网络来说，节点数为N的全局耦合网络拥有N（N－1）条弧。 33.1  规则网络 n  各节点的度均为N－1，因此度分布为单尖峰，可以表示为Delta函数P（k）＝δ（k－N＋1）。 n  每个节点vi的聚类系数均为Ci＝1，故整个网络的聚类系数为     C＝1。 n  从任意一个节点到另外一个节点最短路径长度都为1，故整个网络的平均距离为L＝1。 n  在具有相同节点数的所有网络中，全局耦合网络具有最小的平均距离和最大的集聚系数。该模型作为实际网络模型的局限性很明显：全局耦合网络是最稠密的网络，然而大多数大型实际网络都是很稀疏的，它们边的数目一般至多是O（N）而不是O（N2）。  4n 最近邻耦合网络：对于拥有N节点的网络来讲，通常将每个节点只与它最近的K个邻居节点连接的网络称为最近邻耦合网络，这里K是小于等于N－1的整数。 n 若每个节点只与最近的2个邻居节点相连，这样所有节点相连就构成了一维链或环，如下图（a）所示。如下图（b）所示的二维晶格也是一种最近邻耦合网络。一般情况下，一个具有周期边界条件的最近邻耦合网络包含N个围成一个环的节点，其中每个节点都与它左右各K／2个邻居节点相连，这里K是偶数，如下图（c）所示。 53.1  规则网络 n 每个节点vi的度均为K，因此度分布为单尖峰，可以表⽰示为Delta函数P（k）＝δ（k－K）。n 最近邻耦合⺴⽹网络的平均集聚系数就是每个节点的集聚系数：C＝Ci＝3（K－2）／［4（K－1）］。对较⼤大K值，容易得到C≈0.75。可⻅见，最近邻耦合⺴⽹网络集聚程度还是很⾼高的。n 最近邻耦合⺴⽹网络不是⼩小世界⺴⽹网络，因为对固定K值，该⺴⽹网络直径D和平均距离L分别为D=N／K，L≈N／（2K）；当N→∞，L→∞。6【例3.1】⽤用Matlab程序绘制最近邻耦合⺴⽹网络，并给出具体程序代码。解：（1）最近邻耦合⺴⽹网络绘制的Matlab程序如下：78最近邻耦合网络 （2）当N＝20，K＝6时，该程序的仿真结果如下图所⽰示。9n 星形耦合网络：它有一个中心点，其余的N-1个点都只与这个中心点连接，而彼此之间不连接，如下图所示。 10n 中⼼心节点的度为N－-1，⽽而其它节点的度均为1，所以星型耦合⺴⽹网络的度分布可以描述为如下函数n 星形⺴⽹网络的平均距离为L＝2－2／N。当N→∞，L→2。n 假设定义⼀一个节点只有⼀一个邻居节点时，其聚类系数为1，则中⼼心节点的聚类系数为0，⽽而其余N-1个节点的聚类系数均为1，所以整个⺴⽹网络的平均聚类系数为C＝（N－1）／N。当N→∞，C→1。n 由此可见，星型耦合网络是比较特殊的一类网络，它具有稀疏性、集聚性和小世界特性。 11返回目录3.2随机网络 ¢ 3.2.1随机网络模型¢ 3.2.2随机网络的度分布¢ 3.2.3随机网络的直径和平均距离¢ 3.2.4随机网络的集聚系数123.2.1随机网络模型 随机网络构成有两种等价方法：①ER模型：n 给定N个节点，最多可以存在N（N－1）／2条边，从这些边中随机选择M条边就可以得到一个随机网络，显然一共可产生种可能的随机图，且每种可能的概率相同。133.2.1随机网络模型 ②二项式模型：n 给定N个节点，每一对节点以概率p进行连接。这样，所有连线的数目是一个随机变量，其平均值为M＝pN（N－1）／2。n 若G0是一个节点为v1，v2，…，vN和M条边组成的图，则得到该图的概率为P（G0）＝pM（1－p）N(N-1)/2-M其中pM是M条边同时存在的概率，（1－p）N(N-1)/2-M是其他边都不存在的概率，二者是独立事件，故二概率相乘即得图G0存在的概率。143.2.1随机网络模型 ER模型的一个伟大发现是：当连接概率p超过某个临界概率pc（N），许多性质就会突然涌现。例如，针对随机图的连通性，若p大于临界值（lnN）／N，那么几乎每一个随机图都是连通的。若当N→∞时，连接概率p＝p（N）的增长比pc（N）慢，则几乎所有连接概率为p（N）的随机图都不会有性质Q。相反，若连接概率p（N）的增长比pc（N）快，则几乎每一个随机图都有性质Q。因此，一个有N个节点和连接概率p＝p（N）的随机图有性质Q的概率满足：153.2.2随机网络的度分布 在连接概率为p的ER随机图中，可知其平均度为而某节点vi的度ki等于k的概率遵循参数为N－1和p的二项式分布值得注意的是，若vi和vj是不同的节点，则P（ki＝k）和P（kj＝k）是两个独立的变量。为了找到随机图的度分布，需得到度为k的节点数Xk。为此，需要得到Xk等于某个值的概率P（Xk＝r）。连接度为k的平均节点数为即。163.2.2随机网络的度分布 Xk值的概率接近如下泊松分布这样一来，度为k的节点数目Xk满足均值为λk的泊松分布。上式意味着Xk的实际值和近似结果Xk＝N·P（ki＝k）并没有很大偏离，只是要求节点相互独立。这样，随机图的度分布可近似为二项式分布在N比较大的条件下，它可以被泊松分布取代由于随机网络中节点之间的连接是等概率的，因此大多数节点的度都在均值＜k＞附近，网络中没有度特别大的节点。173.2.2随机网络的度分布 对于大范围内的p值，最大和最小的度值都是确定性的和有限的。例如，若p（N）∝N-1-1/k，几乎没有图有度大于k的节点。另外一个极值情况是，若p＝［ln（N）＋kln（ln（N））＋c]／N，几乎每个随机图都至少有最小的度k。下图给出N＝1000，p＝0.0015时随机网络的度分布，其中图中的点代表Xk／N（度分布），而连续曲线代表期望值E（Xk）／N＝p（ki＝k），可以发现两者偏离确实很少。183.2.3随机网络的直径和平均距离 对于大多数的p值，几乎所有的图都有同样的直径。这就意味着连接概率为p的N阶随机图的直径的变化幅度非常小，通常集中在一些重要的性质：若＜k＞小于1，则图由孤立树组成，且其直径等于树的直径。若＜k＞大于1，则图中会出现连通子图。当＜k＞大于等于3.5时，图的直径等于最大连通子图的直径且正比于ln（N）。若＜k＞大于等于ln（N），则几乎所有图是完全连通的，其直径集中在ln（N）／ln（pN）左右。193.2.3随机网络的直径和平均距离 n 随机网络的平均最短距离可以进行如下估计：考虑随机网络的平均度＜k＞，对于任意一个节点，其一阶邻接点的数目为＜k＞，二阶邻接点的数目为＜k＞2。也就是说，在ER随机图中随机选择一个节点vi，网络中大约有＜k＞Lrand个节点与节点vi的距离为Lrand。依此类推，当l步后达到网络的总节点数目N，有N＝＜k＞l，故n 可以看出，随机网络的平均最短距离随网络规模的增加呈对数增长，这是典型的小世界效应。因为lnN随N增长得很慢，所以即使是一个很大规模的网络，它的平均距离也很小。203.2.4随机网络的集聚系数 n 由于随机网络中任何两个节点之间的连接都是等概率的，因此对于某个节点vi，其邻居节点之间的连接概率也是p，所以随机网络的集聚系数为n 然而，真实网络并不遵循随机图的规律，相反，其集聚系数并不依赖于N，而是依赖于节点的邻居数目。通常，在具有相同的节点数和相同的平均度的情况下，ER模型的集聚系数Crand比真实复杂网络的要小得多。这意味着大规模的稀疏ER随机图一般没有集聚特性，而真实网络一般都具有明显的集聚特性。n 规则网络的普遍特征是集聚系数大且平均距离长，而随机网络的特征是集聚系数低且平均距离小。213.3小世界网络 ¢ 3.3.1小世界网络模型¢ 3.3.2小世界网络的度分布¢ 3.3.3小世界网络的平均距离¢ 3.3.4小世界网络的集聚系数223.3.1小世界网络模型 1.WS小世界模型WS小世界模型的构造算法如下：①从规则图开始：考虑一个含有N个节点的最近邻耦合网络，它们围成一个环，其中每个节点与它左右相邻的各K／2个节点相连，K是偶数。参数满足NKln（N）1。②随机化重连：以概率p随机地重新连接网络中的每条边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边，且每个节点都不能有边与自身相连。这样就会产生pNK／2条长程的边把一个节点和远处的节点联系起来。233.3.1小世界网络模型 在上述模型中，p＝0对应于完全规则网络，p＝1则对应于完全随机网络，通过调节p值就可以控制从完全规则网络到完全随机网络的过渡，如下图所示。由上述算法得到网络模型的集聚系数C（p）和平均距离L（p）都可看作是重连概率p的函数，如下图所示。图中对集聚系数和平均距离作了归一化处理。243.3.1小世界网络模型 最近邻耦合网络（对应p＝0）是高度集聚的（C（0）≈3／4），但平均距离很大（L（0）≈N／2K1）。当p较小时（0＜p1），重新连线后得到的网络与原始的规则网络的局部属性差别不大，从而网络的集聚系数变化也不大（C（p）∝C（0），但其平均距离下降很快（L（p）L（0））。这个结果是不难想象的：一方面，只要几条边的随机重连就足以减小网络的平均距离；另一方面，几条随机重连的边并不足以改变网络的局部集聚特性。这类既具有较短的平均距离又具有较高的集聚系数的网络就是典型的小世界网络。253.3.1小世界网络模型 2.NW小世界模型NW小世界模型是通过用“随机化加边”取代WS小世界模型构造中的“随机化重连”而得到的，具体构造算法如下：①从规则图开始：考虑一个含有N个点的最近邻耦合网络，它们围成一个环，其中每个节点与它左右相邻的各K／2个节点相连，K是偶数。参数满足NKln（N）1。②随机化加边：以概率p在随机选取的一对节点之间加上一条边。其中，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。263.3.1小世界网络模型 在NW小世界模型中，p=0对应于原来的最近邻耦合网络，p=1则对应于全局耦合网络，如下图所示。在理论分析上，NW小世界模型要比WS小世界模型简单一些。当p足够小和N足够大时，NW小世界模型本质上等同于WS小世界模型。273.3.1小世界网络模型 在现实朋友关系网络中，小世界网络模型反映了如下一种特性：大部分人的朋友都是和他们在一条街上的邻居或在同一单位工作的同事；另一方面，也有些朋友住得较远，甚至远在异国他乡，这种情景对应于WS小世界模型中通过重连或在NW小世界模型中通过加入连线产生远程连接。实际上，除了WS小世界模型和NW小世界模型，还有许多改进模型：加点，加边，去点，去边及不同形式的交叉，可产生多种形式的小世界模型。283.3.1小世界网络模型 【例3.2】用Matlab程序分别绘制WS、NW小世界网络模型，并给出具体程序代码。解：由于两个小世界模型都是在最近邻耦合网络的基础上进行的改变，因此各自对应的Matlab程序与例3.1中的差别就在于：在“开始画最近邻耦合网络”的代码段