Privacy-preserving algorithm based on vulnerable nodes for social relationships

In the contemporary era, online social networks have become the prevalent medium for interpersonal interactions, encompassing a multitude of virtual social relationships. To prevent attackers from inferring more sensitive information through social relationships, numerous researchers have devised privacy protection methodologies tailored to these social relationships. However, most of research achievements have tended to overlook considerations pertaining to algorithmic efficiency and the delicate balance between privacy and utility. To address this issue, we first identify vulnerable nodes within social networks using two indicators, namely, the Marchenko–Pastur law rate and the mean spectral radius. This approach aims to enhance algorithm efficiency. Furthermore, we propose a privacy-preserving algorithm based on vulnerable nodes, PPVN, which classifies the friendship links associated with vulnerable nodes into three distinct levels, thereby ensuring precise safeguarding of social relationship privacy while striking an optimal equilibrium between privacy and structural utility. To bolster privacy safeguards, we develop a replacement index θ, designed explicitly to preclude replaced friendship links from evolving into newly sensitive links. Empirical findings substantiate the remarkable efficacy of the PPVN algorithm in preserving user privacy while concurrently upholding data utility. Compared with other privacy-preserving methods, the PPVN algorithm demonstrates superior privacy protection within the shortest computational timeframe.