Nous étudions la détection de communautés dans des modèles de blocs stochastiques sous une protection de la vie privée différentielle au niveau des nœuds, une notion stricte qui protège la participation d'un individu ainsi que tous ses arêtes incidentes. Ce cadre est substantiellement plus difficile que la détection de communautés privée au niveau des arêtes, car modifier un seul nœud peut affecter linéairement de nombreuses observations. Sur le plan algorithmique, nous analysons un estimateur privé des nœuds basé sur le mécanisme exponentiel combiné à un lemme d'extension, et montrons que la récupération exacte reste réalisable. Dans le régime standard clairsemé avec un degré moyen logarithmique et un nombre fixe de communautés, nos résultats impliquent qu'un budget de confidentialité logarithmique suffit pour obtenir des garanties de récupération non triviales. Du côté de la borne inférieure, nous montrons que cette échelle logarithmique est en fait inévitable : toute méthode purement privée au niveau des nœuds doit échouer à atteindre une erreur de récupération exacte de taille polynomialement petite, ou un décalage attendu de taille polynomialement petite, à moins que le budget de confidentialité ne soit au moins de cet ordre. De plus, dans le régime de budgets de confidentialité super-logarithmiques, nos bornes supérieure et inférieure fournissent une caractérisation à deux termes concordante du risque minimax, avec un terme régi par le signal statistique non privé et l'autre par le budget de confidentialité ; ceux-ci correspondent à des constantes universelles dans les exposants. Au total, nos résultats identifient un coût de confidentialité logarithmique inhérent dans la détection de communautés privées au niveau des nœuds, absent sous la confidentialité différentielle au niveau des arêtes, et fournissent une caractérisation précise du compromis entre la confidentialité des nœuds et la récupération des SBM.
Klopp et al. (Fri,) ont étudié cette question.