（控制理论与控制工程专业论文）复杂网络的scalefree性、scalefree现象及其控制.pdf

西北工业大学博士学住论文复杂网络的s c a l e - f e e 性、s c a l e f k e 现象及其控制 摘要 复杂网络是复杂系统的高度抽象，在现实世界中存在大量的复杂网络。自从 1 9 9 8 年、1 9 9 9 年在“n a n 鹏”和“s c i ”两个刊物上发表了关于小世界网络 和s c a l e - 丘e e 网络的两篇文章以来【s 捌，在世界范围内掀起了一股复杂网络的研究 熟潮。究其原因是因为过去关于复杂网络的一些重要结论是不妥的，而今开始了 崭新的研究 此后几年来，关于复杂网络的研究取得了一批重要成果，包括大多数实际网 络中的s c a i e _ 丘优性质的发现、复杂网络的s c a l e - 丘性质对于传播动力学和同步 动力学的深刻影响、复杂网络上的社区发现、复杂网络的演化等等。更令人感兴 趣的是，研究发现，复杂网络的许多研究成果可以直接应用于实际复杂系统，如 s l e - 丘网络中病毒传播的特殊机制，以及据此而对传统病毒防治模式的改进。 总之，复杂网络的重要性已得到了世界范围内有关领域科学家的深切关注。 然而，毕竟是刚刚起步，关于复杂网络的研究还很不充分，远没有形成属于 本方向系统的、独特的研究方法。如复杂网络的拓扑结构的刻画、复杂网络的异 质性的刻画、异质性如何影响复杂网络上的动力学、复杂网络上的s i s 模型的全 局稳定性、s i s 模型中最终感染节点的比例、复杂网络上的s 服模型中病毒爆发 的规模如何受到拓扑结构的影响、复杂网络中度分布指数的变化范围为什么一般 位于扣3 之间以及复杂网络中的控制问题等等方面的研究，是非常不够和初步 的我们正是针对上述诸问题进行了全面而深刻的研究，综合运用了严谨的数学 方法和计算机仿真手段，历经3 年时间，取得了如下主要成果： ( 1 ) 提出了复杂网络中的连接率和吸引率的新概念，并应用于i n t 咖c t 网络。 利用我们所提出的静态概率模型，从理论和实证两个方面证实了：a ) i l l t 咖e t 网 的子网的连接率服从幂律分布；b ) h t e m c t 网存在网络核心( c o r e ) ；c ) 作为一 个推论，发现度分布指数存在一个临界点为2 。 ( 2 ) 将经济学中的洛仑兹曲线与基尼系数引进到复杂网络以刻画复杂网络 的异质性，通过与复杂网络的其它参数( 度分布指数、网络结构熵、度分布熵等) 进行比较，发现基尼系数是刻画复杂网络异质性的一个合理指标 ( 3 ) 从理论上对s l e 丘网络的度分布指数进行了研究，揭示了现实世界 中大多数网络的度分布指数位于扣3 之间的理论根由，从而回答了b 蹦施i 在文 献【9 】中提出的疑问。研究了s c a l e 一丘网络中h u b 点的若干独特性质，如h u b 点的数量、h u b 点的最高度值等问题，发现了度分布指数与h u b 点之间的关系， 并首次给出了h u b 点的量化定义。 ( 4 ) 针对b b s 这样一个具体的复杂网络的s c a l e 丘优性质进行了实证研究， 摘要 发现b b s 用户网络的结构与针对某一个特定话题的b b s 用户网络的结构存在本 质的区别：前者的度分布指数小于2 ，后者的度分布指数大于2 。这说明特定话 题的b b s 用户网络仅存在极少量的h u b 节点，这一结论有利于对重点用户进行 跟踪。此外，还将复杂网络中的社区结构及其发现算法成功地应用于b b s 的热 点发现，仿真结果表明，热点发现的效率大大提高。 ( 5 ) 深入分析了s c a i e 矗网络上的s i s 模型的全局稳定性问题，发现只要 传播强度大于阈值，不管初始感染比例多么地小，网络最终感染节点的比例是一 定的。 探讨了网络最终感染节点的比例以及阈值与网络度分布指数之间的关系，发 现度分布指数越小，则阈值越小，并且网络最终感染节点的比例越大。这一结论 给s c a l e - 丘优网络上的病毒防治提供了一个新的思路。 ( 6 ) 深入分析了s c a l e _ 矗优网络上的s i r 模型的病毒爆发问题。由于s i r 模 型下，最终感染节点均消失，故研究的问题是少数感染节点是否会引起大量节点 被感染，即病毒爆发问题。我们从理论上发现，存在病毒爆发的阈值。 探讨了网络中病毒爆发的规模( 即曾经感染过病毒的节点的比例) 与度分布 指数之间的关系，发现度分布指数越小，病毒爆发规模越大。 ：( 7 ) 研究了s c a l e - 骶e 网络中的控制问题，提出了s c a l c 丘网络中反馈控 制的一般性框架。在此基础上提出了互联网拓扑结构的一个新的演化控制模型， 通过调整某些参数，该模型能够演化出多种类型的网络，并且能够再现互联网的 某些动态特征，如互联网的h u b 点的形成时间等。 “ 关键词：复杂网络；s c a l e 丘性；h u b 节点：社区发现；s c a l e 丘现象；传播 动力学；同步动力学；演化控制 西北工业大学博士学位论文复杂网络的s c a l e f h e 性，s c a l e f k e 现象及其控制 a b s t r a c t c o m p l c ) 【n e t 啪r l 【i st 量l eh i g l la b s 眦t i o no f c 锄p i 懿s y s t 锄s t h e 陀a r cp l 锄t i f i i l o fc o m p l e xn 竹w o 岱i i il 量i e a lw o r l d s i n c c1 9 9 8w h t l l ep a p e 一3 2 1a b o u t “锄a l l w o r l d ”w 笛p u b i i s h e di n “n a n 腿”柚d1 9 9 9w h e n t l l eo t i l e rp a p 一司a b o u t “s c a l e 舶e ， w 弱p u b l i s h e di n “s c i 朋：ag r e a tm 锄yp h y s i c a l i e n t i s t s 锄dm 劬e m a t i c i 觚si l a _ s h i f t c dt l l e i r 佗a r c hi i l t e 陀s t st 0c o m p l e x 玳铆o r l ( s t h e 僧a s f o rw h i c hi st l i a l s o m ec o n c l u s i o 邶a b 0 哦c 咖p l e xn c t w o r l 【so b t a i n e di nl h ep a s ta w r 硼岛e g ，t l l e d e g r e cd i s t r b u t i o no fc o i n p l 甑小船哪士岱o b e y sp o w 盯i a ww h i l ci nt h ep a s ti ti s b e i i e v e d l a t to b c y sp o i s s o nd i s 啊b u t i o n i n 代删y e 邪，t 量圮a p p e a 他dl a 唱p 删m b e ro fa c h i e v e m 锄t si nt l l ef i c l do f p l 麟n e t 、】v o r l c s ，c g ，a h n o s e v e 睁他a ln c t 、o 血i s a l c - 丘，t l l es l c 丘 p r o p e n yo fc o m p l c 】t w o r k sc 卸a 腩c ts p 哟d m gd y 船m i c s 锄ds ”c h r o n i 删 d y n a m i c s 蚰t l l cn 酾o d 【s ，v e m le 丘b c t i v ea i g o r i m m s ，a d e v i s e dt of i l l d c o m m 吼n ys t n l c m i 岱i no m n p l e xn c t 、o d bs c v e m ln e t 、o 血钾o l u t i 加a l g o r i m m s w e d i s v e r e dw h i c hc 锄r 印r o d u c es 锄ep l _ ；d p e r t i 嚣鲫c h 雒a i e - 丘e 锄d 姗a l l - w o r l do fn c t 刚m ( s 锄d o n f u r i l i 锄o r c “i sf o u n dt l l a tt l i e 他a r c hr e 鲫l t s a b o u tc 锄p l e xn c t 啪成s 伽b ca p p l i c dp r a c t i l l yt ol h cc o m p l 既s y s t e m s ，e 辱，t l i e f 融t l l a tv i m ss p 硎i l l g a l e 一丹n c t w o d 匹l l 【s 岫h o l d u s e d 昀d i t i o n a l m e m o do fv i m sp ”v e n t i o n 觚dc u r et ob ec l l a l l g e d s c i c m i g t sr o g n i z et l l a ti ti s n c c 嚣r y 彻di m p o n a n tt o s e a r c hf i l r t h e ra b o u tt l i ec o m p l c xn e t 帅r l 【s h a 眦v t h ef e s 龇h c 啡p l e xn e t o r k si ss t i l l 缸s 纽r t - u ps t a g ca r e ra 1 1 n e 印e c i a l 诧s e a r c hm e t 量l o d o l q g yi nt i l i sf i e l dh 舔n o t 如舶e dy e 锄dt t i e a f c hi s 白r f 椭b e i i l gc n o u g hi nm 柚y 嬲p t so ft i i i sf i c l d s 眦h 船l l l ec h 锄a c t e f i z a t o n0 i lt 量l c 屯o p o l o g i c a i 咖l c 嘛o fc o m p l e xi l e t w o r l 嗡m ec h 娥i c t 耐z a t 两o nt h e g e 酊 o f 踟p l e xn e t 、v o 血s h o wt h eh e t c m g e i i e 时a 腩c t sd y n a m i c so nn e 帆矾岱，t l l eg l o b a l s b b i l i l yo fs i sm o d c lo nc o m p l e xn e t w o r k s ，h o wt o p o i o g i c a ls 仃咖他世b c t st l l e f i n a lp r o 叫i o fi l i 矗蔽c dn o d 鹤i ns i sm o d e l 狮ds i rm o d e l ，、j v i l y d 镏雠 d i s m b u t i c 】【p o n e mo fm o s tn c t w o r i ( sl o c 捆b e t w 嘲2 锄d3 ，柏dt l l e 咖由m l p r o b i 锄i i lc o i l l p i e xn e t w o f l 【s t h ep r o b l 锄sa b o v eh a v eb 咖糟s e a m h e dt 量l o f o u g h l y 锄dd e e p l yi nt l l i sp a p 柚dt i i e 南l l o w i n gc 埘b i i t i o 船a 糟o b t a i n e d ： ( 1 ) t h cm wc o n c 单t so fc o 衄t i v 姆c o e 街c i 舶t 粕da 仕m c t i o nc o e 币c i e l i ta 他 p r o p o s c d ，锄da m 印p l i e dt ot l l ei n t e m e ta si e v e i 阳，o r i c a c c o r d i n gt o 廿i es t a t i c p r o b a b i l i t ym o d e lp r e s 锄t c di l lt l l i sp a p 白u o w i n gr 龉u 恼a 阼v 嘶f i e dt h 佗t i c a l l y 锄d 锄p i r i l l y ：a ) c o 衄e c t i v i t yc f f i c i 肋协o f 鲫b n e t so b e yp o w e rl a w ；b ) t 1 1 e m l a b s t r a c t e x i g t sn 咖。咄c o r em1 1 1 ei m e m e t ；c ) t h ed e g r e ed i s n 曲u t i o ne 籼e n th 髂ac r i t i c a l v a l u e 2 ( 2 ) n c 0 玳印t so fl o r c n zc u r v ea n dg i i i ic o e 币c i e n ti ne c o n o m c sa m i n t i d d u c c di l l t oc o m p l 既n e t o r k st 0c l l a r t 耐z cn 酣o r kh e t c r o g 蜘e i 吼c 鲫p 删 w i t ho t l l e rc o e 币c i 锄t ss u c ha sd e 辨ed i s 嫡b u t i e x p o n 朗t n e t w o d 【s m l c n 啪l 曲们p y 锄dd e g r e cd i s 啊b u t i o ne n n d p y ，g m ic o e 伍c i e n ti s 向u n dt ob ca 豁o n a b l c i i l d e x 血t i l ec h 盯t e 】 盟c i o no f h e t e r o g 胁e i 够 ( 3 ) t h ed e g r e ed s 砸b u t i o n 删e mi ss t i l d i c dl h e o r e t i l l y n e ”a s o nw j 哆 m o s tr lm 押 o r l ( sh a v et h e rd e f d i s m b u t i a 【p l 翎如l o c a t eh ：t 】2 锄d3i s f o u n d s o m es p e c i a l 舯叩e f t i e so fh u bn o d e si i is c a l e 舶cn e 铆o r i 路，鲫c h 勰l l i e n u m b c ro f i u bn o d e s 锄dt i 艟m a x i l i l 啪d e g r e eo fh u bn o d e s a 他p 他n t c d t h e r e i a t i b e t v v e 曲d e g r e ed i 矧b u t i o nc x p o n e n t 锄dh u bn o d e si sf 曲n d ，锄dm e q u 粕t i t ) r 如矗n j t i o no f h u bn o d e si sg i v 钮i n 出i sp a p 盱溉 ( 4 ) t h e 锄p 衔c a ls n l d yi sm a d co nb b s i ti sf o u n dm a tt l l es n l i c t l l 心o f b b s u s c r sn e t w o r ki sd i s t i i l c t 丘o mt h a to f b b su 幅n e t w o r kw i mag i v e nt o p i ci nt l l a tt l l c f o 咖盯h 船i 乜d c 咿ed i s 耐b u t i 麟p o n e ml e s st h 舭2w h i l et h el a t t 盱g r c a t c rt h 觚2 1 t m e a n s t l l a l i i i t h e b b s l i s e r sn e t o 出w i t l lag i v e n 姊i c ，n l e x i s t l y 、，c r y f e w n 啪b 盯o f h u b s n i s h e i p f h l f b r m c 眦l 【i l l g o f k e y u s 郴 n ec o 舢吼时如d i l l ga i g o r i t i ，i ma 他印p l i c ds u c c c s f i l l l yt ot l l et o p i cd e t c d i o fb b sf o r m 1 1 1 es i n l u l a t i o n s i l l ts h a 邺t l l a tt l l i sn 州m c t t l o do f t o p i cd e t e c t i o ni s m o r ee 腧t i v c ( 5 ) 1 kg i o b a ls 妇i b i l 时o fs i sm o d c li i i 蚴l e - 矗n e t w o r i 【si s 卸a l y z e d t i l o m u g h i y - i ti sp r o v e dt i i 缸i f t h ee 丘b c t i v cs p m a d i i l gm t ci s 缈a t 盯t l l 锄t l l cm s h o l d ，。 t i 锄，n om a n 盯h o ws m a i lt l l ei i i 硒a li l l 戤吐幻咀p r o p o n i o ni s t l l e 缅a lj n f c c t i p m p o r t i o ni sd e f m i 钯 w h i c hi si m l a t i v et ot l l ei l i i t i a ii i l f c c t i o np r o p o n i t h er e l a t i o n s 咖咖t 量l e6 n a li n | 融i o np r o p o r t i ，t l l et l i m s h o l dv a l u e 柚dt h e d e g r e ed i s 晡b u t i e x p o n e n ta 他p r e 湖t e d i ti sf o 蚰dt i l 矾l l i ei 豁sm ed e g 嗽 d i s m b u t i 麟p o n e n ti s ，t h ck 站t h et l l m s h o i dv a l mi s 锄dt l l eg r e 撕t l l e 筋a l i n f b c t i o np r o p o 而0 i ii s ( 6 ) n ev i n i sb a k o l i t 脚b l 锄o fs 取m o d e li n a l e - 舶en c t 、】r k si s 柚a l y z e d m o r o u g h l y ni sp r o v c dt l l e m _ e t i l l yt l l a tl l i e 她c x i s t sat h r e s h o l d 矗me 疗b c t i v e s p r e a d i n gr 蹴，a b o v cw h 曲t l l ev i m sw i l lb r e a l co i i ti nt l l en 咖。出 t h ee 】c t e n t t o w h i c h t l l e n 咖d 【i sd a i n a g e d 岫d e r v i m sb 诧a k o u t i s f o 咖d t ob e r e j 删t ot i l ed c g r e ed i s 晡b m i o ne x p o n e n t t h ei e 豁t i l ed c g r d i s 晡b u t i o ne x p o n e n t i s ，t t l em o d a l i l a g e dt h en 咖。出w i l lb e 咖d 盯v i 九j sb a k o u t 西北工业大学博士学位论文复杂网络的s c a l e - 6 性、s c a l e f 沁e 现象及其控制 ( 7 ) t h ec o n 自r o ip b l e mo fs c a l e - f n e 铆o r k si ss t u d i e d 锄dan e wm o d e io f e v o l u t i o n 觚dc o n h _ o lo f i n t 伽e ti sp f o p o s e d t h r o u g ha d j u s t m e n to f m ep a r 锄e t c 传， 曲i sm o d e l 咖e v o l v ei i i t om 锄y 韬n d so fn e h q r i ( s ，a n dc a n 代p r o d u s 伽e d y n 锄i c a lc h a r a c t e 心o f t l l ei n t e m e e g ，t l l et i i n ew h e n h u b sa r ep m d u c c d k e yw 跏s ：c 伽p l 懿n e m o r i s ；s c a l e - 肫ep r o p e r h u bn o d e s ；c o m m 帅时f i n d i i l g ； s c a l e - 丘p h 曲o m e n o n ；s p r e a d i n gd y l l 锄i c s ；s y n c h r o n i z a t i o n 蛳i c s ；e v o l u t i 册 锄dc o n 打o l v 西北工业大学业 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定。即：研究生在校攻读学位期间论文工作 的知识产权单位属于西北工业大学。学校有权保留并向国家有关部门或机构送交论文的复 印件和电子版。本人允许论文被查阅和借阅。学校可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 同时本人保证，毕业后结合学位论文研究课题再撰写的文章一律注明作者单位为西北工业 大学。 保密论文待解密后适用本声明。 学位论文作者签名；尘二垄：= d j 年；月，。日 指导教师签名： 。1 年岁 西北工业大学 学位论文原创性声明 秉承学校严谨的学风和优良的科学道德，本人郑重声明：所呈交的学位论文，是本 人在导师的指导下进行研究工作所取得的成果。尽我所知，除文中已经注明引用的内容 和致谢的地方外，本论文不包含任何其他个人或集体已经公开发表或撰写过的研究成 果，不包含本人或其他已申请学位或其他用途使用过的成果。对本文的研究做出重要贡 献的个人和集体，均己在文中以明确方式表明。 本人学位论文与资料若有不实。愿意承担一切相关的法律责任。 学位论文作者签名：i o ， 使得当z 五时，病毒能够在网络中传播并最终稳定在一定的比例上，而当五 五 时，病毒将以指数速度消亡腓l 。 复杂网络具有s c a l e - 台优特性，其中大多数节点的度值很小，少数节点( 称为 h u b 节点) 度值很大，因而绝大多数节点的度值偏离平均度值( 七) 由于复杂网 络的节点的连接数的这种异质性，r p a s t o r - s a 岫n 粥和a v e s p i 驴锄i 将网络中 的节点按度值进行分组，用岛( r ) 表示f 时刻度值为i 的节点中染病节点所占的比 例，建立了如下基于平均场的反应方程组i l8 l ： 1 2 ! 1 2 = 一j 咚( f ) + 五t 【l p i o ) 】。( ，) ( 1 3 ) “i 其中，o ( f ) 表示任一条边连接到染病节点的概率，o ( r ) 满足 h o ( f ) = ( 七) - 1 f p ( o 日( f )( 1 q f 目 通过对上述方程组进行理论分析，r p a s t o r - s a l 0 i t 鹳和a v c s p i 弘舳i 发现对 于度分布满足( 1 1 ) 的复杂网络，如果网络具有无限多个节点且度分布指数位于 扣3 之间，则病毒传播不存在阈值。亦即任何病毒都可以在这种网络中蔓延并且 染病节点始终占据一定比例。这一发现