Graphon Estimation from Partially Observed Network Data
This addresses a practical issue in network analysis where full data is often unavailable, offering improved estimation for researchers and practitioners, though it is incremental as it builds on existing NBS.
The paper tackles the problem of estimating the edge-probability matrix from a graphon model when only partially observed network data (overlapping subgraphs) is available, by extending the neighbourhood smoothing (NBS) algorithm to handle missing data, and shows experimentally that this extended NBS achieves significantly smaller error rates and greater robustness compared to standard methods.
We consider estimating the edge-probability matrix of a network generated from a graphon model when the full network is not observed---only some overlapping subgraphs are. We extend the neighbourhood smoothing (NBS) algorithm of Zhang et al. (2017) to this missing-data set-up and show experimentally that, for a wide range of graphons, the extended NBS algorithm achieves significantly smaller error rates than standard graphon estimation algorithms such as vanilla neighbourhood smoothing (NBS), universal singular value thresholding (USVT), blockmodel approximation, matrix completion, etc. We also show that the extended NBS algorithm is much more robust to missing data.