复杂网络重构预测和控制

1、会计学1复杂网络重构预测和控制复杂网络重构预测和控制重构、预测和控制重构、预测和控制Who is the source of a message?Social network + some observersAnswer: Question : Z. Shen, et al. under reviewZ. Shen, et al. under reviewH1N1 in China in 2009Z. Shen, et al. under review陶哲轩，现任教于美国加州大学洛杉矶分校（UCLA）数学系的华裔数学家，澳洲惟一荣获数学最高荣誉“菲尔茨奖”的澳籍华人数学教授，继1982年的丘成

2、桐之后获此殊荣的第二位华人。其于1996年获普林斯顿大学博士学位后任教于UCLA，24岁时便被UCLA聘为正教授。 Around 2004 Emmanuel Cands, Terence Tao and David Donoho 压缩感知理论证明对可压缩信号可以通过远低于Nyquist采样频率的方式进行数据采样，仍然能够精确地恢复出原始信号。该理论目前在图像处理、医学成像、模式识别、无线通讯、天文学等很多领域受到高度关注，并被美国科技评论评为当年十大科技进展之一。 应用压缩传感理论通过少量测量值y恢复稀疏向量x。是在x稀疏并且满足约束条件的情况下，M可以远小于N，并且x中非零元素的个数也小于M

3、。信号重构过程在此条件下转化为一个优化问题，求解方法有最小L1范数法和迭代阈值法等。 Z. Shen, W.-X. Wang*, Y. Fan, Z. Di and Y.-C. Lai, Nature Communications, to appear in 2014.Z. Shen, W.-X. Wang*, Y. Fan, Z. Di and Y.-C. Lai, Nature Communications, to appear in 2014.Compressive sensing 21xNxxaaaXxNeighbors of xyNmatchingFull networkZ. She

4、n, W.-X. Wang*, Y. Fan, Z. Di and Y.-C. Lai, Nature Communications, to appear in 2014.将不同路段平均速度分段，构造符号序列，计算路段的熵和可预测性Complex networkControlling complex networks is ultimate goal! 复杂网络的控制25Minimum input theory: (Liu et al. Nature 473, 167 (2011) )find minimum number of driver nodes to satisfy full ran

5、k condition NNMNtttNCBABAABBCBuAxxrankconditionrank ility controllab sKalman,matrix ility Controllab)()()(system Dynamical12Controllability卡尔曼满秩理论26可控性：计算网络最大匹配， 控制未匹配节点可观测性：反向网络的最大匹配结构可控性适用范围：有向网络（无双相边），随机边权重（结构矩阵）结构可控性适用范围：有向网络（无双相边），随机边权重（结构矩阵）任意网络：网络矩阵特征值的最大几何重数无向网络：特征值的最大代数重数（相同特征值数量）稀疏网络：网络矩阵的

6、秩致密网络：单位阵加网络矩阵的秩29Identifying driver nodesUniversal Symmetry in Controlling Complex NetworksC. Zhao, W.-X. Wang*, Y.-Y. Liu* and J.-J. Slotine*First-order nodal dynamicsA mixture of nodal dynamics with different orders无标度网络网络结构动力学小世界网络社团网络权重网络同步博弈交通抗毁性调控功能复杂网络三元素正问题: (1)网络结构如何演化 (2) 网络结构如何影响动力学和功能反问

7、题：从动力学反推网络结构萤火虫发光，鼓掌合作涌现，经济行为物种多样性互联网，输运网络中的拥塞金融危机，大停电基因调控网，神经网络控制复杂网络研究的核心问题：三元素的关系最终目标Full social network structureCompressive sensingTime series ofagents (Detectable)(1) payoffs (2) strategiesEvolutionary gamesEvolutionary gamesyTxxyyxxyxyxyaMyxayxaarrSGbPDDCPSSPPSS :agent from agent of Payoffnet

8、work connection no if 0 connects if 1 :.matrix Adjacency (SG) gameSnowdrift 0111)( (PDG) game dilemma sPrisoner 001)( :matrix Payoff 10)( defector ;01)( cooperator :StrategiesPrisoners dilemma 21xNxxaaaXxNeighbors of xyNFull network structurematchingCompressive sensingseries timefrom obtainable : ;d

9、etectable : by )()()()()()()()()()()()()()()()()()(ted)reconstruc be (to agent of neighbors : )()()( )()()()()()()( : at time of payoff21222222121112111121212211XYXYAPSSPSSPSSPSSPSSPSSPSSPSSPSSXXYPSSPSSPSSNmttttttttttttttttttxaaatMtMtMttattattatMtxmNmTxmmTxmmTxNTxTxTxNTxTxTxxNxxmxxxNTxxNTxxTxxx00.10

10、.0.91DataSuccessful rateSocial network detection, #N=100 edgenoedge01DataSuccessful rateSocial network detection, #N=100 edgenoedge01DataSuc

11、cessful rateSocial network detection, #N=100 edgenoedgePDG for network with 100 nodesScale-freeSmall-worldRandom 01DataSuccessful rateSocial network detection, #N=100 edgenoedge01DataSucce

12、ssful rateSocial network detection, #N=100 edgenoedge01DataSuccessful rateSocial network detection, #N=100 edgenoedgeSG for network with 100 nodesScale-freeSmall-worldRandom Relationship network of 22 students0100.10.

13、0.91DataSuccessful rateSocial network detection, #N=20 edgenoedgeSuccess rate of prediction22 students play PDG together andwrite down their payoffs and strategiesPayoff vs number of neighbors12345670.450.500.550.600.650.700.750.800.85 Normailized payoffnode degreeWinner: Lingchao

14、 JiReconstructing traffic networks and local routing strategy,其中Measurable data: incoming and out going flux of nodesAccording to the flux conservation Z. Shen, et al. under reviewZ. Shen, W.-X. Wang*, Y. Fan, Z. Di and Y.-C. Lai, Nature Communications, to appear in 2014.Compressive sensing 21xNxxaaaXxNeighbors of xyNmatchingFull netw