  Datasets from several domains, such as life-sciences, semantic web, machine
learning, natural language processing, etc. are naturally structured as acyclic
graphs. These datasets, particularly those in bio-informatics and computational
epidemiology, have grown tremendously over the last decade or so. Increasingly,
as a consequence, there is a need to build and evaluate various strategies for
processing acyclic structured graphs. Most of the proposed research models the
real world acyclic structures as random graphs, i.e., they are generated by
randomly selecting a subset of edges from all possible edges. Unfortunately the
graphs thus generated have predictable and degenerate structures, i.e., the
resulting graphs will always have almost the same degree distribution and very
short paths.
  Specifically, we show that if $O(n \log n \log n)$ edges are added to a
binary tree of $n$ nodes then with probability more than $O(1/(\log n)^{1/n})$
the depth of all but $O({\log \log n} ^{\log \log n})$ vertices of the dag
collapses to 1. Experiments show that irregularity, as measured by distribution
of length of random walks from root to leaves, is also predictable and small.
The degree distribution and random walk length properties of real world graphs
from these domains are significantly different from random graphs of similar
vertex and edge size.
