Link Prediction in the Stochastic Block Model with Outliers

Abstract : The Stochastic Block Model is a popular model for network analysis in the presence of community structure. However, in numerous examples, the assumptions underlying this classical model are put in default by the behaviour of a small number of outlier nodes such as hubs, nodes with mixed membership profiles, or corrupted nodes. In addition, real-life networks are likely to be incomplete, due to non-response or machine failures. We introduce a new algorithm to estimate the connection probabilities in a network, which is robust to both outlier nodes and missing observations. Under fairly general assumptions, this method detects the outliers, and achieves the best known error for the estimation of connection probabilities with polynomial computation cost. In addition, we prove sub-linear convergence of our algorithm. We provide a simulation study which demonstrates the good behaviour of the method in terms of outliers selection and prediction of the missing links.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas
Contributor : Solenne Gaucher <>
Submitted on : Friday, November 29, 2019 - 3:11:08 PM
Last modification on : Monday, February 10, 2020 - 6:13:49 PM


Files produced by the author(s)


  • HAL Id : hal-02386940, version 1
  • ARXIV : 1911.13122



Solenne Gaucher, Olga Klopp, Geneviève Robin. Link Prediction in the Stochastic Block Model with Outliers. 2019. ⟨hal-02386940⟩



Record views


Files downloads