Goni, J; Corominas-Murtra, B; Sole, RV; Rodriguez-Caso, C. 2010. Exploring the randomness of directed acyclic networks. PHYSICAL REVIEW E 82 (6): art. no.-066115

[Eugene Garfield]

Goni, J; Corominas-Murtra, B; Sole, RV; Rodriguez-Caso, C. 2010. Exploring the 
randomness of directed acyclic networks. PHYSICAL REVIEW E 82 (6): art. no.-
066115, Part 2.

Author Full Name(s): Goni, Joaquin; Corominas-Murtra, Bernat; Sole, Ricard V.; 
Rodriguez-Caso, Carlos
Language: English
Document Type: Article
KeyWords Plus: COMPLEX NETWORKS; RANDOM GRAPHS; DYNAMICS

Abstract: 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 Erdos-Renyi 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.

Addresses: [Corominas-Murtra, Bernat; Sole, Ricard V.; Rodriguez-Caso, Carlos] 
Univ Pompeu Fabra PRBB, ICREA Complex Syst Lab, Barcelona 08003, Spain; 
[Goni, Joaquin] Univ Navarra, Ctr Appl Med Res, Dept Neurosci, Funct 
Neuroimaging Lab, E-31080 Pamplona, Spain; [Sole, Ricard V.] Santa Fe Inst, 
Santa Fe, NM 87501 USA; [Sole, Ricard V.] CSIC, UPF, Inst Biol Evolut, E-
08003 Barcelona, Spain

Reprint Address: Rodriguez-Caso, C, Univ Pompeu Fabra PRBB, ICREA Complex 
Syst Lab, Dr Aiguader 88, Barcelona 08003, Spain.

E-mail Address: carlos.rodriguez at upf.edu
ISSN: 1539-3755
DOI: 10.1103/PhysRevE.82.066115
fulltext: http://pre.aps.org/abstract/PRE/v82/i6/e066115