Vi presenterar effektiva algoritmer för att släppa användbar statistik om grafdata samtidigt som vi ger rigorösa sekretessgarantier. Våra algoritmer arbetar med dataset som består av relationer mellan individer, såsom sociala band eller e-postkommunikation. Algoritmerna tillgodoser kant differential integritet, vilket i huvudsak kräver att närvaron eller frånvaron av någon särskild relation döljs. Våra algoritmer ger ungefärliga svar på subgrafräkningsförfrågningar. Med tanke på en frågekurva H, till exempel en triangel, k-stjärna eller k-triangel, är målet att returnera antalet kantframkallade isomorfa kopior av H i inmatningskurvan. Det speciella fallet med trianglar övervägdes av Nissim et al. [2007] och en mer allmän undersökning av godtyckliga frågediagram inleddes av Rastogi et al. Detta beslut träder i kraft dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning. Vi utvidgar Nissim et al:s tillvägagångssätt. till en ny statistikklass, nämligen k-star-frågor. Vi ger också algoritmer för k-triangelfrågor med ett annat tillvägagångssätt baserat på den högre ordningens lokala känslighet. För den specifika grafstatistik vi anser (dvs. k-stjärnor och k-trianglar), förbättrar vi avsevärt arbetet i Rastogi et al.: våra algoritmer uppfyller en starkare uppfattning om integritet och lägga mindre buller till svaren innan du släpper dem. Vi utvärderar noggrannheten hos våra algoritmer både teoretiskt och empiriskt, med hjälp av en mängd verkliga och syntetiska dataset. Vi ger tydliga, enkla villkor under vilka dessa algoritmer lägger till en liten mängd buller. Vi tillhandahåller också den genomsnittliga analysen i Erdős-Rényi-Gilbert G(n, p) slumpmässiga grafmodellen. Slutligen ger vi hårdhet resultat som indikerar att närma sig Nissim et al. som används för trianglar kan inte enkelt utvidgas till k-trianglar (därför att motivera vår utveckling av en ny algoritmisk strategi).
Mer nyligen, Karwa et al. REF föreslår algoritmer för att ge ungefärliga svar på subgraph counting-frågor, dvs. med tanke på en frågekurva H (t.ex. En triangel, en k-stjärna), som returnerar antalet kantframkallade isomorfa kopior av H i ingångsgrafen.
Private Analysis of Graph Structure
{'venue': 'TODS', 'journal': None, 'mag_field_of_study': ['Computer Science']}