支持隐私保护的社交网络信息传播方法

doi:10.3778/j.issn.1673-9418.2004007

摘要/Abstract

摘要：

社交网络影响力传播重点关注如何使用少量的种子集合在社交网络中产生尽可能高的影响力，并将转发作为信息传播的唯一方式，忽略了其他传播方式，例如用户可通过发布一条与所见信息内容相似的信息来进行传播，这种传播方式（称为转述）因为难以追踪，所以存在隐私泄漏的风险。针对上述问题，定义了一种支持转述关系的社交网络信息传播模型，提出了一种支持用户隐私保护的信息传播方法LocalGreedy，确保用户发送的信息不泄漏到指定黑名单的同时，最大化传播产生的影响力，平衡了隐私保护和信息传播的矛盾。针对种子集合选取的枚举问题，提出了支持隐私保护的递增策略构造种子集合，减少时间开销；给出了计算节点的局部影响子图方法，快速估计种子集合传播产生的影响力；为确保种子集合满足隐私保护约束限制，提出了推导节点泄漏态概率上限的方法，避免使用蒙特卡洛方法产生的时间开销。使用爬取的新浪微博数据集进行实验验证和实例分析，结果表明了所提方法的有效性。

关键词: 信息传播模型, 传播网络推断, 影响力最大化, 隐私保护, 社交网络

Abstract:

Current relevant researches on influence propagation of social networks focus on how to use a small size seed set to produce the highest impact in social networks, and they often regard forwarding as the only way of information diffusion, ignoring other ways of information diffusion. For example, users can disseminate information by publishing a message with similar content to the message they see. This way of diffusion (referred to as mentioning) is difficult to track, and it is easy to cause the risk of privacy disclosure. Aiming at the causes of privacy leakage in social networks, this paper defines a social network information diffusion model supporting mentioning relationship, and presents a social network information diffusion algorithm LocalGreedy, which can ensure messages sent by users are not leaked to the specified, maximize the influence of the propagation and balance the contradiction between privacy protection and message propagation. This paper proposes an incremental strategy to construct a seed set while reducing time complexity caused by enumeration. After that, giving the calculating method on local influence subgraph, the influence generated by seed set propagation can be quickly estimated. When estimating the influence, a calculation method for deriving the upper limit of privacy leakage probability is proposed to ensure the privacy protection constraint limit and avoid time complexity caused by the Monte Carlo simulation. The crawled Sina Weibo dataset is used to carry out experimental verification and example analysis. The experimental results show that the proposed method is effective.

Key words: information diffusion model, diffusion network inference, influence maximization, privacy protection, social networks

高昂, 梁英, 谢小杰, 王梓森, 李锦涛. 支持隐私保护的社交网络信息传播方法[J]. 计算机科学与探索, 2021, 15(2): 233-248.

