Extending Undirected Graph Techniques to Directed Graphs via Category Theory

Sebastian Pardo-Guerra, Vivek Kurien George, Vikash Morar, Joshua Roldan and Gabriel Alex Silva ()
Additional contact information
Sebastian Pardo-Guerra: Department of Bioengineering, University of California San Diego, La Jolla, CA 92037, USA
Vivek Kurien George: Department of Bioengineering, University of California San Diego, La Jolla, CA 92037, USA
Vikash Morar: Department of Bioengineering, University of California San Diego, La Jolla, CA 92037, USA
Joshua Roldan: Department of Bioengineering, University of California San Diego, La Jolla, CA 92037, USA
Gabriel Alex Silva: Department of Bioengineering, University of California San Diego, La Jolla, CA 92037, USA

Mathematics, 2024, vol. 12, issue 9, 1-20

Abstract: We use Category Theory to construct a ‘bridge’ relating directed graphs with undirected graphs, such that the notion of direction is preserved. Specifically, we provide an isomorphism between the category of simple directed graphs and a category we call ‘prime graphs category’; this has as objects labeled undirected bipartite graphs (which we call prime graphs), and as morphisms undirected graph morphisms that preserve the labeling (which we call prime graph morphisms). This theoretical bridge allows us to extend undirected graph techniques to directed graphs by converting the directed graphs into prime graphs. To give a proof of concept, we show that our construction preserves topological features when applied to the problems of network alignment and spectral graph clustering.

Keywords: undirected graphs; directed graphs; spectral clustering; network alignment; category theory (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/9/1357/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/9/1357/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:9:p:1357-:d:1386067

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().