Link Prediction in the Stochastic Block Model with Outliers

Networks are a powerful tool used to analyze complex systems: agents are represented as nodes, and pairwise interactions between agents are recorded as edges between these nodes. Examples of fields of applications include biology, where networks may be used to describe protein-protein interactions; ecology, where they may represent food webs [13] or spatial distributions in crop diversity networks [46]; ethnology, where networks summarize relationships or trades between individuals or communities [40, 36]; sociology, where the recent development of online social networks offers unprecedented possibilities while fostering new challenges [47]. Real-life networks are often modeled as realizations of random graphs or, equivalently, as noisy versions of more structured networks. In this setting, recovering the "noiseless" version of the graph, i.e. estimating the underlying probabilities of interactions between agents, is a key problem that has recently gained considerable attention (see, e.g., [30, 15, 14, 17, 50]). Most methods for recovering structural properties of a network rely on assumptions on the distribution of the underlying random graph. However, in numerous examples, these assumptions are put in default by the behaviour of a small number of individuals, which strongly departs from the behaviour of the majority of agents, introducing outlier profiles. For example, in graphs obtained from survey data, some individuals may be reluctant to participate and for this reason provide false answers; other individuals may even be paid to provide erroneous answers in order to distort the public opinion on a subject [3].