基于地理社交网络的频繁位置隐私保护算法

宁雪莉，罗永龙，邢 凯，郑孝遥

(1.安徽师范大学 数学计算机科学学院，安徽 芜湖 241002； 2.网络与信息安全安徽省重点实验室(安徽师范大学)，安徽 芜湖 241002)

0 引言

地理社交网络(GeoSocial Network, GSN)本质上是具有地理位置坐标特性的社交网络，从社交网络如Facebook、Twitter到基于位置的社交网络如Foursquare，用户通过带有定位功能的移动设备签到并彼此分享位置，同时利用这些地理位置信息，可以获取更多个性化定制服务，如导航、兴趣点推荐、智能交通等，因此分析并发布用户位置数据信息很有应用意义。然而用户频繁签到的位置可能包含用户极其敏感的个人信息，简单发布这些数据会导致用户个人身份和其他敏感信息泄露，因此，用户频繁位置的隐私保护是目前一个重要的研究热点。

社交网络中用户身份信息泄露已经得到广泛研究[1-5]，然而由于地理社交网络中涉及用户的位置信息，若将上述隐私保护方法直接应用到地理社交网络中仍然存在一些弊端。如攻击者了解目标用户在某一个时刻频繁访问某个或某几个位置，而在这个时刻只有一个用户在该位置签到，那么攻击者就可以根据了解的背景知识将用户和频繁位置唯一匹配，推测出用户身份信息，导致用户身份以及其他和位置有关的敏感信息泄露。

为解决上述问题，本文提出了一个(k,c)-anonymity算法。首先根据用户访问位置的频次设置频繁位置集合；然后将这些频繁位置的子集组合成超边，把不满足匿名参数k的超边进行重组，通过该算法泛化用户频繁访问位置；最后发布地理社交网络数据信息，并且通过Brightkite和Gowalla数据集进行实验验证，结果表明在保证安全性的同时降低了用户的信息损失率。

1 相关工作

多数位置隐私保护技术都是基于k匿名实现的[6-9]。文献[6]提出时空匿名保护技术：New Caper算法，通过空间索引技术组织各个移动对象来提高位置泛化和查询功能。文献[7]使用网格进行k匿名，并在此基础上增加位置多样性，进而提高隐私保护的程度。文献[8]根据位置服务查询结果的相似性来构造匿名区域实现位置隐私保护。文献[9]针对现有位置隐私保护机制忽略隐式收集时空数据而导致隐私泄漏的问题，提出基于时空数据发布中隐式隐私保护方法。上述研究主要是解决基于位置服务的匿名查询问题，仅仅针对用户单点位置进行隐私保护且与地理社交网络中数据匿名方式不同。文献[10-11]提出基于区域的伪装(Region-based Cloaking, CR)算法，该算法的核心是使CR尽可能小以提高服务质量，对于每个查询可信匿名服务器生成一个至少包含k个真实用户位置的CR。在文献[12]中指出连续查询服务需要生成较大的CR，导致服务质量降低，同时基于CR方法的问题也在于潜在k匿名范式易受到背景知识攻击，尤其在地理社交网络中对于时刻签到的用户，攻击者可以用某些特殊位置重构用户身份，进而导致用户身份泄露。

文献[13]介绍一种基于地理社交网络的频繁位置Lk-anonymity模型，该模型认为攻击者了解目标用户所有的频繁位置，但这种假设与实际情况不符。文献[14]提出并定义一种以表格方式处理数据的(k,l)-anonymity模型，该模型数据的处理格式与地理社交网络数据格式不同，且没有把频繁位置作为用户敏感信息的一部分来处理，因此这种方式不能直接应用于地理社交网络。文献[15]提出(k,m)-anonymity频繁位置模型，利用地理社交网络特性，引入社交网络超边重新组合思想构造匿名，这种方式有效地减弱了背景知识攻击以及用户身份泄露风险，但其随机的超边重组机制导致用户偏离度以及位置偏离度较大，使得数据有效性较低。

