Accuracy of the Graphon Mean Field Approximation for Interacting Particle Systems

We consider a system of N particles whose interactions are characterized by a (weighted) graph GN. Each particle is a node of the graph with an internal state. The state changes according to Markovian dynamics that depend on the states and connection to other particles. We study the limiting properties, focusing on the dense graph regime, where the number of neighbors of a given node grows with N. We show that when GN converges to a graphon G, the behavior of the system converges to a deterministic limit, the graphon mean field approximation. We obtain convergence rates depending on the system size N and cut-norm distance between GN and G. We apply the results for two subcases: When GN is a discretization of the graph G with individually weighted edges; when GN is a random graph obtained through edge sampling from the graphon G. In the case of weighted interactions, we obtain a bound of order O (1/N). In the random graph case, the error is of order O ( (N) /N) with high probability. We illustrate the applicability of our results and the numerical efficiency of the approximation through two examples: a graph-based load-balancing model and a heterogeneous bike-sharing system.