# Travel Trajectory Frequent Pattern Mining Based on Differential Privacy Protection

Authors: Weiya Wang; Geng Yang; Lin Bao; Ke Ma; Hao Zhou; Yunlu Bai
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Now, many application services based on location data have brought a lot of convenience to people’s daily life. However, publishing location data may divulge individual sensitive information. Because the location records about location data may be discrete in the database, some existing privacy protection schemes are difficult to protect location data in data mining. In this paper, we propose a travel trajectory data record privacy protection scheme (TMDP) based on differential privacy mechanism, which employs the structure of a trajectory graph model on location database and frequent subgraph mining based on weighted graph. Time series is introduced into the location data; the weighted trajectory model is designed to obtain the travel trajectory graph database. We upgrade the mining of location data to the mining of frequent trajectory graphs, which can discover the relationship of location data from the database and protect location data mined. In particular, to improve the identification efficiency of frequent trajectory graphs, we design a weighted trajectory graph support calculation algorithm based on canonical code and subgraph structure. Moreover, to improve the data utility under the premise of protecting user privacy, we propose double processes of adding noises to the subgraph mining process by the Laplace mechanism and selecting final data by the exponential mechanism. Through formal privacy analysis, we prove that our TMDP framework satisfiesε-differential privacy. Compared with the other schemes, the experiments show that the data availability of the proposed scheme is higher and the privacy protection of the scheme is effective.


---

## Body

## 1. Introduction

With the rapid development in the field of artificial intelligence and big data technology, data mining and data analysis have become an important tool for researchers to extract useful knowledge from data. Location data is a kind of large-scale and fast-changing location information, which mainly comes from automobile network, mobile devices, and social networks. As an important part of mobile Internet services, location data mining and analysis have brought unprecedented changes and convenience to people’s work and life. With the increasing popularity of personal location information, people are increasingly using the system of recording and processing location data, which is usually called “location-based system.” These systems include (a) location-based services (LBSs), in which a user obtains, typically in real-time, a service related to his current location, and (b) location data mining algorithms, used to determine points of interest and traffic patterns. A large number of applications of location data provide convenience for people’s daily life, so location data service is called a new type of mobile computing service. For example, the personalized recommendation based on LBSs can recommend the interesting content to users according to their location POIs (points of interest) and movement trajectory [1]. Most mobile Internet services are based on the combination of location data with social data (personal information, social relationship information, etc.), and the crossduplication of these data will lead to privacy leakage problem [2]. Privacy-preserving data mining (PPDM) is a data mining method to reduce the possibility of sensitive data leakage. PPDM encrypts and sanitizes sensitive information; however, if the location data is “excessively” protected, it is difficult for users to obtain relatively accurate services [3, 4].How to protect sensitive information while providing location data mining service is the key to the current location data privacy protection. The traditional approach of PPDM considers only how to effectively hide sensitive information through heuristics which try their best to minimize side effects of a known NP-hard problem. In PPDM, a complex process of data sanitization using deletion operations on transactions is the most common approach to hide confidential information. The existing location privacy protection schemes mainly include location anonymity, location ambiguity, location transformation, and differential privacy. Among them, the location anonymity scheme [5] is to add the false location to the location data, so that the user’s real location is difficult to distinguish from other false location, to achieve the purpose of protecting the user’s location privacy, such as the more commonly used K-anonymous scheme [6, 7]. In the location ambiguity scheme [8], the true location of the user is generalized to an area or replaced by other locations around it, which makes it difficult for the attacker to determine the true location of the user, to protect the privacy of the user’s location. In the location transformation scheme, the user location is transferred to a different location, so the location service provider cannot obtain the user’s true location. In the differential privacy scheme, controllable random noise is mainly added to protect the user’s location data security [9, 10]. Most of the above schemes are aimed at protecting the discrete location data records in the location database. However, at the present stage, many Internet application services, such as Uber and Keep, provide information services based on the continuous movement trajectory of people; therefore, this paper is aimed at finding an efficient protection scheme for user trail frequent pattern mining. At present, many methods cannot balance the availability of location data with the protection of trajectory frequent pattern mining. Therefore, it is necessary to combine the characteristics of mobile location data and user trajectory to design an effective data mining privacy protection scheme suitable for location data. This method can handle the contradiction between privacy protection and quality of service well so that users can obtain relatively safe, more accurate, and convenient Internet data services [11].


## 2. Contributions

In this paper, we propose a differential privacy protection scheme for location data records based on the trajectory model frequent pattern mining to protect high-frequency access location data (which is related to the user’s location preference). Our contributions are as follows:(1)
In this scheme, we construct the user trajectory model from the database. Such a method has the following advantages: (a) it can intuitively describe the relationship of each path point and the importance of each path point in the user trajectory (as shown in Figure1); (b) it can improve the protection effectiveness of location data: when we add the noises to the corresponding graph nodes, it may protect the relationship of location data and the combination of location data and accessing frequency(2)
In the differential privacy protection phase, we make double processes of selecting data. The first selection is based on the Laplace mechanism; noises are added into the accessing frequencies of the candidate subgraph by the Laplace mechanism. The second selection is based on the exponential mechanism; the frequent trajectory graph with the final differential privacy protection is selected from the candidate subgraphsFigure 1
Trajectory graph modelGexample based on the trajectory in Figure 4.


## 3. Related Work

