Edge partitioning approach for protecting sensitive relationships in social network

doi:10.11772/j.issn.1001-9081.2016.01.0207

Journal of Computer Applications ›› 2016, Vol. 36 ›› Issue (1): 207-211.DOI: 10.11772/j.issn.1001-9081.2016.01.0207

Previous Articles Next Articles

Edge partitioning approach for protecting sensitive relationships in social network

FAN Guoting^1,2, LUO Yonglong^1,2, SUN Dandan^1,2, WANG Taochun^1,2, ZHENG Xiaoyao^1,2

1. College of Mathematics and Computer Science, Anhui Normal University, Wuhu Anhui 241003, China;
2. Engineering Technology Research Center of Network and Information Security, Anhui Normal University, Wuhu Anhui 241003, China

Received:2015-08-04 Revised:2015-09-23 Online:2016-01-10 Published:2016-01-09
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61370050, 61402014) and the Natural Science Foundation of Anhui Province (1308085QF118).

基于边分割的社交网络敏感边保护技术

范国婷^1,2, 罗永龙^1,2, 孙丹丹^1,2, 王涛春^1,2, 郑孝遥^1,2

1. 安徽师范大学数学计算机科学学院, 安徽芜湖 241003;
2. 安徽师范大学网络与信息安全工程技术研究中心, 安徽芜湖 241003

通讯作者: 罗永龙(1972-),男,安徽太湖人,教授,博士,主要研究方向:信息安全、空间数据处理
作者简介:范国婷(1989-),女,安徽阜阳人,硕士研究生,主要研究方向:信息安全;孙丹丹(1990-),女,安徽六安人,硕士研究生,主要研究方向:隐私保护;王涛春(1979-),男,安徽芜湖人,副教授,博士,主要研究方向:传感器网络隐私保护;郑孝遥(1981-),男,安徽芜湖人,讲师,博士研究生,主要研究方向:空间数据处理。
基金资助:
国家自然科学基金资助项目(61370050,61402014);安徽省自然科学基金资助项目(1308085QF118)。

Abstract

Abstract: The sensitive relationships between users are important privacy information in social networks. Focusing on the issue of sensitive relationships leakage between users, an edge partitioning algorithm was proposed. Firstly, every non-sensitive edge was partitioned into some sub-edges after the sensitive edge was deleted in social networks. Secondly, every sub-edge was assigned information which belongs to the original non-sensitive edge. So every sub-edge contained part information of the original non-sensitive edge. The anonymized social network that preserves privacy was generated finally. In the comparison experiments with cluster-edge algorithm and cluster-based with constraints algorithm, the edge partitioning algorithm had a greater decrease of the probability of sensitive relationships leakage with maintaining high availability of data. The probability was decreased by about 30% and 20% respectively. As a result, the edge partitioning algorithm can effectively protect sensitive relationships in social networks.

Key words: social network, privacy preserving, sensitive relationship, partitioning, anonymization

摘要： 用户间的敏感关系是社交网络中用户的重要隐私信息。为了解决社交网络中用户间敏感关系泄露问题,提出一种边分割算法。首先,将已删除敏感边的简单匿名社交网络的非敏感边分割成多条子边;然后,将原非敏感边携带的信息分配到子边上,使得每条子边只携带原非敏感边的部分信息,从而生成具有隐私能力的匿名社交网络。理论分析和仿真实验结果表明,相比cluster-edge和cluster-based with constraints算法,边分割算法在保证数据具有较高可用性的情况下能更大限度降低敏感关系泄露的概率,泄露概率分别降低了约30%和20%,因此所提算法能够有效解决社交网络中敏感关系泄露问题。

关键词: 社交网络, 隐私保护, 敏感边, 分割, 匿名

CLC Number:

TP309.2

FAN Guoting, LUO Yonglong, SUN Dandan, WANG Taochun, ZHENG Xiaoyao. Edge partitioning approach for protecting sensitive relationships in social network[J]. Journal of Computer Applications, 2016, 36(1): 207-211.

