An Erdos-Renyi Random Graph Generator and Analyzer

This JavaScript application is a generator and analyzer of Erdos-Renyi random graphs. The application accepts two parameters, namely n and p. Parameter n refers to the number of vertices of the graph. Parameter p, on the other hand, is the probability to generate an edge between a pair of vertices.

Graph visualization is based on the great sigma.js library by Alexis Jacomy. Graph layout is performed by ForceAtlas2 algorithm. ForceAtlas2 belongs to the force-directed-graph-drawing algorithms family. These algorithms assign a mass and a charge to every vertex in the graph. Vertices exert repulsive forces on one another. Edges behave like springs that pull adjacent vertices close to each other. It is possible to see the intermediate layouts produced by ForceAtlas2 by pausing the algorithm.

Some statistics are calculated for every generated graph, more specifically, the maximum degree, the average degree and the density. The density of the graph is defined as:

d = 2 * m / n * (n - 1)
where m is the number of edges. The expected number of edges in the generated graphs is n*(n - 1)*p/2, therefore the density is close to the edge-genaration probability p. The expected average degree is p * (n - 1).

Moreover, the application performs a connectivity test on every generated random graph. Now, given that the minimum connected graph with n vertices is a tree, given that a tree has n-1 edges and given that the expected number of edges in a random graph is n*(n - 1)*p/2, then one can easily establish that the generated graphs will very likely to be disconnted if

p < n / 2

The Erdos-Renyi Random Graph Generator

The Random Graphs Statistics