Currently, the existing location data privacy protection methods are mainly classified to three categories: the heuristic privacy-measure methods, the probability-based privacy inference methods, and the privacy information retrieval methods. The heuristic privacy-measure methods are mainly to provide the privacy protection measure for some no-high required users, such asK-anonymity [12], t-closing [13], m-invariability [14], and l-diversity [15]. Although the mechanisms such as anonymization [6] and spatial obfuscation [16] provide location privacy through hiding identity or reporting fake locations, they ignore adversary’s knowledge about user’s access pattern and LPPM algorithm and disregard the optimal attack where an attacker may design in an inference attack to reduce his calculation error. The information retrieval privacy protection methods may result in no data that can be released, and these methods have high overhead. Further, the three kinds of method are based on a unified attack model [17], which depends on certain background knowledge to protect location data. The works [18, 19] showed the shortages of the relationship-privacy protection methods. Gedik and Liu [20] proposed the first effective location-privacy preserving mechanism (LPPM) that enables a designer to find the optimal LPPM for a location-based service. Such an LPPM can maximize the expected distortion (error) when the adversary incurs in reconstructing the actual location of a user. Shokri et al. [21] propose an optimization framework to determine the most optimal LPPM against the most effective/optimal inference attack.However, with the deepening of the research, it is not enough to protect the user’s location data only. Therefore, a trajectory privacy protection method is proposed based on location privacy protection. At present, the privacy protection methods of trajectory data mainly include the following: (1) the protection method based onK-anonymous generalization, (2) the privacy protection method based on dynamic kana, (3) the privacy protection method based on noise data, (4) the protection method based on differential privacy, (5) the privacy protection method based on similarity matrix, and (6) locality sensitive hashing. The track privacy protection method based on K-anonymous generalization is mainly to treat continuous n queries as n independent LBS service requests, that is, to construct anonymous space for these n queries, respectively. Spatial and temporal cloaking [6] is the main technology to realize this method. It uses a spatial region CR(Clocking Region) to replace the real location of the user. Or by delaying the response time, the number of users in the empty area is large enough that the attacker cannot deduce the real user. Cheng et al. proposed schemes delaying and patching [22], where delaying is realized by delaying the request and patching is realized by expanding the camouflage area. However, this method reduces the service quality of LBS. Xu and Cai proposed a K-anonymous hidden area generation algorithm, KAA, which supports continuous spatial query [7]. The vicinity information can then be used by the adversary to carry out inference attack, background knowledge attack, or center-of-ASR attack in K-anonymous principle. Gupta and Rao develop a vicinity protection technique, called VIC-PRO, that strengthens the location privacy of the user [23].The main idea of the trajectory privacy protection method based on dynamic kana is that the user uses the pseudonym to replace the real identity when sending an LBS request. However, mobile users are real and visible in the geographic space, and using the same pseudonym for a long time cannot effectively protect users’ privacy. Freudiger et al. proposed a dynamic kana technology based on the mixed region (mix-zone) in literature [24], which constructed the mixed region according to the background knowledge that the attacker may use, such as the starting point of the trajectory, moving speed, and other information. Deploying too many mixed zones, however, can seriously affect the quality of service. Xu et al. proposed a deployment scheme through multiple mix-zones [25]. However, the above method requires a third-party organization to modify the user’s pseudonym centrally, and the reliability of the third party determines the effectiveness of this method.The main idea of the trajectory privacy protection method based on noise data is that several false locations (user peripheral location) are included in LBS request to protect the real location so that the attacker cannot confirm the real location of the user. However, the quality of privacy protection and service is related to the distance between true and false locations. The degree of privacy protection and service quality of this method is related to the distance between true and false locations. Kido et al. randomly moved the real position as a false position [26], but the false position generated by the noise mechanism was not consistent with the real movement characteristics of the user, and it was easy for attackers to distinguish the true and false positions. To solve this problem, Suzuki et al. added constraints such as moving speed and road network when generating false positions [27]. Kato et al. believed that mobile users would not move continuously all the time [28], so when generating noisy data points, the moving object would randomly pause according to the surrounding environment, so as to prevent attackers from distinguishing true and false positions. However, the above methods are not suitable for the attackers who have more background knowledge, and it is difficult to design a good noise mechanism.Presently, it is the key of protecting location data to provide a privacy protection method that is not sensitive to background knowledge. Based on the requirement, differential privacy protection technology can exactly satisfy it. Literature [29] proposed the differential privacy method for the first time to solve the problem of privacy protection in the release of trajectory data of the release scale. The method uses a prefix tree to store the trajectory data and Laplacian noise mechanism to add the noise value to the nodes. The method supports the technique and frequent pattern query of the trajectory data. Hua et al. proposed a differential privacy algorithm based on spatial generalization for the first time [30]. This method solves the requirement that trajectories must have the same prefix in most current research methods. However, moving trajectories in the road network generally have time correlation. If these correlations are ignored, privacy will be compromised. Therefore, Xiao and Xiong proposed a differential privacy protection technology based on “δ-location set” [31], which used the function sensitivity measurement method and the location disturbance mechanism to hide the sensitive locations in the location set, so as to achieve the purpose of privacy protection. This method ignores the relevance of user location points and is vulnerable to a large number of inference attacks. Chatzikokolakis et al. [32] showed a formal notion of privacy that protects the user’s exact location—“geoindistinguishability.” In [32], they proposed two mechanisms to protect the privacy of user when dealing with location-based services. They extended their mechanisms to limit the degradation of the privacy guarantees due to the correlation between the points. However, when the cumulative privacy parameters of differential privacy exceed the given privacy budget, it will lead to privacy leakage. Therefore, when the number of users’ queries accumulates to a certain extent, the effective duration of privacy protection cannot be guaranteed. Wang et al. [33] proposed a real-time spatiotemporal crowd-sourced data publishing scheme with differential privacy. Gupta and Rao propose a mechanism that provides a three-layer iterative RDV masking that exploits the basic geometry mathematics concept of Delaunay triangulation and Voronoi polygon formation to geo-mask the location attribute value before publishing the record [34].The privacy protection method based on similarity matrix takes outline of information acquired for a client as a similarity matrix. Similarity matrix demonstrates the similarity of the result set respecting the client’s present location. Dewri and Thurimella [35] display a novel trusted intermediate server-based framework for LBS applications.Locality sensitive hashing is a proficient mechanism algorithm to enhance the scalability of geofencing. It comprises two principal phases. In the first stage, in order to find out whether the point of concern is within the rectangle with the smallest boundary, an R tree is established for rapid recognition. In the second phase, an edge-based locality sensitive hashing arrangement is outlined and adjusted to the crossing point number calculation.


## 4. Preliminaries

### 4.1. Frequent Graph Pattern Mining

A graphG=V,E is made of two sets, the set of vertices V and the set of edges E. Each vertex is associated with a label, which is drawn from a set of vertex labels. Weighted graph is expressed as G=V,E,W, where W is the weight set of edges. The weight represents the degree of relationship between two nodes in the graph, such as the degree of connection between two location points or the amount of transaction between businesses.Suppose there are two graphsG1=V1,E1 and G2=V2,E2. Let Lu denote the label of vertex u. We say that G1 is contained in G2 if there exists a function f:v1⟶v2, such that ∀u,v∈E1; we have fu,fv∈E2, Lu=Lfu, andLv=Lfv. If G1 is contained in G2, we say that G1 is a subgraph of G2, and G2 is a supergraph of G1, denoted by G1⊆G2.A graph databaseGD=G0,G1,⋯,Gn is a multiset of input graphs, where each input graph represents an individual’s record. supg is the support of graph g which is the number of graphs in GD that contain g. Given a threshold, a graph is called frequent if its support is no less than this threshold.Definition 1.
Noisy support. Add the noise to the support of subgraph g. nsupg=supg+noise, wherensupg represents the noisy support of subgraph g. In this paper, we add Laplace noise to the subgraph.Definition 2.
Frequent subgraph mining (FGM). Given a graph database and a threshold, FGM is aimed at finding all frequent subgraphs for the threshold and computing the support of each frequent subgraph [36, 37].Definition 3.
Subgraph isomorphism. Two graphs G1=V1,E1 and G2=V2,E2 are isomorphic if they are topologically identical to each other; that is, there is a mapping from V1 to V2 such that each edge in E1 is mapped to a single edge in E2 and vice versa. In the case of labeled graphs, this mapping must also preserve the labels on the vertices and edges. Given two graphs G1=V1,E1 and G2=V2,E2, the problem of subgraph isomorphism is to find an isomorphism between G2 and a subgraph of G1, i.e., to determine whether or not G2 is included in G1. As shown in Figures 2 and 3, G2 is a subgraph of G1, and there is a subgraph isomorphism relationship between the two graphs.Figure 2
GraphG1.Figure 3
GraphG2.


### 4.2. Differential Privacy

Differential privacy [38] is a recent privacy model which provides a strong privacy guarantee. The main idea of differential privacy is that after adding or deleting a record to the database, there is almost no difference in the output of the same algorithm applied to the database. Formally, differential privacy is defined as follows.Definition 4.
ε-Differential privacy. A private algorithm A gives ε-differential privacy if for any neighboring databases D1 and D2, and for any possible output S∈RangeA,(1)PrAD1=S≤eε×PrAD2=S,where Pr represents the probability and RangeA represents the value range of the output result of algorithm A.Definition 5.
Sensitivity. For any neighboring databases D1and D2, the sensitivity of f is(2)Δf=maxD1,D2fD1−fD2.Currently, differential privacy protection has two main methods [39]: the Laplace mechanism [40] and the exponential mechanism [41].Theorem 6.
Laplace’s mechanism. The Laplace mechanism is to add noise following Laplace distribution to the output of the algorithm, so that the algorithm meets the differential privacy protection. For any functionf:f:D⟶ℝn with sensitivity Δf, the algorithm A(3)AD=fD+LapΔfε.The Laplace distribution with magnitudeλ, i.e., Lapλ, follows the probability density function asLapλ=1/2λe−∣x∣/λ, where λ=Δf/ε is determined by the sensitivity Δf and the privacy budget ε.Theorem 7.
Exponential mechanism. The exponential mechanism uses a utility score functionu to measure all possible results in the output space of the algorithm, then select an element x from the output space with the probability of Equation (4) as the output result.(4)PrAD=x∝expε×uD,x2Δu.According to the scoring function, eachx of the output space is assigned a weight uD,x. After the weight is amplified by the exponential function, the result is selected according to the weight.Theorem 8.
Sequential composition. For the same data set, if the whole privacy protection process is divided into the different privacy protection algorithmsA1,A2,⋯,An whose privacy protection levels are ε1,ε2,⋯,εn, then the privacy protection level ∑i=1nεi of the whole process needs to satisfy differential privacy protection.Theorem 9.
Parallel composition. For the disjoint data set, if the whole privacy protection process is divided to the different privacy protection algorithmsA1,A2,⋯,An whose privacy protection levels are ε1,ε2,⋯,εn, then the privacy protection level maxεi of the whole process needs to satisfy differential privacy protection.


