Robust Reconstruction of Barabasi-Albert Networks in the Broadcast Congested Clique Model

摘要

In the broadcast version of the congested clique model, n nodes communicate in synchronous rounds by writing O(log n)-bit messages on a whiteboard, which is visible to all of them. The joint input to the nodes is an undirected n-node graph G, with node i receiving the list of its neighbors in G. Our goal is to design a protocol at the end of which the information contained in the whiteboard is enough for reconstructing G. It has already been shown that there is a one-round protocol for reconstructing graphs with bounded degeneracy. The main drawback of that protocol is that the degeneracy m of the input graph G must be known a priori by the nodes. Moreover, the protocol fails when applied to graphs with degeneracy larger than m. In this article, we address this issue by looking for robust reconstruction protocols, that is, protocols which always give the correct answer and work efficiently when the input is restricted to a certain class. We introduce a very simple, two-round protocol that we call Robust-Reconstruction. We prove that this protocol is robust for reconstructing the class of Barabasi-Albert trees with (expected) message size O(log n). Moreover, we present computational evidence suggesting that Robust-Reconstruction also generates logarithmic size messages for arbitrary Barabasi-Albert networks. Finally, we stress the importance of the preferential attachment mechanism (used in the construction of Barabasi-Albert networks) by proving that Robust-Reconstruction does not generate short messages for random recursive trees.