（控制理论与控制工程专业论文）复杂网络系统结构与动态特性分析研究.pdf

摘要 关键词:复杂网络，小世界，无标度，结构特征，局域世界网络，网络抗攻击 性， 随机攻击，蓄意攻击，网络同步，同步稳定性，同步鲁棒性，同步脆弱性， 加权网络，软件系统，l i n u x内核，头文件合作网络 ab s tra c t ab s t r a c t r e c e n t l y , c o m p le x n e t w o r k h a s b e c o m e a n i m p o rt a n t in t e r d i s c ip l i n a r y f i e l d , w h i c h a tt r a c t s m o r e a n d m o r e r e s e a r c h e r s i n p h y s i c s , b i o l o g y , m a t h e m a t i c s , c o m p u t e r , e t c . i n t h i s p a p e r , b y a p p l y in g s t a t i s t i c s a n d c o m p u t e r s i m u l a t i o n , t h e r e s e a r c h e ff o rt s a r e p a i d o n t h e s t u d y o n s e v e r a l p r o b l e m s i n t h e s t ru c t u r e a n d d y n a m i c s o f c o m p l e x n e t w o r k s : n e t w o r k r e s i l i e n c e , s y n c h r o n i z a t i o n o f d y n a m i c a l c o u p l e d s y s t e m s a n d t h e a n a l y s i s o f t h e s t r u c t u r a l o r g a n i z a t i o n o f t h e c o d e s o f l i n u x k e rn e l s b y w e ig h t e d n e t w o r k a p p r o a c h . t h e s t u d y o n t h e s y n c h r o n i z a t i o n o f d y n a m i c a l n e t w o r k e d s y s t e m s , in c l u d e s t h e r e s u b - p r o b le m s : t h e e ff e c t s o f t h e s t ru c t u r a l p r o p e rt i e s o n t h e s y n c h r o n iz a b i l i t y o f t y p e i s y s t e m ; the r e l a t i o n b e t w e e n n e t w o r k s y n c h r o n i z a b i l i t y a n d n e t w o r k t o p o l o g y o f t y p e i s y s t e m , t h e r e l a t i o n b e t w e e n t h e m o d e l p a r a m e t e r s a n d t h e s y n c h r o n i z a b i l it y o f t y p e i i s y s t e m , a n d t h e a b i l it y o f d y n a m i c a l n e t w o r k s t o re s i s t r a n d o m e r r o r s a n d i n t e n t i o n a l a tt a c k s w it h r e s p e c t t o t h e c h a n g e o f t h e i r s y n c h r o n i z a b i l i t y . t h e s e r e s e a r c h r e s u l t s a r e g r e a t ly h e l p f u l t o d e s i g n s a f e s y s t e m s , i m p r o v e t h e s y n c h r o n i z a t i o n o f n e t w o r k e d s y s t e m , a n d t h o r o u g h l y u n d e r s t a n d t h e s t r uc t u r a l p r o p e rt i e s a n d e v o l u t i o n o f l a r g e - s c a l e c o m p u t e r s o ft w a r e s y s t e m s . t h u s t h e w o r k h a s im p o rt a n t s i g n i f i c a n c e i n r e a l - w o r ld a p p l i c a t i o n . t h e m a i n in n o v a t i v e w o r k a n d k e y p o i n t s a r e l i s t e d a s f o l lo w s : ( 1 ) s t u d y o n t h e t o p o l o g i c a l p r o p e rt i e s o f l a r g e - s c a l e l o c a l - w o r l d e v o l v i n g n e t w o r k s . s e v e r a l i m p o rt a n t q u a n t i t i e s a r e u s e d t o i n v e s t i g a t e t h e s t r u c t u r a l p r o p e rt i e s . t h r o u g h n u m e r i c a l s i m u l a t i o n s , t h e r e la t io n s b e t w e e n n e t w o r k t o p o l o g y a n d t h e p a r a m e t e r s o f e v o l v i n g n e t w o r k m o d e l a r e f o u n d ; ( 2 ) i n v e s t i g a t i o n o n t h e r e s i l i e n c e o f l o c a l - w o r l d e v o l v i n g n e t w o r k s t o r a n d o m e r r o r s a n d i n t e n t i o n a l a t t a c k s . t h e d i s t u r b a n c e t o t h e n e t w o r k s c o n n e c t i v i t y i s e m u l a t e d b y n o d e / e d g e r e m o v a l i n t w o d i ff e r e n t w a y s : r a n d o m e r r o r o r f a i l u r e m e a n s r a n d o m r e m o v a l o f a f r a c t i o n o f n o d e s , w h i le d e l i b e r a t e d a m a g e t o a n e t w o r k m e a n s t a r g e t e d r e m o v a l o f n o d e s w i t h h i g h e r d e g r e e s . d u r i n g t h e n e t w o r k f r a g m e n t a t i o n p r o c e s s , t h e d i s ru p t i o n o f t h e i i i ab s t r a c t n e t w o r k t o p o lo g y i s m o n i t o r e d b y m e a s u r i n g t h e c h a n g e s o f s e v e r a l i m p o r t a n t p r o p e rt i e s w i t h t h e i n c r e ase o f t h e n u m b e r o f r e m o v e d n o d e s . t h e n u m e r i c a l r e s u l t s s h o w t h e d i ff e r e n t b e h a v i o r s o f l o c a l- w o r l d e v o l v i n g n e t w o r k s t o d i ff e r e n t t y p e s o f a t t a c k s . f u rt h e r mo r e , t h e r e as o n s w h y t h e s e n e t w o r k s d i s p l a y t r a n s i t i o n a l b e h a v i o r s c o n c e rn i n g t h e r o b u s t n e s s a g a i n s t r a n d o m e r r o r s a n d f r a g i li t y t o i n t e n t i o n a l a tt a c k s a r e a n a l y z e d . ( 3 ) i n v e s t i g a t i o n o n t h e s y n c h r o n i z a t i o n p r o b l e m o f l i n e a r l y - c o u p l e d c o n t i n u o u s - t i m e d y n a m i c a l n e t w o r k s y s t e m w it h c o u p l i n g c o n f i g u r a t io n c o n s t r u c t e d a c c o r d i n g t o l o c a l - w o r l d e v o l v i n g m o d e l n u m e r i c a l s i m u l a t io n s i l l u s t r a t e t h e e ff e c t s o f t h e s t ru c t u r a l p r o p e rt i e s o n t h e s y n c h r o n i z a b i l i t y o f t y p e i s y s t e m a n d t h e r e l a t i o n b e t w e e n t h e m o d e l p a r a m e t e r s a n d t h e s y n c h r o n i z a b i l i t y o f t y p e i i s y s t e m . ( 4 ) s t u d y o n t h e a b i l i t y o f d y n a m i c a l n e t w o r k s t o r e s i s t r a n d o m e r r o r s a n d i n t e n t i o n a l a t t a c k s w i t h r e s p e c t t o t h e c h a n g e o f t h e i r s y n c h r o n iz a b i l i t y . a b e tt e r q u a n t i t y i s i n t r o d u c e d t o m e as u r e t h e s y n c h r o n i z a b i l i t y o f t h e r e s i d u a l n e t w o r k a ft e r n o d e r e m o v a l . u s i n g t h r e e k i n d s o f a t t a c k i n g s t r a t e g i e s , t h e r e s p o n s e o f d y n a m i c a l s y s t e m s w i t h l o c a l - w o r l d t o p o l o g i e s a r e a n a ly z e d . s i m u l a t i o n r e s u lt s s h o w e d t h a t d y n a m i c a l l o c a l - w o r l d n e t w o r k s s h o w t r a n s i t i o n a l b e h a v i o r s c o n c e rn i n g t h e s y n c h r o n i z a b i l i t y r o b u s t n e s s a g a i n s t e r r o r s a n d f r a g i l i t y a g a i n s t i n t e n t i o n a l a t t a c k s b e t w e e n s c a l e - fr e e a n d e x p o n e n t i a l n e t w o r k s . ( 5 ) a n a l y s i s o f t h e s t r u c t u r a l o r g a n i z a t io n o f t h e c o d e s o f l i n u x k e rne l s f r o m t h e v i e w p o in t o f w e i g h t e d c o m p l e x n e t w o r k s . t h e c o l l a b o r a t i o n r e l a t i o n s h i p s b e t w e e n h e a d e r f i l e s i n t h e s o u r c e n o d e o f l i n u x k e rn e ls , w h i c h a r e r e p r e s e n t a t i v e e x a m p l e s o f l a r g e - s c a l e o p e n - s o u r c e s o ft w a r e s y s t e m s , a r e a n a l y z e d b y c o n s t r u c t i n g w e i g h t e d n e t w o r k - h e a d e r f i l e c o l l a b o r a t i o n n e t w o r k ( h f c n ) i n a n a t u r a l w a y : i n t h e n e t w o r k s , e a c h v e r t e x r e p r e s e n t s o n e h e a d e r fi l e a n d t w o v e rt i c e s a r e c o n n e c t e d i f c o r r e s p o n d i n g h e a d e r f i l e s a r e b o t h i n c l u d e d i n t h e s a m e s o u r c e fi le a t l e as t o n c e . a l s o t h e w e i g h t o f a l i n k i s a s s i g n e d t o b e t h e i n t e n s it y o f c o - i n c l u s i o n o f t w o h e a d e r f i l e s . t w o k i n d s o f h f c n n e t w o r k s : h f c n - 1 a n d h f c n - i i a r e c o n s t r u c t e d r e s p e c t i v e l y a c c o r d i n g t h e t y p e o f h e a d e r f i l e s i n l i n u x k e rn e l . t h r o u g h u s i n g a p p r o p r i a t e n o n - w e i g h t e d a n d w e i g h t e d q u a n t i t i e s , t h e i v ab s t r a c t c o m p l e x s t r u c t u r a l p r o p e rt i e s , t h e w e i g h t d i s t r i b u t i o n a n d t h e i m p a c t b e t w e e n t h e m o f t h e s e n e t w o r k s a r e c h a r a c t e r iz e d a n d a n a l y z e d , w h i l e s p e c i a l a tt e n t i o n i s p a i d t o t h e c o m p a r i s o n o f t h e s e t w o ty p e s o f n e t w o r k s . f u rt h e r m o r e , 勿 i n t e g r a t i n g t h e c o r r e s p o n d i n g n e t w o r k e d p r o p e rt i e s a n d p a rt i c u l a r c h a r a c t e r i s t i c s o f l i n u x k e rn e l s , a b e tt e r d e s c r i p t i o n o f t h e o r g a n i z a t i o n a l p r i n c i p l e s a n d e v o l v i n g m e c h a n i s m a r e p r o v i d e d . k e y wo r d s : c o m p l e x n e t w o r k , s m a l l - w o r l d , s c a l e - fr e e , s t r u c t u r a l p r o p e rt i e s , l o c a l - w o r ld e v o l v i n g n e t w o r k , n e t w o r k r e s i l i e n c e , r a n d o m e r r o r , i n t e n t io n a l a tt a c k s , n e t w o r k s y n c h r o n i z a t i o n , n e t w o r k s y n c h r o n i z a b i l i t y , s y n c h r o n i z a b i l i t y r o b u s t n e s s , s y n c h r o n i z a b i l ity f r a g i l i t y , w e i g h t e d n e t w o r k , s o f t w a r e s y s t e m , l i n u x k e rn e l , h e a d e r f i l e c o l l a b o r a t i o n n e t w o r k ( h f c n ) v 南开大学学位论文版权使用授权书 本人完全了 解南开大学关于收集、保存、使用学位论文的规定， 同意如下 各项内容:按照学校要求提交学位论文的印刷本和电 子版 本; 学校有权保存学位论文的印刷木和电子版，并采用影印、缩印、 扫描、 数字化或其它手段保存论文; 学校有权提供 目 录检索以及提供 木学位论文全文或者部分的阅览服务; 学校有权按有关规定向国家 有 关部门或者机构送交论文的复印 件和电子版; 在不以赢利为目的的前 提下，学校可以适 当复制论文的部分或全部 内容用于学术活动。 学 位 论 文 作 者 签 名 : 葫 , ltr 还 有很多 学者 在 其它 类型 的 网 络 对 抗 攻 击 性问 题 展开了 探讨 p : 例 如 新 陈 代 谢网 ， 食 物 链网， e - m a il 网 络 以 及 其 它 根据网 络模 型 建 立的 网 络3 8 -0 5 1 ， 大多 数网 络对 于随 机的 节点的 删除 都 表现出鲁棒性，而对于以 最大度节点为目 标的删除却表现出脆弱性: p . c r u c it ti 等考虑针对网络中节点的几种攻击方式:随机攻击、依最大度的 绪论 蓄意攻击、 依最大负载的蓄意攻击等进行对比研究，采用网络全局通信效率， 衡量 攻击对b a 无标度网 络和e r 随 机网 络的 破坏作用 3 8 1 . 在文 献 3 9 中， p . c ru c itt i 等 研究了 两 种不同 类型的 无标 度网 络: b a无 标度 网络和k e无标度网络的抗攻击性， 考虑随机攻击和蓄意攻击两种方式对网络全 局性质和局部性质的影响，主要采用网络全局通信效率和局部效率来衡量网络 在一定比 例的节点被删除后其拓扑结构变化情况。 文 献 4 4 1 中 ， p . h o lm e 和b . j . k im等 研究 者 全 面 的 研究了 四 种基于 模型 生 成 的网络: e r随机网络、 ws小世界网络、 b a无标度网络和c s f( 高聚集性无标 度) 网络以及两种实际网络: 科研合作网和i n t e rn e t 网络对蓄意攻击抗攻击能力， 分析了这些网络在八种不同的攻击模式下网络拓扑结构变化规律; 随着对复杂网络的抗攻击性问题认识的提高，很多研究者开始研究网络鲁 棒性的优化策略4 6 -5 1 1 ，即如何优化网 络的拓扑结构提高网络抵御突发故障、随 机错误、以及破坏性更大的蓄意攻击的能力。己 有的优化方法包括调节网络度 分布 4 6 -0 9 1 、 提高 网 络的 全局连通 效率 5 0 1 、 优化网 络 嫡 5 1 等: v a l e n t e等人推出对于一次随机攻击和恶意攻击具有最优鲁棒性的网络中的 节点的 度最多只能取自 三个不同的 值46 1 . g . p a u l 等 4 7将 提 高 网 络 对 随 机 攻 击 的 鲁 棒 性 转 化 为 最 大 化 a 值 天 问 题 4 71 研究发现对随机攻击具有最强抵抗能力的网络的度分布服从双项度分布 ( b im o d a l d e gr e e d is tr ib u tio n ) ， 即 网 络 中 存 在 。 一 而个h u b 节 点 和 n - 。 个 度 值 为1 的节点; 通常具有特定度分布的某类网络只对一种攻击方式具有很强的鲁棒性，比 如无标度网络对随机攻击具有很强的鲁棒性，但对于以度值最大的节点为目 标 的 恶 意 攻击则 表 现出 极大的 脆弱 性。 g . p a u l 和t . t a n i z a w a 等4 8 在保持网 络中 边 总数一定的条件下，考虑如何同时提过网络对随机攻击和蓄意攻击的抵抗能力， 研究发现对随机攻击和蓄意攻击都能具有很强的 抵抗能力的网络具有这样的度 分 布 特点 : 只 有 一 个 节 点 的 度 值 为气 - a n 2 13 ， 即 k 2 - a n 2 /3 个 节点 连 接 到同 一 个 节点 ; 其 余 节 点 的 度 值为k , - a n 1/ 3 一 ( k ) o 在文献 5 0 中， 王冰等通过 边重连提高全局 通信效率 提高随机网 络的容错能 力:在网 络耗费一定 ( 即网络中 边总数不变，( k ) = c o n s t )的 情况下，引入边重 连 ( e d g e r e w i ri n g ) 机制， 经 过多次以 提高e 值为目 的的 边重连后， 较之初始 的随机网络，优化网络能够具有更强的对随机攻击的抵御能力; 绪论 由于网络连接异质程度越强，度分布嫡越大，网络容错性也越强，王冰等 等对无标度网络的嫡与度分布幂指数、 最小 度、网络规模的关系进行了 研究， 提出了 一种通过优化网 络嫡来提过无标度网 络的 容错能力的方法1 5 1 1 1 . 2 . 3动态藕合网络同步 自 然界和人类社会中同步现象无处不在，包括蛙鸣、萤火虫发光、心肌细 胞和大脑神经网络的同步、钟摆同步摆动， 鼓掌频率的逐渐同步等等。祸合系 统的同 步问 题多 年来一直吸引 着人们极大 的 研究兴 趣5 2 -5 4 1 。 在早期的 研究中， 人们主要关注拓扑结构比较简单规则网 络，这样使人们将研究重点放在网络节 点的复杂动力学行为上，而忽略掉网络结构对网络整体动力行为的影响。然而 随着近年来复杂网络研究的快速发展，理论研究和实验结果说明复杂网络的拓 扑结构对网络的性能以及其上很多物理行为都起着很大的影响作用，因此研究 者可是把目 光转向研究网络的拓扑结构与网络的同步行为之间的关系问题。 如果在网络的每个节点上加一个动力学系统，节点之间有边相连表示动力 学系统之间存在相互的祸合作用，就形成了一个祸合动态网络系统。对于网络 同 步的 稳定 性问 题， p e c o r a 和c a r r o l l 等人 通过建立主稳定方程 5 5 -5 2 1 ，利用主稳 定函 数; w u c . w . 、 汪小帆、 陈关荣 等 利 用李 雅 普诺 夫 方 法 5 4 ,5 8 -6 0 1 ， 分析 得到 了 网 络的 同 步 稳定判 据， 将系统分析 三 种 类 型 5 2 : 对于 类型i 系 统中， 藕合 矩阵 的 特 征 根 比 值吞 1 .32 越 大 ， 网 络 的同 步 能 力 越 弱 ， 相 反， 若a n 1 凡越 小 ， 系 统 越 容 易 达到 同 步 状态; 对 于 类型i i 网 络， 祸 合 矩阵 的 第 二大 特 征根a2越 小， 队 越 大， 网 络同 步 能 力 越 强， 相反a,越 大， i a 2 i 越 小， 网 络同 步 能 力 越差。 1 . 2 . 3 . 1拓扑结构特征对同步性能的影响 近年来复杂网络的研究进展促使人们开始广泛地关注祸合连接的拓扑结构 对 网 络 同 步 能 力 的 影 响 4 ,5 ,1 1,5 2 ,5 3 .6 1-6 6 1 。 这 些 拓 扑 性 质 包 括 : 节 点 度、 网 络 连 接 不 均匀程度、平均路径长度、聚集系数和介数等。 a ) 节点连接非均匀程度 h o n g h , k im b j , c h o i m y 等 人 利 用w s 小 世界 模 型 研究了 小 世 界网 络中 拓 扑 结 构 对同 步 能 力 的 影 响 6 11 。 随 着 边 重 联 概 率p 的 增 加 ， 网 络 藕 合 矩阵 特 征 根比 值心/ 凡随 之 减 小， 如图1 .2 ( a ) 所 示 ， 1a 明 类 型i 的 小 世 界 网 络的同 步 能 力 会随着“ 小世界” 特性的增强 ( 边重联概率p 增加， 使远程节点之间出现直接 绪论 连边)而增强。 ， 的一一- ， ) .n / x 2 。 . 6 0 加加 4 0 .- 7= 供，、 . 一 一 一一 一 臼 - 气 从 一 . 0 d 一 0. 7 一 d ob 一. be 34j 6 7 械阳 i# 1 1 . 2 ( a ) w s 小 世 界 网 络 中 特 征 根 比 值 人 度 网 络 中 特 征 根 比 值 人/ 2 随边重 联概率p 的变化规律图 ( 取自文 献 6 门)二 ( b ) 无标 幂律指数y的变化规律图 ( 取自文献上 6 2 1 ) 对 于 度 分 布为 幂 律形 式p ( k 卜k - 的 无 标 度网 络， t . n i s h i k a w a 等 人 在 文 献 6 2 1 中 通 过 研 究 不同 y 值的 网 络发 现， y 值 越大 网 络， 其 特征 值比a l / a z 越小， 说 明 幂 指数越大的类型i 网络，其同步能力 越强， 如图1 .2 ( b ) 所示。 汪小帆等研究了由n w 小世界模型生成的网络中网络同步能力和拓扑结构 变 化的 关系 1 5 9 1 ， 根 据 类型1 1 网 络的 同 步稳定 性 判 据，网 络第二大 特征 根随 加 边 概率p 增加的减小， 说明在类型1 1 的小世界网 络中随“ 小世界” 特性的增强， 网络的同步能力会增强 ( 图1 .3 ) e b 1 1 . 3 n w 小 世 界 网 络 中 第 一 人 特 征 根凡随 加 边 概 率 p 的 变 化 规 律 图( 取 白 文 献 5 9 1 ) 用 度分 布 标 准 方差可来 衡 量 网 络中 节点 连 接 的 非均 匀 程 度， 可越大说 明 节 点度分布的范围越广，并有度较大的节点出 现，网络度分布不均匀程度增强。 图1 .4 记 录了 在小 世界网 络中 随 着加 边概率p 的 增加， 度分布不均匀 程度 增加; 结论 在 无 标度网 络中 度分布 标准差s 随幂指 数y 增 大 而变小， 说 明 网 络中 节点 度的 分 布越来越均匀。 图1 . 4 ( a ) w s 小世界网络中度分布标准差、 11 均路径长 度随 边4 联概率p 的变化规律图( 取自 文 献 6 1 1 ) : ( b ) 无标度网络中平均路径长 度、 度分布标准差、平 均度随幕律指数 y的变化规律图 ( 取自 文 献 6 2 j ) 分析网 络同步能力与节点连接非均匀程度的关系:从上述对小世界网 络和 无标度网络的对比分析可得，同样对于类型i i 网络，在小世界网络中度分布的 非均匀程度增加，可以显著提高网络的同步化能力;在无标度网络中的结论刚 好相反，即只有提高网络的均匀性，网络的同步性能刁 能得到提高。因此单独 用度分布均匀性指标无法衡量动态网络的同步能力。 b ) 平均路径长度 上面的例子中，小世界模型的一个显著的特点是随着边重连概率或加边概 率p 的 增加， 网 络的 平均路 径长度会减小( 如图i a ( a ) 所示) ， 此时 类型i 网 络 的 特征值比减小，网络的同步能力增加;而无标度网络中随着网络均匀性的提高， 节点之间的平均路径长度增大，网络的同 步能力也增加，这说明单独采用网络 的平均路径长度也无法衡量动态网络的同步能力。 c ) 聚集系数 复杂网 络的另外一共非常重要的 概念是 聚集系数， 在文献 6 6 中 对网 络平均 聚集系数不同的网 络进行研究， 发现太大的聚集系数不利于类型i 网络同步， 即 聚集系数越大，相应网络的同步能力越差。 d ) 节点介数 文 献 6 1 和【 6 2 的 研究认为 节点介 数在 刻 画网 络同 步能力 时 起到 重 要作 用， 绪论 研究发现网络中最大的节点介数的变化规律和表征网络同步能力的特征值比的 变化是一致的，所以表明最大介数是一个相对比较统一的能够在很大程度上反 映网 络的同 步能力的参数， 但后来 研究者也发 现了一些反 例6 4 1 ， 认为 最大 介数 只能在某些特定网络中反映网络同步能力。 综上所述，网络中节点的度分布、平均路径长度、介数、聚集系数等这些 参数的变化会对不同类型网络的同步性能造成不同的影响，其中的具体原因仍 需进一步探讨，如何进一步从本质上刻画各种影响网络同步化性能的因素仍然 是一个非常 值得研究的课题5 2 1 决定复杂动态网络同步性能的因素有独立节点的动力学函数、网络的拓扑 连接结构、祸合方式 ( 包括祸合强度、是否对称祸合等) 、祸合输出函数等，在 其余条件确定的情况下，可以通过调节节点之间藕合强度、改变网络拓扑结构、 改 变权重分布 等方式可以改善网 络同步 性能 6 7 -7 2 1 :当网 络同步 有益时 提高 网 络 的同步能力:反之降低同步性能以避免有害的同步对系统的破坏。网络同步优 化的目 标一般转化为结构或权重调整后，尽可能增加或减少祸合矩阵的特征根 或特征根比值的问题: 文 献 6 8 中， 研究者采用 结 构 微扰的办 法， 改 变网 络的 拓扑 连 接结构， 重 构 节点之间的连接关系，要改变其祸合矩阵的特征值及其比值，因此改变网络同 步能力; 对网 络祸合 矩阵进行加权也是一种有效地改 进网络性能的手段。 在文献 7 0 的 研究 中 ， 通 过 调 节决定网 络 权 值 大 小 的 参 数p ， 改 变网 络的 特 征 值比人/ 凡， 从而改变网络同步性能; 还有一些调控方式也能够有效地改进各种网络的性能:如通过小波变化对 网 络 外 藕 合 矩阵 进 行 适当 扰 动 7 3 1 ; 改 变时 滞 17 4 】等。 1 . 2 . 3 . 2网络同步的鲁棒性与脆弱性 当网络中发生随机故障或者遭受外界攻击时，网络中的部分节点或边的功 能丧失，由 此造成对网络连通完整性的破坏，也会严重的影响网络的性能，如 动态 节点 间的 同 步能力。 己 有 研 究 3 1 .5 8 1 关 注了 在网 络遭受攻 击条 件下， 具有不同 拓扑结构的动态网络同步性能的变化情况: 汪 小 帆 等 人 在文 献 5 8 中 研 究了 类型i i 的b a 无 标度网 络 的 遭 遇到 随 机 攻 击 和针对度值大的节点的蓄意攻击时同步性能的变化。由于无标度网络的极度不 绪论 均匀性，在随机攻击时，随机去除的节点绝大部分度数较低，这些节点的去除 对网络中剩余节点之间的拓扑连接结构的影响不大，因此剩余节点之间的同步 性能没有太大的变化;但当网络遭受到蓄意攻击时结果就不一样了，这时被刻 意去除的那一小部分节点都是度数很高的节点，因此整个网络的连通性就会发 生剧烈的变化，甚至被分成了若干个不连通的子网，网络的同步能力会大大下 降甚至完全丧失。这就是无标度网络在动力学同步意义下的 “ 鲁棒而又脆弱” 的含义。 1 . 2 . 4加权网络 在无权网络中，只能用节点之间的存在与不存在两种情况来表示节点所代 表的个体之间的相互作用存在与否，这种定性描述有时并不能完全刻画节点之 间的相互作用，因为在许多情况下，节点之间的关系或相互作用强度的差异起 着至关重要的作用。例如在社会网络中， 相互作用强度对网络上的疾病传播等 过程会有重要影响;i n t e rn e t 网络上的通信链路的带宽、航空网络中两个机场间 航班的数量或旅客座位数、科研合作网中的合作次数等等都是影响系统性质的 重要因素。此时无权网络就存在局限性， 仅用一条边表示连接的存在与否不能 准确反映实际网络的细致结构及其功能， 这就需要引入边权来刻画相互作用强 度的差异性，从而形成加权网络。 现实网络的结构与功能往往是通过网络的拓扑结构、物理过程和权重的相 互作用而涌现的，因此加权网络研究的核心问题是理解网络拓扑结构、物理过 程和权重分布三者之间的匹配关系对网络功能的影响。目前对加权网络的 研究 主要分为下面这三个方面: ( 1 ) 实证研究 在加权网络中引入了节点之间相互作用的强度作为边的权重，增加了网络 的 抽 象 刻 画 能 力 ， 丰 富 了 网 络 的 统 计 性 质 ， 许 多 实 例 研 究 2 7 ,8 2 -8 7 1证 明 ， 加 权 网 络 表现除了丰富的统计性质和幂律行为，例如: a l m a a s 等人利用加权网络来分析新陈 代谢反应8 3 1 . n e w m a n 在科研合作网的研究中， 定义边权重刻画科学家之间合作的亲密程 度8 4 -8 6 1 ; 利用n e w m a n 的 权重定义， b a r r a t 等分析了在凝聚态方向 通过合著论文 建立的科研合作网2 7 1 . 绪 论 狄增如等研究者收集了1 9 9 2 - 2 0 0 4 年发表的经济物理方面的文章， 通过综合 考虑文章作者的论文合作、引用和致谢三种关系，建立了相关的加权有向网络， 并对该网 络进行分析，得到了一系 列统计结果 8 2 1 . 研究交通运输通信等类型的 网络时， 通常可以 把输运过程的流量转化为权 重。以 航空网络为例， b a r r a t 等人分 析了 全球航空网， 把机场i 和i 的 航班的有 效座位数当 作权重2 7 1 ; 李炜等人在 研究中国航空网络时， 将两个机场间的航班 数 视为权重8 7 1 . ( 2 ) 建 模 现实世界中加权网络各种特性的出现促使人们从理论上构造网络的演化模 型来解 释这些网络的 统计特性，探索隐藏 在网络背后的内 在演化机制。对于加 权网 络，需要考虑网络拓扑结构和权重分布的祸合演化机制 8 8 - 9 2 1 。国内外的大 量学者 在加 权网 络建模方面进行了 不懈的 探索: 基于无权的 b a无标度模型， y o o k . j e o n g 和b a r a b a s i 提出了 一个 简单的考虑权重的无标度演化模型8 8 1 ; b a r r a t . b a r t h e l e m y 和v e s p i g n a n i ( b b v ) 模型基于点强度驱动和边权逐渐增强机制进行 网 络演化 8 9 1 等等，对加权网 络建模 方面的综述可以 参考文献 4 ,8 2 0 ( 3 ) 动力 学行为 在加权网络上，节点间相互作用强度是制约动力学行为的重要因素，不同 的相互作用、不同的权重分布、 不同的 边权对应关系 会对动力学行为产生不同 的 影响，已 有的加权网络上动力学 行为的 研究包括传播动力学9 3 1 ， 加权网络上 的同 步 6 9 -7 2 1 、加权网络的 抗攻击 性4 .9 4 等。 25复杂软件网络 现代计算机软件越来越复杂， 体现在程序代码量巨 大， 也体现在模块、函 数、类、链接库等之间交互关系日 趋复杂。从网络的角度认识，大规模的计算 机软件可以 视为由不同 粒度上相互作用相互影响的个体 ( 比 如函数、类、 源文 件、 链接库等)组成的 一类复 杂系统。更好的认识和理解软件系统的复杂组织 结 构， 对于提高软件产品的 质量和可靠 性、加快软件系统开发、更好地进行系 统的 维护和扩展等都具有非 常重大的 工程意义和应用价值。 将复杂网 络研究和 传统的 软件研究相结 合，把软件系统中 存在的不同个体 以及个体之间的复杂关系抽象出来，使用图或网络的形式进行描述，分析网络 绪论 拓扑结构性质及其对软件系统的作用和影响，成为近些年来复杂网络研究领域 中的 一个重要方向 9 5 - 1 0 3 1 。 下面分几 个主要 方面来简要综述目 前 国内 外在复杂软 件网络领域的主要研究进展: ( 1 ) 实 证研究 把软件系统中存在的个体以及个体之rh j 的复杂关系抽象出来，使用图或网 络的形式进行描述，采用复杂网络结构分析方法，分析软件网络的定量定性特 征。已有的研究包括对面向 对象程序中类继承引用关系、包依赖关系、函数调 用关系、源代码文件引用关系等网络的分析，发现大多少网络中都存在 “ 小世 界”和 “ 无标度”特征: c . m y e r s 研究了 面向 对象的程序设 计中 类之间的 继承和聚集两种关系， 以大 型 的 开 源 软 件9 5 ， 以v t k v i s u a liz a t io n l ib r a r y , d m , a b iw o r d 等 为 对 象， 建 立 以类为节点的有向网络;通过对各个网络的节点连通特性、度分布、节点度匹 配关系、层次结构等网络特征的统计和分析，发现在类相关网络中存在小世界 和无标度特性: s . v a l v e r d e和其合作者 采用无向 图 描 述j a v a d e v e l o p m e n t f r a m e w o r k 1 .2 ( j d k 1 .2 ) 系 统中的 类关 系网 9 6 ， 研究 发 现网 络的 度 分 布 服 从 幂律 分 布，节 点 聚 集系数比 相应的随机网络要大得多， 这是只有小世界网 络才具有的特征; s h l r l i 和w a n g 等 9 7 研 究 了 不 同 版