Frequent location privacy-preserving algorithm based on geosocial network

doi:10.11772/j.issn.1001-9081.2017071686

Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (3): 688-692.DOI: 10.11772/j.issn.1001-9081.2017071686

Previous Articles Next Articles

Frequent location privacy-preserving algorithm based on geosocial network

NING Xueli^1,2, LUO Yonglong^1,2, XING Kai^1,2, ZHENG Xiaoyao^1,2

1. College of Mathematics and Computer Science, Anhui Normal University, Wuhu Anhui 241002, China;
2. Anhui Provincial Key Laboratory of Network and Information Security(Anhui Normal University), Wuhu Anhui 241002, China

Received:2017-07-10 Revised:2017-09-15 Online:2018-03-10 Published:2018-03-07
Supported by:
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).

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

宁雪莉^1,2, 罗永龙^1,2, 邢凯^1,2, 郑孝遥^1,2

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

通讯作者: 宁雪莉
作者简介:宁雪莉(1993-),女,安徽亳州人,硕士研究生,主要研究方向:信息安全、隐私保护;罗永龙(1972-),男,安徽太湖人,教授,博士生导师,博士,CCF会员,主要研究方向:空间数据处理、信息安全、隐私保护;邢凯(1985-),男,安徽芜湖人,硕士研究生,主要研究方向:信息安全、隐私保护;郑孝遥(1981-),男,安徽芜湖人,副教授,博士研究生,主要研究方向:信息安全、个性化推荐。
基金资助:
国家自然科学基金资助项目（61672039，61370050，61772034）；安徽省自然科学基金资助项目（KJ2017A327）；芜湖市科技计划项目（2015cxy10）。

Abstract

Abstract: Focusing on the attack of frequent location as background knowledge causing user identity disclosure in geosocial network, a privacy-preserving algorithm based on frequent location was proposed. Firstly, The frequent location set was generated by the frequency of user check-in which was allocated for every user. Secondly,according to the background knowledge, hyperedges were composed by frequent location subset. Some hyperedges were remerged which did not meet anonymity parameter k, meanwhile the minimum bias of user and bias of location were chosen as hyperedges remerging metrics. Finally, in the comparison experiments with (k,m)-anonymity algorithm, when the background knowledge was 3, the average bias of user and bias of location were decreased by about 19.1% and 8.3% on dataset Gowalla respectively, and about 22.2% and 10.7% on dataset Brightkite respectively. Therefore, the proposed algorithm can effectively preserve frequent location privacy, and reduces bias of user and location.

Key words: GeoSocial Network (GSN), privacy-preserving, k-anonymity, location generalization, location privacy

摘要： 针对地理社交网络中以频繁位置为背景知识的攻击导致用户身份泄露的问题，提出一种基于地理社交网络的频繁位置隐私保护算法。首先，根据用户对位置访问的频次设置频繁位置并为每个用户建立频繁位置集合；然后按照背景知识的不同，将频繁位置的子集组成超边，把不满足匿名参数k的超边以用户偏离和位置偏离最小值为优化目标进行超边重组；最后，通过仿真实验表明，与（k，m）-anonymity算法相比，在频繁位置为3的情况下，该算法在Gowalla数据集上用户偏离度以及位置偏离度分别平均降低了约19.1%和8.3%，在Brightkite数据集上分别平均降低了约22.2%和10.7%，因此所提算法能够有效保护频繁位置的同时降低用户和位置偏离度。

关键词: 地理社交网络, 隐私保护, k-匿名, 位置泛化, 位置隐私

CLC Number:

TP309.2

NING Xueli, LUO Yonglong, XING Kai, ZHENG Xiaoyao. Frequent location privacy-preserving algorithm based on geosocial network[J]. Journal of Computer Applications, 2018, 38(3): 688-692.

宁雪莉, 罗永龙, 邢凯, 郑孝遥. 基于地理社交网络的频繁位置隐私保护算法[J]. 计算机应用, 2018, 38(3): 688-692.

References

[1] BHATTACHARYA M, MANI P. Preserving privacy in social network graph with K-anonymize degree sequence generation[C]//Proceedings of the 20159th 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 of k-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.

Frequent location privacy-preserving algorithm based on geosocial network

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	WU Kaifan, YIN Xinchun. Lightweight anonymous mutual authentication protocol based on random operators for radio frequency identification system [J]. Journal of Computer Applications, 2021, 41(6): 1621-1630.
[2]	ZHANG En, LI Huimin, CHANG Jian. Verifiable k-means clustering scheme with privacy-preserving [J]. Journal of Computer Applications, 2021, 41(2): 413-421.
[3]	JIN Bo, ZHANG Zhiyong, ZHAO Ting. Location nearest neighbor query method for social network based on differential privacy [J]. Journal of Computer Applications, 2020, 40(8): 2340-2344.
[4]	YANG Yang, WANG Ruchuan. Location based service location privacy protection method based on location security in augmented reality [J]. Journal of Computer Applications, 2020, 40(5): 1364-1368.
[5]	LUO Huiwen, LONG Shigong. Location perturbation algorithm based on geo-indistinguishability of user’s region of interest [J]. Journal of Computer Applications, 2020, 40(3): 760-764.
[6]	LI Zhen, YAO Hanbing, MU Yicheng. Secure ranked search scheme based on Simhash over encrypted data [J]. Journal of Computer Applications, 2019, 39(9): 2623-2628.
[7]	FU Yu, WANG Hong. Virtual trajectory filling algorithm for location privacy protection [J]. Journal of Computer Applications, 2019, 39(8): 2318-2325.
[8]	WANG Yifei, LUO Yonglong, YU Qingying, LIU Qingqing, CHEN Wen. Trajectory privacy-preserving method based on information entropy suppression [J]. Journal of Computer Applications, 2018, 38(11): 3252-3257.
[9]	ZHANG Yaling, WANG Ting, WANG Shangping. Incremental frequent pattern mining algorithm for privacy-preserving [J]. Journal of Computer Applications, 2018, 38(1): 176-181.
[10]	HUO Zheng, CUI Honglei, HE Ping. k-CS algorithm: trajectory data privacy-preserving based on semantic location protection [J]. Journal of Computer Applications, 2018, 38(1): 182-187.
[11]	HUO Zheng, WANG Weihong, CAO Yuhui. PTDC:privacy-aware trajectory data collection technology under road network constraint [J]. Journal of Computer Applications, 2017, 37(9): 2567-2571.
[12]	ZUO Kaizhong, SHANG Ning, TAO Jian, WANG Taochun. Privacy-preserving incomplete data Skyline query protocol in two-tiered sensor networks [J]. Journal of Computer Applications, 2017, 37(6): 1599-1604.
[13]	ZHAO Dapeng, SONG Guangxuan, JIN Yuanyuan, WANG Xiaoling. Query probability-based location privacy protection approach [J]. Journal of Computer Applications, 2017, 37(2): 347-351.
[14]	DENG Jingsong, LUO Yonglong, YU Qingying, CHEN Fulong. Privacy-preserving trajectory data publishing based on non-sensitive information analysis [J]. Journal of Computer Applications, 2017, 37(2): 488-493.
[15]	ZHANG Xinpeng, XU Chunxiang, ZHANG Xinyan, SAI Wei, HAN Xingyang, LIU Guoping. Efficient public auditing scheme for cloud storage supporting user revocability with proxy re-signature scheme [J]. Journal of Computer Applications, 2016, 36(7): 1816-1821.