Anonymisation des graphiques de réseaux sociaux pondérés

La popularité croissante des réseaux sociaux a lancé un domaine de recherche fécond dans l'extraction d'informations et le data mining. Bien que cette analyse puisse faciliter une meilleure compréhension des phénomènes sociologiques, comportementaux et d'autres phénomènes intéressants, il existe une préoccupation croissante quant à la violation de la vie privée personnelle, nécessitant ainsi des techniques d'anonymisation efficaces. Dans cet article, nous considérons l'anonymisation des poids des arêtes dans les graphiques sociaux. Notre approche construit un modèle de programmation linéaire (PL) qui préserve les propriétés du graphique qui sont exprimables sous forme de fonctions linéaires des poids des arêtes. Ces propriétés forment les bases de nombreux algorithmes importants en théorie des graphes tels que les parcours les plus courts, les k-plus proches voisins, l'arbre couvrant minimal, etc. Des solveurs PL standard peuvent alors être utilisés pour trouver des solutions au modèle résultant où la solution calculée constitue les poids dans le graphique anonymisé. Comme preuve de concept, nous choisissons le problème des parcours les plus courts et évaluons expérimentalement les techniques proposées en utilisant des ensembles de données réels des réseaux sociaux.