Abstract：To protect the security of social network, ensure the availability of social network after perturbation, the paper proposed perturbation method of social network based on the signless Laplacian matrix and the social network non-randomness. In the perturbation process, this method controlled the social network spectral radius and the social network non-randomness by certain constraints, thus ensuring the usability and improving the privacy protection degree of the social network. The paper analyzed the security of this method in theory, and provided corresponding algorithm. At last, the experimental results on comparison of harmonic mean of the shortest distance of the social network, subgraph centrality and the social network non-randomness of change, show that the proposed method effectively protects the structural feature of social network and improving the availability of the social network.
许黎明 强小强 宋转. 谱半径和特征显著性约束的随机化社会网络方法[J]. 计算机应用, 2012, 32(02): 485-488.
XU Li-ming JIANG Xiao-qiang SONG Zhuan. Random method of social network based on spectral spectrum and feature significant constraints. Journal of Computer Applications, 2012, 32(02): 485-488.
YING X, WU X. Randomizing social networks: a spectrum preserving approach [C]// SDM 08: Proceedings of the 8th SIAM Conference on Data Mining. Atlanta: SIAM, 2008.739-750
[2]
YING X, WU X. On link privacy in randomizing social networks[C]// PAKDD '09: Pacific-Asia Conference on Knowledge Discovery and Data Mining, LNCS 5476. Berlin: Springer-Verlag, 2009: 28-39.
[3]
LIU K, TERZI E. Towards identity anonymization on graphs [C]// SIGMOD 08: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2008: 93-106.
[4]
YING X, PAN X, WU X, et al. Comparisons of randomization and k-degree anonymization schemes for privacy preserving social network [C]// SNA-KDD '09: The 3rd Workshop on Social Network Mining and Analysis. New York: ACM, 2009: 96-116.
[5]
HANHIJRVI S, GARRIGA G C, PUOLAMKI K. Randomization techniques for graphs [C]// SDM '09: Proceedings of the 9th SIAM Conference on Data Mining. Paris: SIAM, 2009: 780-791.
[6]
YING X, WU X. Graph generation with prescribed feature constraints [C]// SDM '09: Proceedings of the 9th SIAM Conference on Data Mining. Sparks: SIAM, 2009: 966-977.
YING X, WU X. On randomness measures for social networks [C]// SDM '09: Proceedings of the 9th SIAM Conference on Data Mining. Sparks: SIAM, 2009: 709-720.
[9]
孙继广. 矩阵的扰动分析[M]. 2版. 北京: 科学出版社, 2001.
[10]
CVETKOVI D, ROWLINSON P, SIMIC S. Signless Laplacians of finite graphs [J]. Linear Algebra and Its Applications,2007, 423(1):155-171.
[11]
CVETKOVIC D, ROWLINSON P, SIMIC S. Eigenspaces of graphs [M]. Cambridge: Cambridge University Press, 1997.
2012, Vol. 32 
