复杂网络重构预测和控制课件

1、基于大数据重构、预测和控制复杂系统王文旭北京师范大学 系统科学学院/wenxuw大数据与复杂系统重构、预测和控制Outline 推断传播源头和基于压缩感知理论重构网络以及节点性质预测人的移动行为和交通拥塞复杂网络系统的控制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.从少数观察者推断传播源头Who is the source of a message?Social network + some observersAnswer: Question : 时间反演虚拟扩散法Z. Shen, et al. under reviewEmpirical testsH1N1 in China in 2009Z. Shen, et al. under reviewOther applications推断社交网站中信息传播源头树叶中的源头Compressive sensing(压缩感知)陶哲轩，现任教于美国加州大学洛杉矶分校（UCLA）数学系的华裔

3、数学家，澳洲惟一荣获数学最高荣誉“菲尔茨奖”的澳籍华人数学教授，继1982年的丘成桐之后获此殊荣的第二位华人。其于1996年获普林斯顿大学博士学位后任教于UCLA，24岁时便被UCLA聘为正教授。 Around 2004 Emmanuel Cands, Terence Tao and David Donoho 压缩感知理论证明对可压缩信号可以通过远低于Nyquist采样频率的方式进行数据采样，仍然能够精确地恢复出原始信号。该理论目前在图像处理、医学成像、模式识别、无线通讯、天文学等很多领域受到高度关注，并被美国科技评论评为当年十大科技进展之一。 Compressive sensing algo

4、rithm应用压缩传感理论通过少量测量值y恢复稀疏向量x。是在x稀疏并且满足约束条件的情况下，M可以远小于N，并且x中非零元素的个数也小于M。信号重构过程在此条件下转化为一个优化问题，求解方法有最小L1范数法和迭代阈值法等。 从二进制时间序列重构传播网络、节点性质和推断隐藏源头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重构混沌动力系统 Phys. Rev. Lett. 106, 154101 (2011).重构博弈网络 Phys. Rev. X 1, 021021 (2011).重构

6、耦合振子网络 Phys. Rev. Lett. 104, 058701 (2010); Europhys. Lett., 94, 48006 (2011).推断隐藏节点 Phys. Rev. E 85, 065201(R) (2012).预测时间序列同步 Phys. Rev. E 85, 056220 (2012).重构通讯网络和路由策略（finished）重构最后通牒博弈网络（finished）重构公共品博弈网络（ongoing）重构基因调控网络（ongoing）重构布尔动力学网络（ongoing）重构复合种群网络（病毒传播） （ongoing）重构意见动力学网络（ongoing）重构神经元

7、网络（ongoing）预测人的移动能力和交通拥塞热传导模型（小勇）宏微观统一预测模型（小勇）预测交通拥塞信息熵和可预测性将不同路段平均速度分段，构造符号序列，计算路段的熵和可预测性How to control a carComplex networkControlling complex networks is ultimate goal! 复杂网络的控制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任意网络：网络矩阵特征值的最大几何重数无向网络：特征值的最大代数重数（相同特征值数量）稀疏网络：网络矩阵的秩致密网络：单位阵加网络矩阵的秩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无标度网络复杂网络的结构、动力学和功能网络结构动力学小世界网络社团网络权重网络同步博弈交通抗毁性调控功能复杂网络三元素正问题: (1)网络结构如何演化 (2) 网络结构如何影响动力学和功能反问题：从动力学反推网络结构萤火虫发光，鼓掌合作涌现，经济行为物种多样性互联网，输运网络中的拥塞金融危机，大停电基因调控网，神经网络控制复杂网络研究的核心问题：三元素的关

10、系最终目标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