網絡與混沌知識競賽題目

1、第六屆全國網絡科學論壇暨第二屆全國混沌應用研討會 知識趣味競賽2010年7月,網絡論壇與混沌應用知識歡迎參加知識競賽,知識游戲與競賽規(guī)則,整個游戲和競賽過程,既要熱烈踴躍參與,又要遵守秩序,服從主持人統一指揮.主持人宣布題目后才能舉手搶答,由主持人確定誰最先回答.參與者每人獲得搶答的機會最多不超過3次,如果回答不對一次,則扣除一次.每次回答正確者,獎勵一個紀念品.,第1題,考慮一個標準的國際象棋的棋盤，如圖(a

2、)所示。定義一個新的棋子，每步只能往對角線方向移動一格，如圖(b)所示。問：棋盤上是否存在一個作為起點的黑格，使得新棋子從這個黑格起步后可以走遍所有的黑格，不重復不遺漏，最后回到起點？為什么？,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,(a),(b),Answer,不能. 該問題等價于：圖(c)所示的網絡是否為一個歐拉

3、圖？即，是否存在一條路徑，經過所有的節(jié)點，不重復不遺漏，最后回到起點？此問題有解的充分必要條件是圖中所有節(jié)點的度都為偶數。但顯然有兩個節(jié)點的度是奇數，所以此圖不是歐拉圖，故此問題無解。,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,(c),另一種解法:如圖(d)所示，

4、如果該黑點角落是出發(fā)點的話，棋子不重復經過對角線上的黑格它就回不了原處；如果從外面進入這個黑點角落的話，它就不能重新走出去。因此，圖示的黑點角落是個死角（對稱的另一個黑點角落也是個死角）。原問題無解。,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,(d),Answer,第2題,考慮對 Barabasi-Albert 的基本模型作稍微改動如下：第一步：

5、從一個 m 個節(jié)點的星型網絡開始。第二步：每次引進一個新的節(jié)點。這個新節(jié)點帶進 n(≤m)條邊。每條新的邊和老的節(jié)點連接的概率為其中 ki 為節(jié)點 i 的度。問：這樣生成的網絡是什么類型的網絡？為什么？,生成的網絡是一個均勻的隨機網絡，因為大的節(jié)點具有小的概率被新節(jié)點連接，而小的節(jié)點卻有大的概率被新節(jié)點連接。這樣，慢慢地，小的節(jié)點逐漸變大，而原來大的節(jié)點逐漸相對地變小，最后所有節(jié)點都差不多大小，并且具有

6、差不多相同的概率與新節(jié)點連接。,Answer,人類行為模式的分析是近期國內外的一個研究熱點. 當前的實證研究表明: 人們處理某些事件的時候, 事件間隔時間(inter-event time, 用 表示) 并不是以往大家認為的泊松分布, 而是呈現胖尾的冪律分布, 即 . 如下圖所示的三個活動序列對應著三種不同指數 的冪律活動模式 ( 已歸一化處理).

7、 請迅速掃一眼, 然后給出其對應的指數 之間的大小關系.,第3題,第3題,,實際上這三個序列分別是用 生成的,Answer,第4題,考慮下面一個復雜網絡模型. 算法步驟如下:1. (開始)一個很大尺寸的完全連接圖.2. (過程) 對于每個可能的連接節(jié)點對, 用概率p (0<p<1) 刪除它們之間的邊. 隨時刪除可能出現的孤立

8、節(jié)點.3. (結束) 對每個可能的節(jié)點對都如上操作一次, 不重復不遺漏, 然后停止.問: 最后, 會得到一個什么類型的網絡?,最終的網絡是原來隨機網絡的補圖. 因此, 它也是一個隨機網絡.,Answer,第5題,考慮下面復雜網絡模型. 步驟如下: 1. (開始)一個很大尺寸的完全連接圖. 2. (過程)隨機地撿起一條邊: 如果刪去這條邊并不會使整個網絡變得不連通, 則刪除它; 如果刪

9、除這條邊將使網絡變得不連通, 則什么也不要做. 繼續(xù)從余下的網絡中再隨機地撿起另外一條邊, 然后重復上述操作. 3. (結束) 對每個可能的連接邊都運作一次, 不重復不遺漏, 然后停止. 問: 最后會得到一個什么類型的網絡?,最終的網絡是一個生成樹(Spanning Tree).,Answer,第6題,我國召開哪兩個系列復雜網絡會議? 它們的第一屆分別在何年何地舉行? (A) 第一屆全國復雜網絡

