Maximum Likelihood Estimation of Sparse Networks with Missing Observations
arXiv:1902.10605
Abstract
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.
arXiv commentWe derive a variational approximation to the maximum likelihood estimator of the connection probabilities. We bound the risk of this tractable estimator
References in corpus (14)
- Statistical mechanics of complex networks
- Modularity and community structure in networks
- Link Prediction in Complex Networks: A Survey
- Hierarchical structure and the prediction of missing links in networks
- Missing and spurious interactions and the reconstruction of complex networks
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Matrix estimation by Universal Singular Value Thresholding
- Modeling social networks from sampled data
- Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
- Rate-optimal graphon estimation
- Network histograms and universality of blockmodel approximation
- Finding missing edges in networks based on their community structure
- Optimal Estimation and Completion of Matrices with Biclustering Structures
- Consistency and Asymptotic Normality of Stochastic Block Models Estimators from Sampled Data