Análisis de gráficos con privacidad diferencial

El análisis de grafos con privacidad diferencial ^{[ 1 ]} estudia algoritmos para calcular estadísticas precisas de grafos preservando la privacidad diferencial . Estos algoritmos se utilizan para datos representados en forma de grafo, donde los nodos corresponden a individuos y las aristas a relaciones entre ellos. Por ejemplo, las aristas podrían corresponder a amistades, relaciones sexuales o patrones de comunicación. Una entidad que recopiló datos confidenciales del grafo puede procesarlos mediante un algoritmo con privacidad diferencial y publicar el resultado. El objetivo del análisis de grafos con privacidad diferencial es diseñar algoritmos que calculen información global precisa sobre los grafos, preservando la privacidad de los individuos cuyos datos se almacenan en ellos.

La privacidad diferencial impone una restricción al algoritmo. Intuitivamente, requiere que el algoritmo tenga aproximadamente la misma distribución de salida para entradas vecinas. Si la entrada es un grafo, existen dos nociones naturales de entradas vecinas: vecinos de arista y vecinos de nodo, que dan lugar a dos variantes naturales de privacidad diferencial para datos de grafos.

Sea ε un número real positivo y${\displaystyle {\mathcal {A}}}$ser un algoritmo aleatorio que toma un grafo como entrada y devuelve una salida de un conjunto${\displaystyle {\mathcal {O}}}$El algoritmo${\displaystyle {\mathcal {A}}}$es${\displaystyle \epsilon }$-privacidad diferencial si, para todos los grafos vecinos${\displaystyle G_{1}}$y${\displaystyle G_{2}}$ y todos los subconjuntos${\displaystyle S}$de${\displaystyle {\mathcal {O}}}$,

donde la probabilidad se toma sobre la aleatoriedad utilizada por el algoritmo.

El primer algoritmo de privacidad diferencial de aristas fue diseñado por Nissim, Raskhodnikova y Smith. ^{[ 2 ]} La distinción entre privacidad diferencial de aristas y nodos fue discutida por primera vez por Hay, Miklau y Jensen. ^{[ 3 ]} Sin embargo, pasaron varios años antes de que se publicaran los primeros algoritmos de privacidad diferencial de nodos en Blocki et al., ^{[ 4 ]} Kasiviswanathan et al., ^{[ 5 ]} y Chen y Zhou. ^{[ 6 ]} En los tres artículos, los algoritmos son para liberar una sola estadística, como un recuento de triángulos o recuentos de otros subgrafos. Raskhodnikova y Smith proporcionaron el primer algoritmo de privacidad diferencial de nodos para liberar un vector, específicamente, el recuento de grados y la distribución de grados. ^{[ 7 ]}