Embedding graphs in Lorentzian spacetime
File(s)journal.pone.0187301(1).pdf (2.95 MB)
Published version
OA Location
Author(s)
Clough, James R
Evans, Tim S
Type
Journal Article
Abstract
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.
Date Issued
2017-11-06
Date Acceptance
2017-10-16
Citation
PLOS ONE, 2017, 12 (11)
ISSN
1932-6203
Publisher
PUBLIC LIBRARY OF SCIENCE
Journal / Book Title
PLOS ONE
Volume
12
Issue
11
Copyright Statement
©
2017
Clough,
Evans.
This is an open
access
article
distributed
under
the terms
of the
Creative
Commons
Attribution
License (https://creativecommons.org/licenses/by/4.0/),
which
permits
unrestricted use, distribution, and
reproduction
in any medium,
provided
the original
author
and source
are credited.
2017
Clough,
Evans.
This is an open
access
article
distributed
under
the terms
of the
Creative
Commons
Attribution
License (https://creativecommons.org/licenses/by/4.0/),
which
permits
unrestricted use, distribution, and
reproduction
in any medium,
provided
the original
author
and source
are credited.
Identifier
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000414424600025&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=1ba7043ffcc86c417c072aa74d649202
Subjects
Science & Technology
Multidisciplinary Sciences
Science & Technology - Other Topics
PARTIAL ORDERS
NETWORKS
HYPERBOLICITY
Publication Status
Published
Article Number
ARTN e0187301
Date Publish Online
2017-11-06