復(fù)雜網(wǎng)絡(luò)重構(gòu)預(yù)測和控制.ppt

1、基于大數(shù)據(jù)重構(gòu)、預(yù)測和控制復(fù)雜系統(tǒng),王文旭 北京師范大學(xué) 系統(tǒng)科學(xué)學(xué)院 ,大數(shù)據(jù)與復(fù)雜系統(tǒng),重構(gòu)、預(yù)測和控制,Outline,推斷傳播源頭和基于壓縮感知理論重構(gòu)網(wǎng)絡(luò)以及節(jié)點性質(zhì) 預(yù)測人的移動行為和交通擁塞 復(fù)雜網(wǎng)絡(luò)系統(tǒng)的控制,The problem: how to find the source of propagation in a networked system from a small number of observers? Applications: locating the source of disease, rumor, risk spreading in financial

2、 networks, etc.,從少數(shù)觀察者推斷傳播源頭,Who is the source of a message?,Social network + some observers,Answer:,Question :,時間反演虛擬擴散法,Z. Shen, et al. under review,Numerical results,Z. Shen, et al. under review,Empirical tests,H1N1 in China in 2009,Z. Shen, et al. under review,Other applications,推斷社交網(wǎng)站中信息傳播源頭 樹葉

3、中的源頭,從時間序列重構(gòu)復(fù)雜網(wǎng)絡(luò),壓縮感知簡介 從時間序列重構(gòu)病毒傳播網(wǎng)絡(luò)和節(jié)點性質(zhì) Other applications,Compressive sensing(壓縮感知),陶哲軒，現(xiàn)任教于美國加州大學(xué)洛杉磯分校（UCLA） 數(shù)學(xué)系的華裔數(shù)學(xué)家，澳洲惟一榮獲數(shù)學(xué)最高榮譽“菲爾茨獎” 的澳籍華人數(shù)學(xué)教授，繼1982年的丘成桐之后獲此殊榮的 第二位華人。其于1996年獲普林斯頓大學(xué)博士學(xué)位后任教于 UCLA，24歲時便被UCLA聘為正教授。,Around 2004 Emmanuel Cands, Terence Tao and David Donoho,壓縮感知理論證明對可壓縮信號可以通過遠(yuǎn)低于

4、Nyquist采樣頻率的方式進(jìn)行數(shù)據(jù)采樣， 仍然能夠精確地恢復(fù)出原始信號。該理論目前在圖像處理、醫(yī)學(xué)成像、模式識別、 無線通訊、天文學(xué)等很多領(lǐng)域受到高度關(guān)注，并被美國科技評論評為當(dāng)年十大科技 進(jìn)展之一。,Compressive sensing algorithm,應(yīng)用壓縮傳感理論通過少量測量值y恢復(fù)稀疏向量x。是在x稀疏并且滿足約束條件 的情況下，M可以遠(yuǎn)小于N，并且x中非零元素的個數(shù)也小于M。信號重構(gòu)過程在此條件 下轉(zhuǎn)化為一個優(yōu)化問題，求解方法有最小L1范數(shù)法和迭代閾值法等。,從二進(jìn)制時間序列重構(gòu)傳播網(wǎng)絡(luò)、節(jié)點性質(zhì)和推斷隱藏源頭,SIS and CP dynamics,Z. Shen, W.

5、-X. Wang*, Y. Fan, Z. Di and Y.-C. Lai, Nature Communications, to appear in 2014.,Schematic illustration of reconstruction method,Z. Shen, W.-X. Wang*, Y. Fan, Z. Di and Y.-C. Lai, Nature Communications, to appear in 2014.,Compressive sensing,Z. Shen, W.-X. Wang*, Y. Fan, Z. Di and Y.-C. Lai, Nature

6、 Communications, to appear in 2014.,Reconstruction performance,Inferring inhomogeneous infection and recovery rates,Locating hidden source,Other applications,重構(gòu)混沌動力系統(tǒng) Phys. Rev. Lett. 106, 154101 (2011). 重構(gòu)博弈網(wǎng)絡(luò) Phys. Rev. X 1, 021021 (2011). 重構(gòu)耦合振子網(wǎng)絡(luò) Phys. Rev. Lett. 104, 058701 (2010); Europhys. Le

