Search

Abstract: We present the NetCover algorithm, a method for the reconstruction of networks based on the order of nodes visited by a stochastic branching process. Our algorithm reconstructs a network of minimal size that ensures consistency with the data, and we verify performance on both synthetic and real-world data. We show that, crucially, the neighbourhood of each node may be inferred in turn, with global consistency between network and data achieved through purely local considerations. The resulting optimisation problem for each node can be reduced to a set covering problem, which though NP-hard can be approximated well in practice. We provide theoretical bounds on the performance of the algorithm, before describing an extension to account for noisy data, based on the Minimum Description Length principle. We first demonstrate the utility of our algorithm on synthetic data, generated by an SIR-like epidemiological model. Finally we test our approach on data gathered from the social networking site Twitter, demonstrating that we can extract the underlying social graph by analysing only the content of individual user feeds. [Copyright &y& Elsevier]