基于奇异值分解的含权网络匿名化的安全性分析

doi:10.11959/j.issn.1000-436x.2018074

Abstract

Abstract:

The security of anonymous method based on singular value decomposition (SVD) in the privacy preserving of weighted social network was analyzed.The reconstruction method in network with integer weights and the inexact reconstruction method in network with arbitrary weighted were proposed.The $\frac{ε}{N}$ -tolerance was definited to measure its safety.It was also pointed out that the upper bound of ε (the reconfigurable coefficient) obtained in current spectral theories was so conservative that lacks of guidance.The reconfigurable coefficients of random networks,Barabasi-Albert networks,small world networks and real networks were calculated by experiment.Moreover,the reconfigurable coefficients of double perturbation strategies based on SVD were also tested.Experimental results show that weighted social networks have different tolerances on spectrum loss,and there is a close relationship between its tolerance and network parameters.

Key words: singular value decomposition, weighted social networks, privacy preserving

CLC Number:

TP309

Yong ZENG,Lingjie ZHOU,Zhongyuan JIANG,Zhihong LIU,Jianfeng MA. Security analysis of weighted network anonymity based on singular value decomposition[J]. Journal on Communications, 2018, 39(5): 23-33.

Figures/Tables 19

G_p(N,W)	$\frac{ε}{N}$
p=0.2; w=[1,3]	0.257 1
p=0.2; w=[1,5]	0.187 8
p=0.5; w=[1,3]	0.211 2
p=0.5; w=[1,5]	0.153 9

网络参数	$\frac{ε}{N}$
m₀=m=4	0.209 9
m₀=m=8	0.215 7
m₀=m=12	0.220 2

	网络参数		$\frac{ε}{N}$
k		p	$\frac{ε}{N}$
2		0.2	0.169
2		0.4	0.186
2		0.6	0.199
5		0.2	0.213
5		0.4	0.235
5		0.6	0.243

	网络参数			$\frac{ε}{N}$
n_max		p	方法1		方法2
2		0.2	0.24		0.24
2		0.5	0.26		0.26
3		0.2	0.24		0.24
3		0.5	0.26		0.26

References 24

[1]	冯登国, 张敏, 李昊 . 大数据安全与隐私保护[J]. 计算机学报, 2014,37(1): 246-258.
	FENG D G , ZHANG M , LI H ,et al. Big data security and privacy protection[J]. Chinese Journal of Computers, 2014,37(1): 246-258.
[2]	WONG R C W , LI J , FU A W C ,et al. (α,k)-anonymity:an enhanced k-anonymity model for privacy preserving data publishing[C]// The 12th ACM SIGKDD international conference on Knowledge discovery and data mining. 2006: 754-759.
[3]	CORMODE G , SRIVASTAVA D , YU T ,et al. Anonymizing bipartite graph data using safe groupings[J]. The VLDB Journal—The International Journal on Very Large Data Bases, 2010,19(1): 115-139.
[4]	CHENG J , FU A W , LIU J . K-isomorphism:privacy preserving network publication against structural attacks[C]// The 2010 ACM SIGMOD International Conference on Management of Data. 2010: 459-470.
[5]	ABAWAJY J H , NINGGAL M I H , HERAWAN T . Privacy preserving social network data publication[J]. IEEE Communications Surveys ＆Tutorials, 2016,18(3): 1974-1997.
[6]	LIU L , WANG J , LIU J ,et al. Privacy preserving in social networks against sensitive edge disclosure[R]. Technical Report Technical Report CMIDA-HiPSCCS 006-08, 2008.
[7]	DAS S , E?ECIO?LU ? , EL ABBADI A . Anonymizing weighted social network graphs[C]// 2010 IEEE 26th International Conference on Data Engineering (ICDE). 2010: 904-907.
[8]	LI Y , LI Y , YAN Q ,et al. Privacy leakage analysis in online social networks[J]. Computers ＆ Security, 2015,49: 239-254.
[9]	苏洁, 刘帅, 罗智勇 ,等. 基于信息损失量估计的匿名图构造方法[J]. 通信学报, 2016,37(6): 56-64.
	SU J , LIU S , LUO Z Y ,et al. Method of constructing an anonymous graph based on information loss estimation[J]. Journal on Communi-cations, 2016,37(6): 56-64.
[10]	LIU D , WANG H , VAN M P . Spectral perturbation and reconstructability of complex networks[J]. Physical Review E, 2010,81(1):016101.
[11]	XU S , ZHANG J , HAN D ,et al. Singular value decomposition based data distortion strategy for privacy preserving[J]. Knowledge and Information Systems, 2006,10(3): 383-397.
[12]	WU L , YING X , WU X . Reconstruction from randomized graph via low rank approximation[C]// The 2010 SIAM International Conference on Data Mining,Society for Industrial and Applied Mathematics. 2010: 60-71.
[13]	PECH R , HAO D , PAN L ,et al. Link prediction via matrix completion[J]. EPL (Europhysics Letters), 2017,117(3):38002.
[14]	XU X , LIU B , WU J ,et al. Link prediction in complex networks via matrix perturbation and decomposition[J]. Scientific Reports, 2017,7(1):14724.
[15]	SARKAR S , . Spectral (re) construction of urban street networks:generative design using global information from structure[M]// Design Computing and Cognition'14. Springer International Publishing, 2015: 41-55.
[16]	张贤达 . 矩阵分析与应用(第2版)[M]. 北京: 清华大学出版社, 2013.
	ZHANG X D . Matrix analysis and applications(second edi-tion)[M]. Beijing: Tsinghua University PressPress, 2013.
