復雜網(wǎng)絡重構預測和控制第1頁/共48頁大數(shù)據(jù)與復雜系統(tǒng)重構、預測和控制第2頁/共48頁Outline推斷傳播源頭和基于壓縮感知理論重構網(wǎng)絡以及節(jié)點性質預測人的移動行為和交通擁塞復雜網(wǎng)絡系統(tǒng)的控制第3頁/共48頁Theproblem:howtofindthesourceofpropagationinanetworkedsystemfromasmallnumberofobservers?Applications:locatingthesourceofdisease,rumor,riskspreadinginfinancialnetworks,etc.從少數(shù)觀察者推斷傳播源頭Whoisthesourceofamessage?Socialnetwork+someobserversAnswer:Question:第4頁/共48頁時間反演虛擬擴散法Z.Shen,etal.underreview第5頁/共48頁NumericalresultsZ.Shen,etal.underreview第6頁/共48頁EmpiricaltestsH1N1inChinain2009Z.Shen,etal.underreview第7頁/共48頁Otherapplications推斷社交網(wǎng)站中信息傳播源頭樹葉中的源頭第8頁/共48頁從時間序列重構復雜網(wǎng)絡壓縮感知簡介從時間序列重構病毒傳播網(wǎng)絡和節(jié)點性質Otherapplications第9頁/共48頁Compressivesensing(壓縮感知)陶哲軒，現(xiàn)任教于美國加州大學洛杉磯分校（UCLA）數(shù)學系的華裔數(shù)學家，澳洲惟一榮獲數(shù)學最高榮譽“菲爾茨獎”的澳籍華人數(shù)學教授，繼1982年的丘成桐之后獲此殊榮的第二位華人。其于1996年獲普林斯頓大學博士學位后任教于UCLA，24歲時便被UCLA聘為正教授。

Around2004EmmanuelCandès,TerenceTaoandDavidDonoho壓縮感知理論證明對可壓縮信號可以通過遠低于Nyquist采樣頻率的方式進行數(shù)據(jù)采樣，仍然能夠精確地恢復出原始信號。該理論目前在圖像處理、醫(yī)學成像、模式識別、無線通訊、天文學等很多領域受到高度關注，并被美國科技評論評為當年十大科技進展之一。第10頁/共48頁Compressivesensingalgorithm應用壓縮傳感理論通過少量測量值y恢復稀疏向量x。是在x稀疏并且Φ滿足約束條件的情況下，M可以遠小于N，并且x中非零元素的個數(shù)也小于M。信號重構過程在此條件下轉化為一個優(yōu)化問題，求解方法有最小L1范數(shù)法和迭代閾值法等。第11頁/共48頁從二進制時間序列重構傳播網(wǎng)絡、節(jié)點性質和推斷隱藏源頭SISandCPdynamicsZ.Shen,W.-X.Wang*,Y.Fan,Z.DiandY.-C.Lai,NatureCommunications,toappearin2014.第12頁/共48頁SchematicillustrationofreconstructionmethodZ.Shen,W.-X.Wang*,Y.Fan,Z.DiandY.-C.Lai,NatureCommunications,toappearin2014.第13頁/共48頁Compressivesensingx…Neighborsofxy…N…matchingFullnetworkZ.Shen,W.-X.Wang*,Y.Fan,Z.DiandY.-C.Lai,NatureCommunications,toappearin2014.第14頁/共48頁Reconstructionperformance第15頁/共48頁第16頁/共48頁Inferringinhomogeneousinfectionandrecoveryrates第17頁/共48頁Locatinghiddensource第18頁/共48頁第19頁/共48頁Otherapplications重構混沌動力系統(tǒng)Phys.Rev.Lett.106,154101(2011).重構博弈網(wǎng)絡Phys.Rev.X1,021021(2011).重構耦合振子網(wǎng)絡Phys.Rev.Lett.104,058701(2010);

Europhys.Lett.,94,48006(2011).推斷隱藏節(jié)點Phys.Rev.E

