生物医学网络科学Biomedical Network Science
同步与协同动力学12 / 16

共识动力学

阅读
约 1 分钟

如果每个节点只有一个标量状态 xix_i(意见、估计值、温度),并向邻居靠拢:

dxidt=∑jAij(xj−xi)⇔𝒙̇=−L𝒙\frac{dx_i}{dt}=\sum_j A_{ij}(x_j-x_i)\quad\Longleftrightarrow\quad\dot{\mathbf x}=-L\mathbf x

这就是共识(consensus)动力学。把 Kuramoto 模型在同步态附近线性化(sin⁡(θj−θi)≈θj−θi\sin(\theta_j-\theta_i)\approx\theta_j-\theta_i,ωi\omega_i 相同),得到的正是这个方程;它也是主稳定函数中例 1 的特例。

共识定理(无向连通网络):𝒙(t)→x‾𝟏\mathbf x(t)\to\bar x\,\mathbf 1,其中 x‾=1N∑ixi(0)\bar x=\frac1N\sum_i x_i(0) 为初值平均;收敛速度由代数连通度决定,偏离共识的误差约按 e−μ2te^{-\mu_2 t} 衰减。对强连通的有向网络,也会达成一致,但一致值是初值的加权平均,权重由 LL 的左零特征向量给出。

例子:5 个节点的路径图 μ2≈0.38\mu_2\approx0.38,5 个节点的完全图 μ2=5\mu_2=5,后者达成共识快约 13 倍。本站代码中,N=60N=60、平均度 4 的环 μ2≈0.055\mu_2\approx0.055,误差降到 1% 用时约 65;重连概率 0.5 的 WS 网络 μ2≈0.57\mu_2\approx0.57,用时约 5,μ2×\mu_2\times时间在各网络间量级相近。离散时间版本 𝒙(t+1)=W𝒙(t)\mathbf x(t+1)=W\mathbf x(t)(WW 行随机)即社会学中的 DeGroot 意见模型;在多机器人编队、传感器网络中,共识算法用于分布式估计(Olfati-Saber、Fax 与 Murray 2007,Proceedings of the IEEE)。

共识动力学给出了一个统一视角:μ2\mu_2 衡量网络“多快能变得一致”。它同时出现在同步稳定性、共识速度、谱聚类(社团结构与社区发现中的 Fiedler 向量)和随机游走混合时间中,其性质集中整理在拉普拉斯谱与代数连通度。