Reconstruction of geometric random graphs with the Simple algorithm

Research output: Working paper

20 Downloads (Pure)

Abstract

Graph reconstruction can efficiently detect the underlying topology of massive networks such as the Internet. Given a query oracle and a set of nodes, the goal is to obtain the edge set by performing as few queries as possible. An algorithm for graph reconstruction is the Simple algorithm (Mathieu & Zhou, 2023), which reconstructs bounded-degree graphs in Õ (n^3/2) queries. We extend the use of this algorithm to the class of geometric random graphs with connection radius r∼n^k, with diverging average degree. We show that for this class of graphs, the query complexity is Õ (n^{2k+1}) when k > 3/20. This query complexity is up to a polylog(n) term equal to the number of edges in the graph, which means that the reconstruction algorithm is almost edge-optimal. We also show that with only n^{1+o(1)} queries it is already possible to reconstruct at least 75% of the non-edges of a geometric random graph, in both the sparse and dense setting. Finally, we show that the number of queries is indeed of the same order as the number of edges on the basis of simulations.
Original languageEnglish
PublisherArXiv.org
DOIs
Publication statusPublished - 26 Jul 2024

Fingerprint

Dive into the research topics of 'Reconstruction of geometric random graphs with the Simple algorithm'. Together they form a unique fingerprint.

Cite this