Computer Science

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

Special Issue: Theoretical Computer Scinece

• 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)

3037

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 maximization, Influence propagation model, Multi-armed bandit, Online learning algorithm, Social network

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] WANG Jian, PENG Yu-qi, ZHAO Yu-fei, YANG Jian. Survey of Social Network Public Opinion Information Extraction Based on Deep Learning [J]. Computer Science, 2022, 49(8): 279-293.
[2] WEI Peng, MA Yu-liang, YUAN Ye, WU An-biao. Study on Temporal Influence Maximization Driven by User Behavior [J]. Computer Science, 2022, 49(6): 119-126.
[3] YU Ai-xin, FENG Xiu-fang, SUN Jing-yu. Social Trust Recommendation Algorithm Combining Item Similarity [J]. Computer Science, 2022, 49(5): 144-151.
[4] CHANG Ya-wen, YANG Bo, GAO Yue-lin, HUANG Jing-yun. Modeling and Analysis of WeChat Official Account Information Dissemination Based on SEIR [J]. Computer Science, 2022, 49(4): 56-66.
[5] ZUO Yuan-lin, GONG Yue-jiao, CHEN Wei-neng. Budget-aware Influence Maximization in Social Networks [J]. Computer Science, 2022, 49(4): 100-109.
[6] GUO Lei, MA Ting-huai. Friend Closeness Based User Matching [J]. Computer Science, 2022, 49(3): 113-120.
[7] SHAO Yu, CHEN Ling, LIU Wei. Maximum Likelihood-based Method for Locating Source of Negative Influence Spreading Under Independent Cascade Model [J]. Computer Science, 2022, 49(2): 204-215.
[8] WANG Jian, WANG Yu-cui, HUANG Meng-jie. False Information in Social Networks:Definition,Detection and Control [J]. Computer Science, 2021, 48(8): 263-277.
[9] TAN Qi, ZHANG Feng-li, WANG Ting, WANG Rui-jin, ZHOU Shi-jie. Social Network User Influence Evaluation Algorithm Integrating Structure Centrality [J]. Computer Science, 2021, 48(7): 124-129.
[10] ZHANG Ren-zhi, ZHU Yan. Malicious User Detection Method for Social Network Based on Active Learning [J]. Computer Science, 2021, 48(6): 332-337.
[11] BAO Zhi-qiang, CHEN Wei-dong. Rumor Source Detection in Social Networks via Maximum-a-Posteriori Estimation [J]. Computer Science, 2021, 48(4): 243-248.
[12] ZHANG Shao-jie, LU Xu-dong, GUO Wei, WANG Shi-peng, HE Wei. Prevention of Dishonest Behavior in Supply-Demand Matching [J]. Computer Science, 2021, 48(4): 303-308.
[13] ZHANG Hao-chen, CAI Ying, XIA Hong-ke. Delivery Probability Based Routing Algorithm for Vehicular Social Network [J]. Computer Science, 2021, 48(3): 289-294.
[14] YUAN De-yu, CHEN Shi-cong, GAO Jian, WANG Xiao-juan. Intervention Algorithm for Distorted Information in Online Social Networks Based on Stackelberg Game [J]. Computer Science, 2021, 48(3): 313-319.
[15] TAN Qi, ZHANG Feng-li, ZHANG Zhi-yang, CHEN Xue-qin. Modeling Methods of Social Network User Influence [J]. Computer Science, 2021, 48(2): 76-86.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.