导航菜单

Computer Science ›› 2020, Vol. 47 ›› Issue (5): 7-13.doi: 10.11896/jsjkx.200200071

• Theoretical Computer Science • Previous Articles     Next Articles

Survey on Online Influence Maximization

KONG Fang1, LI Qi-zhi2, LI Shuai3   

  1. 1 School of Software,Shandong University,Jinan 250101,China
    2 School of Computer Science and Technology,Xidian University,Xi'an 710071,China
    3 John Hopcroft Center for Computer Science,Shanghai Jiao Tong University,Shanghai 201100,China
  • Received:2020-02-15 Online:2020-05-15 Published:2020-05-19
  • About author:KONG Fang,born in 1998,undergra-duate.Her main research interests include online influence maximization and so on.
    LI Shuai,born in 1988,Ph.D,assistant professor.Her main research interests include multi-armed bandit,online learning,statistical learning,reinforcement learning,machine learning and bioinformatics.

PDF (PC)

678

Abstract: Influence maximization is selecting seed nodes under a given influence propagation model to maximize the information spread.This problem has a wide range of application scenarios,including recommendation systems,viral marketing,information diffusion and link prediction.In practical applications,the node-to-node propagation probabilities in an information propagation model are usually unknown.Besides,online learning algorithms can automatically learn unknown parameters during the interaction process and gradually approach the optimal solution.The paper first discusses the definition of influence maximization problem,introduces commonly used influence propagation models,and summarizes the common offline influence maximization algorithms.Then it introduces the classic online learning framework,the multi-armed bandit setting,analyzes the research status of online influence maximization problem,and compares the performance of common online influence maximization algorithms in real social networks through experiments.Finally,the challenges and research directions of this subject in the future is prospected.

Key words: Influence propagation model, Influence maximization, Social network, Online learning algorithm, Multi-armed bandit

CLC Number: 

  • TP391
