Directed acyclic graphs (DAGs) are important structures across many disciplines, including mathematics and network science. They are especially useful in modeling causal and hierarchical relationships in a wide variety of applications. The primaryfeatures of a DAG, directedness and acyclicity, are traditionally treated as binary. A graph is either DAG or it is not. Because of this, graphs are not usually interpreted as partially acyclic or partially directed. To address this gap in understanding, weintroduce a framework, consisting of five components, that will provide a continuous measure of DAG-ness. This measure will take into account edge acyclicity, node cyclicity, macro cyclicity, hierarchical flow, and spectral recurrence. The result will provide a more nuanced measure of these features of a DAG and will provide more insight than a simple binary interpretation. As a demonstration, the application of this composite measure on five synthetic graphs will highlight the measure’s ability to distinguish graphs with a higher degree of directedness and acyclicity from graphs that are less DAG-like. We suggest that this characterization of DAG-ness opens new opportunities for interpreting graph properties and similarities, especially in cases where binary classification masks important structural features.
Erik Csikos (Sun,) studied this question.