# An Efficient Approach for LBS Privacy Preservation in Mobile Social Networks
## 6 Evaluation
### Performance Analysis  
Assume that there is a clustering process which contains \(k_{c}\) users and a data-pool which contains \(l_{c}\) different kinds of service category, \(k_{c}\) and \(l_{c}\) are both random constant. Because PLAM, LLB, and our SCTB adopt the system architecture of TTP-free, and the kinds of service category in a clustering group are both figured out by the representative of the clustering group, the two algorithms (i.e., PLAM and LLB algorithm) are used for comparison. We assume that all conditions are the same and meet the premise that one user sends one kind of service category in a clustering process. For example, user [PERSON] only sends one request about finding a restaurant in one clustering process, but he cannot send the request that contains both finding a restaurant and a hospital at the same time. We now give the computational cost of our SCTB and PLAM about the process of identifying and calculating l-diversity.  
**Claim 1**.: _In a clustering process, ignoring the computational complexity of decryption, the computational complexity of SCTB on figuring out l-diversity is \(O(k_{c}E)+O(l_{c})\)._  
**Proof of Claim 1.** Firstly, the \(k_{c}\) users should add together to form \(pk_{1}(SL_{i})\), and \(pk_{1}\) is the public key of the representative. We can know the computational complexity is \(O(k_{c}E)\)[32]. Then we decrypt \(pk_{1}(SL_{i})\) and get \(SL_{i}\), the \(NSC\) can be figured out by \(SC_{i}=SL_{i}\bigcap AE_{i}\). Because the number of \(AE_{i}\) is equal to \(l_{c}\), and \(l_{c}\) is the total kinds of service category that can be represented. Therefore, the computational complexity is \(O(l_{c})\). Ignoring the computational complexity of decryption, the computational complexity of this process is \(O(k_{c}E)+O(l_{c})\).  
**Claim 2**.: _In a clustering process, ignoring the computational complexity of decryption, the computational complexity of PLAM on figuring out l-diversity is \(k_{c}O(l_{c})+l_{c}O(k_{c}E^{k_{c}})\)._Proof of Claim 2.: Under the same settings as above. PLAM adopts a set \(a_{i}=(a_{i1},a_{i2},...,a_{in})\) to denote different kinds of service category that available to a \(user_{i}\), and the set also means the total kinds of service category that can be represented is n, where the number n is equivalent to \(l_{c}\). Firstly, the representative should calculate \(pk(\tilde{a}_{i})=(pk(1-a_{i1}),pk(1-a_{i2}),...,pk(1-a_{in}))\), and we know the computational complexity is \(k_{c}O(l_{c})\). Then users cooperatively exchange \(pk(\tilde{a}_{i})\) and calculate \(\prod\limits_{i=1}^{k_{c}}pk(\tilde{a}_{i})=(\prod\limits_{i=1}^{k_{c}}pk(1-a _{i1}),...,\prod\limits_{i=1}^{k_{c}}pk(1-a_{in}))\), and we know the computational complexity of \(\prod\limits_{i=1}^{k_{c}}pk(1-a_{i1})\)is \(O(k_{c}E^{k_{c}})\). Therefore, the computational complexity of \(\prod\limits_{i=1}^{k_{c}}pk(\tilde{a}_{i})\) is \(l_{c}O(k_{c}E^{k_{c}})\). Ignoring the computational complexity of decryption, the computational complexity of this process is \(k_{c}O(l_{c})+l_{c}O(k_{c}E^{k_{c}})\).  
According to above-mentioned analysis, we can know that the computational complexity of our SCTB is smaller than the PLAM. Therefore, it is helpful to finish the clustering process as well as reduce the communication overhead among users.