Simulate a Graph to Analyze Its Characteristics

Introduction

The Erdős–Rényi model, named after the mathematicians Paul Erdős and Alfréd Rényi, is one of the most fundamental random graph models in network science. It is characterized by two parameters: $N$ (the number of nodes) and $p$ (the probability that a pair of nodes is connected by an edge).

Under the Erdős–Rényi model, a graph is generated by connecting nodes randomly. Each edge between two distinct nodes is included in the graph with probability p independent from every other edge. Thus, the model is characterized by having a binomial distribution of degrees, leading to a symmetric bell-shaped degree distribution in the case of large networks with intermediate connection probabilities.

Benefits of using random graphs for simulating real-world scenarios

Random graphs, such as those generated by the Erdős–Rényi model, offer significant advantages in simulating real-world scenarios, especially in fields such as computer networks, epidemiology, and social network analysis. By simulating network topologies, researchers can study the impact of various protocols and the potential performance gains or losses without relying on hard-to-find actual topology maps. This approach allows for a broad range of experimentation due to the ease of generating many graph instances, facilitating statistical significance in the findings. Moreover, random graphs can model the unpredictable nature of real-world networks, from the spread of diseases through populations to the dynamics of social interactions and the robustness of computer networks, providing invaluable insights into their behavior and resilience.

Calculate degree distribution on a simulated graph

In this example, we create a random graph using the Erdős–Rényi model (nx.gnp_random_graph(10, 0.4)).

This model generates a random graph with ten nodes, and each pair of nodes has a 0.4 probability of having an edge between them. This means that for each pair of nodes in the graph, there is a 40% chance that there will be an edge connecting them. Therefore, the number of edges in the graph is not predetermined, and the actual number of edges may vary each time the graph is generated.

Let's calculate the degree distribution for a random graph with ten nodes: