On Consensus in a Correlated Model of Network Formation Based on a Polya Urn Process

In this paper, we consider a consensus seeking process based on local averaging of opinions in a dynamic model of social network formation. At each time step, individual agents randomly choose another agent to interact with. The interaction is one-sided and results in the agent averaging her opinion with that of her randomly chosen neighbor. Once an agent chooses a neighbor, the probabilities of interactions are updated in such a way that prior interactions are reinforced and future interactions become more likely, resulting in a random consensus process in which networks are highly correlated with each other. Using results of Skyrm and Pemantle and utilizing the de Finetti representation theorem as well as properties of Polya urn processes, we show that this highly correlated process is equivalent to a mixture of i.i.d. processes whose parameters are drawn from a random limit distribution. Therefore, prior results on consensus on i.i.d. processes can be used to show consensus and to compute the statistics of the consensus value in terms of the initial conditions. We provide simple expressions for the mean and the variance of the asymptotic random consensus value in terms of the number of nodes. We also show that the variance converges to a factor of the empirical variance of the initial values that depends only on the size of the network and goes to zero as the size of the network grows