为此，本文根据地理社交网络特性设计一种频繁位置匿名模型，并提出一个新的隐私保护算法(k,c)-anonymity算法，首先针对地理社交网络中用户频繁位置隐私泄露问题，构建一个基于用户频繁位置的隐私保护模型，利用(k,c)-anonymity算法泛化用户频繁访问位置，采用超边相交机制和最近距离决定超边重组策略对用户频繁访问位置进行匿名，从而实现对用户签到信息进行局部抑制操作。通过实验证明，该算法降低了用户和位置的偏离度，减少了信息损失，提高了地理社交网络发布数据的有效性。

2 相关定义

定义1 位置差异性。位置li与位置lj之间的距离远近程度称为位置差异性，其中li坐标为(lati,loni)，lj坐标为(latj,lonj)，由欧氏距离公式表示如下：

(1)

定义2 频繁位置。 用户在一定时间内多次访问同一个位置，并根据用户访问位置的频次，对访问超过一定次数的位置称为频繁位置。对于用户频繁访问的位置本文设定为敏感信息，需要保护的对象。

定义3 频繁位置矩阵。V={v1,v2,…,vm}表示所有用户的集合，L={l1,l2,…,ln}表示用户所访问的位置集合，那么用户的频繁位置矩阵表示为VLm×n，如表1中用户-位置矩阵表示。

定义4 频繁位置选择。对于一个位置li属于用户vi的m个频繁访问的位置Lm={l1,l2,…,lm}，当且仅当：

(2)

如果用户vi在一定时间内访问位置li的次数超过系统设定的value值则认为li是用户vi的频繁位置。频繁位置的选择也是数据集处理的一种方式，采用何种方式处理数据集并不会影响匿名效果。通过式(2)，可将表1中的VL矩阵处理成表2中的频繁位置矩阵。

表1 用户访问位置次数Tab. 1 User check-in location frequency

表2 频繁位置转换Tab. 2 Frequent location conversion

定义5 将地理社交网络定义为GSN(V,L,HE,fv,c),其中：V表示用户节点集合，L表示位置集合，HE表示所有超边集合，fv表示由V→L的映射关系，c表示攻击者了解目标用户的频繁位置即背景知识。

定义6 身份重构。在一个GSN中，对于一个用户v的超边eh在整个地理社交网络中是唯一的，那么用户v的身份可以被攻击者唯一识别，称为身份重构。

由表2频繁位置矩阵得到地理社交网络图1(a)，假设c=2即攻击者知道目标用户的两个频繁位置l1和l5，由于访问这两个频繁位置的用户只有v3，那么v3的身份被重构，即被攻击者识别。同理，用户v4和v5也可以用同样的方式重构。

定义7 超边。用户频繁位置的子集组成的边称为超边。

定义8 超边相交。一个超边eh1和另一超边eh2之间有相同的频繁访问位置点，称为超边相交，记为eh1∩eh2。

定义9 超边重组。为抵御身份重构的攻击，需要将超边个数达到匿名参数k值，超边之间的重新组合，称为超边重组。

定义10 (k,c)-anonymity。对于一个GSN(V,L,HE,fv,c)，使得每个用户的超边eh个数都不少于匿名参数k值，称为(k,c)-anonymity。

鉴于图1(a)中出现的身份重构现象，如构造(2,2)-anonymity方式抵御背景知识攻击，v3的超边{l1,l5}和v4的超边{l1,l4}相交于位置l1，将v4的频繁位置l4转变l5，通过超边重组v4的超边为{l1,l5}，同理v5的超边为{l3,l5}，由此处理可得表3匿名之后的频繁位置矩阵以及图1(b)。

表3 匿名的频繁位置Tab. 3 Anonymous frequent location

图1 地理社交网络 Fig. 1 Geosocial network

3 隐私保护算法

3.1 (k,c)-anonymity算法描述

