Models of random graphs and their applications

Networks are ubiquitous. They arise naturally as models of communication networks, networks of friends, in the communication of infection, rumors or information, as models of atoms and bonds between them in chemistry, as autocatalytic nets and elsewhere. Mathematically the notion is captured in a graph: a finite set of vertices V and a set E of edges between some of the distinct vertices. This chapter presents graphs that have finite vertex set; do not have multiple edges between two vertices or loops from a vertex to itself, and whose edges are undirected. The chapter introduces Erdős–Rényi model; a natural generalization of Erdős–Rényi model random graphs is made when the edge between vertices v1 and v2 arises with probability pv1v2, independently of all other edges. Although the Erdős–Rényi model is mathematically tractable; there is mathematical interest in comparing it with alternative models. Additionally, in many real networks, edges will not in fact arise independently and equiprobably.