Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to generate random graphs?

I want to be able to generate random, undirected, and connected graphs in Java. In addition, I want to be able to control the maximum number of vertices in the graph. I am not sure what would be the best way to approach this problem, but here are a few I can think of:

(1) Generate a number between 0 and n and let that be the number of vertices. Then, somehow randomly link vertices together (maybe generate a random number per vertex and let that be the number of edges coming out of said vertex). Traverse the graph starting from an arbitrary vertex (say with Breadth-First-Search) and let our random graph G be all the visited nodes (this way, we make sure that G is connected).

(2) Generate a random square matrix (of 0's and 1's) with side length between 0 and n (somehow). This would be the adjacency matrix for our graph (the diagonal of the matrix should then either be all 1's or all 0's). Make a data structure from the graph and traverse the graph from any node to get a connected list of nodes and call that the graph G.

Any other way to generate a sufficiently random graph is welcomed. Note: I do not need a purely random graph, i.e., the graph you generate doesn't have to have any special mathematical properties (like uniformity of some sort). I simply need lots and lots of graphs for testing purposes of something else.

Here is the Java Node class I am using:

public class Node<T> {
    T data;
    ArrayList<Node> children= new ArrayList<Node>();
    ...}

Here is the Graph class I am using (you can tell why I am only interested in connected graphs at the moment):

public class Graph {
    Node mainNode;
    ArrayList<Node> V= new ArrayList<Node>();

    public Graph(Node node){
        mainNode= node;
    }
    ...}

As an example, this is how I make graphs for testing purposes right now:

//The following makes a "kite" graph G (with "a" as the main node).

/*     a-b
        |/|
        c-d
*/
Node<String> a= new Node("a");
Node<String> b= new Node("b");
Node<String> c= new Node("c");
Node<String> d= new Node("d");
a.addChild(b);
a.addChild(c);
b.addChild(a);
b.addChild(c);
b.addChild(d);
c.addChild(a);
c.addChild(b);
c.addChild(d);
d.addChild(c);
d.addChild(b);
Graph G1= new Graph(a);
like image 813
coneyhelixlake Avatar asked Nov 24 '13 06:11

coneyhelixlake


People also ask

How do you generate random graphs in C++?

1. Using rand(), assign random values to the number of vertex and edges of the graph. 2. Call GenerateRandGraphs(), with 'e' as the number of edges and 'v' as the number of vertexes, in the argument list.

What is a random graph called?

In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs lies at the intersection between graph theory and probability theory.

What is random graph models?

A random graph model is given by a sequence of graph valued random variables, one for each possible value of n : M=(Gn;n∈N) M = ( G n ; n ∈ N ) ” [53]. “In general, a random graph is a model network in which a specific set of parameters take fixed values, but the network is random in other respects” [100].


1 Answers

The following paper proposes an algorithm that uniformly samples connected random graphs with prescribed degree sequence, with an efficient implementation. It is available in several libraries, like Networkit or igraph.

Fast generation of random connected graphs with prescribed degrees. Fabien Viger, Matthieu Latapy

Be careful when you make simulations on random graphs: if they are not sampled uniformly, then they may have hidden properties that impact simulations; alternatively, uniformly sampled graphs may be very different from the ones your code will meet in practice...

like image 51
Matthieu Latapy Avatar answered Oct 19 '22 23:10

Matthieu Latapy