复杂网络重构预测和控制.ppt

基于大数据重构、预测和控制复杂系统,王文旭北京师范大学系统科学学院,大数据与复杂系统,重构、预测和控制,Outline,推断传播源头和基于压缩感知理论重构网络以及节点性质预测人的移动行为和交通拥塞复杂网络系统的控制,Theproblem:howtofindthesourceofpropagationinanetworkedsystemfromasmallnumberofobservers?Applications:locatingthesourceofdisease,rumor,riskspreadinginfinancialnetworks,etc.,从少数观察者推断传播源头,Whoisthesourceofamessage?,Socialnetwork+someobservers,Answer:,Question:,时间反演虚拟扩散法,Z.Shen,etal.underreview,Numericalresults,Z.Shen,etal.underreview,Empiricaltests,H1N1inChinain2009,Z.Shen,etal.underreview,Otherapplications,推断社交网站中信息传播源头树叶中的源头,从时间序列重构复杂网络,压缩感知简介从时间序列重构病毒传播网络和节点性质Otherapplications,Compressivesensing(压缩感知),陶哲轩，现任教于美国加州大学洛杉矶分校（UCLA）数学系的华裔数学家，澳洲惟一荣获数学最高荣誉“菲尔茨奖”的澳籍华人数学教授，继1982年的丘成桐之后获此殊荣的第二位华人。其于1996年获普林斯顿大学博士学位后任教于UCLA，24岁时便被UCLA聘为正教授。,Around2004EmmanuelCands,TerenceTaoandDavidDonoho,压缩感知理论证明对可压缩信号可以通过远低于Nyquist采样频率的方式进行数据采样，仍然能够精确地恢复出原始信号。该理论目前在图像处理、医学成像、模式识别、无线通讯、天文学等很多领域受到高度关注，并被美国科技评论评为当年十大科技进展之一。,Compressivesensingalgorithm,应用压缩传感理论通过少量测量值y恢复稀疏向量x。是在x稀疏并且满足约束条件的情况下，M可以远小于N，并且x中非零元素的个数也小于M。信号重构过程在此条件下转化为一个优化问题，求解方法有最小L1范数法和迭代阈值法等。,从二进制时间序列重构传播网络、节点性质和推断隐藏源头,SISandCPdynamics,Z.Shen,W.-X.Wang*,Y.Fan,Z.DiandY.-C.Lai,NatureCommunications,toappearin2014.,Schematicillustrationofreconstructionmethod,Z.Shen,W.-X.Wang*,Y.Fan,Z.DiandY.-C.Lai,NatureCommunications,toappearin2014.,Compressivesensing,Z.Shen,W.-X.Wang*,Y.Fan,Z.DiandY.-C.Lai,NatureCommunications,toappearin2014.,Reconstructionperformance,Inferringinhomogeneousinfectionandrecoveryrates,Locatinghiddensource,Otherapplications,重构混沌动力系统Phys.Rev.Lett.106,154101(2011).重构博弈网络Phys.Rev.X1,021021(2011).重构耦合振子网络Phys.Rev.Lett.104,058701(2010);Europhys.Lett.,94,48006(2011).推断隐藏节点Phys.Rev.E85,065201(R)(2012).预测时间序列同步Phys.Rev.E85,056220(2012).重构通讯网络和路由策略（finished）重构最后通牒博弈网络（finished）重构公共品博弈网络（ongoing）重构基因调控网络（ongoing）重构布尔动力学网络（ongoing）重构复合种群网络（病毒传播）（ongoing）重构意见动力学网络（ongoing）重构神经元网络（ongoing）,预测人的移动能力和交通拥塞,热传导模型（小勇）宏微观统一预测模型（小勇）预测交通拥塞,信息熵和可预测性,将不同路段平均速度分段，构造符号序列，计算路段的熵和可预测性,车速与可预测性,Howtocontrolacar,Complexnetwork,Controllingcomplexnetworksisultimategoal!,复杂网络的控制,25,Structuralcontrollabilityofcomplexnetworks,Minimuminputtheory:(Liuetal.Nature473,167(2011)findminimumnumberofdrivernodestosatisfyfullrankcondition,Controllability,卡尔曼满秩理论,26,Maximummatchingforstructuralcontrollabilityandobservability,可控性：计算网络最大匹配，控制未匹配节点,可观测性：反向网络的最大匹配,结构可控性适用范围：有向网络（无双相边），随机边权重（结构矩阵）,Exactcontrollabilitytheory,Theoreticalframework,任意网络：网络矩阵特征值的最大几何重数无向网络：特征值的最大代数重数（相同特征值数量）稀疏网络：网络矩阵的秩致密网络：单位阵加网络矩阵的秩,29,Identifyingdrivernodes,UniversalSymmetryinControllingComplexNetworks,C.Zhao,W.-X.Wang*,Y.-Y.Liu*andJ.-J.Slotine*,First-ordernodaldynamics,Amixtureofnodaldynamicswithdifferentorders,Thankyouforyourattention,无标度网络,复杂网络的结构、动力学和功能,网络结构,动力学,小世界网络,社团网络,权重网络,同步,博弈,交通,抗毁性,调控,功能,复杂网络三元素,正问题:(1)网络结构如何演化(2)网络结构如何影响动力学和功能反问题：从动力学反推网络结构,萤火虫发光，鼓掌,合作涌现，经济行为物种多样性,互联网，输运网络中的拥塞,金融危机，大停电,基因调控网，神经网络,控制,复杂网络研究的核心问题：三元素的关系,最终目标,SISdynamics,Evolutionarygames,Prisonersdilemma,Castingthepredictionproblemintotheframeworkofcompressivesensing,Compressivesensing,Successratesofpredictingmodelnetworks,PDGfornetworkwith100nodes,Scale-free,Small-world,Random,SGfornetworkwith100nodes,Scale-free,Small-world,Random,Predictingarealsocialnetworkfromexperiment,Relationshipnetworkof22students,Successrateofprediction,22studentsplayPDGtogetherandwritedowntheirpayoffsandstrategies,Payoffvsnumberofneighbors,Reconstructingtrafficnetworksandlocalroutingstrategy,其中,Measurabledata:incomingandoutgoingfluxofnodes,Accordingtothefluxconservation,Topologyreconstruction,Identifyingroutingparameter,Contactprocess,Inferringthesourceofep