10、論壇(2004, 太湖) (B) 第一屆全國復雜網絡會議(2005, 武漢) (C) 國際復雜性會議(2009, 上海) (D) 國際復雜性會議(2009, 成都),(A), (B),Answer,第7題,小世界, 無標度網絡模型的提出, 引起了科學界的廣泛關注, 并由此形成”復雜網絡”這個交叉學科. 請問下列選項中, 提出小世界模型和無標度模型的分別是哪兩篇? 并請按照文章發(fā)表的先后進行排序. (A) D

11、.J. Watts, and S. H. Strogatz, Collective dynamics of “small-world” networks. Nature. (B) S. H. Strogatz, Exploring complex networks. Nature. (C) R. Albert, and A. L. Barabasi, Statistical mechanics of complex netw

12、orks. Reviews of Modern Physics. (D) A. L. Barabasi, and R. Albert, Emergence of scaling in random networks. Science. (E) M. E. J. Newman, The structure and function of complex networks. SIAM Review.,(A), (D)Watt

13、s D J, Strogatz S H. Collective dynamics of 'small-world' networks[J]. Nature, 1998, 393:440-442.BarabásiA L, Albert R, Emergence of Scaling in Random Networks[J], Science, 1999, 286(5439): 509-512.先后排序為:

14、(A_1998),(D_1999),(B_2001),(C_2002),(E_2003).,Answer,第8題,考慮一個大規(guī)模的無標度計算機網絡,其中節(jié)點是由若干個巨大的服務器和大量的小電腦PC組成.用什么最好的搜索方式可以利用最少可能的信息和最少可能的操作步驟就能從這個巨大計算機網絡中找到一個服務器?,首先從網絡中隨機的選取一個節(jié)點,然后從它的鄰居尋找最大的節(jié)點,以此類推,繼續(xù)在下一個鄰居里找到最大的節(jié)點,這樣很快就能找到一個服務器

15、.原因:因為無標度是不均勻的,第一個撿到的很可能是一個小PC.但是,也正是由于無標度特性,這個PC很可能與一個服務器直接相連,因此是該PC鄰居里的最大節(jié)點.如果不是,則再走一、二步一、二步，則應該能找到一個服務器。請看下圖：,Answer,第9題,“復雜網絡”應該說是Nature 和Science 雜志上的”?？汀? 請問, 在下面列出的復雜網絡研究方向中, 有相關文章在上述兩個雜志發(fā)表的有哪些? (a) 網絡的自導航能力(Na

16、vigability) (b) 網絡上的病毒傳播(Epidemic) (c) 社會標簽系統的模塊(Motif)分析 (d) 社會網絡演化的實證研究 (e) 無標度網絡上的擁塞(Jamming)問題,a, b, d, e,Answer,第10題,BA網絡是偏好連接且增長的網絡，每次引進一個新的節(jié)點按節(jié)點度優(yōu)先連接。現在考慮新的節(jié)點按老節(jié)點的年齡優(yōu)先連接，假設連接老節(jié)點的概率正比于 ，其中 是老節(jié)

17、點的年齡。問：當 從負值增長到正值時，這樣生成的網絡的結構有什么變化？譬如等于－10，0，10時，所生成的網絡分別是什么類型的網絡？,,,,當從負值增長到正值時，新節(jié)點按老節(jié)點的年齡優(yōu)先連接的程度減弱，負的很大時新節(jié)點傾向于連接年齡最大的節(jié)點，正的很大時新節(jié)點傾向于連接年齡最輕的節(jié)點。等于－10，0，10時，所生成的網絡基本上是星形，隨機（與年齡無關）和鏈狀的網絡。,Answer,第11題,指出下面圖示的混沌系統的名稱.,(c)

18、,(d),(b),(a),(a) Lorenz 系統 (b) Chen 系統 (c) Chua 系統 (d) Rossler 系統,Answer,第12題,什么是混沌？指出數學上對混沌有哪些定義？舉出1-2個。給出數學上判別混沌的3-5種常用指標。,(1) 混沌是一種貌似無規(guī)則的運動，是在確定性非線性系統中不需要附加任何隨機因素出現類似隨機行為。混沌系統的最大特點在于系統的非線性演化對初始條件十分敏感。(2)

19、 Devany對混沌的定義: i) 對初值敏感依賴; ii) 拓撲傳遞性; iii) 周期點集的稠密性. Li-Yorke提出的混沌定義, 周期3意味著混沌(3) 正李亞普諾夫指數、正熵、分數維數、連續(xù)功率譜、共軛于符號動力系統、Melnikov 函數具有單零點、滿足Shilnikov 不等式條件、存在Smale 馬蹄，等等,Answer,第13題,舉出中國人在混沌與應用方面有影響的幾項工作和貢獻。,李天巖提出的“周期3意味著

