Random graph models: an overview of modeling approaches

Abstract

This article nonexhaustively reviews random graph models designed to model interaction networks. It begins with the Erd˝os-Rényi model. It has been deeply studied, as it is based on simple assumptions: independence and homogeneity of the links, which are however too simplistic for applications. The article then focuses on modeling approaches of the hetereogeneity and of the dependences between the links. It starts from probabilistic models reproducing generative processes of the real-world networks (Barabási-Albert or Watts-Strogatz models for instance) and arrives to models more suitable for statistics. Exponential models (ERGM or p) enable to introduce dependences between the desired links. Models with latent variables enable to model heterogeneity of the population and to analyze it.