范国婷, 罗永龙, 孙丹丹, 王涛春, 郑孝遥. 基于边分割的社交网络敏感边保护技术[J]. 计算机应用, 2016, 36(1): 207-211.

References

[1] 刘向宇,王斌,杨晓春.社会网络数据发布隐私保护技术综述[J].软件学报,2014,25(3):576-590.(LIU X Y, WANG B, YANG X C. Survey on privacy preserving techniques for publishing social network data [J]. Journal of software, 2014, 25(3):576-590.)
[2] SWEENEY L. Achieving k-anonymity privacy protection using generalization and suppression [J]. International journal of uncertainty, fuzziness and knowledge-based systems, 2002, 10(5): 571-588.
[3] LIU X, YANG X. Protecting sensitive relationships against infer-ence attacks in social networks [C]// DASFAA 2012: Proceedings of the 17th International Conference on Database Systems for Advanced Applications. Berlin: Springer, 2012: 335-350.
[4] HAY M, JENSEN D, SRIVASTAVA S, et al. Anonymizing social networks [C]// VLDB 2007: Proceedings of the 34nd International Conference on Very Large Databases. [S.l.]: VLDB Endowment, 2007: 173-187.
[5] LIU K, TERZI E. Towards identity anonymization on graphs [C]// Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2008: 93-106.
[6] ZHOU B, PEI J. Preserving privacy in social networks against neighborhood attacks [C]// ICDE 2008: Proceedings of the 24th International Conference on Data Engineering. Piscataway, NJ: IEEE, 2008: 506-515.
[7] LI N, LI T, VENKATASUBRAMANIAN S. t-Closeness: privacy beyond k-anonymity and l-diversity [C]// ICDE 2007: Proceedings of the 23rd International Conference on Data Engineering. Piscataway, NJ: IEEE, 2007: 106-115.
[8] YING X, WU X. Randomizing social networks: a spectrum preserving approach [C]// SDM 2008: Proceedings of the 2008 SIAM International Conference on Data Mining. Philadelphia, PA: SIAM, 2008: 739-750.
[9] ZHELEVA E, GETOOR L. Preserving the privacy of sensitive relationships in graph data [C]// PinKDD 2007: Proceedings of the 1st ACM SIGKDD International Workshop on Privacy, Security, and Trust in KDD. Berlin: Springer, 2008: 153-171.
[10] CHENG J, FU A W, LIU J. K-isomorphism: privacy preserving network publication against structural attacks [C]// SIGMOD'10: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2010: 459-470.
[11] CORMODE G, SRIVASTAVA D, YU T, et al. Anonymizing bipartite graph data using safe groupings [C]// VLDB 2008: Proceedings of the 34th International Conference on Very Large Databases. [S.l.]: VLDB Endowment, 2008: 833-844.
[12] HAY M, MIKLAU G, JENSEN D, et al. Resisting structural re-identification in anonymized social networks [J]. Proceedings of the VLDB endowment, 2008, 1(1): 102-114.
[13] SWEENEY L. k-anonmity: a model for protecting privacy [J]. International journal of uncertainty fuzziness and knowledge based systems, 2002, 10(5): 557-570.
[14] 付艳艳,张敏,冯登国,等.基于节点分割的社交网络属性隐私保护[J].软件学报,2014,25(4):768-780.(FU Y Y, ZHANG M, FENG D G, et al. Attribute privacy preservation in social networks based on node anatomy [J]. Journal of software, 2014, 25(4): 768-780.)
[15] 刘华玲,郑建国,孙辞海.基于贪心扰动的社交网络隐私保护研究[J].电子学报,2013,41(8):1586-1591.(LIU H L, ZHENG J G, SUN C H. Privacy preserving in social networks based on greedy perturbation [J]. Acta electronica sinica, 2013, 41(8): 1586-1591.)
[16] BHAGAT S, CORMODE G, KRISHNAMURTHY B, et al. Class-based graph anonymization for social network data [J]. Proceedings of the VLDB endowment, 2009, 2(1): 766-777.
[17] ZHANG C, SUN J, ZHU X, et al. Privacy and security for online social networks: challenges and opportunities [J]. IEEE network, 2010, 24(4): 13-18.
[18] MITTAL P, PAPAMANTHOU C, SONG D. Preserving link privacy in social network based systems [C/OL]. NDSS 2013: 20th Annual Network and Distributed System Security Symposium, San Diego, California, USA, February 24-27, 2013. [2015-08-04]. https://www.princeton.edu/~pmittal/publications/link-privacy-ndss13.pdf.

