DeMEtRIS: Counting (near)-Cliques by Crawling
Suman K. Bera, Jayesh Choudhari, Shahrzad Haddadan, Sara Ahmadian · 2023
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.