在处理地理社交网络存在的身份重构时，(k,m)-anonymity算法[15]的步骤主要是：首先将超边思想引入地理社交网络中，寻找不满足匿名参数k的超边；其次是随机选择两个或者多个不满足条件的超边进行随机组合；最后计算随机组合超边个数，使其达到k匿名目的。由于该算法并没有考虑超边相交和重组机制，并且每次搜寻超边都需要扫描超边集合中所有的边，这样使得用户位置信息偏离原始数据的程度增大，而且若对用户所有超边每次进行扫描，导致数据的有效性降低，花费的时间代价较大。

因此，本文提出一种改进的(k,c)-anonymity算法(具体见算法1)：首先输入部分地理社交网络数据以及给定匿名参数k，将所有用户存储到V集合中，所有访问位置存储到L集合中，所有超边存储到HE集合中，这样减少了每次遍历集合中元素的时间，然后再根据定义7统计不满足匿名参数k的超边个数(见算法1第4～7行)，并将不满足超边个数k存储到一个集合M中，从M中随机选择一个超边作处理，由于HE元素个数大于M，从而在每次遍历用户超边时不需要访问HE集合降低了时间代价；其次根据定义8和9优先考虑有共同交点的超边，若|eh∩eh2|>1说明超边之间有交点，那么将超边进行重组直到满足参数k(见算法1第8～15行)，若|eh∩eh2|=0即它们之间没有公共点，将按照dmin=d(eh,eh2)计算超边之间的位置差异，d的值越小那么位置偏离越小，数据的有效性越高(见算法1第17行)。这样可以保证重组的代价最小以及位置信息损失率最低，最后将两个超边重新组合(见算法1第20～21行)，最终数据有效性得到提高。具体描述如下。

算法1 (k,c)-anonymity。

输入:GSN(V,L,HE,fv,c)以及匿名参数k值；

输出:GSN′(V,L′,HE′,fv′,c)。

1)

V←{v1,v2,…,vn};

2)

L←{l1,l2,…,ln};

3)

HE({eh1,eh2,…,ehn};

4)

if(|V|>k&& |L|>c)

5)

count← number of hyperedges set that less than parameterk

6)

ifcount=0

7)

break

8)

M← all of hyperedges which rank less thankput into a set

9)

eh← select a hyperedge fromMrandomly

10)

eh1=null

11)

foreh2inM

12)

ifeh=eh2

//表示超边自身重组

13)

continue

14)

if(0< |eh∩eh2|≤c-1)

15)

mergeehandeh2

16)

else

17)

dmin=d(eh,eh2)

18)

end if

19)

end for

20)

eh1←eh2

21)

mergeehandeh1

22)

return GSN′(V,L′,HE′,fv′,c)

23)

end if

3.2 复杂度分析

算法1的运行时间主要用于处理超边选择和超边重组，超边重组过程实际是两个位置集合的泛化过程。该算法每次迭代的过程需要从M集合中随机选择一个超边与该集合中另外一条超边重新组合，超边重组过程的时间复杂度为O(n*n)，直到满足匿名参数k值时停止迭代操作，因此，算法1整体的时间复杂度为O(k*n2)。

3.3 衡量标准

信息损失率是衡量数据发布有效性的重要指标。基于目前地理社交网络对用户空间数据挖掘处理时，导致用户以及位置信息损失较大问题，本文将从用户偏离度和位置偏离度[15]这两个方面衡量(k,c)-anonymity算法的数据有效性。

1)用户偏离度：

(3)

其中：rank(eh)表示匿名之前地理社交网络中超边eh的个数，同理rank′(eh)表示匿名之后eh的个数。Zub值越小，表明用户偏离度越小，和原始数据集的相似度越大，得到的数据有效性越高。

2)位置偏离度：

(4)

其中：f(v)表示匿名之前的地理社交网络中用户频繁位置集合，同理f′(v)表示匿名之后的频繁位置集合。若Zlb值越小表明用户频繁访问的位置偏离度越小，用户满意度越高，并且用户要求服务时，获取的服务质量就越高。

4 实验

4.1 实验数据集

