I am trying to generate random DAG's (Directed Acyclic Graphs)... However, the result is not very satisfying to me; What I am doing:

I generate a random graph with the Erdős–Rényi model; More precisely, for every pair of vertices $(i,j)$ I set an edge between $i$ and $j$ with probability $p$; Afterwards I choose a random permutation and then obtain a DAG with it;

(If there is an edge between a pair $(i,j)$ and $i$ is before $j$ in our permutation then the edge becomes directed from $i$ to $j$; In contrary, if $j$ is before $i$ the edge is directed from $j$ to $i$)

Now I read some papers and this is what many people do in order to generate DAGS; However, I find the result not very promising; If the graph gets huge (let's say 100+ vertices) I do have lots of paths between vertices being very far away from each other;

So let's say we have vertex 1 and vertex 100; Then there are many ways between the two of them; To avoid that I can choose my p to be small, e.g. with 100 vertices I could e.g. set $p<0.05$; But then close vertices habe almost no chance to be connected, e.g. vertex 1 and vertex 5; Also, the graph does not contain lots of paths over many vertices which is actually in many case the essence of directed acyclic graphs;

Therefore, I was wondering if you ever created DAGs and had the same problem or if you generally have an idea what to do?

I was thinking of choosing a permutation first and give a higher probability $p$ for vertices close to each other; But I do not know if this is common or what people do in such a case

Therefore, any comment is highly appreciated


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy