復(fù)雜網(wǎng)絡(luò)重構(gòu)預(yù)測(cè)和控制課件

1、基于大數(shù)據(jù)重構(gòu)、預(yù)測(cè)和控制復(fù)雜系統(tǒng)王文旭北京師范大學(xué) 系統(tǒng)科學(xué)學(xué)院/wenxuw大數(shù)據(jù)與復(fù)雜系統(tǒng)重構(gòu)、預(yù)測(cè)和控制Outline 推斷傳播源頭和基于壓縮感知理論重構(gòu)網(wǎng)絡(luò)以及節(jié)點(diǎn)性質(zhì)預(yù)測(cè)人的移動(dòng)行為和交通擁塞復(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 n

2、etworks, etc.從少數(shù)觀察者推斷傳播源頭Who is the source of a message?Social network + some observersAnswer: Question : 時(shí)間反演虛擬擴(kuò)散法Z. Shen, et al. under reviewEmpirical testsH1N1 in China in 2009Z. Shen, et al. under reviewOther applications推斷社交網(wǎng)站中信息傳播源頭樹葉中的源頭Compressive sensing(壓縮感知)陶哲軒，現(xiàn)任教于美國(guó)加州大學(xué)洛杉磯分校（UCLA）數(shù)學(xué)系的華裔

3、數(shù)學(xué)家，澳洲惟一榮獲數(shù)學(xué)最高榮譽(yù)“菲爾茨獎(jiǎng)”的澳籍華人數(shù)學(xué)教授，繼1982年的丘成桐之后獲此殊榮的第二位華人。其于1996年獲普林斯頓大學(xué)博士學(xué)位后任教于UCLA，24歲時(shí)便被UCLA聘為正教授。 Around 2004 Emmanuel Cands, Terence Tao and David Donoho 壓縮感知理論證明對(duì)可壓縮信號(hào)可以通過遠(yuǎn)低于Nyquist采樣頻率的方式進(jìn)行數(shù)據(jù)采樣，仍然能夠精確地恢復(fù)出原始信號(hào)。該理論目前在圖像處理、醫(yī)學(xué)成像、模式識(shí)別、無(wú)線通訊、天文學(xué)等很多領(lǐng)域受到高度關(guān)注，并被美國(guó)科技評(píng)論評(píng)為當(dāng)年十大科技進(jìn)展之一。 Compressive sensing algo

4、rithm應(yīng)用壓縮傳感理論通過少量測(cè)量值y恢復(fù)稀疏向量x。是在x稀疏并且滿足約束條件的情況下，M可以遠(yuǎn)小于N，并且x中非零元素的個(gè)數(shù)也小于M。信號(hào)重構(gòu)過程在此條件下轉(zhuǎn)化為一個(gè)優(yōu)化問題，求解方法有最小L1范數(shù)法和迭代閾值法等。 從二進(jìn)制時(shí)間序列重構(gòu)傳播網(wǎng)絡(luò)、節(jié)點(diǎn)性質(zhì)和推斷隱藏源頭SIS and CP dynamicsZ. Shen, W.-X. Wang*, Y. Fan, Z. Di and Y.-C. Lai, Nature Communications, to appear in 2014.Compressive sensingxNeighbors of xyNmatchingFull n

5、etworkZ. Shen, W.-X. Wang*, Y. Fan, Z. Di and Y.-C. Lai, Nature Communications, to appear in 2014.Reconstruction performanceInferring inhomogeneous infection and recovery ratesLocating hidden sourceOther applications重構(gòu)混沌動(dòng)力系統(tǒng) Phys. Rev. Lett. 106, 154101 (2011).重構(gòu)博弈網(wǎng)絡(luò) Phys. Rev. X 1, 021021 (2011).重構(gòu)

6、耦合振子網(wǎng)絡(luò) Phys. Rev. Lett. 104, 058701 (2010); Europhys. Lett., 94, 48006 (2011).推斷隱藏節(jié)點(diǎn) Phys. Rev. E 85, 065201(R) (2012).預(yù)測(cè)時(shí)間序列同步 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)布爾動(dòng)力學(xué)網(wǎng)絡(luò)（ongoing）重構(gòu)復(fù)合種群網(wǎng)絡(luò)（病毒傳播） （ongoing）重構(gòu)意見動(dòng)力學(xué)網(wǎng)絡(luò)（ongoing）重構(gòu)神經(jīng)元