实验算法环境为Intel Core2 Quad CPU Q9500 2.83 GHz,4 GB内存，操作系统为Microsoft Windows 7，算法使用Java语言实现。实验采用两个地理社交网络数据集Brightkite和Gowalla，由于数据具有无法避免的稀疏特性，对该原始数据进行处理，选择频繁位置个数大于c的用户，按照定义(2)中频繁位置选择机制处理这两个数据集，选择合理的频繁位置，使得该数据集分别包含556个用户和1 087个用户，及分别包括1 451和1 403个频繁位置。

4.2 实验结果与分析

基于3.3节的用户偏离度和位置偏离度衡量标准，本文对(k,c)-anonymity算法与(k,m)-anonymity算法进行比较，图2～3表明两个算法在不同的签到数据集分别在两个衡量标准的对比结果。

图2 不同数据集的用户偏离度 Fig. 2 Bias of user on different dataset

图3 不同数据集的位置偏离度 Fig. 3 Bias of location on different dataset

图2分别表示在Brightkite和Gowalla数据集中用户偏离度的表现，在背景知识不同、k值不同情况下用户偏离度的对比情况。从图2第1列中可以看出，当背景知识为1时，近似演变为位置k匿名的情况，仅对单一位置进行隐私保护，得到用户偏离度较(k,m)-anonymity算法相比仍然很低；同时从图2第3列中也可以看出在同一个背景知识c=3的情况下，随着k值的不断增大，整体趋势表明用户偏离度不断增大，但和文献[15]中的m=3背景知识相比，本文用户偏离度明显降低，尤其当k=5时用户偏离度下降最为显著。这是由于本文考虑超边重组时超边之间的相交现象，优先重组超边之间有交点的情况，这样可以缩减用户偏离度。同样，当k值相同的情况下，由图2可以看出随着背景知识不断的增大(c=1,c=2,c=3)，用户偏离度也不断增大，这是由于为了抵御背景知识攻击，需要将不满足匿名参数k的其他用户放入一个匿名组中，因此，导致用户偏离度增大，损失率会增大的表现。

从图3的1～3列中可以分别看出，在同一个背景知识条件下，随着k值不断增大，用户位置偏离度也呈现出增大的趋势，这是由于随着k值不断增大，用户必须将不满足匿名参数的超边进行重组，导致用户位置偏离度增大。同样，也可以看出在同一个k值条件下，随着背景知识的增大(c=1,c=2,c=3)，位置偏离度也在增大，这是由于攻击者掌握目标用户的背景知识越多，那么为了抵御这种攻击得到k匿名的结果，导致一些频繁位置重新组合，因此，导致了位置偏离度增大。 (k,c)-anonymity算法从两个方面考虑超边之间的重组标准：一是超边之间的有无共同交点即决定了位置差异性的大小；另一个则是超边重组之后位置偏离度标准，总是寻找最近位置即决定发布之后数据的可用性标准。相比(k,m)-anonymity算法，进行匿名时忽略了这两个因素，仅仅把花费最小代价考虑在其范围内，导致位置偏离度较大的现象。

综上，实验结果表明，本文提出的一种基于频繁位置的隐私保护算法——(k,c)-anonymity，在用户偏离度以及位置偏离度两个衡量标准上，与(k,m)-anonymity算法比较均有较好的表现。

5 结语

本文针对地理社交网络中以用户频繁访问位置为背景知识进行攻击而导致用户身份泄露问题，提出一种基于地理社交网络的频繁位置隐私保护算法——(k,c)-anonymity，该算法避免了用户和位置偏离度较大的超边重组，从而提高了数据的有效性。实验结果表明，通过改变c值和k值，(k,c)-anonymity算法在用户偏离度以及位置偏离度衡量标准上均优于(k,m)-anonymity算法。未来拟开展隐私保护的数据挖掘研究，并与地理社交网络中的个性化推荐方法相结合，在提高服务质量的同时也可以保护用户隐私。

参考文献(References)

