Estimation of dense stochastic block models visited by random walks
This work addresses the challenge of accurate network inference from biased random walk samples, which is incremental but relevant for applications like social network surveys.
The paper tackles the problem of recovering information about a dense stochastic block model from a subgraph sampled by a random walk, motivated by chain-referral surveys. It proposes two estimation strategies, including an SAEM algorithm for unobserved types and a de-biasing method based on recent results, to address biases introduced by the sampling process.
We are interested in recovering information on a stochastic block model from the subgraph discovered by an exploring random walk. Stochastic block models correspond to populations structured into a finite number of types, where two individuals are connected by an edge independently from the other pairs and with a probability depending on their types. We consider here the dense case where the random network can be approximated by a graphon. This problem is motivated from the study of chain-referral surveys where each interviewee provides information on her/his contacts in the social network. First, we write the likelihood of the subgraph discovered by the random walk: biases are appearing since hubs and majority types are more likely to be sampled. Even for the case where the types are observed, the maximum likelihood estimator is not explicit any more. When the types of the vertices is unobserved, we use an SAEM algorithm to maximize the likelihood. Second, we propose a different estimation strategy using new results by Athreya and Roellin. It consists in de-biasing the maximum likelihood estimator proposed in Daudin et al. and that ignores the biases.