同步与协同动力学12 / 16
共识动力学
如果每个节点只有一个标量状态 (意见、估计值、温度),并向邻居靠拢:
这就是共识(consensus)动力学。把 Kuramoto 模型在同步态附近线性化(, 相同),得到的正是这个方程;它也是主稳定函数中例 1 的特例。
共识定理(无向连通网络):,其中 为初值平均;收敛速度由代数连通度决定,偏离共识的误差约按 衰减。对强连通的有向网络,也会达成一致,但一致值是初值的加权平均,权重由 的左零特征向量给出。
例子:5 个节点的路径图 ,5 个节点的完全图 ,后者达成共识快约 13 倍。本站代码中,、平均度 4 的环 ,误差降到 1% 用时约 65;重连概率 0.5 的 WS 网络 ,用时约 5,时间在各网络间量级相近。离散时间版本 ( 行随机)即社会学中的 DeGroot 意见模型;在多机器人编队、传感器网络中,共识算法用于分布式估计(Olfati-Saber、Fax 与 Murray 2007,Proceedings of the IEEE)。
共识动力学给出了一个统一视角: 衡量网络“多快能变得一致”。它同时出现在同步稳定性、共识速度、谱聚类(社团结构与社区发现中的 Fiedler 向量)和随机游走混合时间中,其性质集中整理在拉普拉斯谱与代数连通度。