# An Efficient Approach for LBS Privacy Preservation in Mobile Social Networks
## 5 Algorithm Design
### Representative Aggregation Protocol  
According to the given security parameters \(th_{k}\) and \(th_{l}\) in a region, both \(th_{k}\) and \(th_{l}\) are not met in an original clustering group. If the success of this clustering group needs to be promoted, the method is to combine with other clustering groups that have the same conditions (i.e., \(k<th_{k}\), \(l<th_{l}\)). The reason is that the cooperation among clustering groups could have a higher success probability to promote the success of the original clustering group than just waiting for new users to join. Besides, if other clustering groups nearby are found finally, the time cost of clustering will also be reduced. When the users' kinds of service category are similar or even identical in a certain time and space, for the original clustering group, newly-joining users are more likely to contribute to the value of \(k\) rather than the value of \(l\). Note that our method is not to prevent new users from joining, but to find other clustering groups as the first choice.  
From the variety judgment protocol, we can know the number of \(l\) and \(k\) in \(PID_{1}^{CP1}\). Assume that the case is \(k<th_{k}\) and \(l<th_{l}\). \(PID_{1}^{R}\) begins to broadcast the representative aggregating message, but different from request aggregating message, the representative aggregating message can only be responded by representatives. Suppose that there is a clustering group \(PID_{b}^{CP2}\) with the same conditions (i.e., \(k<th_{k}\), \(l<th_{l}\)) as \(PID_{1}^{CP1}\), and its representative \(PID_{b}^{R}\) responds to \(PID_{1}^{R}\). Firstly, \(PID_{1}^{R}\) will send his \(pk_{1}\) to \(PID_{b}^{R}\), then \(PID_{b}^{R}\) sends his current set of pseudo-IDs and encrypted sum \(pk_{1}(SL_{i})\) back to \(PID_{1}^{R}\). Note that this \(SL_{i}\) is from decrypted \(pk_{b}(SL_{i})^{CP2}\). Then, \(PID_{1}^{R}\) will set \(NCG_{PID_{1}^{R}}=2\) and recalculate the value of \(NSC\). Finally, the current \(NSC\) is figured out by the combined sum which is obtained by adding \(SL_{i}\) of \(PID_{1}^{CP1}\) and \(SL_{i}\) of \(PID_{b}^{CP2}\). According to the relationship of current \(k\) and \(l\) between \(th_{k}\) and \(th_{l}\), \(PID_{1}^{R}\) chooses the different protocol mentioned above to finish the subsequent process. Algorithm 4 describes the pseudo code of the representative aggregation protocol.  
```
0: New clustering groups, \(pk_{1}(SL_{i})\)
0: New \(l\), New \(k\)
1:while\(T>0\), \(k<th_{k}\) and \(l<th_{l}\)do
2:\(PID_{1}^{R}\) broadcasts the representative aggregating message, then the \(PID_{b}^{R}\) responds;
3:\(pk_{1}\to PID_{b}^{R}\)
4: The pseudo-IDs set of \(PID_{b}^{R}\) and \(pk_{1}(SL_{i})\to PID_{1}^{R}\);
5:\(NCG_{PID_{1}^{R}}=2\), and \(PID_{1}^{R}\) gets current \(k\) and \(l\) from combined sum \(SL_{i}\);
6:if\(k\geq th_{k}\) and \(l\geq th_{l}\)then
7: The clustering process is a success, the remaining work will be performed;
8:endif
9:if\(k<th_{k}\) and \(l\geq th_{l}\)then
10: Waiting for new users to join;
11:endif
12:if\(k\geq th_{k}\) and \(l<th_{l}\)then
13: Filtering aggregation protocol is adopted;
14:endif
15:if\(k<th_{k}\) and \(l<th_{l}\)then
16: Representative aggregation protocol is adopted;
17:endif
18:endwhile
```  
**Algorithm 4** Representative aggregation