El análisis diferencialmente privado de gráficos [1] estudia algoritmos para calcular estadísticas gráficas precisas al tiempo que se preserva la privacidad diferencial . Dichos algoritmos se utilizan para datos representados en forma de gráfico donde los nodos corresponden a individuos y los bordes corresponden a relaciones entre ellos. Por ejemplo, las aristas podrían corresponder a amistades, relaciones sexuales o patrones de comunicación. Una parte que recopiló datos de gráficos confidenciales puede procesarlos utilizando un algoritmo diferencialmente privado y publicar la salida del algoritmo. El objetivo del análisis diferencialmente privado de los gráficos es diseñar algoritmos que calculen información global precisa sobre los gráficos al tiempo que preservan la privacidad de las personas cuyos datos se almacenan en el gráfico.
Variantes
La privacidad diferencial impone una restricción al algoritmo. Intuitivamente, requiere que el algoritmo tenga aproximadamente la misma distribución de salida en las entradas vecinas. Si la entrada es un gráfico, hay dos nociones naturales de entradas vecinas, vecinos de borde y vecinos de nodo, que producen dos variantes naturales de privacidad diferencial para los datos de gráficos.
Sea ε un número real positivo yser un algoritmo aleatorio que toma un gráfico como entrada y devuelve una salida de un conjunto. El algoritmo es -diferencialmente privado si, para todos los gráficos vecinos y y todos los subconjuntos de ,
donde la probabilidad se toma sobre la aleatoriedad utilizada por el algoritmo.
Privacidad diferencial de borde
Dos gráficos son vecinos de borde si difieren en un borde. Un algoritmo es-edge-diferencialmente privado si, en la definición anterior, se utiliza la noción de vecinos de borde. Intuitivamente, un algoritmo de borde diferencialmente privado tiene distribuciones de salida similares en cualquier par de gráficos que difieran en un borde, protegiendo así los cambios en los bordes del gráfico.
Privacidad diferencial de nodo
Dos gráficos son vecinos de nodo si se puede obtener uno del otro eliminando un nodo y sus bordes adyacentes. Un algoritmo es-nodo-diferencialmente privado si, en la definición anterior, se utiliza la noción de vecinos de nodo. Intuitivamente, un algoritmo diferencialmente privado de un nodo tiene distribuciones de salida similares en cualquier par de gráficos que difieran en uno de los nodos y bordes adyacentes a él, protegiendo así la información perteneciente a cada individuo. La privacidad diferencial de nodo proporciona una protección de privacidad más fuerte que la privacidad diferencial de borde.
Historia de la investigación
El primer algoritmo de borde diferencialmente privado fue diseñado por Nissim, Raskhodnikova y Smith. [2] La distinción entre privacidad diferencial de borde y nodo fue discutida por primera vez por Hay, Miklau y Jensen. [3] Sin embargo, pasaron varios años antes de que se publicaran los algoritmos diferencialmente privados del primer nodo en Blocki et al., [4] Kasiviswanathan et al., [5] y Chen y Zhou. [6] En los tres artículos, los algoritmos son para publicar una única estadística, como un recuento de triángulos o recuentos de otros subgráficos. Raskhodnikova y Smith dieron al primer nodo un algoritmo diferencialmente privado para liberar un vector, específicamente, el recuento de grados y la distribución de grados. [7]
Referencias
- ^ Sofya Raskhodnikova ; Adam Smith (2015). "Análisis diferencialmente privado de gráficos". Kao MY. (Eds) Enciclopedia de algoritmos. Springer, Berlín, Heidelberg . doi : 10.1007 / 978-3-642-27848-8_549-1 .
- ^ Nissim, Kobbi; Raskhodnikova, Sofya ; Smith, Adam (2007). "Suave sensibilidad y muestreo en análisis de datos privados". Actas del Trigésimo Noveno Simposio Anual de ACM sobre Teoría de la Computación - STOC '07 . Nueva York, Nueva York, EE.UU .: ACM Press: 75. doi : 10.1145 / 1250790.1250803 . ISBN 9781595936318.
- ^ Hay, Michael; Li, Chao; Miklau, Gerome; Jensen, David (2009). "Estimación precisa de la distribución de grados de las redes privadas". 2009 Novena Conferencia Internacional IEEE sobre Minería de Datos . IEEE: 169-178. doi : 10.1109 / icdm.2009.11 . ISBN 9781424452422.
- ^ Blocki, Jeremiah; Blum, Avrim; Datta, Anupam; Sheffet, Or (2012). "La transformación de Johnson-Lindenstrauss en sí misma conserva la privacidad diferencial". 53º Simposio Anual de IEEE 2012 sobre los fundamentos de la informática : 410–419. arXiv : 1204.2136 . Código bibliográfico : 2012arXiv1204.2136B . doi : 10.1109 / focs.2012.67 . ISBN 978-0-7695-4874-6.
- ^ Kasiviswanathan, Shiva Prasad; Nissim, Kobbi; Raskhodnikova, Sofya ; Smith, Adam (2013), "Análisis de gráficos con privacidad diferencial de nodo", Teoría de la criptografía , Springer Berlin Heidelberg, págs. 457–476, doi : 10.1007 / 978-3-642-36594-2_26 , ISBN 9783642365935
- ^ Chen, Shixi; Zhou, Shuigeng (2013). "Mecanismo recursivo". Actas de la Conferencia Internacional sobre Gestión de Datos de 2013 - SIGMOD '13 . Nueva York, Nueva York, EE.UU .: ACM Press: 653. doi : 10.1145 / 2463676.2465304 . ISBN 9781450320375.
- ^ Raskhodnikova, Sofya ; Smith, Adam (2016). "Extensiones de Lipschitz para estadísticas de gráficos de nodo privado y el mecanismo exponencial generalizado". 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) . IEEE: 495–504. doi : 10.1109 / focs.2016.60 . ISBN 9781509039333.