标题： 关于扩散网络结构恢复的信息论下界 显示英文标题

标题： Information-Theoretic Lower Bounds for Recovery of Diffusion Network Structures

摘要： 我们研究了正确恢复扩散网络结构的样本复杂度的信息论下界。 我们介绍了一个基于独立级联模型的离散时间扩散模型，在该模型中，对于节点数为$p$的有向图，每个节点最多有$k$个父节点，我们得到了一个阶数为$\Omega(k \log p)$的下界。 接下来，我们引入了一个连续时间扩散模型，在该模型中获得了相似的阶数为$\Omega(k \log p)$的下界。 我们的结果显示 Pouget-Abadie 等人的算法在离散时间框架下是统计最优的。 我们的工作也提出了是否有可能设计出针对连续时间框架下的最优算法的问题。 显示英文摘要

摘要： We study the information-theoretic lower bound of the sample complexity of the correct recovery of diffusion network structures. We introduce a discrete-time diffusion model based on the Independent Cascade model for which we obtain a lower bound of order $\Omega(k \log p)$, for directed graphs of $p$ nodes, and at most $k$ parents per node. Next, we introduce a continuous-time diffusion model, for which a similar lower bound of order $\Omega(k \log p)$ is obtained. Our results show that the algorithm of Pouget-Abadie et al. is statistically optimal for the discrete-time regime. Our work also opens the question of whether it is possible to devise an optimal algorithm for the continuous-time regime.