Edge partitioning approach for protecting sensitive relationships in social network

基于边分割的社交网络敏感边保护技术

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	ZHANG Meng, LI Weihua. Influence maximization algorithm based on user interactive representation [J]. Journal of Computer Applications, 2021, 41(7): 1964-1969.
[2]	SUN Heli, SUN Yuzhu, ZHANG Xiaoyun. Event description generation based on generative adversarial network [J]. Journal of Computer Applications, 2021, 41(5): 1256-1261.
[3]	JIANG Kun, LIU Zheng, ZHU Lei, LI Xiaoxing. Fixed word-aligned partition compression algorithm of inverted list based on directed acyclic graph [J]. Journal of Computer Applications, 2021, 41(3): 727-732.
[4]	SUN Heli, XU Tong, HE Liang, JIA Xiaolin. Personalized social event recommendation method integrating user historical behaviors and social relationships [J]. Journal of Computer Applications, 2021, 41(2): 324-329.
[5]	Xujian ZHAO, Chongwei WANG. Storyline extraction method from Weibo news based on graph convolutional network [J]. Journal of Computer Applications, 2021, 41(11): 3139-3144.
[6]	LI Xiangkun, JIA Caiyan. Collaborative filtering method fusing overlapping community regularization and implicit feedback [J]. Journal of Computer Applications, 2021, 41(1): 53-59.
[7]	SHENG Jun, LI Bin, CHEN Ling. Recommendation algorithm based on modularity and label propagation [J]. Journal of Computer Applications, 2020, 40(9): 2606-2612.
[8]	LI Chunying, TANG Yong, XIAO Zhenghong, LI Tiansong. Influential scholar recommendation model in academic social network [J]. Journal of Computer Applications, 2020, 40(9): 2594-2599.
[9]	MA Minyao, WU Lian, LIU Zhuo, XU Yi. Privacy-preserving determination of integer point-interval relationship [J]. Journal of Computer Applications, 2020, 40(7): 1983-1988.
[10]	YANG Shuxin, LIANG Wen, ZHU Kaili. Reverse influence maximization algorithm in social networks [J]. Journal of Computer Applications, 2020, 40(7): 1944-1949.
[11]	LONG Yangyang, CHEN Yuling, XIN Yang, DOU Hui. Secure energy transaction scheme based on alliance blockchain [J]. Journal of Computer Applications, 2020, 40(6): 1668-1673.
[12]	YI Dongyi, DENG Genqiang, DONG Chaoxiong, ZHU Miaomiao, LYU Zhouping, ZHU Suisong. Medical insurance fraud detection algorithm based on graph convolutional neural network [J]. Journal of Computer Applications, 2020, 40(5): 1272-1277.
[13]	FENG Liping, HAN Qi, ZHOU Zhigang, BAI Zengliang. Bad information diffusion modeling and optimal control strategy influenced by social networks [J]. Journal of Computer Applications, 2020, 40(3): 735-739.
[14]	LIU Huijian, LIU Junsong, WANG Jiawei, XUE Gang. Service composition partitioning method based on process partitioning technology [J]. Journal of Computer Applications, 2020, 40(3): 799-805.
[15]	SHAN Xiaohuan, ZHANG Zhiguo, SONG Baoyan, REN Chenglin. Activity recommendation method based on directed label graph and user feedback in event-based social network [J]. Journal of Computer Applications, 2020, 40(2): 448-453.