Estimating Clustering Coefficient of Multiplex Graphs with Local Differential Privacy

Multiplex graph analysis occupies a prominent position in many real-world applications, such as commodity recommendation, marketing and pandemic tracking. Due to the existence of untrusted data curators, it is in urgent need to design decentralized privacy mechanisms for analyzing multiplex graphs. Local differential privacy(LDP) is an emerging technique for preserving decentralized private data, which has drawn a great deal of attention from academic and industrial fields. The potential of LDP has been proved in various graph analysis tasks in recent researches. However, existing LDP studies may result in insufficient privacy preservation and heavy computation burden for multiplex graphs. In this paper, we introduce an eclectic privacy definition for multiplex graphs. Under this definition, we propose a randomized mechanism, called RALL, to estimate clustering coefficient of multiplex graphs with lower computation cost and higher protection strength. Furthermore, we present a post-processing method to improve the estimation accuracy. The effectiveness and efficiency of RALL mechanism are validated through extensive experiments.