第三章习题

T1

规则网络有哪几种？

  • 全局耦合网络
  • 最近邻网络
  • 星形耦合网络

T2

均匀网络和非均匀网络包括哪些网络类型？

均匀网络（泊松分布）：规则网络、随机网络、小世界网络

非均匀网络（幂律分布）：无标度网络

T3

SIS模型传染病在小世界网络传播阈值是？

λc=1<k>\Large \lambda_c=\frac1{<k>}

T4

尝试证明星型耦合网络平均距离为2-2/N？

网络的平均路径长度L定义为任意两个节点之间的距离的平均值，即有：

L=∑d(i,j)12N(N−1)L=\frac {\sum d(i, j)} {\frac12N(N-1)}

其中，N为网络节点数。节点对的数量为C(N,2)=N(N-1)/2。

在星型网络中，中心节点与其他N-1个叶节点的距离是1，叶节点之间的路径通过中心距离是2。其中距离为1的节点对数量为N-1，距离为2的节点对数量为C(N-1,2)。所以总距离和为：

N−1+(N−1)(N−2)=(N−1)2N-1+(N-1)(N-2) = (N-1)^2

带入公式，平均距离为:

(N−1)212N(N−1)=2(N−1)/N=2−2/N\frac {(N-1)^2} {\frac12N(N-1)} = 2(N-1)/N = 2 - 2/N

T5

证明具有周期边界的最邻近耦合网络聚类系数为3(K−2)4(K−1)\Large \frac {3(K-2)}{4(K-1)}

给定一个网络G，节点vi的ki个邻居节点之间，实际存在的边数为Ei，总的可能存在的边数为C(ki,2)，聚类系数定义为

聚类系数 Ci = \frac {邻居节点间的真实连边}{邻居节点间的可能连边} = \frac{E_i}{C_{ki}^2} = \frac{2E_i}{k_i(k_i - 1)}

采用基于网络中三角形数量的聚类系数的定义来计算，最近邻耦合网络的聚类系数为：

C_n=\frac{3*网络中所有三角形数量}{网络中可连通三元组的数量}

e1bd1259edb98db19d49a25bf6631345

如上图所示，对于最近邻耦合网络，每个节点vi的度均为K，每个节点最多可以向外延伸K/2来组成三角形，所以从每个节点某一侧方向出发，再回到该点的三角形数量为：

CK/22=14K(12K−1)C_{K/2}^2 = \frac 14K(\frac 12 K-1)

综上所述，最近邻耦合网络的聚类系数为：

C=3∗N∗CK/22N∗Ck2=3∗CK/22Ck2=34K(12K−1)12K(K−1)=3(K−2)4(K−1)C=\frac{3*N*C_{K/2}^2}{N*C_{k}^2}=\frac{3*C_{K/2}^2}{C_{k}^2}= \frac{\frac 34K(\frac 12 K-1)}{\frac12K(K-1)}=\frac {3(K-2)}{4(K-1)}

ppt中定义为\Large Ci=\frac{与vi相连的三角形数目}{与vi相连的的三元组数目},相连的定义不清晰，不太会算。。。

T6

随机网络度分布在节点数量较多情况下趋于什么分布，表达式是什么，其中每个参量分别表示什么意思？

随机图的度分布可近似为二项式分布，表达式为

p(k)=CN−1kpk(1−p)N−1−kp(k)=C_{N-1}^kp^k(1-p)^{N-1-k}

当N比较大时，其度分布趋于泊松分布，表达式为

p(k)=(pN)e−(pN)k!=<k>e−<k>k!p(k)=\frac{(pN)e^{-(pN)}}{k!}=\frac{<k>e^{-<k>}}{k!}

参数含义

  • p：连边概率
  • N：节点数量
  • <k>：平均度
  • 注：在连边概率为p的随机图中，平均度<k>=p(N-1)≈pN

T7

试分析下图中聚类系数和平均距离变化趋势的原因。

image-20250506090145390

上图反映了小世界网络的聚类系数和平均路径长度随重连概率的变化趋势，当 0 < p << 1时，网络的集聚系数C(p)变化比较小，而平均路径长度L(p)下降的很快。

当 p较小时，网络同时具备聚类系数较大和平均路径长度较小，这是小世界网络的核心特征。

原因：

  1. 聚类系数下降缓慢：随机重连虽然破坏了部分局部连接，但大部分连接仍保持规则结构，维持了较高的局部聚集。

    WS 小世界的聚类系数 C(p)为：

    image.png

    在p很小时，函数变化不大。

  2. 平均路径长度快速下降：少量随机连接即可形成“捷径”，显著减少节点间的平均距离。这是因为每出现一条捷径，它对整个系统的影响是非线性的，它不仅影响到被这条线直接连着的两点，也影响到这两点的最近邻、次近邻，以及次次近邻等 。

