论文标题
异步Degroot动力学
The Asynchronous DeGroot Dynamics
论文作者
论文摘要
我们分析了degroot动力学的异步版本：在带有$ n $ nodes的连接图$ g $中，每个节点都有$ [0,1] $的初始意见和一个独立的泊松时钟。当节点$ v $戒指的时钟时，$ v $的意见被邻居的平均意见所取代。众所周知，观点融合了共识。我们表明，预期的时间$ \ mathbb e（τ_\ varepsilon）$达到$ \ varepsilon $ -consensus是无方向图和欧拉图的poly $（n）$，但对于某些有界程度的图形，它是指数的。 我们的主要结果是，在无方向的图和欧拉（Eulerian Digraphs）中，如果该学位均匀地界定并且初始意见为I.I.D.我们对限制共识意见的差异进行了详尽的估计，该差异衡量了汇总信息的能力（``人群的智慧''）。我们还证明了对非可逆的马尔可夫链和无限图的概括。对分裂过程和耦合随机步行的独立兴趣的新结果对于我们的分析至关重要。
We analyze the asynchronous version of the DeGroot dynamics: In a connected graph $G$ with $n$ nodes, each node has an initial opinion in $[0,1]$ and an independent Poisson clock. When a clock at a node $v$ rings, the opinion at $v$ is replaced by the average opinion of its neighbors. It is well known that the opinions converge to a consensus. We show that the expected time $\mathbb E(τ_\varepsilon)$ to reach $\varepsilon$-consensus is poly$(n)$ in undirected graphs and in Eulerian digraphs, but for some digraphs of bounded degree it is exponential. Our main result is that in undirected graphs and Eulerian digraphs, if the degrees are uniformly bounded and the initial opinions are i.i.d., then $\mathbb E(τ_\varepsilon)=\text{polylog}(n)$ for every fixed $\varepsilon>0$. We give sharp estimates for the variance of the limiting consensus opinion, which measures the ability to aggregate information (``wisdom of the crowd''). We also prove generalizations to non-reversible Markov chains and infinite graphs. New results of independent interest on fragmentation processes and coupled random walks are crucial to our analysis.
