Nonparametric link prediction in large scale dynamic networks
Nonparametric link prediction in large scale dynamic networks
复制标题
DOI：
10.1214/14-ejs943
复制
发表时间：
2014-01-01
影响因子：
1.1
通讯作者：
Chakrabarti, Deepayan
中科院分区：
文献类型：
--
作者：
Sarkar, Purnamrita;Chakrabarti, Deepayan
我们提出了一种非参数方法来进行大规模动态网络中的链接预测。我们的模型使用节点对及其局部邻域的基于图的特征来预测这些节点是否会在每个时间步链接。该模型允许图的不同部分进行不同类型的演化（例如，社区的增长或缩小）。我们专注于大规模图，并提出了模型的实现，该模型利用局部敏感哈希来使其能够扩展到大型问题。模拟数据以及五个现实世界动态图的实验表明，我们的表现优于最先进的技术，特别是当存在剧烈波动或非线性时。我们还建立了估计器的理论特性，特别是一致性和弱收敛性，后者利用了 Stein 依赖图方法的详细阐述。
We propose a nonparametric approach to link prediction in large-scale dynamic networks. Our model uses graph-based features of pairs of nodes as well as those of their local neighborhoods to predict whether those nodes will be linked at each time step. The model allows for different types of evolution in different parts of the graph (e.g, growing or shrinking communities). We focus on large-scale graphs and present an implementation of our model that makes use of locality-sensitive hashing to allow it to be scaled to large problems. Experiments with simulated data as well as five real-world dynamic graphs show that we outperform the state of the art, especially when sharp fluctuations or nonlinearities are present. We also establish theoretical properties of our estimator, in particular consistency and weak convergence, the latter making use of an elaboration of Stein's method for dependency graphs.