1.网络定义网络的定义G(V,E), where V\{1, 2,\dots,N\} is the set of nodes, and E\{e_{ij}|i,j \in V,i \neq j\} is the set of M links.2.重要性指标边度的定义$$k_{ij} \sqrt {k_i \times k_j},i \neq j \in V,e_{ij} \in E,$$其中k_i和k_j分别代表节点i和节点j的度数。节点介数中心性的定义$$c_l^B\sum_{i \neq j \in V } \frac{P_{ij}^l}{P_{ij}}, l \in V,$$其中c_B^l代表及节点l的介数中心性P_{ij}代表在节点i和节点j之间的最短路径数量P_l^{ij}代表节点i和节点j之间经过节点l的数量。边介数中心性的定义$$c_{e_{kl}}^B\sum_{i \neq j \in V } \frac{P_{ij}^{e_{kl}}}{P_{ij}}, e_{ij} \in E,$$c_{e_{kl}^B}代表边e_{kl}的介数中心性P_{ij}^{e_{kl}}代表节点节点i和节点j之间经过边e_{kl}的数量。节点紧密中心性的定义:$${c’}_i^C \frac{1}{N-1}\sum_{j \in V}d_{ij},i \neq j \in V$$d_{ij}为节点i与节点j之间的最短路径的长度。边紧密中心性的定义$${c’}_{e_{ij}}^C \sqrt{{c}_i^C \times {c}_j^C},i \neq j \in Ve_{ij} \in E,$$其中{c}_i^C和{c}_{e_{ij}}^C分别代表节点和边的紧密中心性。d_{ij}是节点i和节点j之间的最短路径节点的紧密中心性描述了这个节点是否是易达的。紧密中心性越小节点或边越容易到达也就是这个节点或边越重要。而实际上由于网络受到攻击后可能会断开因此两个节点之间的最短路径长度可能是无限的因此修改上述节点和边紧密中心性的计算公式如下$${c’}_i^C \frac{1}{N-1}\sum_{j \in V}\frac {1}{d_{ij}},i \neq j \in V$$$${c’}_{e_{ij}}^C \sqrt{{c}_i^C \times {c}_j^C},i \neq j \in Ve_{ij} \in E,$$通过上述改变紧密中心性越大代表节点或边越重要。3.网络拓扑指标平均最短路径$$D(G)\frac{1}{N(N-1)}\sum_{i\neq j}d_{ij}$$d_{ij}是两个节点之间的最短路径相配性$$\gamma\frac{M^{-1}\sum_{i2}^N\sum_{j1}^{i}a_{ij}k_ik_j-\bigg[M^{-1}\sum_{i2}^N\sum_{j1}^{i}\frac{1}{2}a_{ij}(k_ik_j)\bigg]^2}{M^{-1}\sum_{i2}^N\sum_{j1}^{i}\frac{1}{2}a_{ij}(k_i^2k_j^2)-\bigg[M^{-1}\sum_{i2}^N\sum_{j1}^{i}\frac{1}{2}a_{ij}(k_ik_j)\bigg]^2}$$k_i是节点i的度M是总度的数量a_{ij}邻接矩阵中A_{ij}的值$$a_{ij}\begin{cases}1, \text {if }e_{ij}\in E;\\ 0, \text{otherwise.} \end {cases}$$网络模体在网络G中模体是受一组参数{P,U,D,N}约束的子图G_k其中P表示概率阈值U表示最小阈值D表示最小差异阈值N表示生成随机网络的数目。G_k满足以下条件$$Prob(f_{random}(G_k)f_{original}(G_k))\leq P\\ f_{original}(G_k)\geq U\\ f_{original}(G_k)-\overline f(G_k)D \times \overline f_{random}(G_k)$$其中f_{original}(G_k)表示子图G_{k}在真实网络中的数目f_{random}(G_k)表示子图G_k在随机网络中的数目\overline f_{random}(G_k)表示子图G_k在随机网络中的平均数目。4.蓄意攻击类型HDA(High Degree Adaptive Attack)算法在每一个时间步中都会删除掉一个度数最大的节点。HBA(High Betweenness Centrality Attack)算法中在每一个时间步中有最大介数中心性的边总会被移除。HIA(High Importance Adaptive Attack)算法在每一个时间步中都会先计算节点或边的重要性并删除当前最重要的节点或边。然后剩余的节点和边的重要性会被再次计算继续重复上述过程直到整个网络中只剩下孤立的节点。NA_{HDA}: 基于节点度进行攻击LA_{HDA}: 基于边度进行攻击NA_{HBCA}: 基于节点介数中心性进行攻击LA_{HBCA}: 基于边介数中心性进行攻击NA_{HCCA}: 基于节点紧密中心性进行攻击LA_{HCCA}: 基于边紧密中心性进行攻击5.鲁棒性测度5.1.基于连接的鲁棒性测度边连通性的定义如下$$v(G)\underset{s,t\neq s\in V}{min}\{v_{s-t}(G)\},$$其中v_{s-t}(G)代表想让节点s和t断开连接所要移除的最少的边的数目。该指标的值不大于最小节点度数。因此在不改变度分布和各节点度的情况下通过调整网络拓扑该度量的值无法被改变太多。节点连通性的定义如下$$w(G)\underset{s,t\neq s\in V \wedge e_{st} \notin E}{min}\{w_{s-t}(G)\},$$其中w_{s-t}(G)代表想让节点s和t断开连接所要移除的最少的节点的数目。根据定义w(G)在全联通图中没有定义显然对于任意的s与tw_{s-t}(G)\leq v_{s-t}(G)又有(s,t\neq s\in V \wedge e_{st} \notin E)所以w(G)\leq v(G)。因此在不改变度分布和各节点度的情况下通过调整拓扑不能使该度量的值改变太多。5.2.基于随机图论的鲁棒性测度在复杂网络理论中“critical fraction”指的是网络在遭受节点或连接移除时维持其核心功能所需的最少比例。当移除达到这个比例时网络可能会突然失去其大部分的连接性导致功能失效。这个概念与渗透理论中的临界概率有关当网络的节点被移除达到某个临界分数时会发生相变以一定的概率攻击网络该网络从连通状态转变为非连通状态此时计算随机攻击的临界比例定义如下$$p_c^r1- \frac {1}{k_0-1}$$其中k_0 \frac {k^2}{k}其中k是节点度的平均值k^2为节点度的平方的均值。临界比例的值越大说明网络的鲁棒性越强。针对性攻击不是随机攻击的临界比例为p_c^t攻击度数最大的节点检查网络状况重复此过程直到网络断开即可得到这个值。5.3 R指标公式如下$$R\frac{1}{N}\sum_{Q1}^Ns(Q)$$s(Q)是删除Q个节点后最大联通分量的节点数量归一化因子\frac{1}{N}确保了可以比较不同规模网络的鲁棒性R指标越大这个网络越鲁棒初始的R指标只考虑了对节点的攻击没有考虑对连边的攻击考虑连边后扩展的R指标公式如下$$R_l\frac{1}{M}\sum_{P1}^{M}s(P)$$s(P)是移除P个边后剩下的最大联通分量的节点数量\frac{1}{M}也是归一化因子确保了可以比较不同规模网络的鲁棒性R_l越大网络越鲁棒5.4 网络整体效率(Integral effiency of network)公式如下$$IntE\frac{1}{N}\sum_{Q1}^{N} E(Q)$$E(Q)是网络移除Q个节点后的联通效率\frac {1}{N}为归一化因子E(0)是原始网络的联通效率计算公式如下$$E(G)\frac {1}{N(N-1)}\sum _{i \neq j\in G}\xi_{ij}\frac {1}{N(N-1)}\sum_{i \neq j\in G}\frac {1}{d_{ij}}$$\xi_{ij}是两个节点之间的联通效率,\xi_{ij}\frac {1}{d_{ij}}为这两个节点之间最短距离的反比当任意两个节点之间之间没有通路时d_{ij}\infin且\xi_{ij}0结合R_l指标与IntE对于恶意连边攻击的联通效率还可以被扩展为$$IntE_l\frac{1}{M}\sum_{P1}^ME(P)$$E(P)是网络中被移除P条连边后的网络联通效率\frac{1}{M}也是归一化因子5.5 基于特征值的稳健性度量基于网络拉普拉斯矩阵或邻接矩阵的特征值也可以对网络的鲁棒性进行度量如代数连通性基于拉普拉斯矩阵和自然连通性基于邻接矩阵。代数连通性是拉普拉斯矩阵的第二小的特征值它可以反映整个图的联通程度其公式如下$$\alpha(G)\lambda_2,\lambda_1 \leq\lambda_2\leq\lambda_3\leq\dots\leq\lambda_N$$其中\lambda为拉普拉斯矩阵的特征值。拉普拉斯矩阵Laplacian Matrix是图论中的一个概念常用于描述图的结构。在图论中一个图由节点顶点和边组成。拉普拉斯矩阵是通过图的邻接矩阵和度矩阵构造出的。具体来说拉普拉斯矩阵 L可以定义为$$LD-A$$A是图的邻接矩阵D是图的度矩阵它是一个对角矩阵对角线上的元素D_{ii}等于节点i的度数拉普拉斯矩阵有一些重要性质对称所有行和列等于零半正定但由于代数连通性难以描述结构化网络的鲁棒性因此有人提出来自然量通性。通过量化所有长度的闭合回路的加权数量来表征网络中替代路线的冗余度。自然连通性可以被视为随着边的添加或删除而严格单调变化的平均特征值其公式如下$$\overline \lambdaln(\frac{1}{N}\sum_{i1}^{N}e^{\lambda_i})$$其中 \lambda_i是图邻接矩阵的第 i 个特征值。给定顶点数量空图具有最小自然连通性而完整图具有最大自然连通性。所以\lambda的值越大网络就越鲁棒。6.鲁棒性测度的敏感性6.1 删除或添加边的策略随机策略随机删除边富富策略边按照k_i \times k_j 降序排序其中 k_i 和 k_j是边的两个端节点的度并按此顺序选择边穷穷策略边按照k_i \times k_j 递增排序并按此顺序选择富穷策略边根据|k_i- k_j| 降序排序并按此顺序选择6.2 添加边的流程计算给定网络G_0的鲁棒性使用四种策略中的一种添加或者删除边然后重新计算网络的鲁棒性重复步骤二直到边的数量达到上限全连通图执行步骤1-3十次计算平均值以减少偏差6.3 删除边的流程计算给定网络G_0的鲁棒性使用四种策略之一选择一条边并将所选边从G_0中删除然后重新计算网络的连通性如果G_0的连通性不受影响则重新计算G_0的鲁棒性否则拒绝删除并重复步骤2重复步骤二直到边的数量达到上限网络连通性达到要求执行步骤1-3十次计算平均值以减少偏差7. 网络的类型7.1 无标度网络若随机变量x具有概率密度$$f(x)Cx^{-\alpha}$$其中C与\alpha均为大于0的常数则称x服从幂律分布。又有log(Cx^{-\alpha})log(C)-\alpha log(x)所以幂律分布的双对数曲线是一条直线。