## 4.1. Frequent Graph Pattern Mining

A graphG=V,E is made of two sets, the set of vertices V and the set of edges E. Each vertex is associated with a label, which is drawn from a set of vertex labels. Weighted graph is expressed as G=V,E,W, where W is the weight set of edges. The weight represents the degree of relationship between two nodes in the graph, such as the degree of connection between two location points or the amount of transaction between businesses.Suppose there are two graphsG1=V1,E1 and G2=V2,E2. Let Lu denote the label of vertex u. We say that G1 is contained in G2 if there exists a function f:v1⟶v2, such that ∀u,v∈E1; we have fu,fv∈E2, Lu=Lfu, andLv=Lfv. If G1 is contained in G2, we say that G1 is a subgraph of G2, and G2 is a supergraph of G1, denoted by G1⊆G2.A graph databaseGD=G0,G1,⋯,Gn is a multiset of input graphs, where each input graph represents an individual’s record. supg is the support of graph g which is the number of graphs in GD that contain g. Given a threshold, a graph is called frequent if its support is no less than this threshold.Definition 1.
Noisy support. Add the noise to the support of subgraph g. nsupg=supg+noise, wherensupg represents the noisy support of subgraph g. In this paper, we add Laplace noise to the subgraph.Definition 2.
Frequent subgraph mining (FGM). Given a graph database and a threshold, FGM is aimed at finding all frequent subgraphs for the threshold and computing the support of each frequent subgraph [36, 37].Definition 3.
Subgraph isomorphism. Two graphs G1=V1,E1 and G2=V2,E2 are isomorphic if they are topologically identical to each other; that is, there is a mapping from V1 to V2 such that each edge in E1 is mapped to a single edge in E2 and vice versa. In the case of labeled graphs, this mapping must also preserve the labels on the vertices and edges. Given two graphs G1=V1,E1 and G2=V2,E2, the problem of subgraph isomorphism is to find an isomorphism between G2 and a subgraph of G1, i.e., to determine whether or not G2 is included in G1. As shown in Figures 2 and 3, G2 is a subgraph of G1, and there is a subgraph isomorphism relationship between the two graphs.Figure 2
GraphG1.Figure 3
GraphG2.


## 4.2. Differential Privacy

Differential privacy [38] is a recent privacy model which provides a strong privacy guarantee. The main idea of differential privacy is that after adding or deleting a record to the database, there is almost no difference in the output of the same algorithm applied to the database. Formally, differential privacy is defined as follows.Definition 4.
ε-Differential privacy. A private algorithm A gives ε-differential privacy if for any neighboring databases D1 and D2, and for any possible output S∈RangeA,(1)PrAD1=S≤eε×PrAD2=S,where Pr represents the probability and RangeA represents the value range of the output result of algorithm A.Definition 5.
Sensitivity. For any neighboring databases D1and D2, the sensitivity of f is(2)Δf=maxD1,D2fD1−fD2.Currently, differential privacy protection has two main methods [39]: the Laplace mechanism [40] and the exponential mechanism [41].Theorem 6.
Laplace’s mechanism. The Laplace mechanism is to add noise following Laplace distribution to the output of the algorithm, so that the algorithm meets the differential privacy protection. For any functionf:f:D⟶ℝn with sensitivity Δf, the algorithm A(3)AD=fD+LapΔfε.The Laplace distribution with magnitudeλ, i.e., Lapλ, follows the probability density function asLapλ=1/2λe−∣x∣/λ, where λ=Δf/ε is determined by the sensitivity Δf and the privacy budget ε.Theorem 7.
Exponential mechanism. The exponential mechanism uses a utility score functionu to measure all possible results in the output space of the algorithm, then select an element x from the output space with the probability of Equation (4) as the output result.(4)PrAD=x∝expε×uD,x2Δu.According to the scoring function, eachx of the output space is assigned a weight uD,x. After the weight is amplified by the exponential function, the result is selected according to the weight.Theorem 8.
Sequential composition. For the same data set, if the whole privacy protection process is divided into the different privacy protection algorithmsA1,A2,⋯,An whose privacy protection levels are ε1,ε2,⋯,εn, then the privacy protection level ∑i=1nεi of the whole process needs to satisfy differential privacy protection.Theorem 9.
Parallel composition. For the disjoint data set, if the whole privacy protection process is divided to the different privacy protection algorithmsA1,A2,⋯,An whose privacy protection levels are ε1,ε2,⋯,εn, then the privacy protection level maxεi of the whole process needs to satisfy differential privacy protection.


## 5. The Location Data Privacy Protection Scheme

In this section, we proposed a location data record privacy protection scheme based on a weighted graph model. In the proposed scheme, we first build the user’s location database based on the user’s location data record (Figure4), and then, we construct the user travel trajectory model according to the characteristics of mobile location data. After introducing the weighted graph model to construct the complete user travel trajectory graph database, we propose a three-stage differential privacy protection algorithm based on subgraph edge growth. In the first stage, standardize and code the user travel trajectory graph database, and sort it according to the number of edges. In the second stage, the subgraph data sets generated by the edge-growing pattern are added with Laplace noise. After threshold judgment and selection, candidate frequent graph data sets are obtained. In the third stage, this algorithm generates frequent subgraph data sets by the exponential mechanism (Figure 5).Figure 4
Location data source. The trajectory of an anonymous user in the real world.Figure 5
TMDP framework. The trajectory model is built, and weighted frequent graph mining based on differential privacy algorithm is introduced.The main steps of the user trajectory graph privacy protection framework are described as follows:Step 1.
Design weighted trajectory graph model according to user’s trajectory characteristics.Step 2.
Construct the trajectory graph databaseGD based on the trajectory database TrDatabase=Tr1,Tr2,⋯,Trn.Step 3.
Add Laplace noise to the candidate subgraph for the first screening, introduce the exponential mechanism to carry out the second screening, and obtain the final result.


### 5.1. Establishment of Trajectory Model Graph