20、混沌” 蔡少棠提出的Chua電路 陳關榮提出的Chen系統 呂金虎提出的Lü系統 ……,Answer,第14題,有哪些混沌控制的常用方法？請列舉3-5個，并評論其優(yōu)缺點。,OGY方法，延時控制法，非線性控制法，微擾控制法，自適應控制法，狀態(tài)反饋控制法，智能控制法……,Answer,第15題,混沌同步有哪些方法？有什么應用？,驅動-響應同步法 主動-被動同步法 微擾反饋同步法 自適應同步法

21、 牽制控制法 ……可以應用于混沌編碼、信息隱藏和保密通信、多周期信號發(fā)生器、弱信號檢測、心電圖腦電圖病理分析、湍流分析等方面。,Answer,第16題,對混沌的研究引起越來越多學者們的關注. 我國學者在國內外出版了一系列有關混沌與應用的專著. 指出下列的專著的作者是誰？(任選4項回答即可) （可能有遺漏）： (A) Lorenz系統族的動力學分析、控制與同步 (B) Controlling Chaos

22、 and Bifurcation in Engineering Systems (C) Chaos-Based Digital Communication System, New York: Springer-Verlag, 2003. (D) 駕馭混沌與發(fā)展高新技術 (E) 混沌時間序列分析及其應用 (F) 混沌動力學基礎及其應用 (G) 混沌動力學初步,(A) 陳關榮，呂金虎(B) 陳關榮 (G

23、. Chen)(C) 劉重明，謝智剛 (F.C.M. Lau / C.K. Tse) (D) 方錦清(E) 呂金虎，陸君安，陳士華(F) 劉宗華(G) 陳士華，陸君安,Answer,第17題,混沌在工程技術方面有一些熟知的應用。 指出下列選項中哪些混沌應用和常規(guī)方法相比在某些方面更具有明顯的獨特優(yōu)點？ (A) 混沌保密通信系統 (B) 混沌信號雷達與混沌激光雷達汽車防撞系統 (C) 混沌交織器

24、 (D) 基于半導體激光器的混沌激光測距方法及裝置 (E) 混沌激振器 (F) 超混沌保健裝置 (G) 混沌流體攪拌器,A, B, C, D, E, F, G,Answer,第18題,在耗散系統中，隨著能量的消耗，系統相空間收縮，最終趨向一個相對穩(wěn)定的極限狀態(tài)，這些極限狀態(tài)在相空間里表現為一個低維的小“區(qū)域” ，對不穩(wěn)定的點具有“吸附”作用，故稱為吸引子?！拔铡钡倪^程意味這系統的演化，系統中各個子系統的自

25、由度越來越少，相互聯系和整體約束越來越強。問: 什么是混沌吸引子？它具有什么特性？,混沌吸引子, 是指在相空間中經過無數次的靠攏和分離，來回折疊形成的軌線的極限點集。具有分數維數，具有自相似性，具有正熵，具有對鄰近軌道的吸引性。,Answer,1963年著名氣象學家在美國《大氣科學（J Atmos Sci）》上提出了第一個混沌模型－Lorenz系統，當時還沒有“Chaos”這個詞，到了1975年美國數學家J.約克和李天巖在《美國數

26、學月刊（The American. Mathematical Monthly）》發(fā)表《Period Three Implies Chaos》首先引入了Chaos 的名稱，但是事實上前蘇聯的哪位數學家早在哪一年就建立了比“周期3蘊含混沌”更一般的定理？,第19題,Answer,,沙可夫斯基（Sarkovski A N） 早在1964年在《烏克蘭數學學報（Ukranian Math.J）》發(fā)表了沙可夫斯基定理，指出將自然數排列一個序，如果

27、m排在n前面,那么一個連續(xù)函數如果有周期m，則一定有周期n，而排在第一個正是3，所以沙可夫斯基定理包括了“周期3蘊含無窮多個周期”的結果。但是，李.約克定理的核心是 scrambled set - 它是混沌的本質（沙可夫斯基定理沒有這個內容）,第20題,舉出迄今世界上最大的3個復雜網絡及其主要特性？,互聯網，萬維網，大腦神經網絡，等等。它們都有小世界特性和無標度特性,Answer,第21題,哪國的計算機三兄弟首先怎么證明互聯網的冪律

