Outliers Detection in Networks with Missing Links

Abstract

Outliers arise in networks due to different reasons such as fraudulent behavior 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. Identifying outliers in the presence of missing links is therefore a crucial problem in network analysis. In this work, we introduce a new algorithm to detect outliers in a network that simultaneously predicts the missing links. The proposed method is statistically sound: we prove that, under fairly general assumptions, our algorithm exactly detects the outliers, and achieves the best known error for the prediction of missing links with polynomial computation cost. It is also computationally efficient: we prove sub-linear convergence of our algorithm. We provide a simulation study which demonstrates the good behavior of the algorithm in terms of outliers detection and prediction of the missing links. We also illustrate the method with an application in epidemiology, and with the analysis of a political Twitter network. The method is freely available as an R package on the Comprehensive R Archive Network.

References in corpus (20)

• Finding and evaluating community structure in networks
• Stochastic blockmodels and community structure in networks
• High-resolution measurements of face-to-face contact patterns in a primary school
• Missing and spurious interactions and the reconstruction of complex networks
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Modeling social networks from sampled data
• Fast community detection by SCORE
• Mitigation of infectious disease at school: targeted class closure vs school closure
• Crawling Facebook for Social Network Analysis Purposes
• Modeling homophily and stochastic equivalence in symmetric relational data
• Rate-optimal graphon estimation
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Scalable Robust Matrix Recovery: Frank-Wolfe Meets Proximal Methods
• Optimal Estimation and Completion of Matrices with Biclustering Structures
• Link prediction for egocentrically sampled networks
• Improved Complexities of Conditional Gradient-Type Methods with Applications to Robust Matrix Recovery Problems
• Low-rank Interaction with Sparse Additive Effects Model for Large Data Frames
• Link Prediction Under Imperfect Detection: Collaborative Filtering for Ecological Networks
• Maximum Likelihood Estimation of Sparse Networks with Missing Observations
• Graphon Estimation from Partially Observed Network Data