Random adjacency list generator

Question

I am currently working on developing an application to find the maximum clique in a graph for my final year project. I have most the project complete and am just starting to test the application.

The application currently uses an adjacency list as an input and I was wondering if anyone knew of an adjacency list random generator, so I can test my application?

Many thanks

Answer 1

This problem is much easier to address if you think about the graphs in terms of adjacency matrices rather than adjacency lists. A graph with m vertices can be represented by an m by m matrix where each edge is 0 if it is absent, or 1 if it is present.

For a directed graph, all elements are required, but for an undirected graph, you'll need a upper triangular matrix.

Once you've got the adjacency matrix, you can easily convert it to adjacency lists.

Answer 2

It depends on your random graph model. The simplest model is the Erdős–Rényi model, where you specify the number of nodes and the probability of a link between any given pair. This is easy to generate but the resulting graphs will not be very interesting because they aren't at all similar to most networks observed in the real world. Real-world networks usually have power law degree distributions and higher clustering coefficients. There are a few other standard models you might be interested in that address this (Watts-Strogatz or Barabási–Albert). I have also used the LFR model described in this paper which has source code available here.