论文研究-基于不等概率抽样的不完全信息条件下复杂网络抗毁性模型.pdf,  为了填补随机失效与故意攻击之间的空白,将复杂网络攻击信息的获取抽象成无放回的不等概率抽样问题,建立了不完全信息条件下的复杂网络抗毁性模型.其中网络攻击信息可以通过信息广度参数和信息精度参数调节控制,随机失效或故意攻击是该模型的两个特例.利用母函数方法解析推导出了任意度分布广义随机网络在随机不完全信息和优先不完全信息条件下的两个重要抗毁性度量参数------临界移除比例和巨组元规模,得到的解析结果可以分析和预测不完全信息条件下复杂网络的抗毁性.以无标度网络为例对一般攻击信息参数组合进行了仿真分析,发现随机隐藏少量节点信息将大幅度提高复杂网络的抗毁性,获取少量重要节点的信息可以大幅度降低复杂网络的抗毁性.
第7期 吴俊,等:基于不等概率抽样的不完全信息条件下复杂网络抗毁性模型 1209 即攻击信息量为零,对应随机失效; )当a=1时: 即攻击信息量为完全信息,对应故意攻击 构造节点n的辅助变量如下: 其中δ∈(0,∞)为攻击信息精度参数.由式(3)可得单次抽样(n=1)节点v的入样概率为 2 Ti ∑丌+∑ -6 显然,δ越大,越可能获取到那些重要节点的信息,即获取的攻击信息精度越高.考虑两种极端情况: i)当6=0时: 6 N 即节点被获取信息的概率相等,我们称这种攻击信息为随机不完全信息 )当 时 ∑n∞=∑t∞=1+∑t∞=1 (6) 假设r=1,则 0.t≠ 即最重要的节点信息总是被优先获取,我们称这种攻击信息为优先不完全信息 为∫避免重要度高的节点重复入样,将攻击信息的获取过程抽象成如下无放回的不等概率抽样问题 Step1按照(4)式中的概率抽取一个样本 step2将剩余节点按重要度排序并重新计算辅助变量π;和入样概率Ⅴ; Step3重复Step1和Step2直至抽出n个样本 假设已经确定已知区域Ω(mn=|2|=Na),需要攻击网络中的N/个节点,节点被攻击后与其相连接 的边随之移除.考虑一种最简单的攻击模式:先攻击已知信息节点,再攻击未知信息节点,即 i)若∫≤a,直接在已知区域』中按照节点的重要度从大到小依次攻击 i)若f>a,先把已知区域!中的节点全攻击,然后在未知区域随机攻击N(f-a)个节点 3不完全信息条件下复杂网络抗毁性解析分析 对于一般的复杂网络,解析分析不完全信息条件下的抗毁性非常困难,所以本文仅解析分析具有任意度 分布的广义随机网络的抗毁性,即假没网络在满足度分布p(k)条件下随机连接下面首先利用概率母函 数方法132解析推导不完全信息条件下广义随机网终的两个重要抗毁性度量参数:临界移除比例和巨组元 规模,进而解析分析两种特殊情况(随机信息和优先信息)下复杂网络的抗毁性.为了便于推导,这选取节 点的度作为节点的重要度指标 31临界移除比例和巨组元规模 给定度分布p(k),可得到其概率母函数 (x) ∑ P(k).0 8) 其中m为最小度,M为最大度,令沿随机选择的一条边到达的节点度为k的概率分布为pE(k),其不仅与度 为k的节点数量成正比.还与k本身成正比.因此, kp(k) pE()=、M kp(k 1210 系统工程理论与实践 第30卷 从而,可得PE(k)的概率母函数为 )=∑pz ∑h=nkp(k)x ∑kmkp(k) 当沿随机选择的一条边到达度为k的节点后,还剩k-1条边可以连接其它节点,这就是剩余度的概 念24.其实所谓剩余度就是指节点的度减去1,引入剩余度可以方便推导.令剩余度的概率分布为P(k),由 剩余度的定义易知 pr(k)=p(k+ (11 因此,沿随机选择的一条边到达剩余度为k的概率分布为 1(k) (k+1)p(k+1) (k+1)p(k+1) (k+1)p(k+1)∑ p(k 其概率母函数为 M-1 n(6)24∑A=1 ∑h=n1(k+1)p(k+1) kp(k) ∑kmkp(k)x (13) p(k)9(1) 令度为k的节点未被攻击的概率为q(Kk),则随机选择一个节点,其芍点度为k且没有被攻击的概率为 Co(k)-p(k)q(k),其概率母函数为 F0(x)=∑p(k)(k) (14) 同理沿随机选择的一条边到达一个剩余度为k且没有被攻击的节点的概率为01(k)=p1(k)q(k+1), 其概率母函数为 F1(x)=∑m1(k)(k+1)x=∑ kep(k) k=m2k=m的9(12k ∑mkp(k)q(k)x (15) kp(k) 令h1(k)表示沿随机选择的一条边到达的连通片s的规模为k的概,其概母函数为 I1()-∑h1(k)x (16) 当网络中含有组元时,我们假设h1(k)不包括巨组元24.所谓“组元”指的是包含网络中大多数节 点的连通片,即几乎一定S|=6(N)25-26.当沿随机选择的一条边到达的节点已被攻击时,到达的连通片 规模为零,其概率为 h1(0)=1-∑m1(k)(k+1)=1-F1() 当沿随机选择的一条边到达的节点未被攻击时,到达的连通片规模大于令.当到达节点的剩余度为0时, 到达的连通片规模为1;当到达节点的剩余度为1时,到达的连通片规模为到达节点连接的分支规模再加1 当到达节点的剩余度为2时,到达的连通片规模为到达节点连接的两个分支规模之和再加1,…依此类推 因此,H1(x)可表示为如下递归形式 H1(x)=1-F1(1)+p1(1)q(1)H1(x)+xp1(2)q(2){H1(x)2+… 1-F1(1)+∑m1(k)(k)H2(m) =1-F1(1)+F1H1(x) (18) 第7期 吴俊,等:基于不等概率抽样的不完全信息条件下复杂网络抗毁性模型 1211 同理,令ho(k)表示随机选择的一个节点所属连通片的规模为k的概率.其概率母函数为 )=∑ho(k k=0 当网络中含有巨组元时,同样假设ho(k)不包括巨组元.当沿随机选择的节点已被攻击时,所属连通片规模 为零,其概率为 h0(0)=1-∑p(k)(k)-1-F0(1) 20 k=r H0(x)满足如下递归形式 H0(x)=1-F0(1)+xF0[H1(x) (21) 这样,给定度分布p(k)以及未被攻击概率g(k),我们就可得到F(x)和F1(x),将F1(x)代入(18)式即 可解出H1{m),将F(x)和H1(x)代入(21)式即可解出Ho(x),从而可得到所有连通片规模的概率分布.但 实际上,解析求解方程(18)是非常困难的大多数时候它都是超越方程,没有显式解.虽然很难解析得到连 通片规模的穊率分布,但我们可以通过(18)式和(21)式得到临界移除比例∫∈和巨组元规模S 假设网络中不存在巨组元,则 H1(1)=∑h1( 1)=∑h0(k) 从而,可得平均连通片规模 H6(1)=FoH1(1)+F(1)H1(1)=F0(1)+F(1)H1(1) (24) 又由(18)式可知 H1(1)=HH1(1)+F1(1)H1(1)=F1(1)+F1(1)H1(1) (25) 解得 H1(1) F1(1) (1 (26) 从而 s>=F0(1)+F6(1)H(1)=F0(1)+30(1)F(1) 1-F1(1) (27) 由(27)式可以看出,当F(1)=1时平均连通片规模<>发散,这意味着巨组元存在的临界点或者网络崩 溃的临界点位于F1(1)=1,即 1(1 (1) 2k=m k(k-1)p(k)q(k) (28) k-m kp(k) 由于q(k)仅和攻击信息以及节点移除比例∫有关,所以给定度分布p(k),攻击信息参数a、6后,我们 可由(②28)式解出临界移除比例∫。 当网络中存在巨组元S时由H()定义可知 S/N=1-H0(1) 又由(21)式可知 H1(1)=1-F1(1)+F1(H1(1) (30) 由上式解得H1(1)=,代入(21)式,得 H0(1)=1-F0(1)+Fo() 1) 因此,可得巨组元规模 (1)=F0(1)-Fo() (32 其中u为方程 F1(1)+F1() 212 系统工程理论与实践 第30卷 的最小非负实数解 3.2随机不完全信息条件下的复杂网络抗毁性 若∫≤α,在已知区域中按照节点的度从大到小依次移除Nf节点令K表示9中未被攻击节点 的最大度,则 q(k) k< K k>K 其中K由度分布(k)和∫确定.特别地,若p(k)=(-1)m-k-7(>2),则 /(~-1) (35) 若∫>α,先把已知区域Ω中的节点全部移除,然后在未知区域Ω随机移除N(f-a)节点.因为g中 节点也是随杋选择的,所以这种情况等价于在整个网络中随机移除N∫节点.因此,未被攻击概率为 (k)=1-f 将(36)式代入(28)式,可得随机失效条件下的临界条件 ∑k(k-1m(1)=∑k) (37) 从而可得随机失效条件下的临界移除比例 RF 其中6=<k2>/<k>.特别地若p(k)=(-1)m-k-(>2且γ≠3),则 这与文献[9中的结果一致 若α≤∫F,那么必须至少移除Nα节点才能使得网络崩溃,即∫≥α.此时等价于随机失效,因此 rF 若a>fF,可知f<a.将(34)式代入(28)式,可得临界条件 ∑ k(k-1)P(k)+(1-a)∑kk ∑kp(k) 求解上式,可得临界值Kε,再由K和∫的函数关系即可得到临界移除比例∫。.特别地,若p(k)=( 1)m-1k-(>2且y≠3),式(40)可写为 aK2-7-2m2-7+(2-a)M2-7aK3- (1-a)M3 (41 对于故意攻击(a=1),式(41)可写为 k2-7-2m2-7+M (42) 这与文献[6中的结果一致 从(41)式、(42)式可看出,若>3,则当N→∞,M3-→0,从而总是存在一个有限的临界移除比 例∫<1;但当2<γ<3时,若a<1,则当N→∞,M3-7→∞x,从而f。→1.这意味着,在标度指数 2<γ<3的无标度网络中,当N→∞时,如果我们能隐藏部分节点的信息(α<1),那么几乎需要移除所 有节点才能使得网终崩溃(fc→1).将(34)式、(36)式代人(14)式、(15)式可得Fo(x)和F1(x),再代入 (32)式即可求得巨组元规模 3.3优先不完全信息条件下的复杂网络抗毁性 当f≤a时,在已知区域2中按照节点的度从大到小依次移除Nf节点.因为g2中节点是按照度从大 到小优先选择的,所以这种情况等价于在整个网络中按照节点的度从大到小依次移除N∫节点,即故意攻击 (a=1).令K表示未被攻击节点的最大度,则未被攻击概率可写为 k< K 0.k>K (43) 第7期 吴俊,等:基于不等概率抽样的不完全信息条件下复杂网络抗毁性模型 1213 特别地若p(k)=(-11m7-1k-?(>2),则 F≈ 将(43)式代入(28)式,可得故意攻击条件下的临界条件 K ∑ ∑ k=m 求解上式,可得临界值Kc,再由K和∫的函数关系即可得到故意攻击条件下的临界移除比例∫A.特别地, 若p(k)=(-1)m-4k-7(>2且≠3),则临界条件可写为 K2-7-2m2-7+M2-K 3-7-m (4 2 当∫>α时,先把已知区域Ω中的节点全部移除,然后在未知区域Ω随机移除N(f-a)节点.令m 表示!2中节点的最小度,则未被攻击概率可写为 k m (k) (47) k≥ 其中m由度分布p(k)和∫确定.特别地.若p(k)=(-1)m-1k-7(>2且≠3),则 1/(~-1) 若α≥J,那么仅需移除不超过Nα节点才能使得网络崩溃,即f。≤a.此时等价于故意攻击,因此 「A 若a<f4,可知f>a.将(47)式代入(28)式,可得临界条件 (1-f)∑k-1)m(k)=(1-c)∑kp(k) (49) 求解上式可得到临界移除比例∫特別地,若p(k)=Ck-(>2且Y≠3),式(49)可写为 (M2-7-m2-7)(1-a)+(m2-7-m2-7)(1-f)(m3-7-m3-7)(1-f) 3 (50) 对于随机失效(a=0),式(50)可写为 (2-f)( (1-f)(m32-7-M3-7) (51) 解得 RF 52) 其中 2-y)M3-7-m3-7 这与文献[19中的结果一致 从(50)式、(51)式可看出,当γ>3时,总是存在一个有限的临界移除比例c<1;当2<?<3时,若 a=0,则当N→∞,M3-7→∞,从而f→1,但是若a>0,总是存在一个有限的临界移除比例f<1 这意味着在标度指数2<γ<3的无标度网络中,当N→∞时,只要我们能优先获取很少部分重要节点 的信息(α>0),那么也能通过移除部分节点使得网络崩溃(∫。<1) 将(43)式、(47)式代入(14)式、(15)式可得r(x)和F1(x),再代入(32)式即可求得巨组元规模 4不完全信息亲件下复杂网络抗毁性仿真分析 在上一节中,我们解析硏究了两种特殊情况(随机不完全信息和优先不完全信息)下复杂网络的抗毁性 本节中,我们以无标度网络为例,对一般攻击信息参数组合(α,6)进行详细仿真分析 给定度序列1≥ N,其中w;=ci-1(0-1,m=N为最小度,M=c=1 mN1(-3),为最大度,γ>2,釆用文献25-26中的配置模型构造随机无标度网络,生成网络的度分布为 D(k)=(γ-1)mˆ1k-~.给定攻击信息参数组合(,ω)在生成的随机无标度网络中按照不等概率拙样步骤 确定已知区域Ω,然后按照攻击模型移除节点.选择≡<k2>/<k>≤2作为网络崩溃的临界值1明,每 移除一个节点后计算网络中的巨组元规模|S|以及κ,并记录使得6≤2需要移除的节点比例T.由于使用 1214 系统工程理论与实践 第30卷 配置模型构造随杋无标度网络以及按照不等概率抽样确定已知区域Ω均有随机性,所以我们对于特定冈络 参数独立执行10次配置模型,对每一个网络独立确定10次已知区域g2,最后计算平均值<|S|>和<T 作为巨组元规模和临界移除比例 图2给出了无标度网络在不同攻击信息参数组合(α,δ)条件下巨组元规模|S|随节点移除比例∫变化 图,其中N=1000m=2,y=3.5,实线为解析结果,与仿真结果非常吻合.可以看出,攻击信息对组元规 模|S|有显著影响.如果攻击信息为零信息(α=0),即使50%的节点被移除,巨组元中仍然包含30%的节 点;如果攻击信息为完全信息(α=1),20%的节点被移除,巨组元规模几乎接近零,即网络崩溃.此外,我们 还可以看出,攻击信息凊度比攻击信息广度对巨组元规模丨S|影响更大.例如当δ=2时,获取30%的重要 节点信息(a=0.3),基本等价于故意攻击,即使仅获取10%的节点信息(a=0.1),网络也变得非常脆弱;但 是,如果6=0,获取30%的节点信息(a=0.3),基本没有影响,即使获取80%的节点信息(a=0.8),网络 抗毁性也非常强 0 V∝ ◇ EsA O 图2巨组元规模随节点移除比例变化图 为了直观展现攻击信息广度参数α和攻击信息精度参数δ对巨组元规模丨S的影响,在图3中我们给 出∫节点移除比例∫=50%时,巨组元规模|S关于a、δ的三维关系图以及等高线可以看出,少量高精度 信息就等价于大量低精度信息 图3巨组元规模关于攻击信息参数的三维关系以及等高线图 第7期 吴俊,等:基于不等概率抽样的不完全信息条件下复杂网络抗毁性模型 1215 图4给出了无标度网络在不同攻击信息参数组合(α、δ)条件下临界移除比例∫。随标度指数γ变化图, 其中ⅳ=1000.m-2,实线解析结果.可以看出,当γ≥3时,仿真结果与解析结果吻合良好,但当γ<3 时,仿真结果与解析结果稍有偏差.这是因为当γ<3时,无标度网络的结构最大度( Structure cut-off) √<k>N小于其自然最大度( Natural cut-off)mN1-1),这导致所生成的网络中自环和多重边的数量不 能忽略,而解析结果是在简单图假设下得到的.文献15,27对上述偏差进行过详细分析.可以看},攻击信 息对临界移除比例∫有显著影响.例如当η=2.5时,如果攻击信息为零信息(α=0),则∫。=0.892;但如 果(a,δ)=(0.2,2),则f=0.430,这意味着如果能获取到20%比较重要节点的信息,就可以大幅降低网络 的抗毁性(从0.892到0.430);如果攻击信息为完全信息(a=1),则fe=0.215;但如果(a,5)=(0.8,0),则 f-0.890,这意味着如果能随机隐藏20%的节点信息,就可以大幅提高网络的抗毁性(从O.215到0.890 F日3日日E口口彐已七日 E口〓 日日日廿日日E日日日 6 日日日日日日士日日日日日日日日 8 日日日日日日日E早日日E日口彐日日口廿口日 图4临界移除比例与标度指数关系图 为了直观展现攻击信息广度参数α和攻击信息精度参数δ对临界移除比例∫的影响,在图5中给出了 标度指数γ=2.5时,临界移除比例f与α、δ的三维关系图以及等高线.从中也可以看出,少量高精度信 息就等价于大量低精度信息. 图5临界移除比例关于攻击信息參数的三维关系以及等高线图 1216 系统工程理论与实践 第30卷 5结论与讨论 本文将复杂网络攻击信息获取过程抽象成无放回的不等概率抽样问题,建立了不完全信息条件下的复杂 网络抗毁性模型,其中网络攻击信息可以用信息广度参数α和信息精度参数δ调节控制,以前的随机失效及 意攻击是本文模型的两个特例.利用概率母凶数方法解析推导了随机信息和优先信息条件下具有任意度 分布义随机网络的两个重要抗毁性度量参数:巨组元规模以及临界移除比例.研究表明:对于度分布为 p(k)=(-1)m-1k-7的无标度网络,当γ>3时,总是存在一个有限的临界移除比例f。<1.但当 2<<3时,若δ=0.则只要能隐藏部分节点的信息(α<1),那么几乎需要移除所有节点才能使得网络崩 溃(∫。→1);若δ=∞.则只要能优先获取很少部分重要节点的信息(α>0).那么也能通过移除部分节点使 得网络崩溃(。<1).以无标度网络为例,对一般攻击信息参数组合(a,δ)进行了仿真分析.研究表明攻击 信息对巨组元规模S和临界移除比例∫ε都有显著影响:一方面随机隐藏少量节点信息就可以大幅提髙网 络的抗毁性:另一方面获取少量重要节点的信息就可以大幅降低网络的抗毁性.此外,硏究还发现攻击信息 精度比攻击信息广度对S和J影响更大,当攻击信息精度很高时,只需获取很少节点信息就能使得网络变 得很脆弱;反之:当攻击信息精度很低时,即使需获取大量节点儐信息,网络抗毁性也很强 需要指出的是,本文仅仅考虑了基于节点的抗毁性并且假设节点被攻击后与之相连的边全部移除.实际 上,很多时候节点很难被完全移除,只是与其相连的部分边失效.因此,基于边的不完全信息条件下复杂网络 的抗毁性还有待下一步继续硏究.此外,目前大部分研究(包括本文)都以巨组元规模为网络性能指标以网 络完全崩溃为临界糸件,以临界移除比例作为抗毁性指标.但对于很多复杂网络来说,要使其完全崩溃是非 常困难的攻击少量的节点很难改变巨组元的规模.这时,可以考虑选择其他网络性能指标(例如网络效率、 连通节点对比例)来代榉巨组元规模,以可调的阈值来代替网络崩溃作为临界条件 参考文献 1方锦清,汪小帆,郑志刚,等.一门崭新的交叉科学:网络科学(上)卩J.物理学进展,2007,27(3):239343 Fang Q, Wang X F, Zheng Z G, et aL. New interdisciplinary science: networks science(I)[J. Progress in Physics,2007,27(3):239343 2]方锦清,江小帆,郑志刚,等.一门崭新的交叉科学:网络科学(下)[J.物理学进展,2007,27(4):361-448 Fang J Q, Wang X F, Zheng Z G, et al. New interdisciplinary science: networks science(II)J. Progress in Physics,2007,27(4):361-448 阝]方锦清,汪小帆,刘曾荣.略论复杂性问题和非线性复杂网络系统的研究[.科技导报,2004,22(2):912 Fang J Q, Wang X F, Liu Z R. On the study of complexity and nonlinear complex networks[J]. Science Technology Review, 2004,(2): 9-12 [4]吴金闪,狄增如.从统计物理学看复杂网络研究↓J].物理学进展,2004,24(1):18-46. Wu J s, Di Z R. Complex net works in statistical physics J]. Progress in Physics, 2004, 24(1):18-40 5]郑金连,狄增如.复杂网络研究与复杂现象门.系统辩证学报,2005,13(4):8-13. Zheng J L, Di Z R. A brief discussion on complex networks and complexity[J. Journal of Systemic Dialectics 2005,13(4):8-13 6]陈禹.人类对于网络的认识的新发展!J系统辩证学报,2005,13(4):18-22 Chen Y New progress on the network for the human beingJ. Journal of Systemic Dialectics. 13(4) 阿7]史定半.网络——探索复杂性的新迩径!J系统工程学报,2005、20(2):115-119 Shi D H. Networks- A new approach for exploring complexity[J. Journal of Systems Engineering, 2005, 20(2) 115-119 8]汪秉宏,周涛,何大韧.统计物理学与复杂系统研究最新发展趋势分析J.十国基础科学2005,7(3):3743. Wang B H, Zhou T, He D R. The trend of recent research On statistical physics and complex systeIns[J. China Basic Science, 2005, 7(3):37-43 ⑨]谭跃进,吴俊,邓宏钟复杂网络抗毁性硏究综述·系统工程,2006,24(11):1-5. Tan Y J, Wu J. Deng H Z Invulnerability of complex net works: A survey. Systems Engineering, 2006, 24(11) 10昊俊,谭跃进复杂网络抗毁性测度研究系统工程学报,205,20(2):128-131. Wu J, Tan Y J. Study on measure of complex network invulnerability J. Journal of Systems Engineering, 2005 20(2):128-131 1]谭跃进,吕欣,吴俊,等复杂网络抗毁性研究若干问题的思考刂J.系统工程理论与实践,2008、28(增刊):16-120 Tan Y J, Li X, Wu J, et al. On the invulnerability research of complex networks J. Systems Engineering Theory Practice, 2008, 28(Suppl): 116-120