The $\beta$-model is a powerful tool for modeling network generation driven by degree heterogeneity. Its simple yet expressive nature particularly well-suits large and sparse networks, where many network models become infeasible due to computational challenge and observation scarcity. However, existing estimation algorithms for $\beta$-model do not scale up; and theoretical understandings remain limited to dense networks. This paper brings several significant improvements to the method and theory of $\beta$-model to address urgent needs of practical applications. Our contributions include: 1. method: we propose a new $\ell_2$ penalized MLE scheme; we design a novel fast algorithm that can comfortably handle sparse networks of millions of nodes, much faster and more memory-parsimonious than all existing algorithms; 2. theory: we present new error bounds on $\beta$-models under much weaker assumptions than best known results in literature; we also establish new lower-bounds and new asymptotic normality results; under proper parameter sparsity assumptions, we show the first local rate-optimality result in $\ell_2$ norm; distinct from existing literature, our results cover both small and large regularization scenarios and reveal their distinct asymptotic dependency structures; 3. application: we apply our method to large COVID-19 network data sets and discover meaningful results.
翻译:$\ beta$ 模型是建模网络生成的强大工具, 由程度异质驱动。 它简单但明确的性质, 特别是精美的大型和分散的网络, 许多网络模型由于计算方面的挑战和观测稀缺而变得不可行。 然而, 美元贝塔美元模型的现有估算算法并不扩大; 理论理解仍然局限于密集的网络。 本文对 $\ beta$ 模型的方法和理论做了一些重大改进, 以解决实际应用的迫切需要。 我们的贡献包括: 1. 方法: 我们提出一个新的$\ ell_ 2$的罚款 MLE方案; 我们设计了一个新的快速算法, 能够舒适地处理数百万节点的稀少网络, 比所有现有的算法更快和更多的记忆- 差异; 2. 理论: 我们提出的新错误将美元贝塔美元模型与最弱的假设结合到比文献中最著名的结果; 我们还建立了新的下限量和新失敏性常态的正常性结果; 在适当的参数假设下, 我们展示了首个本地率- 最优化的网络应用结果, 以美元为不同的标准格式化的模型。</s>