Spridningen av sociala nät på nätet och den samtidiga anhopningen av användardata ger upphov till livliga debattfrågor om integritet, säkerhet och kontroll. En specifik utmaning är att dela eller offentliggöra anonymiserade data utan att oavsiktligt läcka ut personligt identifierbar information (PII). Tyvärr är det ofta svårt att fastställa att sofistikerade statistiska tekniker, som eventuellt använder ytterligare externa datakällor, inte kan bryta anonymiteten. I detta dokument tar vi hänsyn till ett exempel på detta problem, där föremålet för intresset är strukturen i ett socialt nätverk, dvs. en graf som beskriver användare och deras länkar. Det senaste arbetet visar att anonymisering av nodidentiteter kanske inte är tillräckligt för att hålla nätverket privat: tillgången till nod och länka data från en annan domän, som är korrelerad med det anonymiserade nätverket, har använts för att återidentifiera de anonymiserade noderna. Detta dokument handlar om förhållanden under vilka en sådan avanonymiseringsprocess är möjlig. Vi försöker belysa följande fråga: kan vi anta att ett tillräckligt sparsamt nätverk i sig är anonymt, i den meningen att även med obegränsad beräkningskraft är deanonymisering omöjlig? Vårt tillvägagångssätt är att införa en slumpmässig graf modell för en version av de-anonymisering problem, som parameteriseras av den förväntade nodgrad och en likhet parameter som styr korrelationen mellan två grafer över samma vertex uppsättning. Vi hittar enkla villkor på dessa parametrar avgränsa gränsen för integritet, och visar att den genomsnittliga nodgrad behöver bara växa något snabbare än log n med nätverksstorlek n för noder för att kunna identifieras. Våra resultat har politiska konsekvenser för utbytet av anonymiserad nätverksinformation.
För detta förlitar vi oss på den slumpmässiga grafmodell som införs i REF.
On the privacy of anonymized networks
{'venue': 'KDD', 'journal': None, 'mag_field_of_study': ['Computer Science']}