Robust reconstruction of Barabási‐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 R obust‐ R econstruction . We prove that this protocol is robust for reconstructing the class of Barabási‐Albert trees with (expected) message size O ( log n ) . Moreover, we present computational evidence suggesting that R obust‐Reconstruction also generates logarithmic size messages for arbitrary Barabási‐Albert networks. Finally, we stress the importance of the preferential attachment mechanism (used in the construction of Barabási‐Albert networks) by proving that R obust‐Reconstruction does not generate short messages for random recursive trees. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 67(1), 82–91 2016