Embedding graphs in Lorentzian spacetime

• Published in: PloS one 2017-11, Vol.12 (11), p.e0187301-e0187301
• Main Authors: Clough, James R, Evans, Tim S
• Format: Article
• Language: English
• Subjects: Algorithms; Citation analysis; Computer and Information Sciences; Computer Graphics; Computer Simulation; Embedding; Geometry; Graph theory; Graphs; Gravitation; Gravity; Mathematics; Multidimensional scaling; Network analysis; Neurosciences; Physical Sciences; Physics; Proteins; Quantum gravity; Research and Analysis Methods; Spacetime; Wireless networks
• ISSN: 1932-6203; 1932-6203
• DOI: 10.1371/journal.pone.0187301

Geometric approaches to network analysis combine simply defined models with great descriptive power. In this work we provide a method for embedding directed acyclic graphs (DAG) into Minkowski spacetime using Multidimensional scaling (MDS). First we generalise the classical MDS algorithm, defined only for metrics with a Riemannian signature, to manifolds of any metric signature. We then use this general method to develop an algorithm which exploits the causal structure of a DAG to assign space and time coordinates in a Minkowski spacetime to each vertex. As in the causal set approach to quantum gravity, causal connections in the discrete graph correspond to timelike separation in the continuous spacetime. The method is demonstrated by calculating embeddings for simple models of causal sets and random DAGs, as well as real citation networks. We find that the citation networks we test yield significantly more accurate embeddings that random DAGs of the same size. Finally we suggest a number of applications in citation analysis such as paper recommendation, identifying missing citations and fitting citation models to data using this geometric approach.