[1] BHATTACHARYA M, MANI P. Preserving privacy in social network graph withK-anonymize degree sequence generation [C]// Proceedings of the 2015 9th International Conference on Software, Knowledge, Information Management and Applications. Piscataway, NJ: IEEE, 2016: 1-7.

[2] DAS S, EGECIOGLU O, ELABBADI A. Anónimos: an LP-based approach for anonymizing weighted social network graphs [J]. IEEE Transactions on Knowledge and Data Engineering, 2012, 24(4): 590-604.

[3] PARRIS I, HENDERSON T. Privacy-enhanced social-network routing [J]. Computer Communications, 2012, 35(1): 62-74.

[4] MITTAL P, PAPAMANTHOU C, SONG D. Preserving link privacy in social network based systems [EB/OL]. [2017- 03- 01]. http://www.princeton.edu/～pmittal/publications/link-privacy-ndss13.pdf.

[5] SWEENEY L.k-anonymity: a model for protecting privacy [J]. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2002, 10(5): 557-570.

[6] MOKBEL M F, CHOW C Y, AREF W G. The new Casper: query processing for location services without compromising privacy [C]// VLDB ’06: Proceedings of the 32nd International Conference on Very Large Data Bases. Seoul, Korea: VLDB Endowment, 2006: 763-774.

[7] BAMBA B, LIU L, PESTI P, et al. Supporting anonymous location queries in mobile environments with privacygrid [C]// WWW ’08: Proceedings of the 17th International Conference on World Wide Web. New York: ACM, 2008: 237-246.

[8] 叶阿勇,李亚成,马建峰,等.基于服务相似性的k-匿名位置隐私保护方法[J].通信学报,2014,35(11):162-169.(YE A Y, LI Y C,MA J F, et al. Location privacy-preserving method ofk-anonymous based-on service similarity [J]. Journal on Communications, 2014, 35(11): 162-169.)

[9] 王璐,孟小峰,郭胜娜.时空数据发布中的隐式隐私保护[J].软件学报,2016,27(8):1922-1933.(WANG L, MENG X F, GUO S N. Preservation of implicit privacy in spatio-temporal data publication [J]. Journal of Software, 2016, 27(8): 1922-1933.)

[10] GEDIK B, LIU L. Location privacy in mobile systems: a personalized anonymization model [C]// ICDCS ’05: Proceedings of the 25th International Conference on Distributed Computing Systems. Washington, DC: IEEE Computer Society, 2005: 620-629.

[11] KALNIS P, GHINITA G, MOURATIDIS K, et al. Preventing location-based identity inference in anonymous spatial queries [J]. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(12): 1719-1733.

[12] CHOW C Y, MOKBEL M F. Enabling private continuous queries for revealed user locations [C]// SSTD ’07: Proceedings of the 10th International Conference on Advances in Spatial and Temporal Databases. Berlin: Springer, 2007: 258-275.

[13] MASOUMZADEH A, JOSHI J. Top location anonymization for geosocial network datasets [J]. Transactions on Data Privacy, 2013, 6(1):107-126.

[14] STOKES K. On computational anonymity [C]// PSD ’12: Proceedings of the 2012 International Conference on Privacy in Statistical Databases. Berlin: Springer, 2012: 336-347.

[15] LI Y, LI Y, XU G. Protecting private geosocial networks against practical hybrid attacks with heterogeneous information [J]. Neurocomputing, 2016, 210: 81-90.

This work is partially supported by the National Natural Science Foundation of China (61672039, 61370050, 61772034), the Natural Science Foundation of Anhui Province (KJ2017A327), the Wuhu Science and Technology Project (2015cxy10).

NINGXueli, born in 1993, M. S. candidate. Her research interests include information security,privacy preserving.

LUOYonglong, born in 1972, Ph. D., professor. His research interests include spatial data processing, information security,privacy preseving.

XINGKai, born in 1985, M. S. candidate. His research interests include information security,privacy preserving.

ZHENGXiaoyao, born in 1981, Ph. D. candidate, associate professor. His research interests include information security, personalized recommendation.