The user trajectory database is preliminarily established through the starting time of movement, the stay time, and the stop position of the user movement location database, as Table1 shows.Table 1
Location data sample.
Encrypted idLongitudeLatitudeCityGridTime (m)W90H0925118.80365532.067106Nanjing020310/1/14:30W90H0925118.78471832.073593Nanjing020910/1/16:38W90H0925118.78829432.066525Nanjing022110/1/17:00W90H0925118.79734832.072255Nanjing034710/1/18:26W90H0925118.79600132.064865Nanjing030910/1/19:55W90H0925118.78829432.066525Nanjing022110/1/22:24The trajectory: β is set as the user residence time threshold based on the regularly reported user location data. When the user stops at a certain location for longer than β, the location is determined to be the user stop position: ni=p,a1≤i≤k, where i represents the sequential value of the sampling positions in the trajectory. p represents the stop position; there are three values of a: (1) if i=1, a is the “starting position”; (2) if 1<i<k, a is the “passing position”; and (3) if i=k, a is the “end position.” The movement trajectory of the user in the sampling period r is denoted as Tr=n1,n2,n3⋯nk,k=Tr.Trajectory model graph: the trajectory graph G=V,E,L is constructed by the user trajectory. V is the set of user’s stop position V=v1,v2,⋯,vmm=V, which represents the area where the user stays, such as school, company, and bank, as shown in Figure 1.vi=id,s_sum,m_num,e_num, where id is the code of the user’s stop position. Between the user’s two stop position is a path. s_sum represents the number of paths with id as a “starting position.” m_num is the number of paths with id as a “passing position.” e_num is the number of paths with id as an “end position.” E=e1,e2,⋯,em is the set of edges; E represents the user’s paths between id. The weight of e is the sum of the number of trajectories in this path; for example, for edge e1=v1,v2, if there is a trajectory Tr whichni=v1 and ni+1=v2, then the weight of edge e1 add one.This section proposes an algorithm (the TGDC algorithm) to construct a trajectory model graph from the trajectory data of users’ travel. Firstly, the set of all “starting position” in the trajectory database will be obtained, and every starting position corresponds to a travel trajectory subgraph. After traversing all the trajectory data, store the trajectory subgraph corresponding to the “starting position” asTr. For each trajectory, positions and edges will be added to the trajectory model to construct the trajectory graph database. After executing the algorithm, label function is applied to the graph structure to obtain the label value of the final point and edge. Finally, we will get the user’s trajectory graph database.Algorithm 1: Trajectory graph database construction.
Input: Trajectory database TrDatabase=Tr1,Tr2,⋯,Trn,Tr=n1,n2⋯nkOutput: Trajectory Graph Database GD=G1,G2,⋯Gn1.for each v=Tr.start_nodeinTrDatabase: /∗ Summarize all trajectory data by traversing the starting points v=Tr.start_node in TrDatabase∗/2.Vstart=null3.ifv not in Vstart:4.Vstart+=v5.for each vinVstart:6.Trs=Null7.for each TrinTrDatabase:8.ifTr.start_node=v:9.Trs+=Tr10.end for11. /∗For each trajectory, points and edges are added to the trajectory graph to construct a complete graph structure ∗/12.for each TriinTrs:13.for j in range (lenTri−1):14.ifTri.njnot inG:15.G.add_nodeTri.nj16.ifTri.nj+1not inG:17.G.add_nodeTri.nj+118.     Edge (Tri.nj,Tri.nj+1).w+=1/∗ Add edge weight to the graph ∗/19.end for20.GD+=G21.end for22.returnGD


### 5.2. Trajectory Frequent Graph Support Calculation Algorithm

In the frequent pattern mining of users’ trajectories, the primary focus of our research is the relationship between the stop positions in users’ moving trajectories and the frequent graph structure constructed by the trajectories. Therefore, we simplify the study of users’ trajectory model into the weighted undirected graph study.Canonical code of trajectory subgraph: in frequent subgraph mining, graph data is usually represented by adjacent matrix. There are three kinds of adjacent matrices in general use: (1) node-centered; (2) edge-centered; and (3) the combination of nodes and edges.The purpose of trajectory frequent subgraph is not only to discover frequent subgraph but also to find implicit relationship between user’s trajectories. In this paper, an edge-centered adjacent matrix representation method is adopted. The definition of adjacent matrix is given below.G=V,E has m nodes, which is VG=v1,v2,⋯,vm; the m-order matrix AG=xij is called the adjacent matrix of G, as Figure 6 shows.(5)xije,thereisanedgeebetweenviandvj,0,otherwise.Figure 6
The adjacent matrix ofGexample.In order to improve the efficiency of the algorithm, the upper triangular matrix of the adjacency matrix is selected according to the symmetry of the matrix. Different orders of nodes will generate different adjacent matrices; if two graphs are isomorphic to each other, they will be assigned the same code. To ensure the uniqueness of the adjacency matrix [42], we introduce a simple way of defining the canonical label of a graph that is as the string obtained by concatenating the upper triangular entries of the graph’s adjacency matrix when this matrix has been symmetrically permuted so that this string becomes the lexicographically largest (or smallest) over the strings that can be obtained from all such permutations.Let(6)X=x11⋯x1m⋮xm1⋯xmmbe an adjacent matrix of graph G, and the code of matrix defining X is CodeX=x12x13⋯x1mx23⋯x2m⋯xm−1m. The canonical matrix encoding of graph X is CanonicalCodeX=maxCodeX. Therefore, if two graphs are isomorphic, they must have the same CanonicalCode [43].In order to reduce the computational complexity of canonical matrix coding and improve computational efficiency, a fast coding strategy (FastCanonicalCodeX) is proposed. The adjacent matrix of the graph is arranged according to the degree of nodes (that is, the number of edges associated with V nodes in the graph) from high to low and in a lexicographic order, and the result is taken as the FastCanonicalCode of the adjacent matrix. Taking the adjacent matrix of graph Gexample in Figure 6 as an example, the degree of 6 nodes (v0,v1,v2,v3,v4,andv5) in the graph is 1, 2, 3, 3, 1, and 1, respectively [43]. According to the principle of FastCanonicalCode, the new node ordering is: v23,v33,v12,v01,v41,andv51 as Figure 7 shows. The FastCanonicalCodeX is e4e200e5e30e60e1000. The isomorphism of graphs can be equivalent to the calculation of CanonicalCode; the general method is to enumerate all the adjacent matrix, taking Figure 1 as an example; the algorithm complexity is 6!=720. By using this strategy, the nonzero elements in the adjacent matrix can appear in front of the subgraph composed of matrix code as much as possible; the algorithm complexity is 2!×3!=12, thus accelerating the matching speed of the candidate subgraph coding in the graph transaction coding subgraph. It greatly reduces the search space of graph, and the new sorting strategy can accelerate the calculation of graph isomorphism and support.Figure 7
The adjacent matrix ofFastCanonicalCode.Weighted frequent trajectory graph: traditional subgraph pattern mining algorithms treat all frequent subgraph patterns equally, but in real user trajectories, different user trajectory subgraphs have different importance. In order to solve these problems, this paper proposes a frequent subgraph mining algorithm based on edge weight.Definition 10.
Edge weight. The number of paths through edge ei in the user trajectory graph is the edge weight Wei.Definition 11.
The weight of the trajectory subgraph. If the subgraph G consists of m edges e1,e2,⋯,em, then the weight of the trajectory subgraph G is defined as WG=∑k=1mWek/m.Definition 12.
Average total weighting (ATW). For the weight processing of weighted frequent subgraph mining, there are generally three edge weighting schemes for controlling candidate set generation [44]: (i) average total weighting (ATW), (ii) affinity weighting (AW), and (iii) utility-based weighting (UBW). ATW is more suitable for the actual situation in the mining of weighted frequent trajectory graph. Assume that the graph database GD contains a total of n different edges e1,e2,⋯,em, where the maximum edge weight is max1≤k≤nWek and the minimum edge weight is min1≤k≤nWek; then, the average weight of this GD is defined as follows: Meanweight=λmax1≤k≤nWek+1−λmin1≤k≤nWek, where λ is the adjustment parameter. Based on many experiments, λ is set as 0.5 in this paper.This paper mainly considers the mining and analysis of the frequent trajectory graph. In the trajectory graph frequency calculation algorithm (TGFC), the node with the largest degree of the subgraphg is the geographical location most frequently visited. We take the node as the initial query point, as shown in line 2 of Algorithm 2. The number of the degree indicates the importance of the node and the priority of the match. The isomorphic points of the initial query point are found from GD to form matchnode.set, as shown in lines 3-7. Finally, starting from the start_node, the isomorphism of the subgraph g is found through the comparison traversal of the node degree, label of the isomorphism points, and the edge set containing the isomorphism points, as shown in lines 4-11. The subgraph isomorphism search algorithm (Iso_search) judges whether CanonicalCodeg is equal to CanonicalCodeGD at first; if CanonicalCodeg=CanonicalCodeGD, it indicates that g and GD are isomorphic. Then, it judges that if the node is the last node in FastCanonicalCode, if the node is the last node, quit the recursion. Otherwise, traversing all the remaining isomorphism points by the adjacency matrix until all isomorphic subgraphs are found.Algorithm 2: Trajectory graph frequency calculation (TGFC).
Input: Graph Database GD, Canonical Code of Trajectory Subgraph code, the number of edges with n as the node EnOutput: the number of trajectory subgraph g in graph database GD1.num=0, trajectory subgraph g, matchnode.set=null2. According to the definition ofFastCanonicalCode, FastCanonicalCode0 has the largest node degree, and takes the node with the highest degree as the starting match query point.3. Each time, select the node with the highest degree fromFastCanonicalCode for matching. Update FastCanonicalCode to FastCanonicalCode_new.4.for each node n in GD.node:5.ifn.degree>=start_node.degree & n.label=start_node.label &En>=Estart_node: /∗ ∗/6.matchnode.set+=n7.end for8.for each node n in matchnode.set:9.num=Iso_searchGD,start_node,n,num10.end for11.return num12. -------Subgraph Isomorphism Search,Iso_search------13. ifCanonicalCodeg=CanonicalCodeGD:14.   num+=115.return num16.else if17.ifstart_node is the last node of FastCanonicalCode_new:18.  num +=119.return num20.for each unvisited node nc in matchnode.set:21.ifnc.degree>=start_node.child.degree & nc.label=start_node.child.label &Enc>=Estart_node.child:22.    traversing all the remaining isomorphism points, obtained isomorphism subgraph by the adjacency matrix.23.    num+=∣isomorphism∣:24.else25.Iso_searchGD,start_node.child,nc,num:26.end for27.return num


