Locally Differentially Private $k$-Triangle Counting in Real-Time Social Graph

Social networks are changing in real-time, and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$ k $</tex-math></inline-formula>-triangle counting as a fundamental task in graph analysis is useful for finding meaningful connection patterns in these dynamical graphs. However, the dynamical graphs and the number of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$ k $</tex-math></inline-formula>-triangles therein both are sensitive and imply users’ private information. The lasted works applied Local Differential Privacy (LDP) to the snapshot graph, counting simple statistical information. Nevertheless, these LDP-based works ignored the real-time development of social graphs and did not count more complex statistics, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$ k $</tex-math></inline-formula>-triangle. To this end, we propose a <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">l</u>oc<underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">a</u>lly differentially <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</u>rivate <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</u>-triangles counting in r<underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">e</u>al-time social graph, namely <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathtt{LAPKE}$</tex-math></inline-formula> that is the first work to provide edge LDP and guarantee a lower upper bound on the estimation error of the number of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$ k $</tex-math></inline-formula>-triangles for dynamical graph models. Thereafter, to further reduce the estimation error, we propose <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathtt{LAPKE^{+}}$</tex-math></inline-formula> and its extension <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathtt{LAPKE^{++}}$</tex-math></inline-formula> that do not require a large number of users’ efforts and synchronization. The main intuition of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathtt{LAPKE}$</tex-math></inline-formula>, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathtt{LAPKE^{+}}$</tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathtt{LAPKE^{++}}$</tex-math></inline-formula> is sampling <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$ k $</tex-math></inline-formula> or 2 disjoint users in real-time social graph to construct the key substructure <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$ k $</tex-math></inline-formula>-wedge of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$ k $</tex-math></inline-formula>-triangle, which minimizes the estimation error while preserving users’ private information. Moreover, we theoretically prove the lower upper bound on the estimation error of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$ k $</tex-math></inline-formula>-triangle for dynamical graphs <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathtt{LAPKE}$</tex-math></inline-formula>, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathtt{LAPKE^{+}}$</tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathtt{LAPKE^{++}}$</tex-math></inline-formula> provide. Finally, the extensive experiment results on three real-world datasets and one synthetic dataset validate the superior performance of the proposed three algorithms compared with three latest existing methods.