论文标题
对动态随机块模型的共识：快速收敛和相变
Consensus on Dynamic Stochastic Block Models: Fast Convergence and Phase Transitions
论文作者
论文摘要
我们介绍了两种共识模型，该模型是按照时间不断发展的随机块模型（SBM）的多数规则，其中网络进化是马尔可夫或非马克维亚人。在多数统治下，在每个回合中，每个代理商同时根据他/她的邻居的大多数人更新他/她的意见。我们的网络具有社区结构，随着时间的流逝而随机发展。与经典环境相反，动态不是纯粹的确定性，并且通过重新采样每个步骤的连接来反映SBM的结构，从而使具有相同意见的代理人比具有不同意见的代理更有可能联系。 在\ emph {Markovian模型}中，根据SBM Law在每个步骤中重新采样，每个代理商通过多数规则更新他/她的意见。我们证明了\ emph {of-One}类型结果，即任何初始偏见都会导致最终赢得胜利的非平凡优势，均匀地在网络的大小上。 在\ emph {non-markovian模型}中，只有在两个更改意见中的某些意见中的某些情况下，否则将两种代理之间的连接重新采样，否则才能保持相同。我们研究了快速收敛到共识与停止动力学之间的相变。此外，我们为各种收敛速度建立了初始铅的阈值。
We introduce two models of consensus following a majority rule on time-evolving stochastic block models (SBM), in which the network evolution is Markovian or non-Markovian. Under the majority rule, in each round, each agent simultaneously updates his/her opinion according to the majority of his/her neighbors. Our network has a community structure and randomly evolves with time. In contrast to the classic setting, the dynamics is not purely deterministic, and reflects the structure of SBM by resampling the connections at each step, making agents with the same opinion more likely to connect than those with different opinions. In the \emph{Markovian model}, connections between agents are resampled at each step according to the SBM law and each agent updates his/her opinion via the majority rule. We prove a \emph{power-of-one} type result, i.e., any initial bias leads to a non-trivial advantage of winning in the end, uniformly in the size of the network. In the \emph{non-Markovian model}, a connection between two agents is resampled according to the SBM law only when some of the two changes opinion and is otherwise kept the same. We study the phase transition between the fast convergence to the consensus and a halt of the dynamics. Moreover, we establish thresholds of the initial lead for various convergence speeds.
