论文标题
分布在意见动力学中平均
Distributed Averaging in Opinion Dynamics
论文作者
论文摘要
我们考虑在任意图上的两个简单的异步观点动力学，其中每个节点$ u $都有一个初始值$ξ_u（0）$。在第一个过程中，每次步骤$ t \ ge 0 $，随机节点$ u $和其邻居的$ k $的随机样本$ v_1，v_1，v_2，\ cdots，v_k $。然后，$ u $更新其当前值$ξ_u（t）$为$ξ_u（t + 1）=αξ_U（t） + \ frac {（1-α）} {K} {k} \ sum_ {i = 1}^k吻在第二个过程中，EDGEMODEL在每个步骤中都选择了随机的相邻节点$（u，v）$，然后节点$ u $将其值等效地更新为$ k = 1 $和$ v $作为所选邻居。对于这两个过程，所有节点的值都收敛到$ f $，这是一个随机变量，具体取决于每个步骤中的随机选择。对于NodeModel和常规图，对于EdgeModel和任意图，$ f $的期望是初始值$ \ frac {1} {n} {n} \ sum_ {u \ in V}ξ_u（0）$的平均值。对于NodeModel和非规范图，$ F $的期望是初始值的度加权平均值。我们的结果是两个方面。我们考虑$ f $的浓度，并在常规图表的$ f $方差上显示紧密的界限。我们表明，当初始值不取决于节点的数量时，差异可以忽略不计，因此节点能够估算节点值的初始平均值。有趣的是，此方差不取决于图结构。为了证明，我们在过程和两个相关随机步行的过程之间介绍了双重性。我们还分析了两个模型和任意图的收敛时间，显示了使所有节点值'$ \ varepsilon $ -close''互相$ t_ \ varepsilon $互相显示的界限。在对初始值的分布的假设下，我们的边界在渐近上很紧。
We consider two simple asynchronous opinion dynamics on arbitrary graphs where every node $u$ has an initial value $ξ_u(0)$. In the first process, the NodeModel, at each time step $t\ge 0$, a random node $u$ and a random sample of $k$ of its neighbours $v_1,v_2,\cdots,v_k$ are selected. Then, $u$ updates its current value $ξ_u(t)$ to $ξ_u(t+1) = αξ_u(t) + \frac{(1-α)}{k} \sum_{i=1}^k ξ_{v_i}(t)$, where $α\in (0,1)$ and $k\ge 1$ are parameters of the process. In the second process, the EdgeModel, at each step a random pair of adjacent nodes $(u,v)$ is selected, and then node $u$ updates its value equivalently to the NodeModel with $k=1$ and $v$ as the selected neighbour. For both processes, the values of all nodes converge to $F$, a random variable depending on the random choices made in each step. For the NodeModel and regular graphs, and for the EdgeModel and arbitrary graphs, the expectation of $F$ is the average of the initial values $\frac{1}{n}\sum_{u\in V} ξ_u(0)$. For the NodeModel and non-regular graphs, the expectation of $F$ is the degree-weighted average of the initial values. Our results are two-fold. We consider the concentration of $F$ and show tight bounds on the variance of $F$ for regular graphs. We show that, when the initial values do not depend on the number of nodes, then the variance is negligible, hence the nodes are able to estimate the initial average of the node values. Interestingly, this variance does not depend on the graph structure. For the proof we introduce a duality between our processes and a process of two correlated random walks. We also analyse the convergence time for both models and for arbitrary graphs, showing bounds on the time $T_\varepsilon$ required to make all node values `$\varepsilon$-close' to each other. Our bounds are asymptotically tight under assumptions on the distribution of the initial values.
