Privacy-preserving and data utility in graph mining
Jordi Casas Roma · TDX (Tesis Doctorals en Xarxa) · 2014
En los ultimos anos, ha sido puesto a disposicion del publico una gran cantidad de los datos con formato de grafo. Incrustado en estos datos hay informacion privada acerca de los usuarios que aparecen en ella. Por lo tanto, los propietarios de datos deben respetar la privacidad de los usuarios antes de liberar los conjuntos de datos a terceros. En este escenario, los procesos de anonimizacion se convierten en un proceso muy importante. Sin embargo, los procesos de anonimizacion introducen, generalmente, algun tipo de ruido en los datos anonimos y tambien en sus resultados en procesos de mineria de datos. Generalmente, cuanto mayor la privacidad, mayor sera el ruido. Por lo tanto, la utilidad de los datos es un factor importante a tener en cuenta en los procesos de anonimizacion. El equilibrio necesario entre la privacidad de datos y utilidad de estos puede mejorar mediante el uso de medidas y metricas para guiar el proceso de anonimizacion, de tal forma que se minimice la perdida de informacion. En esta tesis hemos trabajo los campos de la preservacion de la privacidad del usuario en las redes sociales y la utilidad y calidad de los datos publicados. Un compromiso entre ambos campos es un punto critico para lograr buenos metodos de anonimato, que permitan mejorar los posteriores procesos de mineria de datos. Parte de esta tesis se ha centrado en la utilidad de los datos y la perdida de informacion. En primer lugar, se ha estudiado la relacion entre las medidas de perdida de informacion genericas y las especificas basadas en clustering, con el fin de evaluar si las medidas genericas de perdida de informacion son indicativas de la utilidad de los datos para los procesos de mineria de datos posteriores. Hemos encontrado una fuerte correlacion entre algunas medidas genericas de perdida de informacion (average distance, betweenness centrality, closeness centrality, edge intersection, clustering coefficient y transitivity) y el indice de precision en los resultados de varios algoritmos de clustering, lo que demuestra que estas medidas son capaces de predecir el perturbacion introducida en los datos anonimos. En segundo lugar, se han presentado dos medidas para reducir la perdida de informacion en los procesos de modificacion de grafos. La primera, Edge neighbourhood centrality, se basa en el flujo de informacion de a traves de la vecindad a distancia 1 de una arista especifica. El segundo se basa en el core number sequence y permite conservar mejor la estructura subyacente, mejorando la utilidad de los datos. Hemos demostrado que ambos metodos son capaces de preservar las aristas mas importantes del grafo, manteniendo mejor las propiedades basicas estructurales y espectrales. El otro tema importante de esta tesis ha sido los metodos de preservacion de la privacidad. Hemos presentado nuestro algoritmo de base aleatoria, que utiliza el concepto de Edge neighbourhood centrality para guiar el proceso de modificacion preservando los bordes mas importantes del grafo, logrando una menor perdida de informacion y una mayor utilidad de los datos. Por ultimo, se han desarrollado dos algoritmos diferentes para el k-anonimato en los grafos. En primer lugar, se ha presentado un algoritmo basado en la computacion evolutiva. Aunque este metodo nos permite cumplir el nivel de privacidad deseado, presenta dos inconvenientes: la perdida de informacion es bastante grande en algunas propiedades estructurales del grafo y no es lo suficientemente rapido para trabajar con grandes redes. Por lo tanto, un segundo algoritmo se ha presentado, que utiliza el micro-agregacion univariante para anonimizar la secuencia de grados. Este metodo es cuasi-optimo y se traduce en una menor perdida de informacion y una mejor utilidad de los datos.