{"doi":"10.1016/j.physa.2022.127097","title":"Cycle analysis of Directed Acyclic Graphs","abstract":null,"journal":"Physica A: Statistical Mechanics and its Applications","year":2022,"id":56975,"datarank":0.3590502395300517,"base_score":2.0794415416798357,"endowment":2.0794415416798357,"self_citation_contribution":0.31191623125197543,"citation_network_contribution":0.04713400827807628,"self_endowment_contribution":0.31191623125197543,"citer_contribution":0.04713400827807628,"corpus_percentile":null,"corpus_rank":null,"citation_count":7,"citer_count":3,"citers_with_citation_signal":1,"citers_with_endowment":1,"datacite_reuse_total":1,"is_dataset":false,"is_dataset_confidence":null,"is_data_producer":false,"deposit_databanks":null,"is_oa":false,"file_count":0,"downloads":0,"has_version_chain":false,"published_date":null,"fair_score":null,"fair_percentile":null,"algorithm_id":"datarank_citation_only_1hop_v6","ranking_scope":"data_only","authors":[{"id":297146,"name":"Tim S. Evans","orcid":null,"position":1,"is_corresponding":false},{"id":297147,"name":"Paul Expert","orcid":null,"position":2,"is_corresponding":false},{"id":297145,"name":"Vaiva Vasiliauskaite","orcid":"0000-0003-2039-6236","position":0,"is_corresponding":false}],"reference_count":0,"raw_metadata":{"has_enrichment":true,"resolved":true,"title":"Cycle analysis of Directed Acyclic Graphs","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.","is_dataset_classified":null,"base_score":1.3862943611198906,"endowment":1.3862943611198906,"datacite_reuse_total":1,"file_count":0,"downloads":0,"views":0,"has_version_chain":false,"is_dataset":false,"is_oa":false,"pmid":"19910364","pmcid":null,"openalex_id":"https://openalex.org/W3191289342","authors":[],"funders":[{"funder_name":"Horizon 2020","grant_id":"871042","title":"SoBigData++: European Integrated Infrastructure for Social Mining and Big Data Analytics"},{"funder_name":"NIHR Imperial Biomedical Research Centre","grant_id":"NIHR-BRC-P68711","title":null}],"total_grants":2,"fwci":0.3363,"citation_percentile":0.49261347,"influential_citations":1,"citation_trend":[{"year":2024,"count":2},{"year":2025,"count":1}],"oa_status":"hybrid","license":"cc-by","oa_locations":[{"url":"https://doi.org/10.1016/j.physa.2022.127097","host_type":"journal"},{"url":"https://doi.org/10.1016/j.physa.2022.127097","host_type":"HYBRID"},{"url":"https://doi.org/10.1016/j.physa.2022.127097","host_type":"publisher"},{"url":"https://api.elsevier.com/content/article/PII:S0378437122001340?httpAccept=text/xml","host_type":"publisher"},{"url":"https://api.elsevier.com/content/article/PII:S0378437122001340?httpAccept=text/plain","host_type":"publisher"},{"url":"http://hdl.handle.net/20.500.11850/540682","host_type":"repository"},{"url":"http://arxiv.org/abs/2108.02475","host_type":"repository"},{"url":"http://www.sciencedirect.com/science/article/pii/S0378437122001340","host_type":"repository"},{"url":"https://discovery.ucl.ac.uk/id/eprint/10154887/","host_type":"repository"},{"url":"http://hdl.handle.net/10044/1/97886","host_type":"repository"},{"url":"https://doi.org/10.48550/arxiv.2108.02475","host_type":"repository"},{"url":"https://doi.org/10.3929/ethz-b-000540682","host_type":"repository"},{"url":"https://arxiv.org/pdf/2108.02475","host_type":"repository"},{"url":"https://dx.doi.org/10.48550/arxiv.2108.02475","host_type":""},{"url":"https://dx.doi.org/10.3929/ethz-b-000540682","host_type":""},{"url":"https://zbmath.org/7511838","host_type":""},{"url":"https://arxiv.org/abs/2108.02475","host_type":""},{"url":"https://discovery-pp.ucl.ac.uk/id/eprint/10154887/","host_type":""},{"url":"http://dx.doi.org/10.1016/j.physa.2022.127097","host_type":""},{"url":"https://doi.org/https://doi.org/10.1016/j.physa.2022.127097","host_type":""}],"fields_of_study":["Complex Network Analysis Techniques","Graph theory and applications","CO2 Reduction Techniques and Catalysts","Computer Science","Physics","Mathematics","0301 basic medicine","0102 computer and information sciences","01 natural sciences","03 medical and health sciences"],"mesh_terms":[],"keywords":["Directed acyclic graph","Directed graph","Modular decomposition","Feedback arc set","Comparability graph","Computer science","Moral graph","Strongly connected component","Transitive reduction","Theoretical computer science","Antichain","Combinatorics","Mathematics","Graph","Algorithm","Pathwidth","Line graph","Partially ordered set","Voltage graph","FOS: Computer and information sciences","Complex systems","minimal cycle bases","Fluids & Plasmas","FOS: Physical sciences","Applied Physics (physics.app-ph)","Directed Acyclic Graphs","Statistical mechanics, structure of matter","510","Data science","network theory","0102 Applied Mathematics","FOS: Mathematics","0206 Quantum Physics","Social and Information Networks (cs.SI)","0105 Mathematical Physics","Science & Technology","Multidisciplinary","Complex systems; Network theory; Data science; Statistics; Minimal Cycle Bases; Directed Acyclic Graphs; Transitive reduction","Physics","ALGORITHMS","Statistics","Computer Science - Social and Information Networks","Physics - Applied Physics","COMPUTE","004","NETWORKS","Physical Sciences","physics.app-ph","cs.SI","COMMUNITY STRUCTURE"],"sdg_mappings":[],"linked_datasets":[{"doi":"10.48550/arxiv.2108.02475","title":"Cycle Analysis of Directed Acyclic Graphs","publisher":"arXiv","resource_type":"Text"}],"clinical_trials":[],"software_tools":[],"database_accessions":[],"source":"live","citation_network_status":"fetched"},"created_at":"2026-07-18T21:06:14.504805Z","pmid":null,"pmcid":null,"fwci":null,"citation_percentile":null,"influential_citations":0,"oa_status":null,"license":null,"views":0,"total_file_size_bytes":0,"version_count":0,"fair_f":null,"fair_a":null,"fair_i":null,"fair_r":null,"fair_zscore":null,"fair_rationale":null,"fair_model":null,"fair_agent_version":null,"fair_fulltext_source":null,"fair_has_llm":null,"fair_computed_at":null,"clinical_trials":[],"software_tools":[],"db_accessions":[],"linked_datasets":[],"topics":[]}