Erdős–Rényi Graph Model With Apache AGE

Introduction

In the mathematical field of graph theory, the Erdős–Rényi model refers to one of two closely related models for generating random graphs or the evolution of a random network. These models are named after Hungarian mathematicians Paul Erdős and Alfréd Rényi, who introduced one of the models in 1959.

I've been working on a feature for Apache AGE where it is possible to generate an Erdős–Rényi graph. AGE is an opensource extension for PostgreSQL that enables users to leverage a graph database on top of existing relational databases. Here's the Pull Request for it.

Background

There are two closely related variants of the Erdős–Rényi random graph model, but the one that I made for AGE was the G(n,p) model.

In the G(n,M) model, a graph is chosen uniformly at random from the collection of all graphs which have n nodes and M edges. The nodes are considered to be labeled, meaning that graphs obtained from each other by permuting the vertices are considered to be distinct. For example, in the G(3,2) model, there are three two-edge graphs on three labeled vertices (one for each choice of the middle vertex in a two-edge path), and each of these three graphs is included with probability 1/3.

In the G(n,p) model, a graph is constructed by connecting labeled nodes randomly. Each edge is included in the graph with probability p, independently from every other edge. Equivalently, the probability for generating each graph that has n nodes and M edges is:

p^M x ( 1 − p )^{C(n 2) − M}.

The parameter p in this model can be thought of as a weighting function; as p increases from 0 to 1, the model becomes more and more likely to include graphs with more edges and less likely to include graphs with fewer edges.

Implementation

Here is how it was done to create the vertices in AGE (I skipped some declarations and other parts, but in essence it is like the code below).

    /* Create the vertices and add them to vertex_array */
    for (int i = 0; i < no_vertices; i++)
    {
        vid = nextval_internal(vertex_seq_id, true);
        object_graph_id = make_graphid(vertex_label_id, vid);
        props = create_empty_agtype();

        /* Insert the vertex in the graph and in the list. */
        insert_vertex_simple(graph_id, vertex_label_str, object_graph_id, props);
        vertex_array[i] = object_graph_id;
    }

Then the edges. It uses a nested loop to iterate over unique pairs of vertices. The outer loop iterates from 0 to the number of vertices, and the inner loop starts from the current value of the outer loop variable to the number of vertices.

/* For each unique pair (i, j), generate a random number. If it's probability is P or grater, create
       an edge between i and j. 
     */
    for (int i = 0; i < no_vertices; i++)
    {
        /* It starts with (int j = i) because it's a combination of C(n, 2) total edges. */
        for (int j = i; j < no_vertices; j++)
        {
            /* Generate a random float number between 0 and 1. */
            random_prob = (float) ((float)rand() / (float)RAND_MAX);

            if (random_prob <= set_prob && i != j)
            {
                eid = nextval_internal(edge_seq_id, true);
                object_graph_id = make_graphid(edge_label_id, eid);

                props = create_empty_agtype();

                insert_edge_simple(graph_id, edge_label_str,
                                object_graph_id, vertex_array[i],
                                vertex_array[j], props);

                if (bidirectional == true)
                {
                    eid = nextval_internal(edge_seq_id, true);
                    object_graph_id = make_graphid(edge_label_id, eid);

                    props = create_empty_agtype();

                    insert_edge_simple(graph_id, edge_label_str,
                                    object_graph_id, vertex_array[j],
                                    vertex_array[i], props);
                }
            }
        }
    }

Example

Here is an example of a random generated graph from the Erdos-Renyi function with AGE Viewer:

SELECT ag_catalog.age_create_erdos_renyi_graph('test', 5, '0.4', NULL, NULL, NULL);

NOTICE:  graph "test" has been created
 age_create_erdos_renyi_graph 
------------------------------

(1 row)

The total possible number of edges is C(5,2):

5!/(2! x 3!) =
= (5 x 4 x 3!)/(2! x 3!) =
= (5 x 4)/2! =
= 20/2 =
= 10

But since the set probability was 0.4, each time it tries to create an edge, first a random probability is generated and if this probability is less than 0.4, it creates the edge. That's why the number of edges is reduced.

Conclusion

With this feature developed for Apache AGE, users will easily generate Erdos-Renyi graphs within the PostgreSQL environment. Incorporating this model into AGE expands its capabilities and empowers users to analyze and explore networks efficiently.

If you want to learn more about Apache AGE, checkout my other posts, the Apache AGE website, and it's GitHub repository:

Apache AGE Website
Apache AGE GitHub Repo