Dataset Information

Embedding graphs in Lorentzian spacetime.

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.

SUBMITTER: Clough JR

PROVIDER: S-EPMC5673185 | biostudies-literature | 2017

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Embedding graphs in Lorentzian spacetime.

Clough James R JR Evans Tim S TS

PloS one 20171106 11

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 a ...[more]

PMID: 29107967

Similar Datasets

Project description:Periodic space crystals are well established and widely used in physical sciences. Time crystals have been increasingly explored more recently, where time is disconnected from space. Periodic relativistic spacetime crystals on the other hand need to account for the mixing of space and time in special relativity through Lorentz transformation, and have been listed only in 2D. This work shows that there exists a transformation between the conventional Minkowski spacetime (MS) and what is referred to here as renormalized blended spacetime (RBS); they are shown to be equivalent descriptions of relativistic physics in flat spacetime. There are two elements to this reformulation of MS, namely, blending and renormalization. When observers in two inertial frames adopt each other's clocks as their own, while retaining their original space coordinates, the observers become blended. This process reformulates the Lorentz boosts into Euclidean rotations while retaining the original spacetime hyperbola describing worldlines of constant spacetime length from the origin. By renormalizing the blended coordinates with an appropriate factor that is a function of the relative velocities between the various frames, the hyperbola is transformed into a Euclidean circle. With these two steps, one obtains the RBS coordinates complete with new light lines, but now with a Euclidean construction. One can now enumerate the RBS point and space groups in various dimensions with their mapping to the well known space crystal groups. The RBS point group for flat isotropic RBS spacetime is identified to be that of cylinders in various dimensions: mm2 which is that of a rectangle in 2D, (∞/m)m which is that of a cylinder in 3D, and that of a hypercylinder in 4D. An antisymmetry operation is introduced that can swap between space-like and time-like directions, leading to color spacetime groups. The formalism reveals RBS symmetries that are not readily apparent in the conventional MS formulation. Mathematica script is provided for plotting the MS and RBS geometries discussed in the work.

Project description:Link prediction in biomedical graphs has several important applications including predicting Drug-Target Interactions (DTI), Protein-Protein Interaction (PPI) prediction and Literature-Based Discovery (LBD). It can be done using a classifier to output the probability of link formation between nodes. Recently several works have used neural networks to create node representations which allow rich inputs to neural classifiers. Preliminary works were done on this and report promising results. However they did not use realistic settings like time-slicing, evaluate performances with comprehensive metrics or explain when or why neural network methods outperform. We investigated how inputs from four node representation algorithms affect performance of a neural link predictor on random- and time-sliced biomedical graphs of real-world sizes (??6 million edges) containing information relevant to DTI, PPI and LBD. We compared the performance of the neural link predictor to those of established baselines and report performance across five metrics.In random- and time-sliced experiments when the neural network methods were able to learn good node representations and there was a negligible amount of disconnected nodes, those approaches outperformed the baselines. In the smallest graph (??15,000 edges) and in larger graphs with approximately 14% disconnected nodes, baselines such as Common Neighbours proved a justifiable choice for link prediction. At low recall levels (??0.3) the approaches were mostly equal, but at higher recall levels across all nodes and average performance at individual nodes, neural network approaches were superior. Analysis showed that neural network methods performed well on links between nodes with no previous common neighbours; potentially the most interesting links. Additionally, while neural network methods benefit from large amounts of data, they require considerable amounts of computational resources to utilise them.Our results indicate that when there is enough data for the neural network methods to use and there are a negligible amount of disconnected nodes, those approaches outperform the baselines. At low recall levels the approaches are mostly equal but at higher recall levels and average performance at individual nodes, neural network approaches are superior. Performance at nodes without common neighbours which indicate more unexpected and perhaps more useful links account for this.

Dataset Information

Embedding graphs in Lorentzian spacetime.

Publications

Embedding graphs in Lorentzian spacetime.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets