Exploration d'un graphe aléatoire par des méthodes RDS
| Autor: | Vo, Thi Phuong Thuy |
|---|---|
| Přispěvatelé: | Université Sorbonne Paris Nord, Université Gustave Eiffel, Jean-Stéphane Dhersin, Viet Chi Tran |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
chaîne de Markov
stochastic approximation expectation-maximization graphon Markov chain central limit theorem exploration du marche aléatoire stochastic block model random walk exploration sampling bias EM approximation stochastique Erdös-Rényi graphe vraisemblance incomplète processus stochastique EM estimation Erdo ̈s-Rényi graph sondage biaisé stochastic processes respondent driven sampling [MATH]Mathematics [math] incomplete likelihood chain-referral survey théorème centrale limite random graph graphe aléatoire |
| Zdroj: | Mathematics [math]. Université Sorbonne Paris Nord, 2020. English |
| Popis: | The study of Respondent Driven Sampling (RDS) is invested for the discovery of a social network of hidden populations. It leads to the study of a Markov chain on a random graph whose vertices represent individuals and whose edges describe the relationships between the people connected. Respondents are asked to list their partners and a certain number of coupons are given to some of the latter. The RDS survey searches for hidden nodes in the population by randomly following the edges of the underlying social network, which allows us to trace the sampled individuals.We consider the normalized process of the reference chain on the Erdo ̈s-Rényi model, then on its generalization, the Stochastic Block Model (SBM) when populations are partitioned into communities. We prove that when the population size is large and the graph is sparse, the normalized stochastic process describing the fraction of the graph discovered behaves like a deterministic curve which is the unique solution of a system of ODEs. In our model, the graph and the random walk are constructed simultaneously. The difficulty lies in handling the heterogeneity of the graph.Furthermore, we are also interested in the problem of recovering statistical informa- tion on a SBM from the subgraph discovered by an exploring random walk (RDS with 1 coupon per interviewee). We consider here the dense case where the random network can be approximated by a graphon. First, we write the probability of the subgraph discovered by the random walk: biases emerge because the hubs and the 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 are unobserved, we use an SAEM (Stochastic approximation of Expectation-Maximization) algorithm to maximize the likelihood. Second, we propose a different estimation strategy using new results by Athreya and Ro ̈llin. It consists in de-biasing the variational EM estimator proposed in Daudin et al. andthat ignores the biases.; L’échantillonage en fonction des répondants (“Respondent Driven Sampling", RDS) peut être utilisé pour découvrir des réseaux sociaux dans des populations cachées. Ceci peut conduire à l’étude d’une chaîne de Markov sur un graphe aléatoire dont les sommets représentent les individus et dont les arêtes décrivent les relations entre les deux personnes qu’elles relient. Les personnes interrogées sont invitées à indiquer leurs partenaires et un certain nombre de coupons sont remis à certaines de ces personnes. Par chaînage on peut ainsi retrouver les noeuds cachés dans la population en suivant au hasard les arêtes du réseau social sous-jacent.Nous considérons un processus renormalisé de la chaîne de référence sur le modèle Erdös-Rényi, puis sur le modèle à blocs stochastiques (“Stochastic Block Model", SBM), qui en est une extension lorsque les populations sont partitionnées en communautés. La difficulté réside dans la gestion de l’hétérogénéité du graphe. Dans notre étude, le graphe et la marche aléatoire sont construits simultanément. Nous démontrons que lorsque la taille de la population est grande et les graphes sparses, le processus aléatoire représentant la fraction du graphe découverte, correctement normalisé, se comporte comme une courbe déterministe qui est la solution unique d’un système d’ODE.Par ailleurs, nous nous intéressons également au problème de récupérer des informa- tions statistiques sur un modèle à bloc stochastique à partir du sous-graphe découvert par une marche aléatoire (correspondant à un RDS à un coupon). Nous considérons ici le cas dense où le réseau aléatoire peut être approché par un graphon. Tout d’abord, nous écrivons la vraisemblance du sous-graphe découvert par la marche aléatoire: des biais émergent car les “hubs” et les types majoritaires sont plus susceptibles d’être échantillonnés. Même dans le cas où les types sont observés, l’estimateur du maximum de vraisemblance n’est plus explicite. Lorsque les types de sommets nesont pas observés, nous utilisons un algorithme SAEM (“Stochastic Approximation version of Expectation-Maximization algorithm”) pour maximiser la vraisemblance. Deuxièmement, nous proposons une stratégie d’estimation différente en utilisant les nouveaux résultats d’Athreya et Röllin. Elle consiste à dé-biaiser l’estimateur EM variationnel proposé par Daudin et al. et qui ignore les biais. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|