T8

当概率p趋近于1，WS小世界网络变为**（完全随机网络），NW小世界网络变为(全局耦合网络)**

T9

无标度网络针对（蓄意攻击）具有脆弱性，针对（随机故障）具有鲁棒性

第四章习题

T1

1、 结合信息传播过程中的三种状态 S、I、R，试举例三种传播类型，并做简要说明。

  • SI：单向传播模型，将总体分为两大状态：易感染状态S，感染状态I，且s(t)+i(t)=1，网络中最终都是已知信息节点
  • SIS：循环传播模型，两大状态：易感染状态S，感染状态I，但变为已知态后以定长速率再变为未知态，网络终态为动态平衡
  • SIR：单向传播模型，易感染状态S，感染状态I，免疫状态R，网络终态与传播效率有关，直到I态节点数量为0，传播结束
  • SIRS：循环传播模型，R态后仍有概率为S态

T2

2、 信息传播的内因为和外因分别是什么，请做简要说明。

  • 内因：传播能力、免疫能力

  • 外因：不同的网络类型、同一网络的不同属性

T3

3、 均匀网络中SIS 模型传播行为阈值为（）

均匀网络平均度为

<k>=∑i=1Nki<k>=\sum_{i=1}^Nk_i

传播阈值为

λc=1<k>\lambda_c=\frac1{<k>}

T4

4、 非均匀网络中SIS 模型传播行为阈值为（）（预习后作答）

λc=<k><k2>\lambda_c=\frac{<k>}{<k^2>}

其中<k><k>为平均度数，<k2><k^2>为度数的二阶矩

T5

5、编写SI模型传染病概率image-20250506091115635的matlab程序，并给出仿真结果。

方程

SI为单向传播模型，将总体分为两大状态：易感染状态S，感染状态I。

设s(t)和i(t)分别标记群体中个体在t时刻处于S态和I态的密度，λ为有效传播概率，则SI模型的动力学模型可以用如下的微分方程组描述：

