Outlier detection in networks with missing links

Solenne Gaucher, Olga Klopp and Geneviève Robin

Computational Statistics & Data Analysis, 2021, vol. 164, issue C

Abstract: Outliers arise in networks due to different reasons such as fraudulent behaviour of malicious users or default in measurement instruments and can significantly impair network analyses. In addition, real-life networks are likely to be incompletely observed, with missing links due to individual non-response or machine failures. Therefore, identifying outliers in the presence of missing links is a crucial problem in network analysis. A new algorithm is introduced to detect outliers in a network and simultaneously predict the missing links. The proposed method is statistically sound: under fairly general assumptions, this algorithm exactly detects the outliers, and achieves the best known error for the prediction of missing links with polynomial computational cost. The sub-linear convergence of the algorithm is proven, which confirms its computational efficiency. A simulation study is provided, which demonstrates the good behaviour of the algorithm in terms of outlier detection and prediction of the missing links. The method is also illustrated with an application in epidemiology and with the analysis of a political Twitter network. The algorithm is freely available as an R package on the Comprehensive R Archive Network.

Keywords: Outlier detection; Robust network estimation; Missing observations; Link prediction (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0167947321001420
Full text for ScienceDirect subscribers only.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:csdana:v:164:y:2021:i:c:s0167947321001420

DOI: 10.1016/j.csda.2021.107308

Access Statistics for this article

Computational Statistics & Data Analysis is currently edited by S.P. Azen

More articles in Computational Statistics & Data Analysis from Elsevier
Bibliographic data for series maintained by Catherine Liu ().