Skip to main content
Home

Main navigation

  • Home
User account menu
  • Log in

Breadcrumb

  1. Home

An Erdos-Renyi Random Graph Generator and Analyzer

By Skander, 11 December, 2012

UPDATE this application is now part of SKapps.

 

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 disconneted if

p < n / 2

 

Apps

My Apps

  • Collatz (Syracuse) Sequence Calculator / Visualizer
  • Erdős–Rényi Random Graph Generator / Analyzer
  • KMeans Animator
  • Language Family Explorer

New Articles

Divine Connections: Building Promptheon, a GenAI Semantic Graph Generator of Ancient Gods
Machine Learning Mind Maps
Thompson Sampling With Gaussian Distribution - A Stochastic Multi-armed Bandit
Stochastic Multi-armed Bandit - Thompson Sampling With Beta Distribution
The Exploration-Exploitation Balance: The Epsilon-Greedy Approach in Multi-Armed Bandits

Skander Kort