UCL Discovery Stage
UCL home » Library Services » Electronic resources » UCL Discovery Stage

Cycle analysis of Directed Acyclic Graphs

Vasiliauskaite, Vaiva; Evans, Tim S; Expert, Paul; (2022) Cycle analysis of Directed Acyclic Graphs. Physica A: Statistical Mechanics and its Applications , 596 , Article 127097. 10.1016/j.physa.2022.127097. Green open access

[thumbnail of 1-s2.0-S0378437122001340-main.pdf]
Preview
Text
1-s2.0-S0378437122001340-main.pdf - Published Version

Download (1MB) | Preview

Abstract

In this paper, we employ the decomposition of a directed network as an undirected graph plus its associated node meta-data to characterise the cyclic structure found in directed networks by finding a Minimal Cycle Basis of the undirected graph and augmenting its components with direction information. We show that only four classes of directed cycles exist, and that they can be fully distinguished by the organisation and number of source–sink node pairs and their antichain structure. We are particularly interested in Directed Acyclic Graphs and introduce a set of metrics that characterise the Minimal Cycle Basis using the Directed Acyclic Graphs meta-data information. In particular, we numerically show that transitive reduction stabilises the properties of Minimal Cycle Bases measured by the metrics we introduced while retaining key properties of the Directed Acyclic Graph. This makes the metrics a consistent characterisation of Directed Acyclic Graphs and the systems they represent. We measure the characteristics of the Minimal Cycle Bases of four models of transitively reduced Directed Acyclic Graphs and show that the metrics introduced are able to distinguish the models and are sensitive to their generating mechanisms.

Type: Article
Title: Cycle analysis of Directed Acyclic Graphs
Open access status: An open access version is available from UCL Discovery
DOI: 10.1016/j.physa.2022.127097
Publisher version: https://doi.org/10.1016/j.physa.2022.127097
Language: English
Additional information: This work is licensed under a Creative Commons Attribution 4.0 International License. The images or other third-party material in this article are included in the Creative Commons license, unless indicated otherwise in the credit line; if the material is not included under the Creative Commons license, users will need to obtain permission from the license holder to reproduce the material. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/
Keywords: Science & Technology, Physical Sciences, Physics, Multidisciplinary, Physics, Complex systems, Network theory, Data science, Statistics, Minimal Cycle Bases, Directed Acyclic Graphs, Transitive reduction, COMMUNITY STRUCTURE, ALGORITHMS, NETWORKS, COMPUTE
UCL classification: UCL
UCL > Provost and Vice Provost Offices > School of Life and Medical Sciences
URI: https://discovery-pp.ucl.ac.uk/id/eprint/10154887
Downloads since deposit
475Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item