Computer Science

Computer Science ›› 2022, Vol. 49 ›› Issue (6): 119-126.doi: 10.11896/jsjkx.210700145

• Database & Big Data & Data Science • Previous Articles     Next Articles

Study on Temporal Influence Maximization Driven by User Behavior

WEI Peng1, MA Yu-liang2, YUAN Ye3, WU An-biao1   

  1. 1 School of Computer Science and Engineering,Northeastern University,Shenyang 110000,China
    2 School of Business Administration,Northeastern University,Shenyang 110000,China
    3 School of Computer Science,Beijing Institute of Technology,Beijing 100081,China
  • Received:2021-07-14 Revised:2021-10-20 Online:2022-06-15 Published:2022-06-08
  • About author:WEI Peng,born in 1996,postgraduate,is a member of China Computer Federation.His main research interests include temporal graph and graph data managment.
    MA Yu-liang,born in 1990,postdoctor,is a member of China Computer Federation.His main research interests include graph databases,location-based social networks and social networks analysis.
  • Supported by:
    National Natural Science Foundation of China(61932004,62002054),China Postdoctoral Science Foundation(2020M670780) and Postdoctoral Research Fund of Northeastern University.

PDF (PC)

509

Abstract: Influence maximization(IM) aims to find a group of users in a social network,through whom information can spread most widely in the network.Existing studies mainly focus on the IM problem in static networks.However,social networks are constantly evolving in real life,and propagation models(such as independent cascading model and linear threshold model) based on static networks are not suitable for the information propagation process in evolving networks.Meanwhile,the existing researches ignore the influence of user behavior on information propagation.Therefore,to tackle this problem,this paper proposes a behavior driven independent cascade(BDIC) propagation model,which can effectively describe the information propagation process in the evolving social networks.Based on this model,a user behavior-driven IM algorithm is proposed.It mainly includes three steps.Firstly,the process of message transmission is modeled to calculate the probability of information transmission in evolving social networks.Then,a user behavior-driven reverse influence sampling algorithm is proposed,which can effectively query the most influential user with a specific time.Finally,a seed query algorithm under different time(time series) is designed,which can effectively reflect the dynamic change characteristics of seed nodes in evolving social networks.To evaluate the effectiveness of the proposed algorithm,a similarity comparison method between seed nodes and the affected nodes is designed.Experiments on real datasets verify the efficiency and scalability of the proposed approaches.The results also demonstrate that the BDIC model can effectively reflect the information propagation process in evolving social networks.

Key words: Evolving social networks, Influence maximization, Propagation probability matrix, Reverse reachable set, User behavior driven model

CLC Number: 

  • TP399
