ErdsRényiRandomnetze

ErdsRenyiRandomnetze, often referred to as Erdős–Rényi random networks or ER graphs, are a fundamental class of random graphs in graph theory. Introduced by Paul Erdős and Alfréd Rényi in the late 1950s and early 1960s, these models provide a mathematical framework for studying the properties of networks that arise from random connections.

There are two primary models within the Erdős–Rényi framework. The G(n, p) model, also known as the binomial model, starts with n vertices, and each possible edge between any pair of vertices exists independently with a probability p. The G(n, M) model, also known as the fixed number of edges model, starts with n vertices and a fixed number M of edges, where each edge is chosen uniformly at random from all possible edges.

These models are useful for theoretical analysis because their statistical properties can be precisely determined. For instance, properties like the size of connected components, the existence of cycles, and the degree distribution can be calculated or bounded as a function of n and p (or M). They serve as a baseline for comparison with more complex, real-world networks that often exhibit non-random structures. Despite their simplicity, ER graphs exhibit a phase transition phenomenon. As the probability p increases, the graph transitions from a collection of small, disconnected components to a single, large connected component. This transition occurs around p = 1/n.