Dual-Granularity Local Differential Privacy for Secure Distributed Graph Publishing in Decentralized Network Systems

Abstract

Decentralized social, interaction, and edge-assisted graphs are commonly stored as local neighbor views rather than as a trusted centralized graph, making privacy-preserving collection and useful graph publication difficult. This paper presents DDP-DGP, an integrative dual-granularity local differential privacy framework for undirected and unweighted graphs. Each user perturbs coarse-grained degree information with a full-support, boundary-corrected random-jump mechanism and perturbs fine-grained neighbor indicators with bitwise randomized response. The fine-grained budget is explicitly divided across the |V|-1 indicators, providing a whole-neighbor-list guarantee by sequential composition; a degree-calibrated sampling rule then suppresses randomized-response densification. The publisher uses only privatized reports: inconsistent endpoint reports are reconciled probabilistically, communities are extracted from the privatized adjacency matrix, intra-community edges are generated with clipped Chung-Lu probabilities, and inter-community edges are sampled from counts computed exclusively from privatized data. The contribution is therefore positioned as a privacy-preserving integration and calibration strategy rather than a new differential-privacy primitive. Experiments on four public graph datasets evaluate degree distribution, modularity, eigenvector centrality, and average path length. The displayed results indicate improved structural fidelity for DDP-DGP under the tested privacy budgets.