Att skydda individers integritet i grafstrukturerade data samtidigt som man gör korrekta versioner av tillgängliga data är ett av de mest utmanande problemen i dataintegritet. De flesta ansträngningar hittills för att utföra denna data release hamnar fast i komplexitet, överväldiga signalen med buller, och är inte effektiva för användning i praktiken. I detta dokument introducerar vi en ny metod som garanterar olika privatliv. Den anger en sannolikhetsfördelning över möjliga utgångar som noga definieras för att maximera verktyget för den givna inmatningen, samtidigt som den nödvändiga sekretessnivån tillhandahålls. Distributionen är utformad för att bilda en "ladder", så att varje utgång uppnår den högsta "rung" (maximal sannolikhet) jämfört med mindre föredragna utgångar. Vi visar hur vår stege ram kan tillämpas på problem med att räkna antalet förekomster av subgrafer, ett viktigt mål i grafanalys, och ger algoritmer vars kostnad är jämförbar med den för beräkning av räkningen exakt. Vår experimentella studie bekräftar att vår metod överträffar befintliga metoder för att räkna trianglar och stjärnor i form av noggrannhet, och ger lösningar för vissa problem för vilka ingen effektiv metod tidigare var känd. Resultaten av våra algoritmer kan användas för att uppskatta parametrarna för lämpliga grafmodeller, vilket gör det möjligt att ta prover på syntetiska grafer.
Zhang m.fl. I REF föreslås en stege för att privat räkna antalet förekomster av subgrafer.
Private Release of Graph Statistics using Ladder Functions
{'venue': "SIGMOD '15", 'journal': None, 'mag_field_of_study': ['Computer Science']}