### 5.3. Privacy Protection Based on Weighted Frequent Trajectory Graph

Differential privacy mechanism can effectively protect node and graph structure information mining of users’ travel trajectories. When differential privacy protection is adopted in the mining of user trajectory subgraph, if Laplace noise is directly added in the generation of frequent subgraph, a large number of redundant subgraphs will be generated, resulting in low data utility. In this paper, we propose a privacy protection framework based on subgraph edge growth model. In this framework, we set the subgraph average total weight (ATW) according to the definition of weighted frequent trajectory graph; based on the ATW, we get the threshold judgment condition of Laplace noise support, as shown in line 12. Considering that the user travel trajectory graph is nonnumerical data, the exponential mechanism is introduced to screen the candidate frequent subgraphs again. The framework not only ensures the availability and security of the data but also retains the characteristics of the user trajectory travel graph.The privacy budget for the whole approach isε=ε1+ε2. Firstly, the trajectory subgraph set is arranged according to the number of edges. The 1-graph containing frequent edges is taken as the candidate set of subgraphs. If the subgraph satisfies the canonical code, the child of the subgraph is generated by adding one edge every time. We add Laplace noise to the support of child, if the child’s noisy support is less than the threshold θ. Repeat noise perturbation and threshold filtering for child generated by the subgraph to get the candidate subgraph. The above process consumes a privacy budget ε1. We allocate privacy budget ε2 to introduce the exponential mechanism to screen the candidate subgraphs again. Finally, we find all the frequent subgraph that meets all the conditions.Algorithm 3: Trajectory weighted graph protection (TWGP).
Input: Trajectory TrDatabase=Tr1,Tr2,⋯,Trn, privacy budget ε=ε1+ε2,Threshold θOutput: Frequent i‐subgraphsSi1. Trajectory Graph DatabaseGD=G1,G2,⋯Gn= TGDC (TrDatabase)2.ifg≠CanonicalCodegthen3.return4.G is sorted from smallest to largest by the number of edges of GD5.set=∅6. The number ofgi=i‐graph is ni;7.forj=1 tonido:8. enumerategi∈G⊆GD and its children gchildj/∗gchildj is gj’s child with one edge growth in GD∗/9.for each gchildjdo:10.supgchildj=TGFCgchildj,codegchildj;11.θ=Meanweight∗min_sup/Wgchildj;12.ifnsupgchildj=supgchildj+laplace1/ε1≥θ:13.set⟵gchildj;14.end if15.end for16.gj⟵select a subgraph g from set such that Pr{Selecting subgraph g} ∝expε2∗support/2ni;17.Si+=gj;18.end for19.returnSi;


### 5.4. Security Analysis of the Proposed Scheme

Step 1.
DP-Laplace mechanism privacy analysis: due to the edge growth model which is used to extend the subgraph, after each extension of the difference is only one graph data. The sensitivity of Laplace noise function isΔfLaplace=1. Adding Laplace1/ε1 noise in the subgraph mining process satisfies the ε1-differential privacy.Step 2.
DP-exponential mechanism privacy analysis: the conditional exponential method of Step 2 satisfiesε2-differential privacy.Proof.
The utility score we assigned to each candidate subgraph can be considered as(7)ug,D=0,nsupg<θ,expε2∗supg2ni,nsupg≥θ,where nsupg and supg are the noisy support and the true support of subgraph g in database D. D1 and D2 are two neighboring databases. We add Laplace noise Laplace1/ε1 to the support of each candidate subgraph-gchildj. Based on the definition of Laplace mechanism, we have(8)Prnoise=XPrnoise=X+1=exp−ε1Xexp−ε1X+1=expε1X+1−ε1X≤expε1.Similarly,(9)Prnoise=XPrnoise=X+1≤expε1.Based on Equations (8) and (9),(10)PrsupD1g+noise≥θ=∫θ−supD1g+∞Prnoise=xdx≤∫θ−supD2g+∞expε1Prnoise=x−1dx≤∫θ−supD2g+∞expε1Prnoise=xdx=expε1PrsupD2g+noise≥θ.That is,(11)PrnsupD1g≥θ≤expε1PrnsupD2g≥θ.In a similar way, we can prove(12)Prnoise≥θ−supD1g=∫θ−supD1g+∞Prnoise=xdx≥∫θ+1−supD2g+∞Prnoise=xdx=∫θ−supD2g+∞Prnoise=x+1dx≥exp−ε1∫θ−supD2g+∞Prnoise=xdx=exp−ε1Prnoise≥θ−supD2g.Similarly,(13)PrnsupD1g≥θ≥exp−ε1PrnsupD2g≥θ,PrnsupD1g<θ≤expε1PrnsupD2g<θ,PrnsupD1g<θ≥exp−ε1PrnsupD2g<θ,because for each candidate subgraph g, we have −1≤supD1g−supD2g≤1.(14)exp−ε2≤expε2∗supD1g/2niexpε2∗supD2g/2ni≤expε2.Therefore,(15)PrselectingsubgraphSGfromGinD1=0×PrnsupD1SG<θ+expε2∗supD1SG/2ni×PrnsupD1SG≥θ∑g∈G0×PrnsupD1g<θ+expε2∗supD1g/2ni×PrnsupD1g≥θ≤expε2∗supD1SG/2ni×expε1×PrnsupD2SG≥θ∑g∈Gexpε2∗supD1g/2ni×exp−ε1×PrnsupD2g≥θ≤expε2/2ni×expε2∗supD2SG/2ni×expε1×PrnsupD2SG≥θ∑g∈Gexp−ε2/2ni×expε2∗supD2g/2ni×exp−ε1×PrnsupD2g≥θ≤expε1+ε2niPrselectingsubgraphSGfromGinD2.Based on the above analysis, Step 1 and Step 2 satisfyε-differential privacy. By the sequential composition property [44, 45], the privacy protection based on weighted frequent trajectory graph overall satisfies ε-differential privacy.


## 5.1. Establishment of Trajectory Model Graph

