2.11 课后习题

习题1 埃尔德什－雷尼网络

假如一个埃尔德什－雷尼网络的节点数为N=3000，节点间的连接概率为p=10-3。

（1）该网络的期望链接数是多少？

（2）该网络处于哪个状态？

（3）计算该网络处于临界点时的连接概率pc。

（4）假如连接概率p=10-3固定不变，计算出只有一个连通分支存在时的网络大小Ncr。

（5）对于（4）中的网络，计算出其平均度和节点平均距离。

（6）计算出该网络的度分布pk（采用泊松分布近似）。

习题2 生成埃尔德什－雷尼网络

基于随机网络模型G(N,p)，使用计算机生成大小为N=500的三个网络，平均度分别为（1）=0.8，（2）=1和（3）=8，并对这三个网络进行可视化。

习题3 环形网络

考察大小为N的环形网络，每个节点和其每侧m个邻居节点相连（因此，每个节点的度为2m）。图2-14a给出了一个例子，该网络中m=2，N=20。计算该网络的平均集聚系数和平均最短路径长度。简单起见，我们假设N和m的选择满足(n-1)/2m是整数。当N1时，会怎样？会怎样？

习题4 凯莱树

凯莱树是从一个度为k的中心节点出发构造出来的一棵对称树。和中心节点相距为d（d＜P）的每个节点的度为k。和中心节点相距为P的每个节点的度为1，这些节点被称为叶子节点（图2-16是一棵k=3、P=5的凯莱树）。

（1）计算从中心节点出发t步可以到达的节点个数。

（2）计算网络的度分布。

（3）计算直径dmax。

（4）写出直径dmax关于节点总数N的表达式。

（5）该网络具有小世界性质吗？

习题5 “势利”网络

考虑一个有N个红色节点和N个蓝色节点的网络。相同颜色节点之间的连接概率为p，不同颜色节点之间的连接概率为q。如果p>q，则称该网络是“势利的”。“势利”是指节点倾向于和具有相同颜色的其他节点相连。当q=0时，网络中至少包含两个连通分支，分别对应两种颜色的节点。

（1）计算只有蓝色节点构成的“蓝色”子网络的平均度和整个网络的平均度。

（2）给出网络大概率只包含一个连通分支所需要的p和q。

（3）证明：当N很大时，非常“势利”的网络（pq）也具有小世界性质。

习题6 “势利”社交网络

考虑上面所讨论模型的如下变种：网络有2N个节点，红色节点和蓝色节点数据相同，2N个节点中有比例为f的节点是紫色节点。蓝色节点和红色节点之间不相连（q=0），蓝色节点之间的连接概率是p，红色节点之间的连接概率也是p。另外，紫色节点和红色、蓝色节点之间的连接概率也是p。

（1）如果红色节点和蓝色节点之间的距离为2，我们则称红色社区和蓝色社区是彼此交互的。计算出此时所需要的紫色节点的比例。

（2）如果蓝色（或红色）节点的度1，计算紫色社区中的节点数。

（3）该模型对于研究社会网络结构的启发有哪些？