Compact and Scalable Graph Neighborhood Sketching
Compact and Scalable Graph Neighborhood Sketching
复制标题
DOI：
10.1145/2939672.2939762
复制
发表时间：
2016-08
期刊：
影响因子：
--
通讯作者：
Takuya Akiba;Yosuke Yano
中科院分区：
文献类型：
--
作者：
Takuya Akiba;Yosuke Yano
全距离素描（all-distance sketch， ADS）是近年来出现的一种很有前途的图邻域素描范式。ADS是为图的每个顶点定义的概率数据结构。ads有助于准确估计网络分析中许多有用的指标，并且保证了准确性，并且可以在近线性时间内计算出图中所有顶点的ads。由于这些有用的特性，ADS引起了相当大的关注。然而，ADS的一个关键缺点是它的空间需求，它往往比图本身大得多。在本研究中，我们设计了一种新的图形素描方案，即素描检索捷径（SRS）来解决这个问题。虽然srs比ADS的空间效率高一个数量级，但任何顶点的ADS都可以从srs中快速检索到。检索到的ads可用于估计上述指标，其方法与普通ads完全相同，具有相同的准确性保证。我们在真实网络上的实验证明了sss作为大规模图数据挖掘的实际后端是有用的。
The all-distances sketch (ADS) has recently emerged as a promising paradigm of graph neighborhood sketching. An ADS is a probabilistic data structure that is defined for each vertex of a graph. ADSs facilitate accurate estimation of many useful indicators for network analysis with the guarantee of accuracy, and the ADSs for all the vertices in a graph can be computed in near-linear time. Because of these useful properties, ADS has attracted considerable attention. However, a critical drawback of ADS is its space requirement, which tends to be much larger than that of the graph itself. In the present study, we address this issue by designing a new graph sketching scheme, namely, sketch retrieval shortcuts (SRS). Although SRSs are more space-efficient than ADSs by an order of magnitude, an ADS of any vertex can be quickly retrieved from the SRSs. The retrieved ADSs can be used to estimate the aforementioned indicators in exactly the same manner as with plain ADSs, inheriting the same accuracy guarantee. Our experiments on real-world networks demonstrate the usefulness of SRSs as a practical back-end of large-scale graph data mining.