7、網(wǎng)絡(luò)（ongoing）預(yù)測(cè)人的移動(dòng)能力和交通擁塞熱傳導(dǎo)模型（小勇）宏微觀統(tǒng)一預(yù)測(cè)模型（小勇）預(yù)測(cè)交通擁塞信息熵和可預(yù)測(cè)性將不同路段平均速度分段，構(gòu)造符號(hào)序列，計(jì)算路段的熵和可預(yù)測(cè)性How to control a carComplex networkControlling complex networks is ultimate goal! 復(fù)雜網(wǎng)絡(luò)的控制25Structural controllability of complex networksMinimum input theory: (Liu et al. Nature 473, 167 (2011) )find minimum nu

8、mber of driver nodes to satisfy full rank conditionControllability卡爾曼滿秩理論Exact controllability theoryTheoretical framework任意網(wǎng)絡(luò)：網(wǎng)絡(luò)矩陣特征值的最大幾何重?cái)?shù)無(wú)向網(wǎng)絡(luò)：特征值的最大代數(shù)重?cái)?shù)（相同特征值數(shù)量）稀疏網(wǎng)絡(luò)：網(wǎng)絡(luò)矩陣的秩致密網(wǎng)絡(luò)：?jiǎn)挝魂嚰泳W(wǎng)絡(luò)矩陣的秩29Identifying driver nodesUniversal Symmetry in Controlling Complex NetworksC. Zhao, W.-X. Wang*, Y.-Y. Liu*

9、and J.-J. Slotine*First-order nodal dynamicsA mixture of nodal dynamics with different ordersThank you for your attention無(wú)標(biāo)度網(wǎng)絡(luò)復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)、動(dòng)力學(xué)和功能網(wǎng)絡(luò)結(jié)構(gòu)動(dòng)力學(xué)小世界網(wǎng)絡(luò)社團(tuán)網(wǎng)絡(luò)權(quán)重網(wǎng)絡(luò)同步博弈交通抗毀性調(diào)控功能復(fù)雜網(wǎng)絡(luò)三元素正問題: (1)網(wǎng)絡(luò)結(jié)構(gòu)如何演化 (2) 網(wǎng)絡(luò)結(jié)構(gòu)如何影響動(dòng)力學(xué)和功能反問題：從動(dòng)力學(xué)反推網(wǎng)絡(luò)結(jié)構(gòu)螢火蟲發(fā)光，鼓掌合作涌現(xiàn)，經(jīng)濟(jì)行為物種多樣性互聯(lián)網(wǎng)，輸運(yùn)網(wǎng)絡(luò)中的擁塞金融危機(jī)，大停電基因調(diào)控網(wǎng)，神經(jīng)網(wǎng)絡(luò)控制復(fù)雜網(wǎng)絡(luò)研究的核心問題：三元素的關(guān)

10、系最終目標(biāo)SIS dynamicsFull social network structureCompressive sensingTime series ofagents (Detectable)(1) payoffs (2) strategiesEvolutionary gamesEvolutionary gamesPrisoners dilemmaCasting the prediction problem into the framework of compressive sensingxNeighbors of xyNFull network structurematchingComp

11、ressive sensingSuccess rates of predicting model networks PDG for network with 100 nodesScale-freeSmall-worldRandom SG for network with 100 nodesScale-freeSmall-worldRandom Predicting a real social network from experimentRelationship network of 22 studentsSuccess rate of prediction22 students play P

12、DG together andwrite down their payoffs and strategiesPayoff vs number of neighborsReconstructing traffic networks and local routing strategy,其中Measurable data: incoming and out going flux of nodesAccording to the flux conservation Topology reconstructionIdentifying routing parameterContact processInferring the source of epidemic spreading (ongoi