Estimating Diffusion Networks: Recovery Conditions, Sample Complexity and Soft-thresholding Algorithm

摘要

Information spreads across social and technological networks,but often the network structures are hidden from us and we onlyobserve the traces left by the diffusion processes, calledcascades. Can we recover the hidden network structuresfrom these observed cascades? What kind of cascades and how manycascades do we need? Are there some network structures whichare more difficult than others to recover? Can we designefficient inference algorithms with provable guarantees?Despite the increasing availability of cascade data and methodsfor inferring networks from these data, a thorough theoreticalunderstanding of the above questions remains largely unexploredin the literature. In this paper, we investigate the networkstructure inference problem for a general family of continuous-time diffusion models using an $ell_1$-regularized likelihoodmaximization framework. We show that, as long as the cascadesampling process satisfies a natural incoherence condition, ourframework can recover the correct network structure with highprobability if we observe $O(d^3 log N)$ cascades, where $d$ isthe maximum number of parents of a node and $N$ is the totalnumber of nodes. Moreover, we develop a simple and efficientsoft-thresholding network inference algorithm which demonstratethe match between our theoretical prediction and empiricalresults. In practice, this new algorithm also outperforms otheralternatives in terms of the accuracy of recovering hiddendiffusion networks. color="gray">