P-STM: Privacy-Protected Social Tie Mining of Individual Trajectories

With the prevalence of location-aware devices and applications, enormous volumes of human spatiotemporal trajectories are being produced. It is feasible to estimate the similarity between user movement patterns according to such trajectories, which can be regarded as a potential social tie between users. There are two key research challenges associated with social tie discovery from trajectories: (1) trajectories contain users' accurate locations and releasing such data for social tie discovery raises serious privacy concerns; (2) trajectories are archived as discrete approximations of actual movement patterns using different sampling strategies and rates which are intrinsically heterogeneous. To address these challenges, this paper proposes a Privacy-protected Social Tie Mining (P-STM) approach. It provides a new social tie discovery solution based on the similarity of calibrated trajectories incorporating three key components: (1) a location entropy-based indicative dense region (IDR) mining approach to handle the heterogeneity of trajectories under differential privacy; (2) a private model-based calibration system used to rewrite trajectories using a sanitized IDR set to improve the utility of sanitized trajectories for similarity evaluation; (3) a social tie mining approach to indicate potential social ties between individuals using the similarity trajectories, which aims at finding the acquaintances for users based on solely their local geographical activities. The proposed approach is evaluated using real-world trajectory datasets from location-based social networks.