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

ZHAO Yu; HUANG Kaizhi; GUO Yunfei; ZHAO Xing

doi:10.16511/j.cnki.qhdxxb.2017.25.061

PDF(1330 KB)

Journal of Tsinghua University(Science and Technology) ›› 2017, Vol. 57 ›› Issue (12) : 1245-1253. DOI: 10.16511/j.cnki.qhdxxb.2017.25.061

COMPUTER SCIENCE AND TECHNOLOGY

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

{{article.zuoZhe_EN}}

Author information +

History +

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.

Key words

social network / information diffusion blocking / minimum influence / stochastic optimization / mixed integer programming (MIP)

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations

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

References

[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.