王文旭 北京师范大学 系统科学学院 http://sss.bnu.edu.cn/~wenxuw 基于大数据重构、预测和控制复杂系统 王文旭 北京师范大学 系统科学学院 http://sss.bnu.edu.cn/~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 networks, etc. Question : Who is the source of a message? Answer: Social network + some observers

时间反演虚拟扩散法 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 推断社交网站中信息传播源头 树叶中的源头

从时间序列重构复杂网络 压缩感知简介 从时间序列重构病毒传播网络和节点性质 Other applications

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

Compressive sensing algorithm 应用压缩传感理论通过少量测量值y恢复稀疏向量x。是在x稀疏并且Φ满足约束条件 的情况下，M可以远小于N，并且x中非零元素的个数也小于M。信号重构过程在此条件 下转化为一个优化问题，求解方法有最小L1范数法和迭代阈值法等。

从二进制时间序列重构传播网络、节点性质和推断隐藏源头 SIS and CP dynamics Z. Shen, W.-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.

Full network matching Compressive sensing x … Neighbors of x y N matching Full network Z. Shen, W.-X. Wang*, Y. Fan, Z. Di and Y.-C. Lai, Nature 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. Lett., 94, 48006 (2011). 推断隐藏节点 Phys. Rev. E 85, 065201(R) (2012). 预测时间序列同步 Phys. Rev. E 85, 056220 (2012). 重构通讯网络和路由策略（finished） 重构最后通牒博弈网络（finished） 重构公共品博弈网络（ongoing） 重构基因调控网络（ongoing） 重构布尔动力学网络（ongoing） 重构复合种群网络（病毒传播） （ongoing） 重构意见动力学网络（ongoing） 重构神经元网络（ongoing）

预测人的移动能力和交通拥塞 热传导模型（小勇） 宏微观统一预测模型（小勇） 预测交通拥塞

信息熵和可预测性 将不同路段平均速度分段，构造符号序列，计算路段的熵和可预测性

车速与可预测性

复杂网络的控制 How to control a car Complex network Controlling complex networks is ultimate goal!!!!!

Structural controllability of complex networks Minimum input theory: (Liu et al. Nature 473, 167 (2011) ) find minimum number of driver nodes to satisfy full rank condition Controllability 卡尔曼满秩理论

Maximum matching for structural controllability and observability 可控性：计算网络最大匹配， 控制未匹配节点 可观测性：反向网络的最大匹配 结构可控性适用范围：有向网络（无双相边），随机边权重（结构矩阵）

Exact controllability theory

Theoretical framework 任意网络：网络矩阵特征值的最大几何重数 无向网络：特征值的最大代数重数（相同特征值数量） 稀疏网络：网络矩阵的秩 致密网络：单位阵加网络矩阵的秩

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

复杂网络的结构、动力学和功能 正问题: (1)网络结构如何演化 反问题：从动力学反推网络结构 复杂网络三元素 网络结构 动力学 功能 控制 同步 萤火虫发光，鼓掌 合作涌现，经济行为 物种多样性 小世界网络 博弈 网络结构 动力学 互联网，输运网络 中的拥塞 无标度网络 交通 社团网络 抗毁性 金融危机，大停电 权重网络 调控 基因调控网，神经网络 功能 控制 最终目标 复杂网络研究的核心问题：三元素的关系 正问题: (1)网络结构如何演化 (2) 网络结构如何影响动力学和功能 反问题：从动力学反推网络结构

SIS dynamics

Full social network structure Compressive sensing Time series of agents (Detectable) (1) payoffs (2) strategies Evolutionary games Evolutionary games Prisoner’s dilemma

Casting the prediction problem into the framework of compressive sensing x … Neighbors of x y N Full network structure matching Compressive sensing 40

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 22 students play PDG together and write down their payoffs and strategies Success rate of prediction Relationship network of 22 students 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 spreading (ongoing) Using airlines, trains, and interstate road as the network Using the earliest time of reporting a disease at some locations as observers Inferring the source of the disease from the observers