The user trajectory database is preliminarily established through the starting time of movement, the stay time, and the stop position of the user movement location database, as Table1 shows.Table 1
Location data sample.
Encrypted idLongitudeLatitudeCityGridTime (m)W90H0925118.80365532.067106Nanjing020310/1/14:30W90H0925118.78471832.073593Nanjing020910/1/16:38W90H0925118.78829432.066525Nanjing022110/1/17:00W90H0925118.79734832.072255Nanjing034710/1/18:26W90H0925118.79600132.064865Nanjing030910/1/19:55W90H0925118.78829432.066525Nanjing022110/1/22:24The trajectory: β is set as the user residence time threshold based on the regularly reported user location data. When the user stops at a certain location for longer than β, the location is determined to be the user stop position: ni=p,a1≤i≤k, where i represents the sequential value of the sampling positions in the trajectory. p represents the stop position; there are three values of a: (1) if i=1, a is the “starting position”; (2) if 1<i<k, a is the “passing position”; and (3) if i=k, a is the “end position.” The movement trajectory of the user in the sampling period r is denoted as Tr=n1,n2,n3⋯nk,k=Tr.Trajectory model graph: the trajectory graph G=V,E,L is constructed by the user trajectory. V is the set of user’s stop position V=v1,v2,⋯,vmm=V, which represents the area where the user stays, such as school, company, and bank, as shown in Figure 1.vi=id,s_sum,m_num,e_num, where id is the code of the user’s stop position. Between the user’s two stop position is a path. s_sum represents the number of paths with id as a “starting position.” m_num is the number of paths with id as a “passing position.” e_num is the number of paths with id as an “end position.” E=e1,e2,⋯,em is the set of edges; E represents the user’s paths between id. The weight of e is the sum of the number of trajectories in this path; for example, for edge e1=v1,v2, if there is a trajectory Tr whichni=v1 and ni+1=v2, then the weight of edge e1 add one.This section proposes an algorithm (the TGDC algorithm) to construct a trajectory model graph from the trajectory data of users’ travel. Firstly, the set of all “starting position” in the trajectory database will be obtained, and every starting position corresponds to a travel trajectory subgraph. After traversing all the trajectory data, store the trajectory subgraph corresponding to the “starting position” asTr. For each trajectory, positions and edges will be added to the trajectory model to construct the trajectory graph database. After executing the algorithm, label function is applied to the graph structure to obtain the label value of the final point and edge. Finally, we will get the user’s trajectory graph database.Algorithm 1: Trajectory graph database construction.
Input: Trajectory database TrDatabase=Tr1,Tr2,⋯,Trn,Tr=n1,n2⋯nkOutput: Trajectory Graph Database GD=G1,G2,⋯Gn1.for each v=Tr.start_nodeinTrDatabase: /∗ Summarize all trajectory data by traversing the starting points v=Tr.start_node in TrDatabase∗/2.Vstart=null3.ifv not in Vstart:4.Vstart+=v5.for each vinVstart:6.Trs=Null7.for each TrinTrDatabase:8.ifTr.start_node=v:9.Trs+=Tr10.end for11. /∗For each trajectory, points and edges are added to the trajectory graph to construct a complete graph structure ∗/12.for each TriinTrs:13.for j in range (lenTri−1):14.ifTri.njnot inG:15.G.add_nodeTri.nj16.ifTri.nj+1not inG:17.G.add_nodeTri.nj+118.     Edge (Tri.nj,Tri.nj+1).w+=1/∗ Add edge weight to the graph ∗/19.end for20.GD+=G21.end for22.returnGD


## 5.2. Trajectory Frequent Graph Support Calculation Algorithm

In the frequent pattern mining of users’ trajectories, the primary focus of our research is the relationship between the stop positions in users’ moving trajectories and the frequent graph structure constructed by the trajectories. Therefore, we simplify the study of users’ trajectory model into the weighted undirected graph study.Canonical code of trajectory subgraph: in frequent subgraph mining, graph data is usually represented by adjacent matrix. There are three kinds of adjacent matrices in general use: (1) node-centered; (2) edge-centered; and (3) the combination of nodes and edges.The purpose of trajectory frequent subgraph is not only to discover frequent subgraph but also to find implicit relationship between user’s trajectories. In this paper, an edge-centered adjacent matrix representation method is adopted. The definition of adjacent matrix is given below.G=V,E has m nodes, which is VG=v1,v2,⋯,vm; the m-order matrix AG=xij is called the adjacent matrix of G, as Figure 6 shows.(5)xije,thereisanedgeebetweenviandvj,0,otherwise.Figure 6
The adjacent matrix ofGexample.In order to improve the efficiency of the algorithm, the upper triangular matrix of the adjacency matrix is selected according to the symmetry of the matrix. Different orders of nodes will generate different adjacent matrices; if two graphs are isomorphic to each other, they will be assigned the same code. To ensure the uniqueness of the adjacency matrix [42], we introduce a simple way of defining the canonical label of a graph that is as the string obtained by concatenating the upper triangular entries of the graph’s adjacency matrix when this matrix has been symmetrically permuted so that this string becomes the lexicographically largest (or smallest) over the strings that can be obtained from all such permutations.Let(6)X=x11⋯x1m⋮xm1⋯xmmbe an adjacent matrix of graph G, and the code of matrix defining X is CodeX=x12x13⋯x1mx23⋯x2m⋯xm−1m. The canonical matrix encoding of graph X is CanonicalCodeX=maxCodeX. Therefore, if two graphs are isomorphic, they must have the same CanonicalCode [43].In order to reduce the computational complexity of canonical matrix coding and improve computational efficiency, a fast coding strategy (FastCanonicalCodeX) is proposed. The adjacent matrix of the graph is arranged according to the degree of nodes (that is, the number of edges associated with V nodes in the graph) from high to low and in a lexicographic order, and the result is taken as the FastCanonicalCode of the adjacent matrix. Taking the adjacent matrix of graph Gexample in Figure 6 as an example, the degree of 6 nodes (v0,v1,v2,v3,v4,andv5) in the graph is 1, 2, 3, 3, 1, and 1, respectively [43]. According to the principle of FastCanonicalCode, the new node ordering is: v23,v33,v12,v01,v41,andv51 as Figure 7 shows. The FastCanonicalCodeX is e4e200e5e30e60e1000. The isomorphism of graphs can be equivalent to the calculation of CanonicalCode; the general method is to enumerate all the adjacent matrix, taking Figure 1 as an example; the algorithm complexity is 6!=720. By using this strategy, the nonzero elements in the adjacent matrix can appear in front of the subgraph composed of matrix code as much as possible; the algorithm complexity is 2!×3!=12, thus accelerating the matching speed of the candidate subgraph coding in the graph transaction coding subgraph. It greatly reduces the search space of graph, and the new sorting strategy can accelerate the calculation of graph isomorphism and support.Figure 7
The adjacent matrix ofFastCanonicalCode.Weighted frequent trajectory graph: traditional subgraph pattern mining algorithms treat all frequent subgraph patterns equally, but in real user trajectories, different user trajectory subgraphs have different importance. In order to solve these problems, this paper proposes a frequent subgraph mining algorithm based on edge weight.Definition 10.
Edge weight. The number of paths through edge ei in the user trajectory graph is the edge weight Wei.Definition 11.
The weight of the trajectory subgraph. If the subgraph G consists of m edges e1,e2,⋯,em, then the weight of the trajectory subgraph G is defined as WG=∑k=1mWek/m.Definition 12.
Average total weighting (ATW). For the weight processing of weighted frequent subgraph mining, there are generally three edge weighting schemes for controlling candidate set generation [44]: (i) average total weighting (ATW), (ii) affinity weighting (AW), and (iii) utility-based weighting (UBW). ATW is more suitable for the actual situation in the mining of weighted frequent trajectory graph. Assume that the graph database GD contains a total of n different edges e1,e2,⋯,em, where the maximum edge weight is max1≤k≤nWek and the minimum edge weight is min1≤k≤nWek; then, the average weight of this GD is defined as follows: Meanweight=λmax1≤k≤nWek+1−λmin1≤k≤nWek, where λ is the adjustment parameter. Based on many experiments, λ is set as 0.5 in this paper.This paper mainly considers the mining and analysis of the frequent trajectory graph. In the trajectory graph frequency calculation algorithm (TGFC), the node with the largest degree of the subgraphg is the geographical location most frequently visited. We take the node as the initial query point, as shown in line 2 of Algorithm 2. The number of the degree indicates the importance of the node and the priority of the match. The isomorphic points of the initial query point are found from GD to form matchnode.set, as shown in lines 3-7. Finally, starting from the start_node, the isomorphism of the subgraph g is found through the comparison traversal of the node degree, label of the isomorphism points, and the edge set containing the isomorphism points, as shown in lines 4-11. The subgraph isomorphism search algorithm (Iso_search) judges whether CanonicalCodeg is equal to CanonicalCodeGD at first; if CanonicalCodeg=CanonicalCodeGD, it indicates that g and GD are isomorphic. Then, it judges that if the node is the last node in FastCanonicalCode, if the node is the last node, quit the recursion. Otherwise, traversing all the remaining isomorphism points by the adjacency matrix until all isomorphic subgraphs are found.Algorithm 2: Trajectory graph frequency calculation (TGFC).
Input: Graph Database GD, Canonical Code of Trajectory Subgraph code, the number of edges with n as the node EnOutput: the number of trajectory subgraph g in graph database GD1.num=0, trajectory subgraph g, matchnode.set=null2. According to the definition ofFastCanonicalCode, FastCanonicalCode0 has the largest node degree, and takes the node with the highest degree as the starting match query point.3. Each time, select the node with the highest degree fromFastCanonicalCode for matching. Update FastCanonicalCode to FastCanonicalCode_new.4.for each node n in GD.node:5.ifn.degree>=start_node.degree & n.label=start_node.label &En>=Estart_node: /∗ ∗/6.matchnode.set+=n7.end for8.for each node n in matchnode.set:9.num=Iso_searchGD,start_node,n,num10.end for11.return num12. -------Subgraph Isomorphism Search,Iso_search------13. ifCanonicalCodeg=CanonicalCodeGD:14.   num+=115.return num16.else if17.ifstart_node is the last node of FastCanonicalCode_new:18.  num +=119.return num20.for each unvisited node nc in matchnode.set:21.ifnc.degree>=start_node.child.degree & nc.label=start_node.child.label &Enc>=Estart_node.child:22.    traversing all the remaining isomorphism points, obtained isomorphism subgraph by the adjacency matrix.23.    num+=∣isomorphism∣:24.else25.Iso_searchGD,start_node.child,nc,num:26.end for27.return num


