复杂网络分为随机网络,小世界网络和自相似网络。

这页就讲讲包含随机网络的最近发展很火热的复杂网络可在百度搜索一下,看最被关注的是哪些方面,当然,它的主要发展始于/源于我们图论的随机图.

最近出现中国博士论文引起美国恐慌的大量报道。这源于大连理工大学博士生王建伟和他的导师发表在《安全科学》(Safety Science)的论文Cascade-based attack vulnerability on the US power grid,它应译为基于相继故障攻击美国电网的脆性而非美国影响最大、最盛名的《纽约时报》20日转引美国众议院所说的主题是如何攻击美国小型电网

他们的工作属于复杂网络学科复杂网络科学是21世纪初发展起来的新兴学科。建立在大数据的观测基础上,生活中的各种大型系统在宏观层面往往呈现出网络状的结构。网络科学探索这些系统的静态结构、动态特征,并利用这些结果揭示原系统的工作机制、优化原系统的功能、预测原系统的趋势,建立起了一套普适性方法。

关于复杂网络,和我们海南琼州大学同担任这里13个杂志编委的Erdös20世纪60年代建立的随机图理论被公认是开创复杂网络的系统性研究,使随机图理论在将近过去40年的时间里一直是研究复杂网络结构的基本理论”,“在20世纪即将结束之际,对复杂网络的科学探索发生了重要的转变,复杂网络理论研究不再局限于数学领域,在从物理学到生物学的众多学科中掀起了研究复杂网络的热潮”…。下面1998WattsStrogatz的以及1999BarabásiAlbert“两篇开创性的文章可以看作是复杂网络研究的新纪元开始的标志”。这里也见复杂网络为什么那么火--特别是看到中国首富马云领导着一个“复杂网络”为主的队伍”,其受重视也如复杂网络女学者Albert1997年开始发表论文以来的百篇论文中十篇是《科学》和《自然》-还不包含子刊。其中上面1998Watts和他的导师Strogatz的这论文引入一个有趣的小世界网络模型(也常称为WS模型它基于六度分割理论”--因人们普遍猜测平均Erdös£6(如我的Erdös数都是2)--所以小世界网络模型是否也启发于著名的Erdös数?他们说是源于邮件和演员Bacon,当然也应不假)。1999年又引入下面的无标度网络模型,这两种网络模型的研究队伍如今可谓浩浩荡荡受到自然科学与工程各个领域研究者的广泛关注。前面已说这学科是基于对图论大家Erdös的随机网络的更现实化研究(上面WS论文的第5段说到Erdös关系网的下一句就说到电网”-The graph of the power grid is relevant to the efficiency and robustness of power networks”。其robustness就是系统的健壮性,它是在异常和危险情况下系统生存的关键。不过他们说的Erdös关系网Erdös理论无甚大关系,但Erdös网能成为例子也说明Erdös的工作处处具有强大的理论张力,他们的参考文献16就是给我来信的剑桥大学Bollobás院士的《随机图》专著-它是汇聚和发展Erdös的伟大思想创见的学说-也是复杂网络学科大厦的根基。上面王建伟等研究的这类网络主要是考察如何承受足够意外故障的问题,而其面对协同式攻击却很脆弱。如美国电网的大崩溃事故,我们可能很难感受到纽约人在黑暗的惊栗,如此虽政客说话只考虑政治效应而总凌驾于科学之上但也并非无中生有。王建伟的论文的视野和立意是很不错的, 也打下很好基础,只要王同学戒去年轻人的浮夸或可有好发现。不论如何博士用如此标题仍有沽名钓誉之嫌,王建伟的负荷分配原则也仍有局限:当节点i崩溃后,它的邻居节点j收到的额外负荷DLji=Li[(kjåmÎGjkm)a/ånÎGi(knåfÎGnkf)a],因此人们仍在寻找更有效、更实际的负荷分配原则(原则有很多也各有优劣;而象我的几十个有些已有百年历史的珠峰一般只有唯一的最终结果则人人都只能竟奔一个目标则每一问题都要锲而不舍十八般武艺都比别人精通才能优先到达顶峰至少是有所突破,而哈密顿图之险峻就象历经华山一条路,因此,更多的是要经过几年几十年以致一代代数学家的攀登推动和甘当人梯的铺垫.

关于复杂网络(2001年我一有电脑就把它列在这里最后段,它包括电网、Internet网络、交通网络等至少28类复杂网络,我其后事多就至今没有修改过一个字又没有心情深入研究。复杂网络的一个中心问题是研究网络对随机故障和故意攻击的耐性robustness,这是因复杂网络都有其脆性,正如上面所看到的因此复杂网络遭遇随机故障和蓄意攻击时可能引发相继故障,即大量动态变化的负载引发的随机故障蓄意攻击等触发条件在一定因素下可使子系统崩溃,通过子系统的关联引发其它子系统的崩溃,从而发生连锁反应,引发相继故障,最终使整个系统的脆性被激发而崩溃。这是引起美国众议院的非专业人士恐慌之因吧。

就如上面1998Duncan Watts和他的导师Steven Strogatz创立的WS模型构造算法中的随机化过程有可能破坏网络的连通性,如此 Mark NewmanDuncan James Watts1999年通过用随机化加边取代构造中的随机化重连得到NW模型。

除了小世界网络,最近掀起热潮的另一类网络是1999BarabásiAlbert提出无标度网络模型(也常称为BA模型,他们认为以前的许多网络模型都没有考虑到实际网络的如下两个重要特征:(1)增长(growth)特性:即网络的规模是不断扩大的,例如每个月都会有大量的新的科研文章发表,而WWW上则每天都有大量新的网页产生;(2)优先连接(perferential attachment)特性:即新的节点更倾向于与那些具有较高连接度的“大”节点相连接。这重现象也称为“富这更富(rich get richer)”或“马太效应(Matthew effect)”。例如,新发表的文章更倾向于引用一些已被广泛引用的重要文献,新的个人主页上的超文本连接更可能指向新浪,雅虎等著名的站点。

基于这两个重要特征,BA无标度模型构造算法:(1增长:从一个具有m0个节点的网络开始,每次引入一个新的节点,并且连到m个已存在的节点上,这里m£m0;(2)优先连接:一个新节点与一个已经存在的节点i相连接的概率Õi与节点i的度ki、节点jkj之间满足如下关系:Õi=ki/åjkj

BA无标度网络的平均路径长度LµlogN/loglogN  这表明该网络也具有小世界特性。

BA无标度网络的聚类系数C=[m2(m+1)2/(4m-4)][ln((m+1)/m)-1/(m+1)][ln(t)2/t]  这表明与ER随机图类似,当网络规模充分大时BA无标度网络不具有明显的聚类特征。

BA无标度网络的度分布主方程法)(速率方程法定义p(k,ti,t) 为在ti时刻加入的节点it时刻的度恰好是k的概率。在BA模型中,当一个新节点加入到系统中来时,节点i的度增加1的概率为mÕi=k/2t,否则该节点的度保持不变,由此得到如下递推关系式:p(k,ti,t+1)=(k-1)/(2t)[p(k-1,ti,t)]+[1-k/(2t)]p(k,ti,t);而网络的度分布为:p(k)=limt®¥åti p(k,ti,t)/t,它满足如下递推方程:p(k)=p(k-1) (k-1)/(k+2) (k³m+1)p(k)=2/(m+2) (k=m)

BA无标度网络的鲁棒性和脆弱性:我曾评论其论文的Bollobás院士和他的学生Riordan运用随机图理论对无标度网络的鲁棒性和脆弱性作了数学分析

BA无标度网络的适应度模型:(适应度模型是Bianconi Barabási2001年的论文中提出的

无标度网络的传播临界值:抛开网络均匀性假设,来考虑典型的非均匀网络无标度网络-传播临界值。定义相对密度rk(t)是一个度为k的节点被感染的概率。它的平均场方程为:rk(t)/t=-rk(t)+lk[1-rk(t)]Q(rk(t)) ………1), 这里同样考虑单位恢复速率并且忽略高阶项(rk(t)<<1)Q(rk(t)表示任意一条给定的边与一个被感染节点相连的概率。记rk(t)的稳态值为rk。令式(1)右端为零,可以求得:rk=klQ(l)/(1+ klQ(l))………2,这表明节点的度越高,被感染的概率也越高。在计算Q时必须考虑到网络的非均匀性,对于无关联的无标度网络,即不同节点的度之间是不相关的无标度网络,由于任意一条给定的边指向度为s的节点的概率可以表示为sP(s)/<k>,可以求得:Q(l)= åkkP(k)rk/<k>………3)。

BA无标度网络模型的平均度和度分布分别是:<k>=òm¥kP(k)dk=2m,  P(k)=2m2k-3。此时,由式(3)可得:Q(l)= mlQ(l)òm¥(1/(k+kklQ(l))dk = mlQ(l)ln(1+1/(mlQ(l))),从而 Q(l)=(e-1/ml/(ml))(1-e-1/ml)-1………4),计算阶参数如下:r=åkP(k)rk=2m2lQ(l)òm¥(1/(kk+kkklQ(l))dk=2m2lQ(l)[1/m+lQ(l)lm(1+1/(mlQ(l)))………5)。把式(4)代入式(5),可得:rµ 2e-1/ml,此式右端为非负数,且右端为零当且仅当l=0,这意味着BA无标度网络对应的传播临界值lC=0

以前我们海南深山区的琼州大学在这里见曾突破世界大师Ivan Gutman院士等进展缓慢的多圈图的p-电子能量关于此类图的能量已被广泛应用于复杂网络、生物信息等学科领域中)但因我们回来海南山区后因条件极端落后而搁下2000年某些专家又再引入一个度量高分子长链的折叠度的图的Estrada指数。自从Estrada指数提出以后,它也被广泛地应用于分子化学、量子化学、信息科学、复杂网络等GEstrada指标EE(G)=åi=1neli,它为复杂网络中心度的研究提供了一种有效的方法.

刚知道Ivan Gutman等在最近的2007年左右从另一度量复杂网络的参量-图的Estrada指数得到下面几个结果长为n的圈的Estrada指标EE(Cn)≈(ò02p e2cosxdx=)n/2p≈2.27958580n,

长为n的路的Estrada指标EE(Pn)≈(ò0p e2cosxdx=)(n+1)/p -( e2+e-2)/2≈2.27958580n - 1.48261039

m的点垂直各和Pn的一点连接而得的Pn,mEstrada指标EE(Pn,m)≈(m-1)n+2(n+1)(ò0p [ecosxcoshÖ(m+cos2x)]dx/p

当然,这方面还有许多图类也已解决,在这里只给出Cn(n是阶时就是哈密顿圈)Pn(n是阶时就是哈密顿路)等的情况

2000Réka Albert Albert-László Barabási又对BA模型拓展通过增加节点边和边的配置网络得以增长和扩展而得的模型常称为AB模型

国外还有许多权威先驱也在复杂网络的一些方面做出很大贡献,如Albert-László Barabasi的导师Harry Eugene Stanley院士也做了非常多复杂网络论文,还有Jon Michael KleinbergJürgen KurthAlessandro VespignaniTamás VicsekHawoong JeongLuís A. Nunes Amaral,斯坦福年轻的Jure Leskove基于图论,Hans Jürgen HerrmannBrian Uzzi RomualdoPastor-SatorrasYamir MorenoSanto FortunatoMarc BarthelemyJosé F.F. MendesSerguei DorogovtsevAlex ArenasJanos KerteszMartin NowakJames H. FowlerZoltán ToroczkaiCristopher Moore也应参考这里中间的几个随机图大家

这里有复杂网络为什么那么火的一个解说。再看一例:你看中国首富马云出任院长阿里巴巴商学院资师力量列在前头有相片的8个人--其中吕琳媛、张子柯和他们的导师张翼成都是做复杂网络--不用看进他们的各人网页-直接看研究方向的第一个全都就是复杂网络(现在这阿里巴巴商学院的院长仍是马云、几个副总裁任副院长如此强大的巨头就领导着这8个复杂网络为主的专家为主的研究队伍,可见,“复杂网络否?它的特聘教授和客座教授都是从外面聘的人,就不用看了)

在我们中国工业与应用数学学会复杂网络与复杂系统专业委员会可见更多信息(在海南省工业与应用数学学会网可进入),在此也附我以前写的一个复杂网络网页,因没心情时间,以前只则重某些点。科学网有一个复杂网络专题科学网有许多复杂网络做得很好的博主,如汪秉宏方锦清陆君安周涛张海峰章忠志(林苑是其学生)等。其它国内著名权威还有吕金虎李翔CN华人领袖陈关荣,从事复杂网络和电力电子谢智刚(IEEECSM主编)。附校长张杰院士兼院长的上海交通大学致远学院常务院长汪小帆编写的《网络科学导论》做为该校研究生公共课每周一次共12次以及相关课件信息(汪是复杂网络与复杂系统专业委员会主任并获得复杂网项目获国家自然科学二等奖,该院聘许多计算机诺贝尔奖获得者如John Hopcroft为教授,可见课程有国际参考价值);周涛教授说最全面的复杂网络著作是牛津学士博士出身的Mark Newman的名著《网络科学引论(此书网页)。(一些很有世界影响的专题教材有: 《自然》《科学》发表很多论文的以色列物理学会主席Shlomo Havlin的《复杂网络健壮性》,哈佛大学Martin Nowak教授的《进化动力学》还搞出进化图论--这里最后他在《自然》《科学》2刊就发表了60多篇论文或见他个人网

关于复杂网络的定义看维基网的第一句就是a complex network is a graph (network) with non-trivial topological features—features that do not occur in simple networks such as lattices or random graphs but often occur in graphs modelling of real systems,也就是一复杂网络就是一个图

关于复杂网络,可看CSIAM复杂网络专委会第一副主任方锦清教授(主任是美国休斯敦大学教授陈关荣)重点推荐的复杂网络教材:即7080年代已是两个IEEE杂志主编的Lewis的《网络科学:原理与应用》等,国内的汪小帆等的书也不错。概况可看方锦清教授的“复杂网络研究”,他在网络科学三大里程碑中就重点说到琼州大学居世界领先的哈密顿图

不仅看基于这两种模型的复杂网络,还要看密切相关的学科。如可看也是做为研究复杂系统模型的一种数学工具的“Petri网”,正如和加州大学金兰教授合作指导清华大学计算机系第一位博士生何敬民的卢开澄教授的《图论及其应用》教材第2版序说“图论没有理由将Petri网拒之门外”,如此他在这书中列入Petri网,即图论是各类复杂网络、复杂系统模型的本源,更因“ A Petri Net is a directed bipartite graph二分图”(这里的Bipartite graph二分图网页哈密顿图专家写的二分图书籍等)。要知道仅Petri网就已发展成为中国计算机学会佩特里(Petri)网专业学会。我也有幸得到中国Petri网专业委员会原主任北京大学计算机系袁崇义教授我国第一本Petri网著作《Petri网》等出版后90年代就赠送给我-并在封2写上赵克文老师指正-(其袁教授在我国的先驱性如Petri网奠基人Petri在为北大袁崇义教授1989年出版的我国第一本Petri网著作Petri一书写的序“网论现状”说“最重要的进展属于下列诸位:Holt预见并建议了‘完美网’的着色定理袁崇义教授”)-但很惭愧也很遗憾因这里条件差使我没有足够多条件、时间和心血深入研究和无法做出好成果-负了袁教授-本来只有多掌握密切相关的、交叉的学科,才会给你更多启发(国际数学联盟主席嘉当就说“对数学的所有重要分支进行综合研究,看来时机已经成熟”):三元组N=(S, T, ; F)称为Petri网的充分必要条件是:1. S∩T=Æ, 2. ST≠Æ, 3. FÍS´TT´S, 4. dom(F)cod(F)=ST。其中dom(F)={x| $y (x,y)ÎF}, cod(F)={y |$x (x,y)ÎF}, 分别为F的定义域和值域。ST分别称为N的库所(place)和变迁集(transition)F为流关系(flow relation)也称弧集合。PF常分别用圆形、矩形表示   与复杂网络有关的还有,2):还有这里这里的传感器网络”“无线网络计算机互连网络”“复杂社会系统”“社会网络计算”等.    2002~2014年复杂网络项目中标情况也看出我国某些研究情况.

袁崇义教授简介:1941年生,山东人。1964年南京大学数学系毕业,入中科院数学所为研究生,1968年毕业留所。1975年改行学习计算机软件。1977年至1979年加拿大多伦多大学,滑铁卢大学进修软件开发。1984年至1990年期间4次共3+年访问西德GMD(国家研究中心)Petri教授的研究所,1992年底调入北京大学计算机系,教授,后任博导。主要研究方向:Petri网、工作流、软件语义正确性验证。2005年退休。在北大教授两门研究生软件理论课:Petri网和并行计算(形式语义)有4Petri网专著。基于Petri网,首创程序语义正确性验证理论,以期替代统治软件工程已久的软件测试步骤刚看到最近教育部软件工程教学指导委员会主任孙家广院士主编的《软件工程--理论方法与实践一书只参考4个中文文献-其中就有袁崇义教授Petri一书,可见袁教授的学科的作用特别是在软件工程领域的作用)

关于图论及其哈密顿图在Petri的作用,也如其后也担任Petri网专业委员会主任的同济大学副校长/东华大学校长蒋昌俊候选院士在科研工作早期就做许多哈密顿图论文,阶互素图张量积的Hamiltonian分解问题,张量乘积图的Hamiltonian分解(),图的强笛积哈密顿分解问题,张量乘积图的Hamiltonian分解Ⅱ,

图论有如此作用是因“网络是从同类问题中抽象出来的用数学中的图论来表达并研究的一种模型”,也就是正如百度百科的定义或说解释:网络是由节点和连线()构成,表示诸多对象及其相互联系。在数学上,网络是一种图”,简言之,网络就是图论中研究的图,但图论中的图不只代表网络还代表很多含义。因此,图论还有很多方面的应用关于图论,再多说一、二:图论在工程等中正显示其越来越强大的生命力,这方面的著作见这里倒数第3几个美国大学校长写的图论在工程中的应用著作。同时,基于我国4公共权威期刊《中国科学》《中国工程科学》《科学通报》《应用科学学报》中的应用工程类杂志《中国工程科学》和《应用科学学报》发表论文迄今为止海南一共仅有5(但就有其中4是琼州大学赵克文的,另1是这里第8黄宗道院士的。在中国期刊网输入这2个期刊名再输入“海南”可知如此琼州大学赵克文被欧洲著名SCI杂志《工业与应用工程杂志》聘为编委哈佛大学Austin教授等共38人任编委)赵克文担任编委的SCI杂志《应用数学与信息科学》也属应用工程学科(赵克文列在第11个编委,前面10编委都是资深教授如我前一位Wolf院士是全美洲最古老大学也是世界前60大学的资深教授),从而使琼州大学成为海南历史上第一个SCI杂志编委单位

此外,当今学科趋势正如计算机诺贝尔奖获得者姚期智院士说“计算机科学每一次新发展都需要用数学…”,如此我们海南省也创办国际信息科学与计算机数学杂志》(出版我们杂志的国外出版社见这里中间段顺注知全世界六个专家在这出版社的创办杂志并任主编),我们的杂志也有很多世界名家投稿英国计算机动画领域唯一英国国家中心主席张建军和Hongchuan YU教授2人合作的论文既直接寄来琼州大学、同时也寄去这国外著名大学出版我们琼州大学的上面杂志的出版社的(即这里倒数第2段的Azad院士的大学,但我是主编,按章程Azad院士总要转来给我)( 顺注:张建军教授欢迎我国计算机, 数学, 物理等专业学生去英国这个世界中心读博士。该中心参与《星球大战,金刚,珍珠港,哈利波特》和《怪物史莱克等一系列席卷全球的影片制作, 多次获得国际奖项)

  Network scienceNetwork Science

现在是地震、暴雨、台风等灾害频发,如此对下面Azad院士转给我的中国灾害防御协会风险学会理事长Zhou Zongfang-周宗放教授的2封信很感兴趣(第2封是周教授一年后的关于他的第2篇投稿的信。我校数学系曾福庚老师正在该校读博士生)

Dear Prof. Azad:
    Attached is our paper "
Research on Optimal Variable Weighted Matrix in the MPDC". Would you please consider this paper for publication at your journal "International Journal of Information Science and Computer Mathematics (IJISCM)". If you need any additional information, please let me know.

Thank you very much in advance for your kind support.
Best regards
Zhou Zongfang
 

Professor, School of management and economics,

University of Electronic Science & Technology of China,

Sichuan, P.R.China, 610054 

 

Dear Prof. Arun Azad: 

Attached is our paper  " Study on Evaluating the EIT Project Establishment Based on Membership Cloud Gravity Center" co-authored by Yu Jike and Li Yongkui. Would you please consider this paper for publication at your journal  " International Journal of Information Science and Computer Mathematics ". 
Thank you very much in advance for your kind support.
Best regards

Zhou Zongfang

Professor, School of management and economics,

University of Electronic Science & Technology of China, P.R.China, 610054 

(上面2次给琼州大学杂志投稿的周宗放理事长吴宗之院长等是风险学会理事长。从他们的论文的引用论文知道周理事长已在权威SCI论文发表很多这课题前期工作,也如周理事长的论文涉及哈佛大学经济系主任James Stock教授的工作如此我邀请Stock教授等多个这方面专家评审他的这篇做出重要阶段工作的论文,得到James Stock教授的很好建议(这里见James Stock教授的主页。(这里附是一个成绩非常突出的北京大学才子的很值得总结的经验)。

赵克文的主页