On Random Seeding for Influence Maximization in Differentially Private Graphs: Balancing Privacy and Utility Using Percolation Theory

Influence maximization in social networks is a fundamental problem in network science with applications in viral marketing, information diffusion, and opinion formation. However, privacy concerns pose a significant challenge while designing strategies to maximize the spread of influence. In this paper, we study influence maximization under differential privacy constraints by considering two graph perturbation mechanisms: edge addition and edge addition/ deletion. We demonstrate that random seeding along with carefully crafted graph perturbation mechanisms achieve effective diffusion outcomes while preserving privacy. This approach leverages percolation theory to show that graph perturbation diminishes the value of network information, making random seeding asymptotically comparable to conventional optimization techniques in certain percolation phases. We provide theoretical proofs and experimental validations demonstrating the effectiveness of our approaches. Our methods offer a robust solution to the trade-off between privacy and utility in influence maximization, opening avenues for privacy-preserving strategies in social network analysis.