7、tt., 94, 48006 (2011). 推斷隱藏節(jié)點 Phys. Rev. E 85, 065201(R) (2012). 預(yù)測時間序列同步 Phys. Rev. E 85, 056220 (2012). 重構(gòu)通訊網(wǎng)絡(luò)和路由策略（finished） 重構(gòu)最后通牒博弈網(wǎng)絡(luò)（finished） 重構(gòu)公共品博弈網(wǎng)絡(luò)（ongoing） 重構(gòu)基因調(diào)控網(wǎng)絡(luò)（ongoing） 重構(gòu)布爾動力學(xué)網(wǎng)絡(luò)（ongoing） 重構(gòu)復(fù)合種群網(wǎng)絡(luò)（病毒傳播） （ongoing） 重構(gòu)意見動力學(xué)網(wǎng)絡(luò)（ongoing） 重構(gòu)神經(jīng)元網(wǎng)絡(luò)（ongoing）,預(yù)測人的移動能力和交通擁塞,熱傳導(dǎo)模型（小勇） 宏微觀統(tǒng)一預(yù)測模型（

8、小勇） 預(yù)測交通擁塞,信息熵和可預(yù)測性,將不同路段平均速度分段，構(gòu)造符號序列，計算路段的熵和可預(yù)測性,車速與可預(yù)測性,How to control a car,Complex network,Controlling complex networks is ultimate goal!,復(fù)雜網(wǎng)絡(luò)的控制,25,Structural controllability of complex networks,Minimum input theory: (Liu et al. Nature 473, 167 (2011) ) find minimum number of driver nodes to s

9、atisfy full rank condition,Controllability,卡爾曼滿秩理論,26,Maximum matching for structural controllability and observability,可控性：計算網(wǎng)絡(luò)最大匹配， 控制未匹配節(jié)點,可觀測性：反向網(wǎng)絡(luò)的最大匹配,結(jié)構(gòu)可控性適用范圍：有向網(wǎng)絡(luò)（無雙相邊），隨機邊權(quán)重（結(jié)構(gòu)矩陣）,Exact controllability theory,Theoretical framework,任意網(wǎng)絡(luò)：網(wǎng)絡(luò)矩陣特征值的最大幾何重數(shù) 無向網(wǎng)絡(luò)：特征值的最大代數(shù)重數(shù)（相同特征值數(shù)量） 稀疏網(wǎng)絡(luò)：網(wǎng)絡(luò)矩陣的秩 致密

10、網(wǎng)絡(luò)：單位陣加網(wǎng)絡(luò)矩陣的秩,29,Identifying driver nodes,Universal Symmetry in Controlling Complex Networks,C. Zhao, W.-X. Wang*, Y.-Y. Liu* and J.-J. Slotine*,First-order nodal dynamics,A mixture of nodal dynamics with different orders,Thank you for your attention,無標(biāo)度網(wǎng)絡(luò),復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)、動力學(xué)和功能,網(wǎng)絡(luò)結(jié)構(gòu),動力學(xué),小世界網(wǎng)絡(luò),社團(tuán)網(wǎng)絡(luò),權(quán)重網(wǎng)絡(luò),同步,

11、博弈,交通,抗毀性,調(diào)控,功能,復(fù)雜網(wǎng)絡(luò)三元素,正問題: (1)網(wǎng)絡(luò)結(jié)構(gòu)如何演化 (2) 網(wǎng)絡(luò)結(jié)構(gòu)如何影響動力學(xué)和功能 反問題：從動力學(xué)反推網(wǎng)絡(luò)結(jié)構(gòu),螢火蟲發(fā)光，鼓掌,合作涌現(xiàn)，經(jīng)濟(jì)行為 物種多樣性,互聯(lián)網(wǎng)，輸運網(wǎng)絡(luò) 中的擁塞,金融危機，大停電,基因調(diào)控網(wǎng)，神經(jīng)網(wǎng)絡(luò),控制,復(fù)雜網(wǎng)絡(luò)研究的核心問題：三元素的關(guān)系,最終目標(biāo),SIS dynamics,Evolutionary games,Prisoners dilemma,Casting the prediction problem into the framework of compressive sensing,Compressive sens

12、ing,Success rates of predicting model networks,PDG for network with 100 nodes,Scale-free,Small-world,Random,SG for network with 100 nodes,Scale-free,Small-world,Random,Predicting a real social network from experiment,Relationship network of 22 students,Success rate of prediction,22 students play PDG

13、 together and write down their payoffs and strategies,Payoff vs number of neighbors,Reconstructing traffic networks and local routing strategy,其中,Measurable data: incoming and out going flux of nodes,According to the flux conservation,Topology reconstruction,Identifying routing parameter,Contact process,Inferring the source of epidemic sprea