论文标题
Demetris：计数（接近） - 爬行
DeMEtRIS: Counting (near)-Cliques by Crawling
论文作者
论文摘要
我们研究了图表中大约计数集团和近集团的问题，在该图中，只有通过爬行其顶点才能获得对图的访问。因此，通常只看到其中的一小部分。该模型被称为随机步行模型或邻里查询模型，最近引入了现实生活中的场景，其中整个图形太大而无法整体存储或完全扫描，并且独立进行采样顶点是非平凡的。我们通过随机入射采样引入Demetris：密集的基序估计。此方法为集团和近集团计数提供了可扩展的算法。我们通过严格的数学分析和广泛的实验证明了算法的正确性。我们的理论结果和实验都表明，Demetris仅通过在顶点上爬下亚线性部分来获得高精度估计，因此我们证明了对先前已知的结果的显着改善。
We study the problem of approximately counting cliques and near cliques in a graph, where the access to the graph is only available through crawling its vertices; thus typically seeing only a small portion of it. This model, known as the random walk model or the neighborhood query model has been introduced recently and captures real-life scenarios in which the entire graph is too massive to be stored as a whole or be scanned entirely and sampling vertices independently is non-trivial in it. We introduce DeMEtRIS: Dense Motif Estimation through Random Incident Sampling. This method provides a scalable algorithm for clique and near clique counting in the random walk model. We prove the correctness of our algorithm through rigorous mathematical analysis and extensive experiments. Both our theoretical results and our experiments show that DeMEtRIS obtains a high precision estimation by only crawling a sub-linear portion on vertices, thus we demonstrate a significant improvement over previously known results.