GAO Ang, LIANG Ying, XIE Xiaojie, WANG Zisen, LI Jintao. Social Network Information Diffusion Method with Support of Privacy Protection[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(2): 233-248.

参考文献

[1] KEMPE D, KLEINBERG J, TARDOS é. Maximizing the spread of influence through a social network[C]//Proceedings of the 9th ACM SIGKDD International Conference on Know-ledge Discovery and Data Mining, Washington, Aug 24-27, 2003. New York: ACM, 2003: 137-146.
[2] GRANOVETTER M. Threshold models of collective behavior[J]. American Journal of Sociology, 1978, 83(6): 1420-1443.
[3] NEWMAN M. Networks: an introduction[M]. Oxford University Press, 2010.
[4] ZUO Y, LIANG Y, BI X D, et al. An inference method of knowledge diffusion network in community question answering sites[J]. Chinese Journal of Computers, 2018, 41(1): 82-97.
左遥, 梁英, 毕晓迪, 等. 社会化问答网站知识传播网络推断方法[J]. 计算机学报, 2018, 41(1): 82-97.
[5] CAI S Q, YUAN Q, ZHOU P. Research on linear threshold diffusion model for negative word-of-mouth under enterprises response[J]. Journal of Systems Engineering, 2017, 32(2): 145-155.
蔡淑琴, 袁乾, 周鹏. 企业响应下负面口碑线性阈值传播模型研究[J]. 系统工程学报, 2017, 32(2): 145-155.
[6] ZHAO J H, WAN K W. Research on the communication dynamics model of social network public opinion based on the SIS model[J]. Information Science, 2017, 35(12): 36-40.
赵剑华, 万克文. 基于信息传播模型-SIR传染病模型的社交网络舆情传播动力学模型研究[J]. 情报科学, 2017, 35(12): 36-40.
[7] PAN Y, CONG F, CHEN K L, et al. Diffusion-aware personalized social update recommendation[C]//Proceedings of the 7th ACM Conference on Recommender Systems, Hong Kong, China, Oct 12-16, 2013. New York: ACM, 2013: 69-76.
[8] ZHANG Q, GONG Y Y, GUO Y, et al. Retweet behavior prediction using hierarchical dirichlet process[C]//Proceedings of the 29th AAAI Conference on Artificial Intelligence, Austin, Jan 25-30, 2015. Menlo Park: AAAI, 2015: 403-409.
[9] BIAN J W, YANG Y, CHUA T S. Predicting trending messages and diffusion participants in microblogging network[C]//Proceedings of the 37th International ACM SIGIR Conference on Research and Development in Information Retrieval, Gold Coast, Jul 6-11, 2014. New York: ACM, 2014: 537-546.
[10] LUO Z C, OSBORNE M, TANG J T, et al. Who will retweet me?: finding retweeters in twitter[C]//Proceedings of the 36th International ACM SIGIR Conference on Research and Development in Information Retrieval, Dublin, Jul 28-Aug 1, 2013. New York: ACM, 2013: 869-872.
[11] JUNG K, HEO W, CHEN W. IRIE: scalable and robust influence maximization in social networks[C]//Proceedings of the 12th IEEE International Conference on Data Mining, Brussels, Dec 10-13, 2012. Washington: IEEE Computer Society, 2012: 918-923.
[12] GOYAL A, LU W, LAKSHMANAN L V S. Simpath: an efficient algorithm for influence maximization under the linear threshold model[C]//Proceedings of the 11th IEEE International Conference on Data Mining, Vancouver, Dec 11-14, 2011. Washington: IEEE Computer Society, 2011: 211-220.
[13] TANG Y Z, XIAO X K, SHI Y C. Influence maximization: near-optimal time complexity meets practical efficiency[C]// Proceedings of the 2014 International Conference on Management of Data, Utah, Jun 22-27, 2014. New York: ACM, 2014: 75-86.
[14] COHEN E, DELLING D, PAJOR T, et al. Sketch-based influence maximization and computation: scaling up with guarantees[C]//Proceedings of the 23rd ACM International Conference on Information and Knowledge Management, Shanghai, Nov 3-7, 2014. New York: ACM, 2014: 629-638.
[15] SHANG J X, ZHOU S B, LI X, et al. CoFIM: a community-based framework for influence maximization on large-scale networks[J]. Knowledge-Based Systems, 2017, 117: 88-100.
[16] LI X, CHENG X, SU S, et al. Community-based seeds selection algorithm for location aware influence maximization[J]. Neurocomputing, 2018, 275: 1601-1613.
[17] SINGH K, BHOLA S, LEE W. xBook: redesigning privacy control in social networking platforms[C]//Proceedings of the 18th USENIX Security Symposium, Montreal, Aug 10-14, 2009. Berkeley: USENIX, 2009: 249-266.
[18] AIELLO L M, RUFFO G. LotusNet: tunable privacy for distributed online social network services[J]. Computer Communications, 2012, 35(1): 75-88.
[19] YAN Z, WANG M J. Protect pervasive social networking based on two-dimensional trust levels[J]. IEEE Systems Jour-nal, 2014, 11(1): 207-218.
[20] LI N, YAN Z, WANG M, et al. Securing communication data in pervasive social networking based on trust with KP-ABE[J]. ACM Transactions on Cyber-Physical Systems, 2018, 3(1): 1-23.
[21] CHENG J, ADAMIC L A, DOW P A, et al. Can cascades be predicted?[C]//Proceedings of the 23rd International World Wide Web Conference, Seoul, Apr 7-11, 2014. New York: ACM, 2014: 925-936.