[17]	戴华 . 矩阵论[M]. 北京: 科学出版社, 2001.
	DAI H . Matrix theo-ry[M]. Beijing: Science PressPress, 2001.
[18]	HORN R A , JOHNSON C R . 矩阵分析[M]. 天津: 天津大学出版社, 1989.
	HORN R A,JOHNSON , C R . Matrix analysis[M]. Tianjin: Tianjin University PressPress, 2001.
[19]	ZHANG X D . Matrix analysis and applications[M]. Cambridge University Press, 2017.
[20]	ERD?S P RéNYI A . On the evolution of random graphs[J]. Transactions of the American Mathematical Society, 1984,286(1): 257-274.
[21]	BARABáSI A L , ALBERT R . Emergence of scaling in random networks[J]. Science, 1999,286(5439): 509-512.
[22]	WATTS D J , STROGATZ S H . Collective dynamics of “small-world”networks[J]. Nature, 1998,393(6684): 440-442.
[23]	ABUELHAIJA S , PEROZZI B , ALRFOU R . Learning edge representations via low-rank asymmetric projections[C]// The 2017 ACM Conference on Information and Knowledge Management. 2017: 1787-1796.
[24]	GLEISER P M , DANON L . Community structure in jazz[J]. Advances in Complex Systems, 2003,6(4): 565-573.

Metrics

Recommended 0

No Suggested Reading articles found!

Security analysis of weighted network anonymity based on singular value decomposition

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 19

References 24

Related Articles 15

Metrics

Recommended 0

[1]	Lichuan MA, Jiayi PENG, Qingqi PEI, Haojin ZHU. Efficient privacy-preserving decision tree classification protocol [J]. Journal on Communications, 2021, 42(8): 80-89.
[2]	Xianpeng WANG,Yuehao GUO,Mengxing HUANG,Chong SHEN,Chunjie CAO,Wenlong FENG. Robust angle estimation method for noncircular targets in MIMO radar with mutual coupling [J]. Journal on Communications, 2019, 40(7): 144-150.
[3]	Hongfa DING,Changgen PENG,Youliang TIAN,Shuwen XIANG. Privacy risk adaptive access control model via evolutionary game [J]. Journal on Communications, 2019, 40(12): 9-20.
[4]	Hui LIN,Mengyang YU,Youliang TIAN,Yijie HUANG. Dynamic game and reliable recommendation based transferring reputation mechanism for mobile cloud computing [J]. Journal on Communications, 2018, 39(5): 85-93.
[5]	Lingbo WEI,Xiaobing FENG,Chi ZHANG,Hualong SHENG,Nenghai YU. Network function outsourcing system based on prefix-preserving encryption [J]. Journal on Communications, 2018, 39(4): 159-166.
[6]	Yihan YU,Yu FU,Xiaoping WU. Stochastic gradient descent algorithm preserving differential privacy in MapReduce framework [J]. Journal on Communications, 2018, 39(1): 70-77.
[7]	Zhi-qiang WU,Ken-li LI,Hui ZHENG. Efficient and scalable architecture for searchable symmetric encryption [J]. Journal on Communications, 2017, 38(8): 79-93.
[8]	Hao WANG,Zheng-quan XU,Li-zhi XIONG,Tao WANG. CLM:differential privacy protection method for trajectory publishing [J]. Journal on Communications, 2017, 38(6): 85-96.
[9]	Yang GAO,Jun-li CHEN,Guang-li YANG. Off-grid DOA estimation algorithm based on unitary transform and sparse Bayesian learning [J]. Journal on Communications, 2017, 38(6): 177-182.
[10]	Wen-jun XIONG,Zheng-quan XU,Hao WANG. Privacy level evaluation of differential privacy for time series based on filtering theory [J]. Journal on Communications, 2017, 38(5): 172-181.
[11]	Hong-cheng LI,Xiao-ping WU,Yan CHEN. k-means clustering method preserving differential privacy in MapReduce framework [J]. Journal on Communications, 2016, 37(2): 125-131.
[12]	Li-bing WU,Yong XIE,Yu-bo ZHANG. Efficient and secure message authentication scheme for VANET [J]. Journal on Communications, 2016, 37(11): 1-10.
[13]	Yong-hao GU,Jiu-chuan LIN,Da GUO. Clustering-based dynamic privacy preserving method for social networks [J]. Journal on Communications, 2015, 36(Z1): 126-130.
[14]	Wei-ni ZENG,Ya-ping LIN,Ye-qing YI,Shi-ming HE,Peng CHEN. Data processing based on the privacy-preserving vector for wireless sensor networks [J]. Journal on Communications, 2015, 36(9): 34-46.
[15]	Li-hui LAN,Shi-guang JU. Privacy preserving based on differential privacy for weighted social networks [J]. Journal on Communications, 2015, 36(9): 145-159.