28、分布特性？,加拿大Faloutsos三兄弟于１９９９年首先揭示了Internet拓撲的一些冪律分布，他們是通過分析１９９７年１１月至１９９８年１２月AS層面Internet的統計數據而獲得，從此開拓了Internet拓撲研究的新方向。后來他們又進一步拓廣到AS層面上Internet拓撲演化，得到四種冪律分布。,Answer,第22題,“網絡科學”的報告最早何國、何時和由何單位或誰提出來的？請說明實際背景。,最早由美國國防部所屬委員會于２

29、００５年１１月發(fā)表一個研究報告：“網絡科學”。背景是美國國防部海軍作戰(zhàn)部部長在１９９７年提出“網絡中心戰(zhàn)”，隨后美國政府幾國防部實施了一系列與網絡科學相關的研究，例如８個重電研究機會，２００４年９月美國科學院國家研究委員會所屬“陸軍科學技術專業(yè)委員會”開展了“網絡科學在未來陸軍的應用” 項目研究，在一系列研究活動的基礎上發(fā)表了“網絡科學”報告。,Answer,第23題,“網絡科學與工程”報告在何國、何時和由何單位或誰提出來的？請說明實

30、際背景。,2009年9月由美國麻省理工大學等十所著名大學聯合組成了“美國網絡科學與工程委員會”. 在專題報告“網絡科學與工程的研究議事日程”中，空前強調了美國今后加強網絡科學與工程應用研究的重大意義和研究方向，要求政府必須加大研究經費的投入力度。,Answer,第24題,迄今國際上出版了一系列“網絡科學”方面的書籍. 請將下列書名和作者對號入座. (任選3項回答即可),,(A) Linked: The New Science

31、of Networks(B) Six Degrees: The Science of a Connected Age (C)  Networks: An Introduction (D) Large　Scale　Structure　and　Dynamics　of　Complex　Networks: From Information Technology to Finance and Natural Scie

32、nce (E) Network Science –Theory and Applications,A.L. Barabasi Guido Caldarelli Ted G. LewisM. E. J. Newman D. J. Watts,Answer,,(A) Linked: The New Science of Networks(B) Six Degrees: The Science of a Con

33、nected Age (C)  Networks: An Introduction (D) Large　Scale　Structure　and　Dynamics　of　Complex　Networks: From Information Technology to Finance and Natural Science (E) Network Science –Theory and Applications

34、,A.L. Barabasi Guido Caldarelli Ted G. LewisM. E. J. Newman D. J. Watts,,,,,,第25題,網絡的同配性系數(assortativity coefficient) 反映了網絡的度相關性質, 即:與度大節(jié)點相連接的節(jié)點的度偏高還是偏低. 指出下列給出的網絡通常是同配性網絡還是異配性網絡? (A) 技術網絡 (B) 生物網絡

35、 (C) AS 層面的Internet (D) 社會網絡,Answer,(A) 異配性(B) 異配性(C) 異配性(D) 同配性,第26題,很多人可能都有這樣的經歷: 偶爾碰到一個陌生人, 同他聊了一會兒后發(fā)現你認識的某個人居然他也認識, 然后你們會一起發(fā)出”這個世界真小”的感嘆. 著名的小世界實驗(社會調查)表明:地球上任意兩個人之間的平均距離是6. 問: 該推斷最早由國際上哪位學者提出?,Answer,20世紀

36、60年代美國哈佛大學的心理學家Stanley Milgram (1933-1984),第27題,下面是與混沌相關的一些比較著名的圖形，請分別指出圖的名稱。,A,B,C,Answer,A) 蝴蝶效應B) Mandelbrot集C) Henon映射不動點,第28題,研究項目”混沌反控制與廣義Lorenz系統族的理論及其應用”, 獲得 2008年國家自然科學二等獎. 該項目的主要完成人有: 陳關榮，呂金虎，周天壽，陸

37、君安. 問: 什么叫混沌的反控制? 又問：國內外目前唯一的一本混沌反控制的書，書名是什么？作者是誰？,Answer,為了利用混沌, 通過設計控制器的方法, 將系統混沌化.陳關榮、汪小帆：動力系統的混沌化 — 理論、方法與應用,上海交通大學出版社（2006）,第29題,復雜動力網絡的同步研究具有非常廣泛的實際意義, 例如, 夏日晚間螢火蟲的同步發(fā)光, Internet上的路由器周期性地發(fā)布路由消息, 生物界中魚群鳥群的集

38、群行為. Kuramoto振子的同步, 等等. 你能說出三種或三種以上研究復雜動力網絡同步的常用方法嗎?,Answer,主穩(wěn)定函數(master stability function)方法Lyapunov 函數方法基于連接圖的穩(wěn)定性方法 (connection graph based stability method)牽制(pinning)控制法,第30題,網絡科學的歷史可以分為3個階段：初期階段(1736–1960)

