Furthermore, we develop a framework for computing the quantiles of essentially any (reasonable) function $f$ of vertices/edges of the graph. Using this framework, we can estimate many health measures of social graphs such as the clustering coefficients and the average degree, where the verifier performs only a small number of queries to the graph.
Using the Fiat-Shamir paradigm, we are able to transform the above protocols to a non-interactive argument in the random oracle model. The result is that social media companies (e.g., Facebook, Twitter, etc.) can publish, once and for all, a short proof for the size or health of their social network. This proof can be publicly verified by any single user using a small number of queries to the graph.
Category / Keywords: foundations / interactive proofs; social graphs; succinct arguments Date: received 15 Nov 2020 Contact author: eylony at gmail com Available format(s): PDF | BibTeX Citation Version: 20201115:121551 (All versions of this report) Short URL: ia.cr/2020/1433