论文标题
马尔可夫随机几何图（MRGG）：时间动态网络的增长模型
Markov Random Geometric Graph (MRGG): A Growth Model for Temporal Dynamic Networks
论文作者
论文摘要
我们介绍了Markov随机几何图（MRGGS），这是一种时间动态网络的增长模型。它基于马尔可夫潜在空间动态：使用未知的马尔可夫内核在欧几里得球上采样连续的潜在点；并且两个节点与概率连接，具体取决于其潜在的大地测量距离的未知功能。更确切地说，在每个邮票时间$ k $中，我们添加了一个潜在点$ x_k $，通过从前一个$ x_ {k-1} $跳到一个均匀选择的$ y_k $的方向，并从一个未知的分布中绘制的长度$ r_k $。每对节点之间的连接概率等于这两个潜在点之间距离的包络功能。我们为纬度和包络功能的非参数估计提供了理论保证。我们提出了一种有效的算法，该算法基于临时分层集聚聚类方法来实现这些非参数估计任务。作为产品，我们展示了如何使用MRGG来检测成长图中的依赖性结构并解决链接预测问题。
We introduce Markov Random Geometric Graphs (MRGGs), a growth model for temporal dynamic networks. It is based on a Markovian latent space dynamic: consecutive latent points are sampled on the Euclidean Sphere using an unknown Markov kernel; and two nodes are connected with a probability depending on a unknown function of their latent geodesic distance. More precisely, at each stamp-time $k$ we add a latent point $X_k$ sampled by jumping from the previous one $X_{k-1}$ in a direction chosen uniformly $Y_k$ and with a length $r_k$ drawn from an unknown distribution called the latitude function. The connection probabilities between each pair of nodes are equal to the envelope function of the distance between these two latent points. We provide theoretical guarantees for the non-parametric estimation of the latitude and the envelope functions.We propose an efficient algorithm that achieves those non-parametric estimation tasks based on an ad-hoc Hierarchical Agglomerative Clustering approach. As a by product, we show how MRGGs can be used to detect dependence structure in growing graphs and to solve link prediction problems.
