Clough James R, Evans Tim S
Centre for Complexity Science, Imperial College London, London, United Kingdom.
PLoS One. 2017 Nov 6;12(11):e0187301. doi: 10.1371/journal.pone.0187301. eCollection 2017.
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.
网络分析的几何方法将简单定义的模型与强大的描述能力相结合。在这项工作中，我们提供了一种使用多维缩放（MDS）将有向无环图（DAG）嵌入闵可夫斯基时空的方法。首先，我们将仅为具有黎曼度量特征定义的经典MDS算法推广到任何度量特征的流形。然后，我们使用这种通用方法开发一种算法，该算法利用DAG的因果结构为闵可夫斯基时空中的每个顶点分配空间和时间坐标。如同在量子引力的因果集方法中一样，离散图中的因果联系对应于连续时空中的类时分离。通过计算因果集和随机DAG的简单模型以及真实引用网络的嵌入来证明该方法。我们发现，我们测试的引用网络产生的嵌入比相同大小的随机DAG更准确得多。最后，我们提出了一些在引用分析中的应用，例如使用这种几何方法进行论文推荐、识别缺失引用以及将引用模型拟合到数据。
