Intrinsic Degree: An Estimator of the Local Growth Rate in Graphs
Intrinsic Degree: An Estimator of the Local Growth Rate in Graphs
复制标题
内在度：图中局部增长率的估计
DOI：
10.1007/978-3-030-02224-2_15
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Stephan Guennemann
中科院分区：
文献类型：
--
作者：
Lorenzo von Ritter;Michael E. Houle;Stephan Guennemann
图中查询节点的邻域大小通常随着到节点的距离呈指数增长，使得邻域搜索即使对于小距离也非常昂贵。因此，估计邻域大小的增长率是一个重要的任务，以确定一个适当的距离，在搜索过程中遍历节点的数量将是可行的。在这项工作中，我们提出了内在度模型，它通过分析原点的无穷小附近来捕获指数函数的增长率。我们进一步推导出一个估计，它允许应用的内在度模型的图形。特别地，我们可以通过观察图中某些查询点的近邻来局部估计邻域大小的增长率。我们评估的估计器的性能，通过人工和真实的网络上的实验。
The neighborhood size of a query node in a graph often grows exponentially with the distance to the node, making a neighborhood search prohibitively expensive even for small distances. Estimating the growth rate of the neighborhood size is therefore an important task in order to determine an appropriate distance for which the number of traversed nodes during the search will be feasible. In this work, we present the intrinsic degree model, which captures the growth rate of exponential functions through the analysis of the infinitesimal vicinity of the origin. We further derive an estimator which allows to apply the intrinsic degree model to graphs. In particular, we can locally estimate the growth rate of the neighborhood size by observing the close neighborhood of some query points in a graph. We evaluate the performance of the estimator through experiments on both artificial and real networks.