39、、中期階段(1960–1998) 、現代階段(1998–present).請說說這3個階段的特點和代表性的工作。,Answer,初期階段(1736–1960)：1736, 七橋問題，Euler建立圖論 。中期階段(1960–1998) : 1960, Erdos和 Renyi建立ER隨機圖; 開始某些應用，如社會科學（六度分離）?，F代階段(1998–present)：小世界、無標度特性的發(fā)現和建模，模擬現實復雜系統。,近年我國與

40、復雜網絡、復雜系統有關的成果陸續(xù)獲得省(市)、部科技獎勵。請至少舉出獲得省(市)、部一等獎的1-3單位及其個人名字？還能夠舉出第四、第五單位和個人獲獎單位和個人名字嗎？（多一個，加1分）。,第31題,Answer,獲省部級獎勵（可能有遺漏）：1. 脈沖動力系統的穩(wěn)定與控制,教育部一等獎, 華中科技大學，關治洪,廖銳全,王燕舞,錢同惠,陳武華，2005 2. 幾類典型復雜系統的建模、分析與應用，教育部一等獎，武漢大學, 呂金虎, 陸

41、君安, 何克清, 禹思敏, 陳士華, 李兵, 吳曉群, 周進，20073. 復雜動態(tài)網絡同步與控制研究，上海市一等獎，上海交通大學，汪小帆,李翔，20084. 面向交通運輸系統的復雜網絡理論與方法, 教育部一等獎, 北京交通大學，高自友,吳建軍,李克平,黃海軍,孫會君,趙小梅,鄭建風,趙暉,李新剛，20095.復雜網絡的結構、功能與動力學研究,教育部一等獎，中國科學技術大學，汪秉宏,王文旭,周濤,謝彥波,趙明,殷傳洋，20096

42、.神經信息分析的理論、方法與應用，教育部一等獎，電子科技大學，堯德中,李春光,陳華富,徐鵬，2009,網絡同步有著廣泛的應用， 請舉幾個應用例子。,第32題,Answer,,網絡同步有著廣泛的應用，譬如:網絡同步可以解釋生物現象, 例如螢火蟲群[1], 蟋蟀群[2], 神經振子[3]和心肌細胞群[4];在認識大腦認知紊亂[5], 神經計算[6],解釋人類集體行為如掌聲響起來[7][8],還有在激光系統, 超導材料和通信系統

43、中也有重要應用。,Answer,,可以參考：[1] J. Buck, “Synchronous rhythmic flashing of fireflies II,” Q. Rev. Biol.,1988,63(3):265–289[2] T. J. Walker, “Acoustic synchrony: Two mechanisms in the snowy treecricket,” Science, 1969,166(

44、3907):891–894[3] D. Hansel and H. Sompolinsky, “Synchronization and computation ina chaotic neural network,” Phys. Rev. Lett., 1992,68:718–721[4] C. S. Peskin, Mathematical Aspects of Heart Physiology. New York: Cou

45、rant Institute of Mathematical Sciences, 1975.[5] Neural Synchrony in Brain Disorders: Relevance for Cognitive Dysfunctions and Pathophysiology .  Neuron, 2006,52 , Issue 1:155 - 168 [6] IEEE Transactions on

46、 Circuits and Systems I: Regular Papers, 2001，48（2）: 133-138[7] Neda Z,Ravasz E,Vicsek Tet al.The sound of many hands clapping.Nature,2000,403:849-850[8]李德毅,劉 坤,孫 巖,韓明暢，涌現計算: 從無序掌聲到有序掌聲的虛擬現實，中國科學 E 輯,2007,37(10):12

47、48-1257,圖的熵是圖的度序列分布隨機性的度量, 熵大則隨機性強，所以計算圖的熵可以度量圖的隨機性。(1)現有兩個圖的歸一化度序列分別為[0,1/4,1/8,1/2,1/8], [0,1/4,1/4,1/4,1/4], 問哪個圖的熵大?(2)現在有節(jié)點數為100,邊數為200的4種圖(星形, 鏈狀, 環(huán)狀, 全連接和隨機圖),它們的熵可以有一對一的4種選擇: 0，0, 0.0807，0.1414，2.9bits, 請一一對號入

48、座.,第33題,Answer,,環(huán)狀 0全連接0星形 0.0807鏈狀 0.1414 隨機圖2.9,第34題,Logistic 映射 a)分叉圖, b) Lyapunov 指數 圖請說說圖的主要含義,,Answer,,分叉區(qū)域: , Lyapunov 指數λ為負,在 處為0,表明Logistic映射從倍周期通向混沌.混沌區(qū)域: ,Lya