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

1、基于大数据重构、预测和控制复杂系统,王文旭 北京师范大学 系统科学学院 ,大数据与复杂系统,重构、预测和控制,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

2、 networks, etc.,从少数观察者推断传播源头,Who is the source of a message?,Social network + some observers,Answer:,Question :,时间反演虚拟扩散法,Z. Shen, et al. under review,Numerical results,Z. Shen, et al. under review,Empirical tests,H1N1 in China in 2009,Z. Shen, et al. under review,Other applications,推断社交网站中信息传播源头 树叶

3、中的源头,从时间序列重构复杂网络,压缩感知简介 从时间序列重构病毒传播网络和节点性质 Other applications,Compressive sensing(压缩感知),陶哲轩，现任教于美国加州大学洛杉矶分校（UCLA） 数学系的华裔数学家，澳洲惟一荣获数学最高荣誉“菲尔茨奖” 的澳籍华人数学教授，继1982年的丘成桐之后获此殊荣的 第二位华人。其于1996年获普林斯顿大学博士学位后任教于 UCLA，24岁时便被UCLA聘为正教授。,Around 2004 Emmanuel Cands, Terence Tao and David Donoho,压缩感知理论证明对可压缩信号可以通过远低于

4、Nyquist采样频率的方式进行数据采样， 仍然能够精确地恢复出原始信号。该理论目前在图像处理、医学成像、模式识别、 无线通讯、天文学等很多领域受到高度关注，并被美国科技评论评为当年十大科技 进展之一。,Compressive sensing algorithm,应用压缩传感理论通过少量测量值y恢复稀疏向量x。是在x稀疏并且满足约束条件 的情况下，M可以远小于N，并且x中非零元素的个数也小于M。信号重构过程在此条件 下转化为一个优化问题，求解方法有最小L1范数法和迭代阈值法等。,从二进制时间序列重构传播网络、节点性质和推断隐藏源头,SIS and CP dynamics,Z. Shen, W.

5、-X. Wang*, Y. Fan, Z. Di and Y.-C. Lai, Nature Communications, to appear in 2014.,Schematic illustration of reconstruction method,Z. Shen, W.-X. Wang*, Y. Fan, Z. Di and Y.-C. Lai, Nature Communications, to appear in 2014.,Compressive sensing,Z. Shen, W.-X. Wang*, Y. Fan, Z. Di and Y.-C. Lai, Nature

6、 Communications, to appear in 2014.,Reconstruction performance,Inferring inhomogeneous infection and recovery rates,Locating hidden source,Other applications,重构混沌动力系统 Phys. Rev. Lett. 106, 154101 (2011). 重构博弈网络 Phys. Rev. X 1, 021021 (2011). 重构耦合振子网络 Phys. Rev. Lett. 104, 058701 (2010); Europhys. Le

7、tt., 94, 48006 (2011). 推断隐藏节点 Phys. Rev. E 85, 065201(R) (2012). 预测时间序列同步 Phys. Rev. E 85, 056220 (2012). 重构通讯网络和路由策略（finished） 重构最后通牒博弈网络（finished） 重构公共品博弈网络（ongoing） 重构基因调控网络（ongoing） 重构布尔动力学网络（ongoing） 重构复合种群网络（病毒传播） （ongoing） 重构意见动力学网络（ongoing） 重构神经元网络（ongoing）,预测人的移动能力和交通拥塞,热传导模型（小勇） 宏微观统一预测模型（

8、小勇） 预测交通拥塞,信息熵和可预测性,将不同路段平均速度分段，构造符号序列，计算路段的熵和可预测性,车速与可预测性,How to control a car,Complex network,Controlling complex networks is ultimate goal!,复杂网络的控制,25,Structural controllability of complex networks,Minimum input theory: (Liu et al. Nature 473, 167 (2011) ) find minimum number of driver nodes to s

9、atisfy full rank condition,Controllability,卡尔曼满秩理论,26,Maximum matching for structural controllability and observability,可控性：计算网络最大匹配， 控制未匹配节点,可观测性：反向网络的最大匹配,结构可控性适用范围：有向网络（无双相边），随机边权重（结构矩阵）,Exact controllability theory,Theoretical framework,任意网络：网络矩阵特征值的最大几何重数 无向网络：特征值的最大代数重数（相同特征值数量） 稀疏网络：网络矩阵的秩 致密

10、网络：单位阵加网络矩阵的秩,29,Identifying driver nodes,Universal Symmetry in Controlling Complex Networks,C. Zhao, W.-X. Wang*, Y.-Y. Liu* and J.-J. Slotine*,First-order nodal dynamics,A mixture of nodal dynamics with different orders,Thank you for your attention,无标度网络,复杂网络的结构、动力学和功能,网络结构,动力学,小世界网络,社团网络,权重网络,同步,

11、博弈,交通,抗毁性,调控,功能,复杂网络三元素,正问题: (1)网络结构如何演化 (2) 网络结构如何影响动力学和功能 反问题：从动力学反推网络结构,萤火虫发光，鼓掌,合作涌现，经济行为 物种多样性,互联网，输运网络 中的拥塞,金融危机，大停电,基因调控网，神经网络,控制,复杂网络研究的核心问题：三元素的关系,最终目标,SIS dynamics,Evolutionary games,Prisoners dilemma,Casting the prediction problem into the framework of compressive sensing,Compressive sens

12、ing,Success rates of predicting model networks,PDG for network with 100 nodes,Scale-free,Small-world,Random,SG for network with 100 nodes,Scale-free,Small-world,Random,Predicting a real social network from experiment,Relationship network of 22 students,Success rate of prediction,22 students play PDG

13、 together and write down their payoffs and strategies,Payoff vs number of neighbors,Reconstructing traffic networks and local routing strategy,其中,Measurable data: incoming and out going flux of nodes,According to the flux conservation,Topology reconstruction,Identifying routing parameter,Contact process,Inferring the source of epidemic sprea