Exploring the randomness of directed acyclic networks

The feed-forward relationship naturally observed in time-dependent processes and in a diverse number of real systems-such as some food webs and electronic and neural wiring-can be described in terms of the so-called directed acyclic graphs (DAGs). An important ingredient of the analysis of such networks is a proper comparison of their observed architecture against an ensemble of randomized graphs, thereby quantifying the randomness of the real systems with respect to suitable null models. This approximation is particularly relevant when the finite size and/or large connectivity of real systems make inadequate a comparison with the predictions obtained from the so-called configuration model. In this paper we analyze two methods of DAG randomization as defined by the desired combination of two topological invariants (directed degree sequence and component distributions) aimed to be preserved. A highly ordered DAG, called snake graph, and an Erdös-Rényi DAG were used to validate the performance of the algorithms. Finally, three real case studies, namely, the C. elegans cell lineage network, a Ph.D. student-supervisor network, and the Milgram's citation network, were analyzed using each randomization method. Results show how the interpretation of degree-degree relations in DAGs with respect to their randomized ensembles depends on the topological invariants imposed.