在线社会网络中面向节点影响力的信息传播阻断模型

赵宇; 黄开枝; 郭云飞; 赵星

doi:10.16511/j.cnki.qhdxxb.2017.25.061

PDF(1330 KB)

清华大学学报（自然科学版） ›› 2017, Vol. 57 ›› Issue (12) : 1245-1253. DOI: 10.16511/j.cnki.qhdxxb.2017.25.061

计算机科学与技术

在线社会网络中面向节点影响力的信息传播阻断模型

赵宇^1,2, 黄开枝^1,2, 郭云飞¹, 赵星^1,2

作者信息 +

Information diffusion blocking model of node influence-oriented in online social network

ZHAO Yu^1,2, HUANG Kaizhi^1,2, GUO Yunfei¹, ZHAO Xing^1,2

Author information +

文章历史 +

摘要

目前信息传播阻断模型是在网络中选择并删除l个最佳节点（边）使信息传播到的节点数量最小，该模型未考虑信息传播节点的影响力，导致选择的l个最佳节点（边）并不准确，阻断有效性较差。针对此问题，该文提出一种面向节点影响力的信息传播阻断模型，并设计了一种基于采样平均近似的求解方法。模型以网络中节点的影响力为有效性依据，通过选择并删除l个最佳节点来改变网络结构，使信息传播到的目标节点影响力之和最小；该模型为随机优化问题，首先利用采样平均近似将目标函数转化为确定性问题，其次进一步编码为混合整数规划问题，最后采用一种量子遗传算法解决该问题得到l个最佳节点并将其删除。仿真结果表明：相比于传统模型，通过本模型选择的l个最佳节点能够将信息传播的影响力控制在更小的范围，且处理时间更短。

Abstract

Information diffusion blocking maximization is used to select and delete the best l nodes (edges) to minimize the number of nodes receiving information in the network. However, the model does not take into account the node's influence which blocks the information flow and lowers the efficiency. This paper presents an information diffusion blocking model that considers the node's influence with a method based on the sampling average approximation (SAA). The model is selects and deletes the best l nodes to change the network structure which minimizing the influence of the target nodes. The model is a stochastic optimization problem which is transferred into a deterministic problem using SAA. The problem is then encoded as a mixed integer programming (MIP) problem. Finally, a quantum genetic algorithm is used to select the best l nodes and remove them. Simulations show that the best l nodes selected by this model influence the information diffusion over a smaller range and the processing time is shorter than the traditional model.

导出引用

赵宇, 黄开枝, 郭云飞, 赵星. 在线社会网络中面向节点影响力的信息传播阻断模型[J]. 清华大学学报（自然科学版）. 2017, 57(12): 1245-1253 https://doi.org/10.16511/j.cnki.qhdxxb.2017.25.061

ZHAO Yu, HUANG Kaizhi, GUO Yunfei, ZHAO Xing. Information diffusion blocking model of node influence-oriented in online social network[J]. Journal of Tsinghua University(Science and Technology). 2017, 57(12): 1245-1253 https://doi.org/10.16511/j.cnki.qhdxxb.2017.25.061

中图分类号： TN915.81

参考文献

[1] 陈卫. 社交网络影响力传播研究[J]. 大数据, 2017, 1(3):201503.CHEN Wei. Research on influence diffusion in social netwok[J]. Big Data, 2017, 1(3):201503. (in Chinese)[2] Nowzari C, Preciado V M, Pappas G J. Analysis and control of epidemics:A survey of spreading processes on complex networks[J]. IEEE Control Systems, 2016, 36(1):26-46.[3] Prakash B A, Chakrabarti D, Valler N C, et al. Threshold conditions for arbitrary cascade models on arbitrary networks[J]. Knowledge and Information Systems, 2012, 33(3):549-575.[4] Tong H, Prakash B A, Eliassi-Rad T, et al. Gelling, and melting, large graphs by edge manipulation[C]//Proceedings of the 21st ACM International Conference on Information and Knowledge Management. Hawaii, USA:ACM, 2012:245-254.[5] Saha S, Adiga A, Prakash B A, et al. Approximation algorithms for reducing the spectral radius to control epidemic spread[C]//Proceedings of the 2015 SIAM International Conference on Data Mining. Vancouve, Canada:Society for Industrial and Applied Mathematics. 2015:568-576.[6] Chen C, Tong H, Prakash B A, et al. Node immunization on large graphs:Theory and algorithms[J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(1):113-126.[7] Khalil E B, Dilkina B, Song L. Scalable diffusion-aware optimization of network topology[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, NY, USA:ACM, 2014:1226-1235.[8] Zhang Y, Adiga A, Saha S, et al. Near-optimal algorithms for controlling propagation at group scale on networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(12):3339-3352.[9] Kempe D, Kleinberg J M, Tardos É. Maximizing the spread of influence through a social network[J]. Theory of Computing, 2015, 11(4):105-147.[10] Liu Y, Tang M, Zhou T, et al. Identify influential spreaders in complex networks, the role of neighborhood[J]. Physia A:Statistical Mechanics and Its Applications, 2016, 452:289-298.[11] Xia Y, Ren X, Peng Z, et al. Effectively identifying the influential spreaders in large-scale social networks[J]. Multimedia Tools and Applications, 2016, 75(15):8829-8841.[12] Zhang J X, Chen D B, Dong Q, et al. Identifying a set of influential spreaders in complex networks[J]. Scientific Reports, 2016, 6:27823.[13] Kitsak M, Gallos L H, Havlin S, et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2010, 6(11):888-893.[14] Rubinstein R Y, Kroese D P. Simulation and the Monte Carlo Method[M]. New York:John Wiley & Sons, 2016.[15] Verweij B, Ahmed S, Kleywegt A J, et al. The sample average approximation method applied to stochastic routing problems:A computational study[J]. Computational Optimization and Applications, 2003, 24(2-3):289-333.[16] Narayanan A. An introductory tutorial to quantum computing[C]//Proceedings of the IEEE Colloquium on Quantum Computing Theory, Applications and Implications. London, England:IEEE, 1997:1-3.[17] 江逸茗, 兰巨龙, 周慧琴. 网络虚拟化环境下的资源监控策略[J]. 电子与信息学报, 2014, 36(3):708-714.JIANG YiMing, LAN JuLong, ZHOU Huiqin. Resource monitoring policy for network virtualization environment[J]. Journal of Electronics & Informaion Technology, 2014, 36(3):708-714. (in Chinese)[18] Leskovec J, Krause A, Guestrin C, et al. Cost-effective outbreak detection in networks[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Jose, CA, USA:ACM, 2007:420-429.