Detecting Communities under Differential Privacy

Hiep Nguyen 1 Abdessamad Imine 1 Michaël Rusinowitch 1
1 PESTO - Proof techniques for security protocols
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : Complex networks usually expose community structure with groups of nodes sharing many links with the other nodes in the same group and relatively few with the nodes of the rest. This feature captures valuable information about the organization and even the evolution of the network. Over the last decade, a great number of algorithms for community detection have been proposed to deal with the increasingly complex networks. However, the problem of doing this in a private manner is rarely considered. In this paper, we solve this problem under differential privacy , a prominent privacy concept for releasing private data. We analyze the major challenges behind the problem and propose several schemes to tackle them from two perspectives: input perturbation and algorithm perturbation. We choose Louvain method as the back-end community detection for input perturbation schemes and propose the method LouvainDP which runs Louvain algorithm on a noisy super-graph. For algorithm perturbation, we design ModDivi-sive using exponential mechanism with the modularity as the score. We have thoroughly evaluated our techniques on real graphs of different sizes and verified that ModDivisive steadily gives the best modularity and avg.F1Score on large graphs while LouvainDP outperforms the remaining input perturbation competitors in certain settings.
Type de document :
Communication dans un congrès
Workshop on Privacy in the Electronic Society - WPES 206, Oct 2016, Vienna, Austria. pp.83 - 93, 2016
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01393266
Contributeur : Hiep H. Nguyen <>
Soumis le : lundi 7 novembre 2016 - 14:47:06
Dernière modification le : jeudi 11 janvier 2018 - 06:27:43
Document(s) archivé(s) le : mercredi 8 février 2017 - 12:54:56

Fichier

wpes08-nguyen-non-acm.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01393266, version 1

Collections

Citation

Hiep Nguyen, Abdessamad Imine, Michaël Rusinowitch. Detecting Communities under Differential Privacy. Workshop on Privacy in the Electronic Society - WPES 206, Oct 2016, Vienna, Austria. pp.83 - 93, 2016. 〈hal-01393266〉

Partager

Métriques

Consultations de la notice

401

Téléchargements de fichiers

107