Open Problem: Finding Good Cascade Sampling Processes for the Network Inference Problem

Abstract

Information spreads across social and technological networks, but often the network structures are hidden and we only observe the traces left by the diffusion processes, called cascades. It is known that, under a popular continuous-time diffusion model, as long as the model parameters satisfy a natural incoherence condition, it is possible to recover the correct network structure with high probability if we observe O(d^3 \log N) cascades, where d is the maximum number of parents of a node and N is the total number of nodes. However, the incoherence condition depends, in a non-trivial way, on the source (node) distribution of the cascades, which is typically unknown. Our open problem is whether it is possible to design an active algorithm which samples the source locations in a sequential manner and achieves the same or even better sample complexity, e.g., o(d_i^3 \log N), than previous work.