{ds(t)dt=−λi(t)s(t)di(t)dt=λi(t)s(t)\Large \left\{ \begin{matrix} \frac{ds(t)}{dt}=-\lambda i(t)s(t) \\ \frac{di(t)}{dt}=\lambda i(t)s(t) \end{matrix} \right.

又

s(t)+i(t)=1\Large s(t)+i(t)=1

{ds(t)dt=−λi(t)(1−i(t))i(0)=i0\Large \left\{ \begin{matrix} \frac{ds(t)}{dt}=-\lambda i(t)(1-i(t)) \\ i(0)=i_0 \end{matrix} \right.

得：

i(t)=11+(1/i0−1)e−λt\Large i(t)=\frac 1{1+(1/i_0-1)e^{-\lambda t}}

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
clc; clear; close all;

t = 0:0.01:20; % 时间范围
i0 = 0.05; % 初始密度
lambda = [0.1, 0.25, 0.5, 0.75];  % 传播率参数

% 预分配存储矩阵
I_values = zeros(length(lambda), length(t));

% 计算不同lambda下的感染比例变化
for j = 1:length(lambda)
    for i = 1:length(t)
        I_values(j, i) = 1 / (1 + (1/i0 - 1) * exp(-lambda(j) * t(i)));
    end
end

% 绘制结果曲线
figure('Color', 'w');
hold on;
colors = lines(length(lambda));  % 使用不同颜色区分曲线

for j = 1:length(lambda)
    plot(t, I_values(j, :), 'LineWidth', 2, 'Color', colors(j, :))
end

% 图形标注
xlabel('时间 (t)', 'FontSize', 14, 'Interpreter', 'latex')
ylabel('感染比例 (i)', 'FontSize', 14, 'Interpreter', 'latex')
title('SI模型感染变化曲线', 'FontSize', 16)
legendCell = cellstr(num2str(lambda', '\\lambda = %.2f'));
legend(legendCell, 'Location', 'southeast', 'FontSize', 12)
grid on;
box on;

% 设置坐标轴范围
xlim([0, 20])
ylim([0, 1])

仿真结果

si

T6

6、简述为什么当网络节点数目无穷大情况下，无标度网络的传播阈值为0？（预习后作答）

无标度网络的节点度数服从幂律分布$ P(k)∼k^{−γ}$，其中大多数节点度数较低，但少数枢纽节点的度数极高。当网络规模 N→∞ 时，由于枢纽节点（高度数节点）的存在，幂律分布的二阶矩，即 =∑k^2P(k)，可能发散。

无标度网络传播阈值可表示为：

λc=<k><k2>\lambda_c=\frac{<k>}{<k^2>}

其中<k><k>为平均度数，<k2><k^2>为度数的二阶矩。当 →∞（即二阶矩发散）时，λ_c→0，传播阈值趋近于0，这意味着即使传播率极低，信息仍能通过枢纽节点持续传播。

复杂网络社团挖掘

t1

1.社团挖掘方法可以分为（独立社团划分）和（重叠社团划分）两大类。

t2

2.网络社团结构的定义分为两种：基于网络节点的（相对连接频数）和以（网络连通性）为评判标准。

t3

3.选择用作检验社团网络的实际网络时，需要注意哪三点？

（1）保证构建网络的数据方便易得；

（2）保证网络有实际的意义，社团划分的结果可解释；

（3）宜采用已被广泛使用的实际网络。

t4

4.设下图 给出人造网络的实际划分(a)和某算法的划分结果(b)，其中节点的不同形状表示属于不同的社团。试用上面三种方法分别评价算法的划分结果。

三种方法为：正确划分率法、共同信息比较法、D函数比较法

由图可知，人造网络实际具有3个社团，但划分结果只有一个社团与实际社团完全相同，而第二个社团包含了另外两个社团。

（1）正确划分率法：

正确划分节点数/总结点数

S=NR/N=4/12=0.333S = N_R/N=4/12=0.333

（2）共同信息比较法：

设矩形节点为社团1，圆形节点为社团2，菱形节点为社团3，

真实社团CA=3，划分社团CB=2，因此混合矩阵为3*2：

M=[400404]M=\left[ \begin{matrix} 4 & 0 \\ 0 & 4 \\ 0 & 4 \end{matrix} \right]

根据计算公式：

I(A,B)=−2{4log[4×124×4]+8log[4×124×8]}[12log(412)]+[4log(412)]+[8log(812)]=−6.3443−9.04267=0.73368I(A,B) = \frac{ -2 \left\{ 4 \log\left[\frac{4 \times 12}{4 \times 4}\right] + 8 \log\left[\frac{4 \times 12}{4 \times 8}\right] \right\} }{ \left[12 \log\left(\frac{4}{12}\right)\right] + \left[4 \log\left(\frac{4}{12}\right)\right] + \left[8 \log\left(\frac{8}{12}\right)\right] } = \frac{-6.3443}{-9.04267} = 0.73368

（3）D函数比较法：

d=∣A∩B‾∣∪∣A‾∩B∣∣A∪B∣d = \frac{|A \cap \overline{B}| \cup |\overline{A} \cap B|}{|A \cup B|}

将真实划分a与算法划分b中矩形节点集合、圆形节点集合、菱形节点集合与空集分别进行配对，它们之间的相异性分别为：

d1=0，d2=4/8=1/2，d3=4/(0+4)=1

真实划分与算法划分结果有：

D=(0+1/2+1)/3=1/2D=(0+1/2+1)/3=1/2

t5

5.利用派系过滤算法寻找下图所示网络的4－派系社团，并写明计算过程。

img

1.找到网络中所有大于等于4的派系

从度最大节点 v6v_6 出发，寻找大小为 s=5s=5 派系有：

{v1,v2,v3,v5,v6}\{v_1, v_2,v_3, v_5, v_6\},==1==

删除v6后没有其他大小为 s=5s=5 的派系

从v6出发，寻找大小为 s=4的派系有

{v1,v2,v3,v6}\{v_1, v_2, v_3, v_6\},
{v2,v3,v5,v6}\{v_2, v_3, v_5, v_6\},
{v3,v4,v5,v6}\{v_3, v_4, v_5, v_6\},
{v6,v7,v8,v9}\{v_6, v_7, v_8, v_9\},
{v1,v2,v6,v7}\{v_1, v_2, v_6, v_7\},
{v1,v3,v5,v6}\{v_1, v_3, v_5, v_6\}。

删除 v6v_6 及其连边后，从另一个节点 v5v_5 继续寻找，寻找大小为 s=4s=4 派系：
{v1,v2,v3,v5}\{v_1, v_2, v_3, v_5\}。

删除 v5v_5 及其连边后，没有大小为 s=4s=4 的派系

共7个4k派系

删除完全包含与5k派系的4k派系后（它们一定是相邻的）剩余3个4k派系：

{v3,v4,v5,v6}\{v_3, v_4, v_5, v_6\}==2==,{v6,v7,v8,v9}\{v_6, v_7, v_8, v_9\}==3==,{v1,v2,v6,v7}\{v_1, v_2, v_6, v_7\}==4==,

k派系社团定义

  • 相邻：两个k派系有k-1个公共节点
  • 连通：一个k派系通过若干个相邻k派系到达另一个k派系
  • k派系社团：所有连通的k派系集合(所有相邻的共享k-1个节点的k派系)

建立重叠矩阵

对角线为派系大小，非对角线为重叠数量

[5343141214]\left[ \begin{matrix} 5 \\ 3 & 4 \\ 3 & 1 & 4\\ 1 & 2 & 1 & 4\\ \end{matrix} \right]

找到其中对角线元素大于等于4，且非对角线大于等于3的置为1，可得到邻接矩阵

[1111010001]\left[ \begin{matrix} 1 \\ 1 & 1 \\ 1 & 0 & 1\\ 0 & 0 & 0 & 1\\ \end{matrix} \right]

可知1，2，3连通为1个4k派系社团，4为一个4k派系社团

{v1,v2,v3,v5,v6}\{v_1, v_2,v_3, v_5, v_6\},==1=={v3,v4,v5,v6}\{v_3, v_4, v_5, v_6\}==2==,{v6,v7,v8,v9}\{v_6, v_7, v_8, v_9\}==3==,{v1,v2,v6,v7}\{v_1, v_2, v_6, v_7\}==4==,

即

社团1：{v1,v2,v3,v4,v5,v6,v7}

社团2：{v6,v7,v8,v9}

复杂网络混沌同步

T1

1.同步具有初值敏感依赖性、（确定性非周期性）、（有界性），洛伦茨吸引子。

T2

2.Li-Yorke 的混沌定义中系统是否有周期点，请简要说明。

存在周期点，但其周期点的周期无上界，即f具有任意正整数周期的周期点

（覆盖所有周期，也相当于没有周期，但混沌就在于有序又不可预测的周期运动）

T3

3.给出Logistic 模型每个α 迭代500 次，取后100次的仿真图

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
% Logistic Map and Chaos
% Define the parameter initial condition x0, and number of iterations

x0 = 0.5; % Initial condition, should be between 0 and 1
iterations = 500; % Number of iterations

% To observe bifurcation diagram for varying r
r_range = 0:0.001:4; % Range of r values to explore
final_x_values = [];

skip_num = 400 ;

for r = r_range
    x_temp = x0;
    for i = 1:iterations
        x_temp = r * x_temp * (1 - x_temp);
        if i > (skip_num) % Only consider last half iterations for stability
            final_x_values = [final_x_values; r, x_temp];
        end
    end
end

% Plot the bifurcation diagram
figure;
plot(final_x_values(:,1), final_x_values(:,2), '.', 'MarkerSize', 1);
xlabel('r');
ylabel('Steady State Values of x');
title('Bifurcation Diagram of Logistic Map');
grid on;

仿真图：

T4

  1. 混沌系统的刻画指标包括(李雅普诺夫指数), (测度熵), (分形维)

T5

5.给出对于一维离散系统Lyapunov指数计算公式的推导过程。

Lyapunov 指数定义

对于一维离散系统$ x_{n+1}=f(x_n)$，Lyapunov 指数 σ 定义为：

\boxed{ \sigma = \lim_{\substack{ n \to \infty}} \frac{1}{n} \sum_{i=0}^{n-1} \ln |f'(x_i)| }

公式推导

考虑两个邻近初始点，仅存在微扰 ε\varepsilon：

{x0x0+ε(ε→0)\begin{cases} x_0 \\ x_0 + \varepsilon \quad (\varepsilon \to 0) \end{cases}

那么每次迭代误差传播为

δ1=f(x0+ε)−f(x0)≈f′(x0)⋅ε\delta_1 = f(x_0 + \varepsilon) - f(x_0) \approx f'(x_0) \cdot \varepsilon

根据多次迭代的系统轨迹，可以假设平均每次迭代所引起的是指数级偏移，设指数分离的指数为 σ\sigma，那么每次迭代误差传播

δ1=ε⋅eσ\delta_1 = \varepsilon \cdot e^{\sigma}

n 次迭代误差传播

δn=ε⋅enσ\delta_n = \varepsilon \cdot e^{n\sigma}

得到：

enσ=∣f(n)(x0+ε)−f(n)(x0)∣ε=∏i=0n−1∣f′(xi)∣e^{n\sigma} = \frac{|f^{(n)}(x_0 + \varepsilon) - f^{(n)}(x_0)|}{\varepsilon} = \prod_{i=0}^{n-1} |f'(x_i)|

取对数求极限得：

nσ=ln(∏i=0n−1∣f′(xi)∣)=∑i=0n−1ln∣f′(xi)∣n\sigma = \ln \left( \prod_{i=0}^{n-1} |f'(x_i)| \right) = \sum_{i=0}^{n-1} \ln |f'(x_i)|

σ=1n∑i=0n−1ln∣f′(xi)∣\sigma = \frac{1}{n} \sum_{i=0}^{n-1} \ln |f'(x_i)|

物理意义

  • σ>0\sigma > 0：误差不断放大 → 混沌
  • σ<0\sigma < 0：误差不断减小 → 稳定
  • σ=0\sigma = 0：误差线性变化 → 临界状态