（信息与通信工程专业论文）复杂网络演化模型、鲁棒性与动力学过程研究.pdf

e v o l v 烈gm o d e l s ，r o b u s t n e ssa n d d y n a m i c a lp r o c e ss e so f c o m p l e xn e t w o r k s ad i s s e r t a t i o ns u b m i t t e dt o s o u t l l e a s tu n i v e r s i 够 f o rt h ea c a d e m i cd e g r e eo fd o c t o ro f e n g i n e e r i n g b y l it a o s u p e r v i s e db y p r o p e iw - e n - j i a n g s c h o o lo fi n f - o r m a t i o ns c i e n c ea n de n g i n e e r i n g s o u t h e a s tu n i v e r s 时 2 0 1 0 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知， 了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 为获得东南大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名： 牛 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件和电子 文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致。 除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括以电子信息形式刊登) 论文的 全部内容或中、英文摘要等部分内容。论文的公布( 包括以电子信息形式刊登) 授权东南大学研究生 院办理。 繇肆名：垃 日期：兰竺兰多 摘要 现实世界网络所蕴含的小世界效应、无标度特性、拓扑分形特征以及模块化结构等基本属性改变 了人们以往基于规则网络和随机网络对复杂网络所建立的认识。复杂网络理论作为复杂系统与复杂性 科学研究的重要分支，其目标在于揭示蕴涵于现实实体关系中的普遍规律，并探索其在科学技术领域 中的应用。本文围绕复杂网络演化与动力学机制，着重从派系社团网络和分形复杂网络演化机制及模 型、基于竞争与动态合作机制的网络社团结构检测算法、基于随机行走理论的复杂网络负载传输优化 策略、基于社团重叠结构的多目标攻击方法等几个方面开展深入研究，具体研究内容和主要贡献如下： 研究了基于派系社团重叠结构的复杂网络演化模型。首先，介绍了特征路径长度、节点度分布以 及聚类系数等复杂网络的主要结构测度：分析了小世界效应和无标度特性等复杂网络的基本属性：研 究了随机网络模型、小世界网络模型和无标度网络模型的演化机制。其次，提出了一种基于派系社团 重叠结构的复杂网络演化模型，并分别给出了模型的社团规模分布、社团度分布、节点度分布以及聚 类系数的解析解。分析和实验结果表明该模型的社团规模及节点度服从幂率分布，社团度服从指数和 幂律混合度分布，且具有模块化结构特征。 研究了基于类有限扩散凝聚过程的分形复杂网络模型。首先，对复杂网络的分形特征、生成机制 和分形维数计算方法进行了分析；讨论了确定性和非确定性分形复杂网络模型。其次，采用类有限扩 散凝聚过程的受限连接和去活动机制，提出了一种分形网络模型( 模型i ) 。进一步，在模型i 的基础 上，将乘性生长机制引入网络的生长过程，提出了分形网络模型i i 。分别给出了两种模型的度分布和 聚类系数的解析解，并利用盒维数法对其分形特性进行了研究。分析与实验结果表明两种模型均具有 可调的聚类系数和层次化模块结构，且其节点度服从指数和幂律混合分布。对于模型i ，当去活动参 数为0 和l 时，分别与o h o 和k e 模型等价。当参数在o 3 到o 8 之间时，具有分形特性，分形维数 在2 3 到2 8 之间变化：对于模型i i ，在乘性生长和邻域连接参数的控制下，分形维数在1 4 到3 7 之 间变化。 研究了基于竞争与动态合作聚类机制的网络社团结构检测算法。首先，介绍了社团定义和社团划 分结果定量分析测度；研究了诸如分裂法、凝聚法以及谱分析法等复杂网络社团结构检测的基本方法。 其次，针对社团边界模糊、社团异构分布以及分割粒度难以确定等社团结构检测难题，提出了一种基 于竞争与动态合作聚类机制的社团结构检测算法。该方法基于节点最短路径向量构造相似度矩阵，并 采用主分量分析技术实现对节点相似度矩阵的特征提取和降维。在此基础上，结合竞争与动态合作聚 类分析算法，实现了对复杂网络社团结构的有效检测。基于n e w m 锄网络、z a c h a 叮网络和d o l p h i n s 网络的实验与对比分析表明所提方法能够自适应地确定社团划分粒度，特别是在社团边界严重模糊的 条件下，其检测性能远优于g n 算法和n e w m 锄快速算法。 l 研究了基于随机行走理论的复杂网络负载传输优化策略。首先，分析了基于网络局部信息、全局 信息以及结合动态负载信息的路由策略；研究了包括节点度分布、聚类系数和节点度相关性等拓扑结 构特性对网络负载传输效率的影响。其次，结合对布朗粒子随机行走理论的研究成果，提出了一种基 于极小化路径节点度连乘积原则的优化路由策略。实验结果表明该策略使得网络节点的平均路由中心 度与节点度成线性关系，网络负载传输能力正比于网络规模的平方，且与单个节点度值无关，因此网 络负载获得最优分配。此外，所提策略的平均传输路径长度与网络节点数成对数关系，具有小世界效 应，且随着节点平均度值的增加，其平均传输路径长度逼近最短路径长度。对比实验表明该路由策略 的性能远优于最短路由策略和有效路由策略。 研究了基于社团重叠结构的复杂网络多目标攻击方法。首先，分析了影响复杂网络鲁棒性的主要 结构因素；研究了网络单目标随机与度选择攻击方法、多目标攻击方法以及网络抗毁结构优化策略。 其次，基于现实世界复杂网络普遍存在内部社团相互重叠缠绕的结构特征，提出了一种针对网络高社 团成员值节点的多目标攻击方法。该方法在攻击单个节点的同时，能够影响网络中多个社团的内部结 构并改变社团间的重叠关系，从而导致网络整体性能的下降。进一步，利用l 模型和i m e m e t 自治域 网络进行了攻击对比实验，针对特征路径长度、全局效率、聚类系数、最大簇值、最大社团值以及社 团数量等多种特征量的实验结果均验证了所提方法的性能远优于随机攻击和度选择攻击，同时还具有 独特的网络社团数量随攻击强度增加而急剧减少的特点。 形复杂网络，派系社团，社团结构检测，随机行走，路由策略，网络鲁棒性， i i a b s t r a c t m 锄y 陀a j 一、 r o r l dn e t w o f k ss h a r ec o m m o nt o p o l o 西c a ja i l dd 舯i c a lf e a ：c u r e ss u c h 硒p o w e r - 1 a wd e g r e e d i s 们b u t i o n s h o r ta v e r a g eg e o d e s i cd i s t a l l c e ，l a 玛ec l u s t e r i n gc o e m c i e n t ，t o p o l o g i c a js e l f s i m i l 撕t ya n d 1 1 i e r a r c l l i c a lm o d u l 撕t ) ，e t c ，w h i c ha 陀d i 毹r e n t 舶mm o s eo f 啪d o mn e 觚or ：k s 锄dr e g u l 盯l a 钍i c e s a s 觚 e m e 曙i n gb r a n c ho fc o m p l e ) 【i 够s c i e n c em a ts t u d i e sh o l i s t i cs y s t e m s ，r e s e a r c ho nc o m p l e xn e t w o f i 【st r i e st 0 r e v e a j 也eu i l i 、，e r s a l p r i n c i p l e so fr e a l 一w o r l dn e t w o r l 岱a n dd e v e l o pe n g i n e e r i n ga p p l i c a t i o n s r e c e l e n t l y c o m p l e xn e t 、】l ，o r l c sh a v eb e e ns t u d i e de 赋e n s i v e l yi i ln e r d i s c i p l i n a 拶f i e l d s i i l l i sd i s s e 僦i o mw ef o c u so n t 1 1 et o p i co fe v o l v i n gm o d e l s ，r o b u s 伽e s s 锄dd y n 锄i c a lp r o c e s so fc o m p l e x n e t w o r l ( s ，i n c l u d i n g 廿l em o d e l s w i t l lo v e r l 印p i n gc l i q u ec o m m u i l i t ) ，蛐r u c t u r eo rt o p 0 1 0 9 i c a ls e l f s i m i l a r i 劬t h ed e t e c t i o na l g o r i t h mf 0 rf u z 巧 锄dh e t e r o g e i l e o 眦d i g t r i b u t e dc o m m 嘶t ) rs t r i l c n l r e s ，廿1 eo p t i i i l a l 缸a 伍c r o u t i n gs n 锨e g yw i t t l l o a d s e l f b a l a n c i n gp r o p e r c ) ，锄dt l l em u l t i 叱醒e t sa t t a c ks c h e m e t h em a i nc o n t r i b u t i o i l so ft t l i sd i s s e n a t i o n 黜 l i s t e da sf o l l o w s ： f i r s t l y ，w es t u d yt h eg r o w mm o d e lo fc o m p l e xn e t w o f k sw i mo v e 订a p p i n gc l i q u ec o m m u i l i t ys n u c t u r e a f b 玎ab r i e fr e v i e wo ft h em e a s u r e m e n t sf 沁q u e n t l yu s e di i lc o m p l e xn e t w o f k sa n a l y s i s ，s u c ha sa v e r a g e g e o d e s i cd i s t a l l c e ，d e g r e ed i s t r i b u t i o i l ，c l u s t e r i n gc o e f f i c i e 峨e t c ，w ea n a l y s es y s t e m i c a l l l y 廿1 es 切l i s t i c a j p r o p e r t i e s 勰dt 1 1 ee v o l v i i l gm e c h a j l i s m so f 啪d o m ，如1 a l l - w o r l d 锄ds c a l e 一五r e en e 似，0 f i ( s w ep r o p o 觚 e v o l v i l l gn e 觚o r km o d e lw i t ho v e r l 印p i n gc l i q u ec o i r u t l u n 时s 仃u c t u 】r e 锄d 锄a l y s ei t s 如n d 锄e n t a lp r o p e r t i e s s u c h 雒c o m m u n n ys i z ed i s t r i b u t i o mc o m m u n i t ) ，d e g r e ed i s t r i b u t i o mn o d ed e g 陀ed i s t r i b u t i o n 柚dc i u s t e r i n g c o e f f i c i e n t t h e 陀s u l t ss h o w ，觚a l 如c a l l y 锄dn u m e r i c a j l y m a ：tt 1 1 ec o i n m 岫n ys i z ed i s t r i b u t i o n 锄d 廿l en o d e d e g r e ed i s t r i b u t i o ne ) d l i b i t 廿l ep o w e r _ l a ws c a l i n g 卸dt 量l ec o m m u n i 锣d e g r e ef 0 1 l o w sam i x e dd i s t r i b u t i o n ( i e ， e x p o n e l l t i a l 锄da l g e b r a j cd e g r e ed i 矧b u t i o n ) m o 瑚v e r ，t h el o c a lc o e 历c i e n ti n d i c a t e sm a tt l l em o d e l h a sa 1 1 i e “i r c h i c a lm o d u l a rs 仃u c t i l r e 。 s e c o n d l y ，w es t l l d yt h eg r o w t l lm o d e l so fm l c t a lc o m p l e xn e t w o r kb a s e d0 n 廿1 ep r o c e s so fd i 币l s i o n l i m i t i e da g g r e g a t i o n ( d l a ) f o l l o w e db y 协e 锄a l y s i so fu l ed e t e n n i n i s t i c 锄dm e 瑚d o m 丘徼t a lc o m p l e x n e t w o 水m o d e l s ，w ei n v e s t i g a 【t et 1 1 es 虮】c 删c h a r a c t e r i s t i c s ，t l l ee v o l v i n gm e c h 枷s m s 强d 廿l e 丘a c t a j d i m e n s i o na l g o r i t h m s0 ft l l e 触c t a lc o m p l e xn e 铆o i k s f o r t h e 册o r e ，w ep r e s e n tt w o 疗a c t a ln e t w o r km o d e l s o nn l e b 舔i so f 廿l er e s t r i c t e dp r e f e r e m i a la t t a c h m e n tm e c h a l l i s m ，m ed e a c t i v a t e dm e c h a i l i s m 锄d 舭 m u l t i p l i c a t i v eg r o w mm e c h 锄i s m b o 廿lm o d e l sh a v et u n a b l ec l u s t e r i n gc o e 伍c i e n t s 觚dh i e l i a r c h i c a lm o d u l 盯 s t r u m 鹏sw 汕t 1 1 es p e c 仇l m so fd e g r e ed i s t r i b 佣0 nr a n 西n gf h na l g e b r a j ct 0e x p o n e n t i a l l f 0 rf i l s tm o d e l ，i t i s e q u i v a j e n tt ol ( e 锄do h o m o d e l sw h e nt l l ev a l u eo ft 1 1 ed e a c t i v a t e dp 猢酏盯i so 锄d1 r e s p e c t i v e l y m o r e o v e r i th 鹄t o p o l o 西c a l 胁c t a lg 咖c t l 鹏w 曲t 1 1 ef a c t a ld i m e i l s i o nv a 巧i n gb e 附e e i l2 3 锄d2 8w h e n t h ev a l u eo ft l l ed e a c t i v a t e dp a m m e t e rr a n g e sf b m0 3t 00 8 f o r 廿l es e c o n dm o d e l ，t 1 1 ef t a jd i m e l l s i o n c h a n g e s 丘。o m1 4t o3 7w i t l lr e s p e c tt ot 1 1 ev a j u eo f t l l em u l t i p l i c a t i v ep a 飓m e t e r 锄dt h er e s t r i c t e d 撒h i i l e n t p a r a m e t e r t l l i l - d l y ，w ef 砬璐o n l ec o m m 岫i t yd e t e c t i o na l g o r i t h l t lb 勰e do nm ec o m p e t i t i v e 锄dc 0 0 p e m t i v e c l u s t e r i n gm e c h a n s m a f t e rr e v i e w 访g 廿l ep r i n c i p l ed e f i n i t i o 璐锄d 也em e a s u r e m e n t sa _ b o u tt h en e t w o r k c o m m u n i 劬w ei n v e s t i g a t et h ec o m m u i l i 够d e t e c t i o na l g o r i t l l m s ，i n c l u d i i l ga g g l o m e r a t i v ea l g o r i t h m s ，d i v i s i v e a l g o r i t l l m s ，s p e c 删a l g o r i m m se t c s y s t e m i c a l l y i i lo r d e rt ot a c et h en o n t r i b a lp r o b l e me n c o u n t e r e di i l i i i c o m m u n i t yd e t e c t i o 玑s u c ha sf u z 巧c o m m u n i t yb o 吼d a r i e s ，h e t e r o g e n e o u sc o m m u n i 够蛐n j c t u r e ，d i 历c u l t yi n d 酏e 加1 i n i l l gm ec o m m u n i t ) rs c a l e ，w ep r o p o s eac o m m u n i t yd e t e c t i o na l g o r i t h mb a s e do nm ec o m p e t i t i v ea n d c o o p e r a t i v ec l u s t e r i n gm e c h a n i s m a r e rd e f i v i n gn l es i m 订撕t ) rm a t r i xf r o mt h ev e c t o r so ft 1 1 eg e o d e s i c d i s t 啪c e ，廿l ep r e s e n t e da l g o r i m me x t r a c t sf e a t u r e sf 如mm es i i i l i l 撕够m a t r i xa n dp r o j e c t s i t0 n t oa n a p p r o p r i a t el o w e r - d i m e n s i o n a jf e a t u r es p a c eb yu s i n gm ep r i n c i p a lc o m p o n e n ta n a l y s i s t h e n ，i tc 硎e s0 u t t h ec o m p e t i t i v e 锄dc o o p e r a t i v ec l u s t e r i n ga l g o r i t h i i lt 0d e t e c t 也ec o m m u n i t i e si nm ef i e a n 鹏s p a c e n e r e s u l t so fe x p e r i m e n t a t i o no nt 1 1 en e w m 锄c o m p u t e r g e n e r a t e dn e 似o i l ( s ，t l l ez a c h a 巧sk a r a t ec l u bn e 似o r k a n d 也eb o t t l e n o s ed o l p h i nn e t w o r ks h o wt l l a tt 1 1 ep r e s e n t e da l g o r i n l mc 锄a d a p tw i t ht h ec o m m u n i 锣s c a l e a u l dt l l ep e 墒册锄c ei s 陆s u p e r i o rt 0t h eg na 1 9 0 r i t h m 柚dt h en e w m 锄缸ta l g o r i 廿1 r n ，e s p e c i a l l yf o rt h e c o m m u n i t i e sw i t hf l l z z yb o u n d 撕e s f o u n h l y ，w es t u d yt h eo p t i m 削r o u t i n gs 仃j l t e 影0 ns c a l e - f r e ec o m p l e xn e 觚7 0 f k s w er e v i e ws o m et y p i c a l r o u t i n gs 仃a t e 西e s ，w h i c ha r eb a l s e do nl o c a ln e t 、】 r o r km f 0 肌a t i o i l ，g l o b a ln e 鲰，o r ki n f 0 册a t i o na n dd y n 锄i c l o a di n f o m a t i o n r e s p e c t i v e l y f o r t l l e r m o r e ，w e 觚a l y z et h ei n f l u e n c e so n 打a n s p o r te 伍c i e n c ye x e n e db y n o d ed e g r e ed i s t r i b u t i o i l ，c l u s t e r i n gc o e f f i c i e n t ，c o r r e l a t i o nc o e 街c i e n ta n do t l l e rt o p o l o g i c a j 丛p e c t s 、矾t ht h e 锄a l y s i so fn l er 觚d o mw a l ko nn 咖r k s ，w ep r o p o s ean e wr o u t i n gs 廿a t e g yt 0i m p r o v en l e 舰n s p o n a t i o n p e r f 0 瑚锄c e0 ns c a l e f 沁en e t w o f k s ，n 锄e do p t i m a jr o u t i n g 蚰眦e g y a m o n ga l lt 1 1 ep o s s i b l ep a t h sf b m t h e s o u r c en o d et ot 1 1 ed e s t i n a t i o nn o d e ，t l l ep r e s e m e dr o u t i n g 触g ys e l e c t st h ep 砒t h a th 舾m el e a s tv a l u eo f 廿1 ep r o d u c to fa l ln o d e s d e g r e e0 ni t e x p e r i m e n t a jr e s u l t ss h o wt l l a t 竹l ea v e r a g er o u t i n gb e 铆e e n n e s s c e n n a l i 够i n c r e a s e sl i n e a r l yw 曲m ei n c r e a l s i n go f t h ed e g r e e ，m en e t w o r kc a p a b i l i t yi sp m p o n i o n a t et ot h e s q u a r eo f l en e 锕o r ks i z ea n di si n d e p e n d e n to f e a c hn o d ed e g r e e ，i n d i c a t i n g 也a t 廿1 e1 0 a do ne a c hn o d ef i t s w e nw i t ht h ec a p a c i t ) ，o fm en o d e c o m p a r e dw i t l lt h es h o 巾e s tp a mr o u t i n gs 仃a t e g y 锄dt 1 1 ee 伍c i e n tr o u t i n g s 仃a t e 科m ep r e s e n t e dr o u t i n gs 仃a t e 斟c 柚e n h a i l c e 廿l en 舐) r o r kc a p a b i l i 够s e v e r a lt i m e s m o r e o v e r 廿l e a v e r a g ep 砒l e n g ：廿1o ft h ep r e s e n t e dr o u t i n gs n a t e 斟i n c r e 硒e si np r o p o r t i o nt 0t h el o g 撕t h mo ft 1 1 en e t w o 出 s i z ea l l d 伊a d u a l l y 印p r o a c h i n gt 0t 1 1 a to fm es h o r t e s tp a mw i t ht h em c r e a s i n go f 廿1 ea v e r a g en o d ed e g r e e l a s tb u tn o tt h el e a w e 蜘j d yt 1 1 em u l t i t a 唱e t sa 位a c ks c h e m ew i mr e s p e c tt 0t h eo v e 订a p p i n g c o m m u l l i t ys 仃u c t u r e w ei n v e s t i g a t em ea ：t t a c km e t l l o d ss u c h 船s i n 9 1 e i t a 唱e t 舭k s ，m u l t i 切昭e t sa n a c l ( s ， e t c a 1 1 dt h es t 九j c t u r eo p t i n l i z a t i o nm e m o d sf o ri m p r 0 v i n gt h en e 铆o r kr o b u s 协e s ss y s t e m i c a l l y a c c o r d i n gt 0 t l l ef 砬tt h a lm a i l yr e a l - w o r l dc o m p l e xn e t w o r l ( sa r em a d eo fi n t e n v o v e no v e r l 印p i n gc o m m u n i t i e s ，w e p r e s e man e wm u l t i 叱l 略e t s 撒ks c h e m ef b m l ep o i n to fv i e wo ft h ec o m m u n i t ym e m b e r s h i po f e a c hn o d e s i n c et i l ea t t a c k e dn o d e sb e i o n gt os e v e r e a jc 0 姗u n i t i e s ，m ed e l e t i o no fs u c hn o d e sw i l ld r 2 l s t i c a l i ya j t e rt h e i n t e m a ls 饥l c t u r e s 锄d 廿l eo v e r l 印p i n gr e l a t i o 舾o f 辩v e r a lc o m m u n i t i e s ，r e s u l t i n gi nt h ep e 而m a n c e d e t e r i o r a t i o no f 廿l ee n t i r en e 铆o r k b a s e d0 nt h ea n a l y s i so fa v e 孵g e o d e s i cd i s t a n c e ，9 1 0 b a le 币c i e n c y ， c l u s t e r i n gc o e 伍c i e n t ，g i a n tc o m p o n e n ts i z e ，m a i nc o m m u m 够s i z ea l l dc o m m u n i t ) ，n 啪b e r e x i ) e r i m e m i a l r e s u l t so fa t t a c k i n gm e k en e t w o r k 锄di n t e m e ta sn e t 、v o r ks h o wt l l a tt h ep e r f 0 皿a 1 1 c eo ft l l ep r e s e m e d s c h e m ei sm o r ep m m m e mt h a nm e 舳d o ma ：c t a c ka 1 1 dd e g r e eb a s e d 甜a c k i m e r e s t i n g l y ，w e0 b s e r v e t h a t 也e n 啪b e ro fc o m m u n i t i e sw i l ld e c r e 勰er a p i d l yu n d e rt l l ep r e s e n t e dm u l t i 也唱e t sa t t a c k k 岛僻o r d sc o m p l e xn e m o r k s ，f m c t a lc o m p l e xn e m o r k s ，c l i q u ec o m m u l l i 劬c o m m u l l 时d e t e “0 1 1 ，r 锄d o m w a l kr o u t i n gs n a t e g y ，n e t w o r kr o b u s n l e s s ，m u l t i - t a 玛e t s 撇k 摘要 目录 目录 第一章绪论 i v l 1 1 研究背景1 1 2 国内外研究现状4 1 3 论文开展的主要工作一10 1 4 论文的组织结构。1 2 第二章基于派系社团重叠结构的复杂网络模型研究1 4 2 1 复杂网络统计特征1 4 2 2 复杂网络模型19 2 2 1 随机网络模型2 0 2 2 2 小世界网络模型。2 1 2 2 3 无标度网络模型2 4 2 3 基于派系社团重叠结构的复杂网络模型2 8 2 3 1 网络模型生长机制2 9 2 3 2 网络模型统计特征理论与实验分析3 0 2 4 本章小结3 3 第三章基于类有限扩散凝聚过程的分形复杂网络模型研究3 4 3 1 分形研究背景3 4 3 2 分形复杂网络曼一3 7 3 2 1 现实世界分形复杂网络及其形成机制3 7 3 2 2 复杂网络分形维数计算3 8 3 3 分形复杂网络模型。4 0 3 3 1 确定性分形网络模型4 0 3 3 2 非确定性分形网络模型4 l 3 4 基于受限连接和去活动机制的分形复杂网络模型。4 3 3 4 1 网络模型生长机制4 3 3 4 2 网络模型统计特征理论与实验分析4 4 3 5 基于乘性生长机制的分形复杂网络模型。4 6 3 5 1 网络模型生长机制4 6 3 5 2 网络模型统计特征理论与实验分析4 7 3 6 本章小结。5 0 第四章基于竞争与动态合作聚类机制的社团结构检测算法研究5 l 4 1 复杂网络社团结构定义及其度量。5 l 4 2 社团结构检测算法5 3 v 4 2 1 分裂类社团结构检测算法5 3 4 2 2 凝聚类社团结构检测算法5 6 4 2 3 其它社团结构检测算法。5 8 4 3 基于竞争与动态合作聚类机制的社团结构检测算法。6 l 4 3 1 竞争与动态合作数据聚类算法6 l 4 3 2 基于竞争与动态合作聚类机制的社团结构检测算法6 7 4 4 本章小结7 l 第五章基于随机行走理论的复杂网络负载传输优化策略研究7 2 5 1 复杂网络负载传输优化策略。7 2 5 1 1 网络负载传输路由优化策略7 3 5 1 2 网络负载传输结构优化策略7 8 5 2 基于随机行走理论的复杂网络负载传输优化策略一8 0 5 2 1 基于随机行走理论的优化路由策略8 0 5 2 2 基于随机行走理论的优化路由策略性能分析8 2 5 3 本章小结8 7 第六章基于社团重叠结构的复杂网络多目标攻击方法研究。 8 8 6 1 复杂网络鲁棒性分析8 8 6 1 1 复杂网络攻击方法及抗攻击性能分析8 8 6 1 2 复杂网络抗攻击结构优化一9 3 6 2 基于社团重叠结构的复杂网络多目标攻击方法。9 5 6 2 1 基于社团重叠结构的多目标攻击机制9 6 6 2 2 基于社团重叠结构的多目标攻击方法性能分析9 7 6 3 本章小结1 0 2 总结和展望 致谢 参考文献 攻读博士期间完成论文专利和科研工作 v l 1 0 3 1 0 5 1 0 6 1 1 8 第一章绪论 1 1 研究背景 第一章绪论弟一早殖t 匕 无论是从因特网、电力网、万维网以及电子邮件网等用于资源分配和信息传输的有形技术信息网 络，到科学家合作网络、世界贸易网络以及演员合作网络等由个人或社会群体依据彼此之间交互关系 所构成的无形社会网络；还是从食物链网络等描述自然界不同物种间交互关系的宏观网络，到基因调 控网络、神经网络、新陈代谢网络等描述基因、蛋白质和细胞代谢物之间复杂生化关系的微观网络， 现实世界复杂网络所蕴含的小世界效应、无标度特性、拓扑分形特征以及层次化社团结构等特性改变 了人们基于规则网络和随机网络所形成的对复杂网络的传统认识。目前，复杂网络理论已成为复杂系 统与复杂性科学研究的重要分支，其目的在于揭示蕴涵于现实实体关系中的普遍规律，并探索其在科 学技术领域中的应用。 1 技术网络 技术网络主要用于各种有形或无形资源的分配和传输，如电力网络 14 】、因特网【5 9 】、电话网络 【l o - 1 l 】、电子邮件网络【1 2 】以及交通运输网络【1 3 】等。其中，电力网络主要用于远距离三相高压交流电 的传输。2 0 0 0 年美国西部电力网络的大规模瘫痪事件使得该网络成为研究焦点，尤其是对其鲁棒性的 分析【14 】。文献【l 】指出美国西部电力网络的平均节点度为2 6 7 ，特征路径长度为1 8 7 ，聚类系数为0 0 8 。 此外，值得注意的是该网络的节点度服从指数分布，因此不具备无标度特性。 因特网是复杂网络领域研究最为广泛的技术网络【5 9 】。该网络由计算机、路由器等网络终端设备 以及光纤、电缆和无线信道等通信链路组成。通常，可以将因特网定义为两种不同粒度的网络：若采 用细粒度，节点代表计算机，边代表计算机间的通信链路；若采用粗粒度，节点代表不同的域，而边 则代表域间的链路连接。f a l o u t s o s 等对上述两种定义下的因特网均进行了研究，结果表明其节点度均 服从幂率分布，而幂率指数的变化范围在2 1 5 到2 2 之间【5 】。文献【8 】则对更大规模的域级因特网进行 了深入研究，该网络包含1 5 万个域和2 0 万条链路，结果表明其节点度的幂率指数约为2 3 。此外，文 献 9 】研究表明域级因特网具备小世界和高聚类的特性，其特征路径长度在3 7 到3 7 7 之间，而聚类系 数在0 2 2 到0 3 之间变化。 电话网络作为一种有向技术网，其节点表示不同的通话人，而边则由通话的发起者指向接收者。 文献【l o - 1l 】利用a t & t 公司一天内的长途通话记录对该网络的结构进行了分析，发现其节点的出度和 入度均服从指数为2 1 的幂率分布。 2 信息网络 信息网络也称为知识网络，其典型例子为文献引用网络【1 4 - 1