[1] LI Y,FAN J,WANG Y,et al.Influence Maximization on Social Graphs:A Survey[C]//IEEE Transactions on Knowledge and Data Engineering.IEEE,2018:1852-1872.
[2] GOYAL A,BONCHI F,LAKSHMANAN L.Learning influence probabilities in social networks[C]//Proceedings of the 3rd ACM International Conference on Web Search and Data Mi-ning.New York:WSDM,2010:241-250.
[3] DOMINGOS P,RICHARDSON M.Mining the network value of customers[C]//Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mi-ning.New York:ACM,2001:57-66.
[4] CNNIC.The 46th china Statistical Report on Internet Development[R/OL].2020.http://www.cnnic.net.cn/hlwfzyj/hlwxzbg/hlwtjbg/202009/t2020092971257.html.
[5] MATSUBARA Y,SAKURAI Y,PRAKASH B A,et al.Riseand fall patterns of information diffusion:model and implications[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM,2012:6-14.
[6] KEMPE D,KLEINBERG J,TARDOS E.Maximizing the spread of influence through a social network[C]//Proceedings of the ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM,2003:137-146.
[7] YOSHIDA A,HIGURASHI T,MARUISHI M,et al.New Performance Index ‘Attractiveness Factor’ for Evaluating Websites via Obtaining Transition of Users’ Interests[J].Data Science and Engineering,2020,5(3):48-64.
[8] TIAN S,MO S,PENG Z.Deep Reinforcement Learning-BasedApproach to Tackle Topic-Aware Influence Maximization[J].Data Science and Engineering,2020,5(3):1-11.
[9] YANG Y,MAO X,PEI J,et al.Continuous Influence Maximization[J].Association for Computing Transactions on Knowledge Discovery from Data,2020,14(3):1-38.
[10] HUANG H,MENG Z,SHEN H.Competitive and complementary influence maximization in social network:A follower’s pers-pective[J].Knowledge-Based Systems,2021,213(3):106600.
[11] OHSAKA N,AKIBA T,YOSHIDA Y,et al.Dynamic influence analysis in evolving networks[C]//Proceedings of the Very Large Data Bases Endowment.2016:1077-1088.
[12] WANG B,CHEN G,FU L,et al.DRIMUX:Dynamic Rumor Influence Minimization with User Experience in Social Networks[C]//IEEE Transactions on Knowledge and Data Engineering.2017:2168 -2181.
[13] WANG Y,FAN Q,LI Y,et al.Real-Time Influence Maximization on Dynamic Social Streams[C]//Proceedings of the VLDB Endowment.2017:805-816.
[14] XIE M,YANG Q,WANG Q,et al.DynaDiffuse:a dynamic diffusion model for continuous time constrained influence maximization[C]//Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence.2015:346-352.
[15] WU A B,YUAN Y,QIAO B Y,et al.The Influence Maximization Problem Based on Large-Scale Temporal Graph[J].Chinese Journal of Computers,2019,42(12):2647-2664.
[16] WEI J,CUI Z,QIU L,et al.A community-based algorithm for influence maximization on dynamic social networks[J].Intelligent Data Analysis,2020,24(1):959-971.
[17] DUPUIS D,MOUZA D,TRAVERS N,et al.Real-Time In-fluence Maximization in a RTB Setting[J].Data Science and Engineering,2020,5(9):224-239.
[18] LI W,ZHONG K,WANG J,et al.A dynamic algorithm based on cohesive entropy for influence maximization in social networks[J].Expert Systems with Applications,2021,169(5):114207.
[19] WANG C,LIU Y,GAO X,et al.A Reinforcement LearningModel for Influence Maximization in Social Networks[C]//Database Systems for Advanced Applications.Cham,2021:701-709.
[20] WU X,FU L,MENG J,et al.Maximizing Influence Diffusionover Evolving Social Networks[C]//Proceedings of the Fourth International Workshop on Social Sensing.New York,USA,2019:6-11.
[21] BORGS C,BRAUTBAR M,CHAYES J,et al.Maximizing Social Influence in Nearly Optimal Time[C]//Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms.Society for Industrial and Applied Mathematics,2013:946-957.
[22] GUO Q,WANG S,WEI Z,et al.Influence Maximization Revisited:Efficient Reverse Reachable Set Generation with Bound Tightened[C]//Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data.New York,USA,2020:2167-2181.
[23] MAO J X,LIU Y Q,ZANG M,et al.Social Influence Analysis for Micro-Blog User Based on User Behavior[J].Chinese Journal of Computers,2014,37(4):791-800.
[24] HOGG T,LERMAN K.Social dynamics of Digg[J].EPJ Data Science,2012,1(1):1-5.
[25] ZHANG J,LIU B,TANG J,et al.Social influence locality for modeling retweeting behaviors[C]//Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence.Beijing,China,2013:2761-2767.
[26] ZHANG M,LI W H. Influence maximization algorithm based on user interactive representation[J/OL].Journal of Computer Applications.http://kns.cnki.net/kcms/dtail/51.1307.TP.20201229.1645.010.html.
[1] ZUO Yuan-lin, GONG Yue-jiao, CHEN Wei-neng. Budget-aware Influence Maximization in Social Networks [J]. Computer Science, 2022, 49(4): 100-109.
[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] KONG Fang, LI Qi-zhi, LI Shuai. Survey on Online Influence Maximization [J]. Computer Science, 2020, 47(5): 7-13.
[4] HU Qing-cheng, ZHANG Yong, XING Chun-xiao. K-clique Heuristic Algorithm for Influence Maximization in Social Network [J]. Computer Science, 2018, 45(6): 32-35.
[5] LV Wen-yuan, ZHOU Li-hua and LIAO Ren-jian. Coupled Topic-oriented Influence Maximization Algorithm [J]. Computer Science, 2017, 44(12): 28-32.
[6] XIONG Chao, CHEN Yun-fang and CANG Ji-yun. Event-based Node Influence Analysis in Social Network Evolution [J]. Computer Science, 2016, 43(Z6): 404-409.
[7] CAI Guo-yong and PEI Guang-zhan. Influence Maximization Based on LT+ Model in Social Networks [J]. Computer Science, 2016, 43(9): 99-102.
[8] WANG Xue-guang. Research on Critical Nodes in Social Networks Based on Owen Values [J]. Computer Science, 2016, 43(5): 47-50.
[9] WANG Jun,YU Wei,HU Ya-hui and LI Shi-jun. Heuristic Algorithm Based on 3-layer Centrality for Influence Maximization in Social Networks [J]. Computer Science, 2014, 41(1): 59-63.
[10] GONG Xiu-wen and ZHANG Pei-yun. Research on Propagation Model and Algorithm for Influence Maximization in Social Network Based on PageRank [J]. Computer Science, 2013, 40(Z6): 136-140.
[11] . Research on Influence Maximization Problem Based on Dynamic Networks [J]. Computer Science, 2012, 39(6): 111-115.
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.