85,065201(R)(2012).預測時間序列同步Phys.Rev.E85,056220(2012).重構通訊網(wǎng)絡和路由策略（finished）重構最后通牒博弈網(wǎng)絡（finished）重構公共品博弈網(wǎng)絡（ongoing）重構基因調(diào)控網(wǎng)絡（ongoing）重構布爾動力學網(wǎng)絡（ongoing）重構復合種群網(wǎng)絡（病毒傳播）（ongoing）重構意見動力學網(wǎng)絡（ongoing）重構神經(jīng)元網(wǎng)絡（ongoing）第20頁/共48頁預測人的移動能力和交通擁塞熱傳導模型（小勇）宏微觀統(tǒng)一預測模型（小勇）預測交通擁塞第21頁/共48頁信息熵和可預測性將不同路段平均速度分段，構造符號序列，計算路段的熵和可預測性第22頁/共48頁車速與可預測性第23頁/共48頁HowtocontrolacarComplexnetworkControllingcomplexnetworksisultimategoal!!!!!復雜網(wǎng)絡的控制第24頁/共48頁25StructuralcontrollabilityofcomplexnetworksMinimuminputtheory:(Liuetal.Nature473,167(2011))findminimumnumberofdrivernodestosatisfyfullrankconditionControllability卡爾曼滿秩理論第25頁/共48頁26Maximummatchingforstructuralcontrollabilityandobservability可控性：計算網(wǎng)絡最大匹配，控制未匹配節(jié)點可觀測性：反向網(wǎng)絡的最大匹配結構可控性適用范圍：有向網(wǎng)絡（無雙相邊），隨機邊權重（結構矩陣）第26頁/共48頁Exactcontrollabilitytheory第27頁/共48頁Theoreticalframework任意網(wǎng)絡：網(wǎng)絡矩陣特征值的最大幾何重數(shù)無向網(wǎng)絡：特征值的最大代數(shù)重數(shù)（相同特征值數(shù)量）稀疏網(wǎng)絡：網(wǎng)絡矩陣的秩致密網(wǎng)絡：單位陣加網(wǎng)絡矩陣的秩第28頁/共48頁29Identifyingdrivernodes第29頁/共48頁UniversalSymmetryinControllingComplexNetworksC.Zhao,W.-X.Wang*,Y.-Y.Liu*andJ.-J.Slotine*第30頁/共48頁First-ordernodaldynamicsAmixtureofnodaldynamicswithdifferentorders第31頁/共48頁Thankyouforyourattention第32頁/共48頁第33頁/共48頁第34頁/共48頁無標度網(wǎng)絡復雜網(wǎng)絡的結構、動力學和功能網(wǎng)絡結構動力學小世界網(wǎng)絡社團網(wǎng)絡權重網(wǎng)絡同步博弈交通抗毀性調(diào)控功能復雜網(wǎng)絡三元素正問題:(1)網(wǎng)絡結構如何演化

(2)網(wǎng)絡結構如何影響動力學和功能反問題：從動力學反推網(wǎng)絡結構螢火蟲發(fā)光，鼓掌合作涌現(xiàn)，經(jīng)濟行為物種多樣性互聯(lián)網(wǎng)，輸運網(wǎng)絡中的擁塞金融危機，大停電基因調(diào)控網(wǎng)，神經(jīng)網(wǎng)絡控制復雜網(wǎng)絡研究的核心問題：三元素的關系最終目標第35頁/共48頁SISdynamics第36頁/共48頁第37頁/共48頁第38頁/共48頁Fullsocial

networkstructureCompressivesensingTimeseriesofagents(Detectable)(1)payoffs

(2)strategiesEvolutionarygamesEvolutionarygamesPrisoner’sdilemma第39頁/共48頁Castingthepredictionproblemintotheframeworkofcompressivesensingx…Neighborsofxy…N…FullnetworkstructurematchingCompressivesensing第40頁/共48頁SuccessratesofpredictingmodelnetworksPDGfornetworkwith100nodesScale-freeSmall-worldRandomSGfornetworkwith100nodesScale-freeSmall-worldRandom第41頁/共48頁PredictingarealsocialnetworkfromexperimentRelationshipnetworkof22studentsSuccessrateofprediction22studentsplayPDGtogetherandwritedowntheirpayoffsandstrategiesPayoffvsnumberofneighbors第42頁/共48頁Reconstructingtrafficnetworksandlocalroutingstrategy,其中Measurabledata:incomingandoutgoingfluxofnodesAccordingtothefluxconservation第43頁/共48頁Topologyreconstruction第44頁/共48頁Identifyingroutingparameter第45頁/共48頁Contactprocess第46頁/共48頁Inferringthesource