[1] KEMPE D,KLEINBERG J M,TARDOS É.Maximizing thespread of influence through a social network[J].Theory of Computing,2015,11(4):105-147.
[2] CENTOLA D,MACY M.Complex contagion and the weakness of long ties[J].American Journal of Sociology,2007,113(3):702-734.
[3] WANG C,CHEN W,WANG Y.Scalable influence maximization for independent cascade model in large-scale social networks[J].Data Mining and Knowledge Discovery,2012,25(3):545-576.
[4] CHEN W,YUAN Y,ZHANG L.Scalable influence maximization in social networks under the linear threshold Model[C]//Proceedings of the 10th IEEE International Conference on Data Mining (ICDM).2010:88-97.
[5] CHEN W,LAKSHMANAN L V S,CASTILLO C.Information and Influence Propagation in Social Networks[M].Morgan & Claypool Publishers,2013.
[6] LESKOVEC J,KRAUSE A,GUESTIN C,et al.Cost-effective outbreakdetection in networks[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Disco-very and Data Mining (KDD).2007:420-429.
[7] GOYAL A,LU W,LAKSHMANAN L V S.CELF++: Optimizing the greedy algorithm for influence maximization in social networks (poster entry)[C]//Proceedings of the 20th International World Wide Web Conference (WWW).2011:47-48.
[8] KIMURA M,SAITO K,NAKANO R.Extracting influentialnodes for information diffusion on a social network[C]//Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI).2007:1371-1376.
[9] CHEN W,WANG Y, YANG S.Efficient influence maximization in social networks[C]//Proceedings of the 15thACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD).2009:199-208.
[10] 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 (ICDM).2011:211-220.
[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 (ICDM).2012:918-923.
[12] KIM J,KIM S K,YU H.Scalable and parallelizable processing of influence maximization for large-scalesocial networks[C]//Proceedings of the 29th IEEE International Conference on Data Engineering (ICDE).2013:266-277.
[13] WANG Y,CONG G,SONG G,et al.Community-based greedyalgorithm for mining top-K influential nodes in mobile social networks[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD).2010:1039-1048.
[14] JIANG Q,SONG G,CONG G,et al.Simulated annealing based influence maximization in social networks[C]//Proceedings of the 25th AAAI Conference on Artificial Intelligence (AAAI).2011:127-132.
[15] BORGS C,BRAUTBAR M,CHAYES J,et al.Maximizing social influence in nearly optimal time[C]//Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA).2014:946-957.
[16] TANG Y,XIAO X,SHI Y.Influence maximization: near-optimal time complexity meets practical efficiency[C]//Proceedings of ACM SIGMOD Conference (SIGMOD).2014:75-86.
[17] TANG Y,SHI Y,XIAO X.Influence maximization in near-li-near time: A martingale approach[C]//Proceedings of ACM SIGMOD Conference (SIGMOD).2015:1539-1554.
[18] CHEN W.An issue in the martingale analysis of the influence maximization algorithm IMM[J].arXiv:1808.09363,2018.
[19] NGUYEN H T,THAI M T,DINH T N.Stop-and-Stare: Optimal sampling algorithms for viral marketing in billion- scale networks[C]// Proceedings of the 2016 International Conference on Management of Data (SIGMOD).2016:695-710.
[20] NGUYEN H T,NGUYEN T P,PHAN N H,et al.Importance sketching of influence dynamics in billion-scale networks[C]//Proceedings of the 2017 IEEE International Conference on Data Mining (ICDM).2017.
[21] AUDIBERT J-Y,BUBECK S,LUGOSI G.Minimax policies for combinatorial prediction games[C]//Proceedings of the 24th Annual Conference on Learning Theory (COLT).2011.
[22] LEI S,MANIU S,MO L,et al.Online influence maximization[C]//Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD).2015:645-654.
[23] CHEN W,WANG Y,YUAN Y,et al.Combinatorial multi-armed bandit and its extension toprobabilistically triggered arms[J].Journal of Machine Learning Research,2016,17(50):1-33.
[24] AUER P,CESA-BIANCHI N,FISCHER P.Finite-time analysis of the multiarmed bandit problem[J].Machine Learning Journal,2002,47(2/3):235-256.
[25] WANG Q,CHEN W.Improving regret bounds for combinatorial semi-bandits with probabilistically triggered arms and its applications[C]//Proceedings of the 30 th Annual Conference on Neural Information Processing Systems (NeurIPS).2017.
[26] WEN Z,KVETON B,VALKO M,et al.Online influence maximization under independent cascade modelwith semi-bandit feedback[C]//Proceedings of the 30th Annual Conference on Neural Information Processing Systems (NeurIPS).2017.
[27] WU Q Y,LI Z G,WANG H Z,et al.Factorization Bandits for Online Influence Maximization[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Disco-very and Data Mining (KDD).2019: 636-646.
[28] VASWANI S,LAKSHMANAN L V S,SCHMIDT M.Influence maximization with bandits[C]//NIPS Workshop on Networks in the Social and Information Sciences.2015.
[29] BAO Y X,WANG X K,WANG Z,et al,Online influence maximization in non-stationary social networks[C]//IEEE/ACM 24th International Symposium on Quality of Service (IWQoS).2016.
[30] VASWANI S,KVETON B,WEN Z,et al.Diffusion independent semi-bandit influence maximization[C]//Proceedings of the 34 th International Conference on Machine Learning (ICML).2017.
[31] CARPENTIER A,VALKO M.Revealing graph bandits formaximizing local influence[C]//International Conference on Artificial Intelligence and Statistics.2016.
[32] LUGOSI G,NEU G,OLKHOVSKAYA J.Online influencemaximization with local observations[C]// Proceedings of the 30th International Conference on Algorithmic Learning Theory.2019:557-580.
[33] AUER P,CESA-BIANCHI N,FREUND Y,et al.The non-stochastic multi-armed bandit problem[J].SIAM Journal on Computing,2002,32(1):48-77.
[34] LINT,LI J,CHEN W,Stochastic Online Greedy Learning with Semi-bandit Feedbacks[C]//Proceedings of the 28th Annual Conference on Neural Information Processing Systems (NeurIPS).2015:352-360.
[35] LICHAO S,WEIRAN H,PHILIP S Y,et al.Multi-Round Influence Maximization[C]// Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD).2018: 2249-2258.
[1] MA Li-bo, QIN Xiao-lin. Topic-Location-Category Aware Point-of-interest Recommendation [J]. Computer Science, 2020, 47(9): 81-87.
[2] CHEN Jin-yin, ZHANG Dun-Jie, LIN Xiang, XU Xiao-dong and ZHU Zi-ling. False Message Propagation Suppression Based on Influence Maximization [J]. Computer Science, 2020, 47(6A): 17-23.
[3] YANG Zhuo-xuan, MA Yuan-pei and YAN Guan. Polynomial Time Community Detection Algorithm Based on Coupling Strength [J]. Computer Science, 2020, 47(6A): 102-107.
[4] LIANG Jun-bin, ZHANG Min, JIANG Chan. Research Progress of Social Sensor Cloud Security [J]. Computer Science, 2020, 47(6): 276-283.
[5] FU Kun, QIU Qian, ZHAO Xiao-meng, GAO Jin-hui. Event Detection Method Based on Node Evolution Staged Optimization [J]. Computer Science, 2020, 47(5): 96-102.
[6] LIU Xiao-fei, ZHU Fei, FU Yu-chen, LIU Quan. Personalized Recommendation Algorithm Based on User Preference Feature Mining [J]. Computer Science, 2020, 47(4): 50-53.
[7] WU Lei,YUE Feng,WANG Han-ru,WANG Gang. Academic Paper Recommendation Method Combined with Researcher Tag [J]. Computer Science, 2020, 47(2): 51-57.
[8] ZHANG Min-jun, HUA Qing-yi. Personalized Recommendation of Social Network Users' Interest Points Based on ProbabilityMatrix Decomposition Algorithm [J]. Computer Science, 2020, 47(12): 144-148.
[9] LI Xiao, QU Yang, LI Hui, GUO Shi-kai. User Importance Evaluation for Q&A Platform Based on User Relations [J]. Computer Science, 2020, 47(11A): 430-436.
[10] GU Qiu-yang, JU Chun-hua, WU Gong-xing. Social Network Information Recommendation Model Combining Deep Autoencoder and Network Representation Learning [J]. Computer Science, 2020, 47(11): 101-112.
[11] ZHAO Xia, LI Xian, ZHANG Ze-hua, ZHANG Chen-wei. Community Detection Algorithm Combing Community Embedding and Node Embedding [J]. Computer Science, 2020, 47(10): 121-125.
[12] SUN Yong-yue, LI Hong-yan, ZHANG Jin-bo. RAISE:Efficient Influence Cost Minimizing Algorithm in Social Network [J]. Computer Science, 2019, 46(9): 59-65.
[13] LIU Xiao-jie, LV Xiao-qiang, WANG Xiao-ling, ZHANG Wei, ZHAO An. Mining User Interests on Twitter Using Wikipedia Category Graph [J]. Computer Science, 2019, 46(9): 79-84.
[14] ZHANG Zheng, WANG Hong-zhi, DING Xiao-ou, LI Jian-zhong, GAO Hong. Identification of Same User in Social Networks [J]. Computer Science, 2019, 46(9): 93-98.
[15] SHI Jun-ling,WANG Xing-wei,HUANG Min. Content-centric Routing Scheme in Vehicular Social Networks [J]. Computer Science, 2019, 46(7): 50-55.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[2] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[3] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[4] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[5] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[6] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[7] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[8] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[9] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .
[10] WANG Zhen-chao, HOU Huan-huan and LIAN Rui. Path Optimization Scheme for Restraining Degree of Disorder in CMT[J]. Computer Science, 2018, 45(4): 122 -125 .
渝ICP备16013121号-4
Copyright © 2019 Editorial Office of Computer Science
Add:18# Honghu West Rd., Yubei District,Chongqing,China    Zip Code: 401121
Editorial Office: 023-63500828    E-mail: jsjkx12@163.com    jsjkx_bianwu@163.com(Finance)