提出高效采样算法，揭示网络重构中的不确定性和多种合理解。
Uncertainty quantification and posterior sampling for network reconstruction
- 基于MCMC的后验采样方法，可生成多组合理网络结构。
- 单次迭代仅需O(N log² N)时间，适合大规模稀疏网络。
- 适用于需要评估不确定性与共识的复杂系统建模场景。
网络重构是基于系统元素的行为推断其未观测到的相互作用。该逆问题通常病态，同一观测可能对应多个解。然而，现有统计方法大多只输出单一“点估计”网络，难以表征不确定性或展示结构差异但概率相近的备选方案。本文提出一种高效的马尔可夫链蒙特卡洛（MCMC）算法，用于从重构网络的后验分布中采样，能够揭示给定问题下所有可能解的完整群体，并按合理性加权。该方法通用性强，不依赖特定生成模型；特别适用于大规模稀疏网络，单次迭代时间复杂度为O(N log² N)，优于朴素方法的O(N²)。在多种合成与真实数据案例中验证了其在提供不确定性分析和解的共识方面的有效性，共识提升可显著增强重构准确率。
原文摘要 · Abstract (English)
Network reconstruction is the task of inferring the unseen interactions between elements of a system, based only on their behavior or dynamics. This inverse problem is in general ill-posed, and admits many solutions for the same observation. Nevertheless, the vast majority of statistical methods proposed for this task -- formulated as the inference of a graphical generative model -- can only produce a ``point estimate,'' i.e. a single network considered the most likely. In general, this can give only a limited characterization of the reconstruction, since uncertainties and competing answers cannot be conveyed, even if their probabilities are comparable, while being structurally different. In this work we present an efficient MCMC algorithm for sampling from posterior distributions of reconstructed networks, which is able to reveal the full population of answers for a given reconstruction problem, weighted according to their plausibilities. Our algorithm is general, since it does not rely on specific properties of particular generative models, and is specially suited for the inference of large and sparse networks, since in this case an iteration can be performed in time $O(N\log^2 N)$ for a network of $N$ nodes, instead of $O(N^2)$, as would be the case for a more naive approach. We demonstrate the suitability of our method in providing uncertainties and consensus of solutions (which provably increases the reconstruction accuracy) in a variety of synthetic and empirical cases.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。