Voter model on random directed graphs
We consider Markovian dynamics on a typical realization of the so-called Directed Configuration Model (DCM), which is a random directed graph with prescribed in- and out-degrees. In this random geometry, we study the meeting time of two random walks on a typical realization of the graph starting at stationarity, the coalescence time for a system of coalescent random walks, and the consensus time of the voter model. Indeed, it is known that the latter three quantities are related to each other when the underlying sequence of graphs satisfies certain mean field conditions. We provide a complete characterisation of the distribution of meeting, coalescence and consensus time on a typical random graph as a function of a single quantity θ. More precisely we show that, for a typical large graph from the DCM ensemble, the distribution of the meeting time is well-approximated by an exponential random variable. Furthermore, we provide the precise first-order approximation of its expectation, showing that the latter is linear in the size of the graph, and the explicit pre-constant θ depends on some easy statistics of the degree sequence. As a consequence, we can analyse the effect of the degree sequence on the expected meeting time and, via some explicit examples, how its regularity/variability play crucial roles in the information diffusion. This is based on a joint work with Luca Avena (University of Florence), Rajat Subhra Hazra (Leiden University) and Matteo Quattropani (Sapienza, University of Rome).
Area: IS21 - Complex networks and random graphs (Luca Avena)
Keywords: Random directed graphs, voter model, meeting times
Please Login in order to download this file