## 5.3. Privacy Protection Based on Weighted Frequent Trajectory Graph

Differential privacy mechanism can effectively protect node and graph structure information mining of users’ travel trajectories. When differential privacy protection is adopted in the mining of user trajectory subgraph, if Laplace noise is directly added in the generation of frequent subgraph, a large number of redundant subgraphs will be generated, resulting in low data utility. In this paper, we propose a privacy protection framework based on subgraph edge growth model. In this framework, we set the subgraph average total weight (ATW) according to the definition of weighted frequent trajectory graph; based on the ATW, we get the threshold judgment condition of Laplace noise support, as shown in line 12. Considering that the user travel trajectory graph is nonnumerical data, the exponential mechanism is introduced to screen the candidate frequent subgraphs again. The framework not only ensures the availability and security of the data but also retains the characteristics of the user trajectory travel graph.The privacy budget for the whole approach isε=ε1+ε2. Firstly, the trajectory subgraph set is arranged according to the number of edges. The 1-graph containing frequent edges is taken as the candidate set of subgraphs. If the subgraph satisfies the canonical code, the child of the subgraph is generated by adding one edge every time. We add Laplace noise to the support of child, if the child’s noisy support is less than the threshold θ. Repeat noise perturbation and threshold filtering for child generated by the subgraph to get the candidate subgraph. The above process consumes a privacy budget ε1. We allocate privacy budget ε2 to introduce the exponential mechanism to screen the candidate subgraphs again. Finally, we find all the frequent subgraph that meets all the conditions.Algorithm 3: Trajectory weighted graph protection (TWGP).
Input: Trajectory TrDatabase=Tr1,Tr2,⋯,Trn, privacy budget ε=ε1+ε2,Threshold θOutput: Frequent i‐subgraphsSi1. Trajectory Graph DatabaseGD=G1,G2,⋯Gn= TGDC (TrDatabase)2.ifg≠CanonicalCodegthen3.return4.G is sorted from smallest to largest by the number of edges of GD5.set=∅6. The number ofgi=i‐graph is ni;7.forj=1 tonido:8. enumerategi∈G⊆GD and its children gchildj/∗gchildj is gj’s child with one edge growth in GD∗/9.for each gchildjdo:10.supgchildj=TGFCgchildj,codegchildj;11.θ=Meanweight∗min_sup/Wgchildj;12.ifnsupgchildj=supgchildj+laplace1/ε1≥θ:13.set⟵gchildj;14.end if15.end for16.gj⟵select a subgraph g from set such that Pr{Selecting subgraph g} ∝expε2∗support/2ni;17.Si+=gj;18.end for19.returnSi;


## 5.4. Security Analysis of the Proposed Scheme

Step 1.
DP-Laplace mechanism privacy analysis: due to the edge growth model which is used to extend the subgraph, after each extension of the difference is only one graph data. The sensitivity of Laplace noise function isΔfLaplace=1. Adding Laplace1/ε1 noise in the subgraph mining process satisfies the ε1-differential privacy.Step 2.
DP-exponential mechanism privacy analysis: the conditional exponential method of Step 2 satisfiesε2-differential privacy.Proof.
The utility score we assigned to each candidate subgraph can be considered as(7)ug,D=0,nsupg<θ,expε2∗supg2ni,nsupg≥θ,where nsupg and supg are the noisy support and the true support of subgraph g in database D. D1 and D2 are two neighboring databases. We add Laplace noise Laplace1/ε1 to the support of each candidate subgraph-gchildj. Based on the definition of Laplace mechanism, we have(8)Prnoise=XPrnoise=X+1=exp−ε1Xexp−ε1X+1=expε1X+1−ε1X≤expε1.Similarly,(9)Prnoise=XPrnoise=X+1≤expε1.Based on Equations (8) and (9),(10)PrsupD1g+noise≥θ=∫θ−supD1g+∞Prnoise=xdx≤∫θ−supD2g+∞expε1Prnoise=x−1dx≤∫θ−supD2g+∞expε1Prnoise=xdx=expε1PrsupD2g+noise≥θ.That is,(11)PrnsupD1g≥θ≤expε1PrnsupD2g≥θ.In a similar way, we can prove(12)Prnoise≥θ−supD1g=∫θ−supD1g+∞Prnoise=xdx≥∫θ+1−supD2g+∞Prnoise=xdx=∫θ−supD2g+∞Prnoise=x+1dx≥exp−ε1∫θ−supD2g+∞Prnoise=xdx=exp−ε1Prnoise≥θ−supD2g.Similarly,(13)PrnsupD1g≥θ≥exp−ε1PrnsupD2g≥θ,PrnsupD1g<θ≤expε1PrnsupD2g<θ,PrnsupD1g<θ≥exp−ε1PrnsupD2g<θ,because for each candidate subgraph g, we have −1≤supD1g−supD2g≤1.(14)exp−ε2≤expε2∗supD1g/2niexpε2∗supD2g/2ni≤expε2.Therefore,(15)PrselectingsubgraphSGfromGinD1=0×PrnsupD1SG<θ+expε2∗supD1SG/2ni×PrnsupD1SG≥θ∑g∈G0×PrnsupD1g<θ+expε2∗supD1g/2ni×PrnsupD1g≥θ≤expε2∗supD1SG/2ni×expε1×PrnsupD2SG≥θ∑g∈Gexpε2∗supD1g/2ni×exp−ε1×PrnsupD2g≥θ≤expε2/2ni×expε2∗supD2SG/2ni×expε1×PrnsupD2SG≥θ∑g∈Gexp−ε2/2ni×expε2∗supD2g/2ni×exp−ε1×PrnsupD2g≥θ≤expε1+ε2niPrselectingsubgraphSGfromGinD2.Based on the above analysis, Step 1 and Step 2 satisfyε-differential privacy. By the sequential composition property [44, 45], the privacy protection based on weighted frequent trajectory graph overall satisfies ε-differential privacy.


## 6. Experiments and Results Analysis

