（轮机工程专业论文）复杂网络的仿真研究及在轮机系统中的应用.pdf

中文摘要 摘要 复杂网络经历了由七桥问题引发的图论、e r 随机图模型、小世界网络和无 标度网络的发展历程，应用十分广泛，对人类生活影响巨大。然而在分析与应用 中尚存在着动态化不强、数据不可靠引起的误判等问题，因此对它的正确分析和 应用极为重要。其发展方向主要有随机性和确定性混合、大型化和超网络。由于 计算机网络系统的应用，复杂网络己渗透到很多工程领域，包括轮机系统。 首先介绍了复杂网络的定义，阐述了复杂网络的研究内容和复杂性，解释了 复杂网络中的三个基本概念：特征路径长度、聚类系数和度分布，并给出了它们 的计算流程。然后针对当前研究最多的最近邻耦合网络、随机图模型、w s 小世 界网络、n w 小世界网络和b a 无标度网络，给出它们的生成方法、统计性质和 仿真流程。用m a t l a b 进行仿真，得到相应的网络图和特征分布图及特征路径 长度、聚类系数和平均度三个网络特征参数值。并以一个在3 0 0 0 k w 以上非自 动化海船轮机部在最低船员配置下的节点数为7 、边数为l8 的从属关系网络为 例做出计算，结论表明在严格执行从属关系下网络不易发生聚类，但处于聚类边 缘。神经网络故障诊断法的优点是数据结果可靠、误判率低，缺点是识别维数受 到限制。利用复杂网络中的社团结构搜索，将与主机故障相关的热力参数进行分 类，选取每类中有代表性的参数用于故障诊断，弥补了神经网络诊断法的不足， 分析了降维前后故障诊断的准确率。最后介绍了网络分析软件p a j e k 的可视化、 抽象化和高速计算的三个强大功能和基本操作方法，如求度、求节点间距离、求 k 近邻、求聚类系数和度分布等。充分利用p a j e k 对轮机系统的1 3 个子系统组成 的网络进行分析，给出定义的宏和运行宏后得到的分析报告，表明主机易发生故 障和发电机组故障更易引起其它故障的特点，便于深入细致研究轮机系统。 结尾给出复杂网络在轮机系统中的部分故障诊断应用和子系统组成的网络分 析的相关结论，有待于进一步的研究的方面有：在网络分析应用上，还需要更多 的数据分析各个子系统，使之形成超网络；对轮机系统故障实行在线诊断； m a t l a b 和p a j e k 的数据互导。 关键词：复杂网络；故障诊断；p a j e k ；仿真； 英文摘要 a b s t r a c t e x p e r i e n c e dd e v e l o p m e n tp r o c e s s e so fg r a p ht h e o r y c a u s e db yt h es e v e n b r i d g e sp r o b l e m s ，e rr a n d o mg r a p hm o d e l ，s m a l l - w o r l dn e t w o r ka n ds c a l e f r e e n e t w o r k , c o m p l e xn e t w o r ki sw i d e l yu s e da n dh a sat r e m e n d o u si m p a c to nh u m a n l i f e h o w e v e r ，i nt h ea n a l y s i sa n da p p l i c a t i o n ，s o m ec o m p l e xn e t w o r k sa r en o t d y n a m i ce n o u g h ，a n du n r e l i a b l ed a t aw i l lc a u s em i s j u d g m e n ls oi ti se x t r e m e l y i m p o r t a n tt oc o r r e c t l ya n a l y z ea n da p p l y t h em a i nd i r e c t i o n s a r er a n d o ma n d d e t e r m i n i s t i cm i x e d ，l a r g es c a l ea n ds u p e rn e t w o r k s i n c et h ea p p l i c a t i o no f c o m p u t e rn e t w o r ks y s t e m s ，c o m p l e xn e t w o r k sh a v ep e n e t r a t e di n t om a n yf i e l d so f e n g i n e e r i n g ，i n c l u d i n gm a r i n es y s t e m t h i sp a p e ri n t r o d u c e st h ed e f i n i t i o no fc o m p l e xn e t w o r k s ，d e s c r i b e sac o m p l e x n e t w o r ko fc o n t e n ta n dc o m p l e x i t y , e x p l a i n st h ec o m p l e xn e t w o r ko ft h r e eb a s i c c o n c e p t ：c h a r a c t e r i s t i cp a t hl e n g t h ，c l u s t e r i n gc o e f f i c i e n ta n dd e g r e ed i s t r i b u t i o n ， a n dg i v e st h e i rc a l c u l a t i o np r o c e s s t h eg e n e r a t i o nm a h o d ，s t a t i s t i c a lp r o p e r t i e sa n d s i m u l a t i o np r o c e s so ft h em o s tr e s e a r c h e dn e t w o r k s t h en e a r e s tn e i g h b o rc o u p l e d n e t w o r k , r a n d o mg r a p hm o d e l ，w ss m a l l - w o r l dn e t w o r k ，n ws m a l l w o r l dn e t w o r k a n db as c a l e - f r e en e t w o r ka r e g i v e n u s i n g m a t l a bs i m u l a t i o n ，t h e c o r r e s p o n d i n gn e t w o r km a p s ，c h a r a c t e r i s t i c sd i s t r i b u t i o nd i a g r a m sa n dt h et h r e e n e t w o r kc h a r a c t e r i s t i c sp a r a m e t e rv a l u e s c h a r a c t e r i s t i cp a t hl e n g t h ，c l u s t e r i n g c o e f f i c i e n ta n da v e r a g ed e g r e e a r eg o t a n dc h a r a c t e r i s t i c sp a r a m e t e rv a l u e so f a f f i l i a t i o nn e t w o r ki nam o r et h a n3 0 0 0 k wn o n - a u t o m a t e ds h i p se n g i n ed e p a r t m e n t w i t ht h em i n i m u mc r e wc o n f i g u r a t i o nw h i c hh a s7v e r t i c e sa n d18a r c sa r e c a l c u l a t e da sa ne x a m p l e c o n c l u s i o n ss h o wt h a tt h en e t w o r ku n d e rs t r i c t s u b o r d i n a t i o nl e s sp r o n et oc l u s t e r i n g ，b u tc l u s t e r i n gc o e f f i c i e n th a sa l r e a d yb e e na t t h ee d g e n e u r a ln e t w o r kf a u l td i a g n o s i sm e t h o dh a st h ea d v a n t a g e so fr e l i a b l ed a t a a n dl o wf a l s ep o s i t i v e s ，a n dt h ed i s a d v a n t a g eo fl i m i t e di d e n t i f i e dd i m e n s i o n u s i n g c o m m u n i t ys t r u c t u r es e a r c ho fc o m p l e xn e t w o r k ，t h et h e r m a lp a r a m e t e r sr e l a t e d w i t ht h em a i ne n g i n ef a u l ta r ec l a s s i f i e d s e l e c tar e p r e s e n t a t i v ep a r a m e t e rf o re a c h c l a s s i f i c a t i o nt ob eu s e di nf a u l td i a g n o s i s s on e u r a ln e t w o r kd i a g n o s t i c sa r e 英文摘要 o p t i m i z e d c o m p a r et h er e s u l to ff a u l td i a g n o s i sb e f o r ed i m e n s i o nr e d u c t i o nw i t h a f t e rd i m e n s i o nr e d u c t i o n t h et h r e ep o w e r f u lf u n c t i o n so fn e t w o r ka n a l y s i ss o f t w a r e p a j e k - v i s u a l i z a t i o n ，a b s t r a c t i o n ，a n dh i g h s p e e dc o m p u t i n g - a n db a s i co p e r a t i o n m e t h o d s ，s u c ha st h ec a l c u l a t i o no fd e g r e e s ，t h ed i s t a n c eb e t w e e nv e r t i c e s ，t h e k - n e a r e s tn e i g h b o r , t h ec l u s t e r i n gc o e f f i c i e n ta n dd e g r e ed i s t r i b u t i o na r ei n t r o d u c e d u s i n gp a j e k , an e t w o r ko f13s u b - s y s t e m si nt h em a r i n es y s t e mi sa n a l y z e d t h e d e f i n e dm a c r oa n dt h ea n a l y s i sr e p o r ta f t e rr u n n i n gt h em a c r oa r eg i v e n ，w h i c h i n d i c a t e st h a tt h ee n g i n ep r o n e st om o r ef a u l t sa n dg e n e r a t o rf a u l t sp r o n e st oc a u s e o t h e rs y s t e mf a u l t s t h i sm a k e si t e a s yt o f u r t h e rd e t a i l e dr e s e a r c hi nm a r i n e s y s t e m s o w i n g t ot i m ec o n s t r a i n t s ，o n l ya p p l i c a t i o n so fac o m p l e xn e t w o r ki nt h ef a u l t d i a g n o s i so ft h em a r i n es y s t e ma n dn e t w o r ka n a l y s i so fs u b s y s t e m si nt h em a r i n e s y s t e ma r ec o m p l e t e d t h ef o l l o w i n gt h r e ea s p e c t sn e e df u r t h e rs t u d y ：i na p p l i c a t i o n o fn e t w o r ka n a l y s i s ，m o r ed a t ai sn e e d e dt o a n a l y s i ss u b s y s t e m ss ot h a t a s u p e r - n e t w o r ki sf o r m e d ；o n - l i n ef a u l td i a g n o s i so ft h em a r i n es y s t e m ；m a t l a b a n dp a j e kd a t at r a n s c o n d u c t a n c e k e yw o r d s ：c o m p l e xn e t w o r k ；f a u l td i a g n o s i s ；p a j i e k ；s i m u l a t i o n 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成博硕士学位论文= = 复盘圆终鲍鱼墓堑塞丛在整扭丕统圭数廛圈：。除 论文中已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已 在文中以明确方式标明。本论文中不包含任何未加明确注明的其它个人或集体已 经公开发表或未公开发表的成果。本声明的法律责任由本人承担。 学位论文作者签名： 学位论文版权使用授权书 本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学 位论文的规定，即：大连海事大学有权保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。同意将本学位论文收录到中国优秀博硕士 学位论文全文数据库( 中国学术期刊( 光盘版) 电子杂志社) 、中国学位论文 全文数据库( 中国科学技术信息研究所) 等数据库中，并以电子出版物形式出 版发行和提供信息服务。保密的论文在解密后遵守此规定。 本学位论文属于：保密口在年解密后适用本授权书。 不保密西( 请在以上方框内打“，) 论文作者签名：纵锸导师繇舯旆 日期：幻0 年6 月w 曰 复杂网络的仿真研究及在轮机系统中的应用 第1 章绪论 ll 课题来源及意义 当今的社会生括中，人类的社会括动逐渐增加，空间范围愈来愈大，交往形 式也愈来愈繁多。细观各个混沌状态和复杂系统，微观上的人体细胞内分子运动， 宏观上的世界各国的相互联系，纵观至历史的更替变换，每一个体都是某个或某 些网络的一部分。马丁路德金说过：我们不可避免的身处于相互联系的网络 世界中无论那些网络体系是直接影响我们，还是间接影响我们i ”。 图1l - 16 分g 给出了几种常见的网络图( 依次属于交通运输网络、人工神 经网络、电力网络、认知网络、计算机网络和食物链网络) 。 图l l 上海市地铁两络图 f i g 1 1s h a n g h a i m e t y o n e t w o r k m a p 形形色色的网络的出现，描述了生活中的大量的系统，为交往和沟通提供了 方便。网络已经越来越深地融 了社会生括的各个方面。交通工程师们利用网络 知识来分析交通网络模型，实现交通的智能化；金融学家利用金融网络模型来预 第1 章绪论 测风险，力求做到超前控制；传染病学家利用传染病扩散网络模型来分析疾病传 染的渠道，希求最有效的控制传染病的蔓延；国家安全人员利用恐怖分子关系网 统计分析恐怖活动的地理分布和时间分布，预测即将发生的恐怖活动f 2 】o 耽 模糊规则 ( 彳)( 口)( f ) ( 刃) ( f )( ，) ( ) 图i 2 模糊神经网络结构图 f i g 1 2f u z z yn e u r a ln e t w o r ks t r u c t u r e 黄渡e - - f 图1 32 0 0 0 年华东5 0 0 k v 电力网 f i g 1 3e a s t5 0 0 k vp o w e rg d di n2 0 0 0 复杂弼l 苦的仿真研究瑟在轮机系统中的应用 图i4 语义记忆的网络模型 f i g1 4 n e t w o r k m o d e lo f a n t i e m e m o r y 图】5 南阳理工学院网络拓扑结构图 f i g1 5 n e t w o r k t o p o l o g y d i a g r a mo f n a n y a n g t e c l m o l o g yc o l l e g e i 、。斌自f、“，麓 帆；霎屹哪 蝴舯舱蒺蹶 ：厶丧、 ，q ， 牝， 辫均联鏖 第1 章绪论 圈l6 食物同 f i g 】6 f o o dn e t w o r k 反过来可以说，网络技术的不成熟对社会生活的影响甚大。因为对某些关 键节点投有正确地加以控制而未能有效阻止传染病的流行，社会上不断散布的流 言蜚语以讹传讹，网络病毒的肆意传播造成的服务器服务中断、电力系统的局部 故障所引起的电力网覆盖地区大面积停电，通信系统的中断引起的相应交通运输 系统瘫痪，这些都是网络带来的危害p 。所以，更加深入地认识自然网络和更加 高效地干预人工网络，就成为科学技术所要解决的一个重要问题。 然而，复杂系统既非常复杂又难咀控制。事实表明对于很多复杂系统，哪 怕一点轻微的改变，也会对整个系统产生极其深远的影响。复杂系统通常非常难 以控制，且从控制论角度讲最优解根难求取，也就是说，调节到一个最佳工作 状态是非常困难的。2 0 0 6 年1 1 月4 日的一场远至葡萄牙的区域性断电，究其原 因竟是德国北部一条电力电缆的断开造成的经济损失巨大” 。通过诸多案例， 人们逐斯认识到，复杂系统产生故障的原因过多，根本无法对所有可能都做好防 范，只能尽力采用相关知识预测和分析，以尽力减小损失。 复杂网络的仿真研究及在轮机系统中的应用 1 2 复杂网络的研究现状 1 2 1 复杂网络国外的研究现状 1 理论方面 随着网络规模的日益扩大，网络连接也日益复杂，人们希望对网络能够用抽 象的逻辑与数学工具来加以描述和分析，希望科学家们将网络分析推广到各个学 科和领域并加以应用。 在欧洲，欧盟委员会投入了两百亿欧元的资金给复杂系统领域。在足够的资 金支持下，复杂网络尽管进一步的具体发展方向未知，却始终站在复杂网络研究 领域的前沿【5 】。 而在美国，十年以前，网络研究大部分集中在纯理论和学术性程度较高的领 域。而9 1l 事件发生以后，政府把大量的资金用于军方寻找恐怖分子的一些实际 应用上，很多研究网络模型的公司争夺军事基金，以前学术性的网络科学研究者 也转而投入到反恐基金的竞争活动中，这把其余的理论研究者们推向了两难的境 地更为困难的基金前景和高度的研究价值【6 】。 2 实际应用方面 环境与能源：环境问题已经成为了全球性的问题。人类对环境的有意无意的 破坏和自然因素引起的气候变化，不可避免地影响着生态系统。b a s c o m p t e 正在 研究如何将其中的关系用网络知识量化并做出进一步的环境状况预测m 。 微观生物学：细胞内部结构的是如何相互联系的，对外界环境的变化和外部 刺激如何形成反射，以及此过程的模拟和对未来某个时间段细胞动作的预测，这 些都是分子生物学家们研究的内容。通过网络系统分析，信号传导和代谢过程也 被模拟出来并加以研究。 反恐活动：这是复杂网络的应用中颇惹争议的一项。根据已发生的恐怖活动 的时间和地点分布，以每次恐怖活动为一个节点，时间和地点作为属性和位置， 来预测下一个节点出现的时间和地点。也有一部分网络科学工作者根据涉及到恐 怖组织的人的社会关系，来建立恐怖分子社会关系网络，通过分析度分布和介数 等参数，查找恐怖组织的核心人物和恐怖活动的主要组织者。美国学者j o h n b o h a n n o n 和c a r l e y 等科学家正在研究这一课题。 计算机：由1 9 6 9 年1 2 月美国西南部四所大学的四台主机的连接到今天数以亿 第1 章绪论 计的庞大网络，互联网的发展速度真是令人叹为观止。由于起初的不确定性连接 和后来的飞速发展，使得网络结构异常复杂，这无论是现在还是将来，都会对网 络的研究造成了不小的困难。因此，一些计算机科学家为了更好地分析网络的性 质和实际应用，正在绘制互联网和万维网的结构图。 流行病：2 0 0 3 年的s a r s 和2 0 0 9 年的甲型流感都给世界带来了恐慌，严重影 响了全球一体化经济的发展，对病毒传播网络的控制则显得尤为重要。印第安纳 大学的a l e s s a n d r ov e s p i g n a n i 结合部分城市交通地图和全球的航线网络，制作了 甲型流感传播的具体模型，该模型能够对该疾病的感染率给出预测，也能够对疾 病蔓延的地理途径给出预测。美国国立卫生研究院十分重视对于流行病的研究， 提供了基金支持，鼓励网络分析学者们投入到某些实际问题例如甲型流感的流行 问题的研究中来。其他国家对此也加以重视，人们都已逐渐认识到在流行病防治 上，需要让网络科学发挥其更大的作用。 1 2 2 复杂网络国内的研究现状 现在，无论是在国际上还是国内，对于复杂网络的研究方兴未艾。我国的相 关研究要从2 0 0 1 年春，我国学者进军复杂网络分析领域，研究小世界和无标度 网络开始。香港城市大学的陈关荣老师是第一个把复杂网络研究带入我国的人。 2 0 0 2 年至今，众多研究人员陆续对复杂网络的研究产生了兴趣，多个学科都已 进行理论研究与应用。 1 学术会议 自2 0 0 4 年4 月无锡举行的首届全国复杂动态网络学术论坛以来，2 0 0 5 年1 0 月和2 0 0 6 年11 月，分别在武汉大学和华中师范大学举行了全国复杂网络学术会 议。2 0 0 7 年1 2 月、2 0 0 8 年l o 月和2 0 0 9 年1 0 月，第三届、第四届和第五届全 国复杂网络学术会议分别在上海理工大学、北京大学和青岛大学举行。会议邀请 国内外知名专家，介绍国内外研究动态：复杂网络模型和新特性的发现与理论新 进展等。很多高校师生、科研院所和企业的科研人员都积极参加了这些活动。2 0 1 0 年秋，第六届全国复杂网络学术会议将在苏州大学召开。 2 专著 上海系统科学研究院郭雷院长与许晓鸣院长组织国内有关专家编写了复杂 网络一书。该书对当前复杂网络的大部分研究分支如加权网络、动态网络、网 6 复杂网络的仿真研究及在轮机系统中的应用 络传播、网络同步和网络控制都加以介绍，并在应用篇讨论了广义合作网络、生 物网络的稳定性、城市交通网络的复杂性、通讯网络、在制造和经济领域中复杂 网络的应用和网络模拟方法。上海交通大学汪小帆教授主攻复杂网络与混沌控制 研究领域，取得一系列创新性成果，目前主要研究方向为复杂动态网络分析与控 制。他著有复杂网络理论及其应用一书，此书于2 0 0 6 年出版。大连海事大 学王志平教授1 9 9 7 年以来，主要从事网络拓扑与可靠性的研究，这期间解决了 国际著名刊物上的一个猜想，并对网络优化问题进行了深入研究：2 0 0 4 年以来 主要从事超网络的理论及其在管理科学与工程中的应用研究；2 0 0 8 年3 月，超 网络理论及其应用一书完稿，这是我国在超网络方面的第一本专著。 3 其它文献 “一院两校”网络科学联合项目组主要研究复杂网络的理论模型和相关领域 的应用。根据初步统计，至u 2 0 0 8 年，该项目组的成员已经有l o o 余篇论文，分别 发表在2 0 余种国内外著名学术期刊与杂志上，如：p h y sl e t t a ，p h yr e ve ，p h y s a ，e u r p h y sl e t t ，i n tjm o d e rp h y sb ，a d v a n c ei nc o m p l e xs y s t e m s ，c h i np h y sl e t t ， c h i ns c ig ，c h i np h y s ，c o m m nt h e o rp h y s ，i e e et r a n s a c t i o n so ns y s t e m s ，物理 学报，物理学进展，复杂系统与复杂性科学，自然科学进展，计算机工程与应用， 科技导报，通信学报，系统工程学报等等。这些科研成果不但反映了该项目取得 的进展，也代表了国内研究人员的科研水平。中国原子能科学研究院的方锦清老 师和上海交通大学汪小帆教授等对这些成果进行了总结【8 1 。 1 3 本文所作的工作 在已有的复杂网络理论基础上，研究复杂网络的性质和应用，总结复杂网络 的定义、性质和仿真流程，将复杂网络理论应用于轮机系统中。用m a t l a b 编 写程序，对当前几大网络作出评价和分析，并将复杂网络的社团搜索与轮机系统 的降维故障诊断结合起来。利用网络分析软件p a j e k ，定义了宏，对轮机系统中 的一部分网络进行了分析。 具体工作总结如下： 1 介绍了复杂网络的定义，阐述了复杂网络的研究内容和复杂性，解释了 复杂网络中的三个基本概念：特征路径长度、聚类系数和度分布，给出了它们的 计算流程。 第1 章绪论 2 针对当前研究最多的最近邻耦合网络、随机图模型、w s 小世界网络、 n w 小世界网络和b a 无标度网络，给出了它们的生成方法、统计性质和仿真流 程并进行了仿真，得到了相应的网络图和特征分布图及三个网络特征参数。 3 利用复杂网络中的社团结构搜索，将与主机故障相关的热力参数进行分 类，选取每类中有代表性的参数用于故障诊断，弥补了神经网络诊断法的不足， 分析了降维前后故障诊断的准确率。 4 介绍了网络分析软件p a j e k 的功能和基本操作方法，利用p a j e k 对轮机部 分系统进行分析，给出定义的宏，便于对轮机系统进一步深入细致的研究。 8 复杂网络的仿真研究及在轮机系统中的应用 2 1 复杂网络的发展 2 1 1 复杂网络的发展史 1 哥尼斯堡七桥问题 第2 章复杂网络概述 南区 图2 1 七桥问题 f i g 2 1s e v e nb r i d g e sp r o b l e m 几何图形出现的年代很早，早在欧几里得时代就已经成为数学研究的一个重 要对象。而由几何图形描述的网络作为一门科学，也就是“网络科学”，开始于1 8 世纪3 0 年代时著名数学家欧拉在解决七桥问题时开创图论这门学科。 七桥问题是数学史上著名古典数学问题之一。问题是这样的：普雷格尔 河流经普鲁士的柯尼斯堡镇，奈发夫岛位于河中，共有7 座桥横跨河上，把 全镇连接起来。本镇的居民非常热衷于解决这样一个难题：如何找到一条路 线，通过它可不重复地走遍七座桥。这就是哥尼斯堡七桥问题。当欧拉在1 7 3 6 年访问这个小镇时，他发现当地人正积极从事这项极有趣的消遣活动：在每 星期六散步，一次走过所有七座桥，其中每座桥只能经过次，而且起点与 终点必须是同一地点。但是无人成功【9 1 。 同年，欧拉交给彼得健科学院篇名为哥尼斯堡七座桥的论文。此 报告阐述了他的对该问题的具体解决方法。他把岛和陆地用点表示，连接岛 和陆地的桥用两点之问的连线表示，这样将将河流、小岛和桥的结构简化成 一个网络，七桥问题随之转化成判断一个连通的网络能否被一笔画出的问题。 欧拉推断出此种走法是不可能的。他的依据是：除了起点以外，每次当一个 9 第2 章复杂网络概述 人由一座桥进入一块陆地时，他也是由另一座桥离开此陆地。所以每行经一 点，要有两条边，从起点离开的线与最后回到始点的线亦计算两条边，因此 每一个陆地与其他陆地连接的桥数必为偶数。七桥所成之图形中，没有一点 含有偶数条边，所以上述的任务无法完成【1 0 】。 欧拉对七桥问题的研究不仅限于此。他在圆满地回答了哥尼斯堡七桥问 题之后，进一步证明了有关一笔画的三条结论，也就是举世闻名的欧拉定理。 现在，为了纪念这个伟大的数学家，人们把连通图中从某结点出发一笔画成 所经过的路线称为欧拉路，把一笔画成回到出发点的欧拉路称为欧拉回路， 而具有欧拉回路的图称做欧拉图。欧拉对七桥问题的巧解，不仅开创了数学理 论中对图论这一分支的研究先河，也为建立后来的一个数学新分支一一拓扑学 奠定了基础。 2 随机网络 复杂网络研究的第二个重要发展始于2 0 世纪中叶，s o l o m o n o f f 和r a p o p o r t 以及p 射e r d 6 s 和a l f r 6 dr 6 n y i 对随机图论的引入和研究。这给复杂网络的研究者 提供了一个重要的工具，同时也引起了人们对于互联网系统的随机性连接的广泛 思掣1 1 1 。 在图论中具有代表性的随机图模型有g ( n ，p ) 模型和g ( n ，m ) 模型等。g ( n ，p ) 模型首先是由e d g a rg i l b e r t1 9 5 9 年在一篇研究连通性临界值的论文中引入的。 g ( n ，m ) 模型则是在1 9 5 9 年由e r d 6 s 和r 6 n y i 引入。它们用概率方法来证明图的性 质，或者说来证明一个推断：对几乎全部的图来说一个性质均成立。 随着研究的不断深入，网络分析者们发现，g ( n ，p ) 模型的边独立和边相似两 个主要的假设可能在实际情况建模中不现实。特别地，一个e r 图可能不会像许多 真实的网络一样无尺度。这要求以此为基础的新模型修正这个限制。 作为实际中广泛应用的复杂网络的模型，尽管随机图理论还存在着明显的缺 陷，然而在i - 个世纪的后几十年中，此理论仍然是研究复杂网络拓扑结构的基本 理论。该理论中的一些基本思想，直到今天在| ) 【) 9 络性质的研究中依然很重要【1 2 1 。 针对理论与实际有很大不符之处这一事实，部分网络专家从多个角度对随机 图的各个方面进行扩展与延伸，以使其能够更加接近真实的网络。 i o 复杂网络的仿真研究及在轮机系统中的应用 世纪之交，n e w m a n 等人将随机图中的度数分布加以扩展，使之具有任意给定 度分布，称为“广义随机图，进一步深入了复杂网络的研究。 3 小世界网络和无标度网络 近年来在统计物理中出现的两种网络，h o d , 世界网络和无标度网络，是目前 的研究热点之一。 1 9 9 8 年，w a a s 和s t r o 啦引入了一种现在被称为“w s d , 世界模型”的复杂网络 模型，这是一种由完全规则网络到完全随机图的过渡模型。该种模型的构造策略 是采用随机化加边，这种性质介于随机性和确定性之间的网络连接策略对网络的 连通性有可能是一种破坏。稍后，n e w m a n 和w a a s 建立了一种被称为“n w d 世界 模型”的网络模型，这是另一种研究较多的小世界模型。该模型在w s d , 世界模型 的基础上加以改进，将w s d , 世界模型构造过程中的“随机化重连刀替换成为“随 机化加边一而得【1 3 】。 长时间以来人们一直认为实际的网络是随机的，连接度分布规律是泊松分布。 然而对万维网结构的调查结果表明，万维网的连接度并不服从泊松分布，而是服 从幂律分布。这说明，现实中的复杂网络也有着非随机分布的特性。此后，人们 陆续发现一些实际生活中的其它网络连接度也服从幂律分布，例如新陈代谢网络 等。因为其节点的连接度并无明显的特征长度，“无标度网络的概念也就由此而 来。为了对幂律分布的产生机理进行合理的解释，b a r a b i s i 和a l b e r t 于19 9 9 年提出 了一个无标度网络模型，即为今天网络科学界广泛研究的b a 无标度网络。无标度 网络充分考虑了实际网络的增长特性和优先连接的特性，它的产生对模拟实际网 络有着重要的意义【1 4 】。 2 1 2 复杂网络分析与应用中存在的问题 由于当前的网络大部分是随时间改变的，处于不断进化中，对此图论这一专 门分析静态结构的理论显得无能为力。可以肯定地说，图论作为网络分析的基础 数学理论，在日益动态化的网络进程中，已经不够灵活。一点微小的连接的变动 即可以完全地改变整个图，而对于图论，这一切都要重新生成。面对网络规模的 增长，图论无法提供合适的降噪过程，这使有效信息量逐渐减少，严重地影响了 网络分析结果【1 5 1 。 第2 章复杂网络概述 对于社会网络分析，已经有人证明了当前的网络理论对一些社会网络并不适 用。这也不仅仅是理论上的问题。社会学中数据的采集过程融合了网络研究者的 主观判断，这直接影响到分析结果。当前争议颇大的反恐怖主义网络分析中也存 在这样的问题。主观因素的干扰，客观上无法找到衰减函数进行有效降噪，得到 的结果便只有很低的可信度【16 1 。 2 1 3 复杂网络发展趋势 1 研究将随机性与确定性有机结合 现实中的复杂网络，节点和边缘规模巨大，种类繁多，属性各异，有着错综 复杂的结构和动态行为，对它们的模拟和研究难度很大。完全随机的网络并不能 用来模拟大部分的实际网络，这个已经从统计学的角度得到了证明，小世界网络 和无标度网络也就应运而生。而过于确定的网络也不利于预测网络的下一步行为。 比如，由于互联网的发展没有确定性的统一规划，给互联网网络图的绘制工作带 来了很大的困难。因此，对随机性和确定性的比率的研究，成为了一个发展趋势。 2 由小型网络到大型网络 生活中存在着很多超大规模的网络系统，在计算机处理技术不发达的情 况下，这些网络性质的研究受到了限制。随着计算机处理功能的强大和完善， 大型网络的研究工作如火如荼的开展起来。处理大型网络的网络分析软件 p a j e k 的出现，使得几百万个节点的复杂性较高的网络也能更加方便地得到分 析和处理。 3 超网络 有的网络系统超越了一般的网络。这些系统可能是网络对网络的包含和 嵌套，分层分级，层内和层间、或者级内和级间连接结构复杂，有着多维的 流量、多属性或多准则，拥堵问题时而发生，全局和个体有时会存在优化矛 盾问题。这些网络可以用超图来描述，称为超网络。对超网络的研究，不但 有利于实际网络的分析模拟，也从另一个方面探究着系统的复杂性。因此， 超网络理论的完善问题必会渐渐融入复杂网络分析领域的主流【1 7 1 。 2 2 复杂网络的定义 由相互作用的节点组成的系统即为网络。网络中必不可少的成分是节点与边， 1 2 复杂网络的仿真研究及在轮机系统中的应用 节点代表了系统中的元素，边即节点间的连线，代表了元素之间的关系。尽管概 念很简短，网络却能呈现出高度的复杂性，这样的网络即为复杂网络。只要描述 的足够严谨，就能够模拟各种实际的复杂系统框架、拓扑结构和动力学性质等。 在网络分析中，常用名词如下【1 8 】： 网络静态几何量：这是指网络的统计性质； 网络演化性质：这是对实际网络演化统计规律的分析结果。例如，w w w 网 络中网页数量的时间演化规律的研究也就是对该网络演化性质的研究； 网络演化机制模型：这是对具有特定几何性质的网络形成机制的研究，比如， 研究无标度网络的形成机制即是研究网络演化机制模型； 网络上的动力学性质：描述建立在网络上的其他模型( 如传染病、渗流模型 等) 的动态过程； 网络的结构稳定性：这是指网络的各种攻击方式与响应，例如，选择性隔离 对于传染病流行的控制作用的研究也就是对该网络结构稳定性的研究。 2 3 复杂网络的研究内容 各种实际网络在结构上会有着或多或少的差异。然而，尽管表面上互不相同， 它们的一些性质和处理方法却有很多相似之处。复杂网络理论即旨在寻找它们的 共性和处理这些复杂网络的普遍适用的技术手段。随着网络处理技术的发展，所 研究的网络规模也发生了变化，以前至多分析几百个节点的网络，如今对数以百 万计的节点的网络的研究也很常见，网络分析方法也随之改变，所以说，复杂网 络理论的研究内容是与时俱进的，就目前来看，复杂网络理论主要着眼于以下四 项工作【1 9 】： 发现：探究描述复杂网络的结构统计性质，和将所发现的统计性质进行量化 分析的最优策略。 建模：生成恰当的网络模型，用来使网络系统的统计性质的含义和生成机制 被更好地理解。 分析：对单个节点的性质和网络系统本身的结构特性进行分析，并对网络的 行为加以预测。 控制：在充分理解了网络特性的情况下，提出行之有效的方法改善其性能， 第2 章复杂网络概述 并建立新的经优化的网络。 统计物理与图论都是分析网络性质的重要理论。 在图论中，网络的概念是指由一个点集矿和一个边集e 所组成的一个图，且 边集中的每条边都有点集中的一对点与之对应。记顶点数为n = s i z e ( v ) ，边数为 l = s i z e ( e ) 。如果在网络中，对于任意节点“、，( 材，1 ，) 与化甜) 都对应着同一条 边，那么该网络就被称为无向网络，否则，这个网络就是有向网络；如果任意边 的属性皆为1 ，那么该网络即为无权网络，不满足该条件的则为加权网络。 在统计物理学中，网络是一个系统，它包含着大量个体，个体与个体之间相 互作用。网络也是一种图，该图是可能是某种现象、也可能是某类关系的抽象化， 将个体抽象为顶点，个体之间的相互作用抽象为边。 统计物理学能够将复杂网络的宏观性质和微观性质联系起来，而对复杂网络 中节点与边的度和权重等微观性质与复杂网络几何性质、效率及稳定性等宏观性 质之间的具体关系的研究恰好为复杂网络所研究的核心内容。这使得复杂网络的 研究与统计物理学的发展紧密相连。 统计物理学之所以在复杂网络分析中广为应用，它在模型演化机制与结构稳 定性等诸多方面的大量研究经验也是一个重要原因。而图论之所以在复杂网络分 析中应用甚广，是因为它提供的网络静态几何量也是复杂网络研究工作的一个基 础。 统计物理学与图论在网络分析上的相异之处在于，前者在技术手段上偏向于 抽象化，从实际网络现象中提取一般的网络几何量，而且力求利用提取出的几何 量来对现实中大量其它网络的分析工作作出指导，进一步地，将各个具体现象如 何发展成为复杂网络模型的手法加以探讨，最后再对网络本身的形成机制进行分 析；而后者侧重于对静态网络进行分析，并提供出相应的网络静态几何量。 2 4 复杂网络的复杂性 复杂网络，顾名思义，有着高度的复杂性。以互联网为例，一般体现在如下 几个方面 2 0 】： 1 结构错综复杂：节点众多，网络规模庞大，在结构上有多种不同特征。 例如互联网连接的数不胜数的主机。 1 4 复杂网络的仿真研究及在轮机系统中的应用 2 连接属性多样：节点之间的连接不同，有的体现在权重上，有的体现 在方向上。在互联网中，体现在网速和网络权限的设置上。 3 网络产生进化：节点或边的产生与消失使网络构造不断发生变化，呈 现出进化特性。相应地在互联网中体现在各主机被使用和废弃，上网与断网。 4 节点多样性：在复杂网络中，节点具有多样性，能够代表实际网络中 任何对象。 5 随时间变化( 即动力学复杂性) ：节点的属性( 大小、形状、颜色、 状态等) 随时间可能会发生变化。互联网中体现在联网时间与方式的不同。 6 综合多重复杂性：即以上五点的存在和相互影响，这样更加不利于对 网络行为的预测。 2 5 复杂网络中的基本概念 为了量化复杂网络的统计物理学特性，网络分析者定义了很多概念，提出了 一些方法。在这些概念中，有三个最为常见，即平均路径长度( 特征路径长度) 、 聚类系数与度分布【2 1 1 。 2 5 1 特征路径长度 首先定义网络图中两节点间距离d 玎： 吒= m i n s i z e ( ih 肼( 2 1 ) 即图中连接节点f 和j 的路径中边数的最小值。 网络的直径d 则定义为 d = m 举办( 2 2 ) 即网络图中任意两个节点之间的距离的最大值。 在整个网络中，任意两节点之间距离的平均值即网络的特征路径长度，定 义式为 = _ l 略 ( 2 3 ) 二( n + 1 ) ，7 、 z 式中，为节点总数。 第2 章复杂网络概述 考虑i = 时，即4 ，= 0 ，故式( 2 3 ) 中求和元素个数取去( + 1 ) 。如果不考虑 i = j 的情况，( 2 3 ) 式应为 2 五n ( 州- 1 州吃 ( 2 4 ) 在实际情况下，如果网络规模足够大，即