The widespread availability of GPS has opened up a whole new market that provides a plethora of location-based services. Location-based social networks have become very popular as they provide end users like us with several such services utilizing GPS through our devices. However, when users utilize these services, they inevitably expose personal information such as their ID and sensitive location to the servers. Due to untrustworthy servers and malicious attackers with colossal background knowledge, users’ personal information is at risk on these servers. Unfortunately, many privacy-preserving solutions for protecting trajectories have significantly decreased utility after deployment. We have come up with a new trajectory privacy protection solution that contraposes the area of interest for users. Firstly, Staying Points Detection Method based on Temporal-Spatial Restrictions (SPDM-TSR) is an interest area mining method based on temporal-spatial restrictions, which can clearly distinguish between staying and moving points. Additionally, our privacy protection mechanism focuses on the user’s areas of interest rather than the entire trajectory. Furthermore, our proposed mechanism does not rely on third-party service providers and the attackers’ background knowledge settings. We test our models on real datasets, and the results indicate that our proposed algorithm can provide a high standard privacy guarantee as well as data availability.

A public-private-graph (pp-graph) is developed to model social networks with hidden relationships, and it consists of one public graph in which edges are visible to all users, and multiple private graphs in which edges are only visible to its endpoint users. In contrast with conventional graphs where the edges can be visible to all users, it lacks accurate indexes to evaluate the importance of a vertex in a pp-graph. In this paper, we first propose a novel concept, public-private-core (pp-core) number based on the k-core number, which integrally considers both the public graph and private graphs of vertices, to measure how critical a user is. We then give an efficient algorithm for the pp-core number computation, which takes only linear time and space. Considering that the graphs can be always evolving over time, we also present effective algorithms for pp-core maintenance after the graph changes, avoiding redundant re-computation of pp-core number. Extension experiments conducted on real-world social networks show that our algorithms achieve good efficiency and stability. Compared to recalculating the pp-core numbers of all vertices, our maintenance algorithms can reduce the computation time by about 6–8 orders of magnitude.