Analysis of centrality measures under differential privacy models

作者：

Highlights：

• Lower bounds on the smooth sensitivity of eigenvector, Laplacian and closeness centrality are provided.

• In general, differentially private computation of these centrality measures based on smooth sensitivity is infeasible or impractical.

• Empirical results show Laplacian centrality to be more accurately computable in real-life and scale-free synthetic graphs than eigenvector and closeness centrality.

摘要

•Lower bounds on the smooth sensitivity of eigenvector, Laplacian and closeness centrality are provided.•In general, differentially private computation of these centrality measures based on smooth sensitivity is infeasible or impractical.•Empirical results show Laplacian centrality to be more accurately computable in real-life and scale-free synthetic graphs than eigenvector and closeness centrality.

论文关键词：Privacy,Graph,Centrality,Differential privacy,Social network

论文评审过程：Received 7 March 2021, Revised 20 July 2021, Accepted 21 July 2021, Available online 9 August 2021, Version of Record 9 August 2021.

论文官网地址：https://doi.org/10.1016/j.amc.2021.126546