Cycle analysis of directed acyclic graphs
File(s)
Published version
Author(s)
Vasiliauskaite, Vaiva
Evans, Tim S
Expert, Paul
Type
Journal Article
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.
Date Issued
2022-06-15
Date Acceptance
2022-02-15
Citation
Physica A: Statistical Mechanics and its Applications, 2022, 596, pp.1-22
ISSN
0378-4371
Publisher
Elsevier BV
Start Page
1
End Page
22
Journal / Book Title
Physica A: Statistical Mechanics and its Applications
Volume
596
Copyright Statement
© 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
License URL
Identifier
https://www.sciencedirect.com/science/article/pii/S0378437122001340?via%3Dihub
Subjects
cs.SI
cs.SI
physics.app-ph
Fluids & Plasmas
0102 Applied Mathematics
0105 Mathematical Physics
0206 Quantum Physics
Publication Status
Published
Article Number
127097
Date Publish Online
2022-02-25