Papers for
social network platform developers
Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.
Theory explains how network links can be predicted more accurately
A Theoretical Perspective on Link Prediction Heuristics
Abstract: In network analysis, nodes with different degrees are usually weighted differently in tasks such as link prediction. For example, two individuals connected to the same high-degree node (e.g., a celebrity) are often considered less likely to know each other than if they share a low-degree connection. In this paper, we theoretically justify the reasoning behind this heuristic using a graph generation model. In this model, nodes are embedded in a latent metric space, and edges are more likely to form between nearby nodes. We analytically derive degree-based weighting schemes for commonly used link prediction and similarity measures. In particular, we identify the optimal weighting scheme for the Common Neighbors index and extend our analysis to other popular heuristics, including the graph distance. Our theoretical findings align with previous empirical observations, and we further validate them through experiments on both synthetic and real-world networks.
Locally private graph synthesis preserves neighborhood structures better
LDPGraph: Locally Differentially Private Graph Synthesis by Exploiting Neighborhood Structure
Abstract: The widespread application of graph data inevitably brings significant privacy risks, as its unprotected use can lead to the leakage of sensitive information. These risks are particularly acute in the setting with an untrusted curator, where the data remains decentralized and each user only holds the connections to their neighbors. To mitigate such privacy risks, we adopt local differential privacy (LDP) to collect users' private information and generate a synthetic graph. However, existing methods suffer from either excessive noise injection by perturbing the local adjacency lists or significant structural information loss due to the simplistic graph encoding process. To address these issues, we propose LDPGraph, an effective graph synthesis algorithm that takes one step further by exploiting neighborhood structures under LDP. To obtain neighborhood statistics beyond degrees, LDPGraph aggregates a noisy global view from perturbed adjacency lists and combines it with projected local connections to estimate node-level triangle counts. To correct the structural inconsistency caused by separately perturbing degree and triangle count, LDPGraph jointly refines them into feasible degree-triangle targets. To reconstruct a global graph from these estimated targets, LDPGraph adopts a triangle-first strategy that first preserves local clustering structures and then fulfills remaining degree requirements. Extensive experiments on four real-world datasets and multiple commonly used graph metrics validate the superiority of LDPGraph. Source code is available at https://github.com/ZJU-TrustAID/LDPGraph.