The experiments are conducted on big data platform which is IBM X3650M4 with Intel e5 CPU 16 Core (2.2 GHZ) 256 GB RAM and 3TB ROM. All the proposed algorithms are coded by the Python 3.6 programming language in CentOS7.5. We use the desensitized 4G location signaling data of the anonymous user group in Nanjing in October 2019. The data fields are as follows: time, encrypted account number, longitude, latitude, city, and grid number. The location data is randomly divided into three parts according to the same tag attributes crowd for the experiment, and the corresponding graph database is generated by the trajectory graph database construction algorithm (GDC) as follows.In the experiments, we use three encrypted real data sets: DATA1, DATA2, and DATA3. The characteristics of these data sets are summarized in Table2. Besides, the privacy budget ε is set to 15, ε1:ε2=3:2. We employ three widely used metrics in travel trajectory frequent pattern mining based on differential privacy protection (TMDP): F‐score, relative error, and run time.Table 2
Summary of graph data sets.
Data setTrajectoryNumber of verticesThe number of edgesThe weight rangeDATA153314325165380-5DATA2132718593284765-15DATA3657152362021215-20


### 6.1.F‐score

F−score=P∗R/P+R,F−score∈0,1, and P=UP∩UC/UP; P is accuracy and R is recall rate. Up represents the frequent subgraph mined based on differential privacy and UC represents the exact frequent subgraph mined. Within the range of 0-1, the larger the F−score value is, the higher the data utility of the algorithm will be.


### 6.2. Relative Error (RE)

RE=medianx∈UP∣nsupx−supx∣/supx is used to measure the error with respect to the true supports of frequent subgraphs. The smaller the RE is, the higher the data utility of the algorithm is.


### 6.3. Run Time

Run time reflects the influence of parameters and data sets on experimental results and intuitively represents the operating efficiency of the algorithm.In the experiment, we introduce the Basic1 comparison algorithm which introduces Laplace noise into the frequent subgraph mining algorithm of Apriori. The Basic2 algorithm only adds Laplace noise into the frequent subgraph mining process in this paper. This paper will measure the performance of the algorithms (Basic1, Basic2, and TMDP) from three aspects: (1) analysis ofF‐score based on frequency threshold θ, (2) analysis of relative error based on frequency threshold θ, and (3) analysis of algorithm running time .(1)
Analysis of results based on frequency thresholdθAs shown in Figure8, with the increase of threshold θ, fewer subgraphs match the thresholdθ condition during frequent subgraph mining. Therefore, with the increase of T, the F-score also increases, and the data utility also increases. In the three data sets, the data utility of the TMDP framework is better than algorithm Basic1 and algorithm Basic2, and it is more obvious in the relatively large data set DATA2. When the threshold θ is 0.6, the data utility reaches 0.79, which indicates that the TMDP framework has a better overall performance on the trajectory graph protection algorithms.(2)
Analysis of relative error based on frequency thresholdθFigure 8
The scoring performance (F‐score) of each data set under the change of threshold θ.As shown in Figure9, with the increase of the threshold θ, the value of RE is constantly decreasing. When the threshold is smaller, the number of false frequent graphs will be larger, which makes the relative error of the results larger; that is, the RE will increase. The experimental results of this paper show that when the threshold is selected around 0.5, the RE result performs relatively well. The overall performance of the DMP framework for the three data sets is much better than that of Basic1.(3)
Analysis of algorithm running time run timeFigure 9
The relative error of each data set based on frequency thresholdθ.Finally, we compared the running time of each algorithm, as shown in Figure10. In contrast, the TMDP framework consumes more time. Meanwhile, the larger the threshold θ, the less time is consumed, because the larger threshold θ, the fewer frequent subgraphs in the graph set that meet the conditions, and the smaller running time. From the comparison of the three graphs, the larger the data set, the greater the number of graphs, and therefore, the more time consumed.Figure 10
Comparison of running time of each algorithm.In the above experiments, travel trajectory frequent pattern mining based on differential privacy protection (TMDP) can realize privacy protection on the premise of ensuring data utility. Although the overall running time and work are increased, it reduces running time and improves data utility. We can see that our TMDP framework achieves better performance.


## 6.1.F‐score

F−score=P∗R/P+R,F−score∈0,1, and P=UP∩UC/UP; P is accuracy and R is recall rate. Up represents the frequent subgraph mined based on differential privacy and UC represents the exact frequent subgraph mined. Within the range of 0-1, the larger the F−score value is, the higher the data utility of the algorithm will be.


## 6.2. Relative Error (RE)

RE=medianx∈UP∣nsupx−supx∣/supx is used to measure the error with respect to the true supports of frequent subgraphs. The smaller the RE is, the higher the data utility of the algorithm is.


## 6.3. Run Time

Run time reflects the influence of parameters and data sets on experimental results and intuitively represents the operating efficiency of the algorithm.In the experiment, we introduce the Basic1 comparison algorithm which introduces Laplace noise into the frequent subgraph mining algorithm of Apriori. The Basic2 algorithm only adds Laplace noise into the frequent subgraph mining process in this paper. This paper will measure the performance of the algorithms (Basic1, Basic2, and TMDP) from three aspects: (1) analysis ofF‐score based on frequency threshold θ, (2) analysis of relative error based on frequency threshold θ, and (3) analysis of algorithm running time .(1)
Analysis of results based on frequency thresholdθAs shown in Figure8, with the increase of threshold θ, fewer subgraphs match the thresholdθ condition during frequent subgraph mining. Therefore, with the increase of T, the F-score also increases, and the data utility also increases. In the three data sets, the data utility of the TMDP framework is better than algorithm Basic1 and algorithm Basic2, and it is more obvious in the relatively large data set DATA2. When the threshold θ is 0.6, the data utility reaches 0.79, which indicates that the TMDP framework has a better overall performance on the trajectory graph protection algorithms.(2)
Analysis of relative error based on frequency thresholdθFigure 8
The scoring performance (F‐score) of each data set under the change of threshold θ.As shown in Figure9, with the increase of the threshold θ, the value of RE is constantly decreasing. When the threshold is smaller, the number of false frequent graphs will be larger, which makes the relative error of the results larger; that is, the RE will increase. The experimental results of this paper show that when the threshold is selected around 0.5, the RE result performs relatively well. The overall performance of the DMP framework for the three data sets is much better than that of Basic1.(3)
Analysis of algorithm running time run timeFigure 9
The relative error of each data set based on frequency thresholdθ.Finally, we compared the running time of each algorithm, as shown in Figure10. In contrast, the TMDP framework consumes more time. Meanwhile, the larger the threshold θ, the less time is consumed, because the larger threshold θ, the fewer frequent subgraphs in the graph set that meet the conditions, and the smaller running time. From the comparison of the three graphs, the larger the data set, the greater the number of graphs, and therefore, the more time consumed.Figure 10
Comparison of running time of each algorithm.In the above experiments, travel trajectory frequent pattern mining based on differential privacy protection (TMDP) can realize privacy protection on the premise of ensuring data utility. Although the overall running time and work are increased, it reduces running time and improves data utility. We can see that our TMDP framework achieves better performance.


## 7. Conclusion

In order to solve the problem of the balance between the utility and security of user location data privacy under the mobile Internet service, we propose a weighted trajectory graph model scheme, which converts the discrete location data of users into graph data based on weighted frequent graph pattern. The weighted trajectory graph model not only preserves the characteristics of users’ trajectories but also facilitates the establishment of privacy-preserving data mining algorithm. In order to ensure the utility of the location data in our privacy protection framework (TMDP), we make double processes of adding noises to the subgraph mining process by the Laplace mechanism and selecting final data by the exponential mechanism. The experiments show that the data utility of the proposed frame is higher and the privacy protection of the frame is effective. However, Internet applications require high real-time and diversity of location data; how to customize efficient privacy protection model and improve data availability under high-dimensional data sources in specific scenarios will be the main research direction in the future.



---

*Source: 6379530-2021-08-10.xml*