Analyse privée de la structure des graphes

Nous présentons des algorithmes efficaces pour publier des statistiques utiles sur les données de graphes tout en fournissant des garanties de confidentialité rigoureuses. Nos algorithmes fonctionnent sur des ensembles de données qui consistent en des relations entre individus, telles que des liens sociaux ou des communications par email. Les algorithmes satisfont à la vie privée différentielle des arêtes, qui exige essentiellement que la présence ou l'absence de toute relation particulière soit cachée. Nos algorithmes produisent des réponses approximatives à des requêtes de comptage de sous-graphes. Étant donné un graphe de requête H, par exemple, un triangle, un k-étoile ou un k-triangle, l'objectif est de retourner le nombre de copies isomorphes induites par les arêtes de H dans le graphe d'entrée. Le cas particulier des triangles a été considéré par Nissim, Raskhodnikova et Smith (STOC 2007), et une enquête plus générale sur des graphes de requêtes arbitraires a été initiée par Rastogi, Hay, Miklau et Suciu (PODS 2009). Nous étendons l'approche de NRS à une nouvelle classe de statistiques, à savoir, les requêtes k-étoiles. Nous proposons également des algorithmes pour les requêtes k-triangle en utilisant une approche différente, basée sur la sensibilité locale d'ordre supérieur. Pour les statistiques de graphe spécifiques que nous considérons (c'est-à-dire, k-étoiles et k-triangles), nous améliorons significativement le travail de RHMS : nos algorithmes satisfont à une notion plus forte de confidentialité, qui ne dépend pas d'une distribution antérieure particulière sur les données, et ajoutent moins de bruit aux réponses avant de les publier. Nous évaluons la précision de nos algorithmes à la fois théoriquement et empiriquement, en utilisant une variété d'ensembles de données réelles et synthétiques. Nous donnons des conditions explicites et simples sous lesquelles ces algorithmes ajoutent une petite quantité de bruit. Nous fournissons également une analyse du cas moyen dans le modèle de graphe aléatoire Erdős-Rényi-Gilbert G(n,p). Enfin, nous donnons des résultats de complexité indiquant que l'approche utilisée par NRS pour les triangles ne peut pas être facilement étendue aux k-triangles (justifiant ainsi notre développement d'une nouvelle approche algorithmique).