Social Graph Generation Under Local Differential Privacy Protection

Social networks collect data on users' social relationships to construct social network graphs. Service providers analyze and mine this data to capture business value and enhance revenue. However, untrusted servers pose a risk of user privacy breaches. Local differential privacy (LDP) techniques allow untrusted data aggregators to perform item-based data analysis on distributed private data, such as users' social relationships. Implementing differential privacy protocols in large-scale social networks presents challenges due to the multidimensional structures of user relationships and the need to preserve data utility. The introduction of noise in these methods can lead to significant loss of information entropy. To address this issue, we propose LDP-MSN, an aggregation method designed for relationship preservation in large user social networks operating under LDP. LDP-MSN reduces the dimensionality of large networks through a random projection method while maintaining the similarity between users. This approach allows for user network analysis using the reduced-dimensionality data, preserving similarity and minimizing the effects of noise mechanisms by perturbing the reduced data rather than the original data. Since the downscaled data is sensitive to noise, applying differential privacy techniques can lead to reduced functionality. To counter this, we employ the Rank-1 Singular Multivariate Gaussian (R1SMG) mechanism. This mechanism is more stable and less likely to produce excessive noise that could distort query results, thereby helping to preserve user network relationships. We provide a theoretical proof of the privacy and utility of LDP-MSN and demonstrate its advantages over existing methods using publicly available datasets.