Estimating the matrix of connections probabilities is one of the key questions when studying sparse networks. In this work, we consider networks generated under the sparse graphon model and the in-homogeneous random graph model with missing observations. Using the Stochastic Block Model as a parametric proxy, we bound the risk of the maximum likelihood estimator of network connections probabilities , and show that it is minimax optimal. When risk is measured in Frobenius norm, no estimator running in polynomial time has been shown to attain the minimax optimal rate of convergence for this problem. Thus, maximum likelihood estimation is of particular interest as computationally efficient approximations to it have been proposed in the literature and are often used in practice.
翻译:估计连接概率矩阵是研究稀疏网络时的一个关键问题。 在这项工作中,我们考虑到根据稀疏的图形模型和同源随机图模型生成的网络并缺少观测。 使用Stochatic区块模型作为参数替代,我们将网络连接概率最大可能性估计值的风险捆绑起来,并显示这是最优化的。 在根据Frobenius规范衡量风险时,没有显示在多元时间内运行的估算器能够达到这一问题最小最佳趋同率。 因此,由于文献中已经提出了计算效率高的近似值,而且在实践中经常使用,因此最大可能性估算是特别有意义的。