复杂网络重构预测和控制.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聘为正教授 Around2004EmmanuelCand s 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 Prisoner sdilemma 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