计算机科学 ›› 2022, Vol. 49 ›› Issue (6): 119-126.doi: 10.11896/jsjkx.210700145

• 数据库&大数据&数据科学 • 上一篇    下一篇


魏鹏1, 马玉亮2, 袁野3, 吴安彪1   

  1. 1 东北大学计算机科学与工程学院 沈阳 110000
    2 东北大学工商管理学院 沈阳 110000
    3 北京理工大学计算机学院 北京 100081
  • 收稿日期:2021-07-14 修回日期:2021-10-20 出版日期:2022-06-15 发布日期:2022-06-08
  • 通讯作者: 马玉亮(mayuliang@mail.neu.edu.cn)
  • 作者简介:(vpeng1009@163.com)
  • 基金资助:

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.

摘要: 影响力最大化IM问题旨在查找社交网络中的一组用户,通过这些用户,使信息在网络中传播的范围最大化。现有研究主要关注静态网络中的IM问题,然而在现实生活中,社交网络是不断演化的,基于静态网络的传播模型(如独立级联模型、线性阈值模型)无法适用于演化网络中的信息传播过程。同时,现有研究忽略了用户行为对信息传播的影响。因此,针对该问题,提出了一种用户行为驱动的独立级联BDIC传播模型,该模型主要根据用户行为对信息的传播过程进行建模,可有效刻画演化社交网络中的信息传播过程。在该模型的基础上,提出了用户行为驱动的影响力最大化算法,主要包括3个步骤:首先,建模消息传播过程,计算演化社交网络中的信息传播概率;然后,提出一种用户行为驱动的反向影响力采样方法,有效查询单个时间点下的种子用户;最后,设计一种不同时间节点(时间序列)下的种子节点查询方法,有效反映演化社交网络中种子节点动态变化的特性。为了评估所提算法的有效性,设计了种子节点与受影响节点的相似度对比方法。通过大量真实数据集上的实验,验证了信息传播概率算法的高效性和扩展性,证明了相比普通的独立级联模型,BDIC模型能更好地建模演化社交网络中的信息传播过程。

关键词: 传播概率矩阵, 反向可达集, 行为驱动模型, 演化社交网络, 影响力最大化

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


  • 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] 孔世明, 冯永, 张嘉云.
Multi-level Inheritance Influence Calculation and Generalization Based on Knowledge Graph
计算机科学, 2022, 49(9): 221-227. https://doi.org/10.11896/jsjkx.210700144
[2] 陈晋音, 张敦杰, 林翔, 徐晓东, 朱子凌.
False Message Propagation Suppression Based on Influence Maximization
计算机科学, 2020, 47(6A): 17-23. https://doi.org/10.11896/JsJkx.190900086
[3] 孔芳, 李奇之, 李帅.
Survey on Online Influence Maximization
计算机科学, 2020, 47(5): 7-13. https://doi.org/10.11896/jsjkx.200200071
[4] 吕文渊,周丽华,廖仁建.
Coupled Topic-oriented Influence Maximization Algorithm
计算机科学, 2017, 44(12): 28-32. https://doi.org/10.11896/j.issn.1002-137X.2017.12.005
[5] 熊超,陈云芳,仓基云.
Event-based Node Influence Analysis in Social Network Evolution
计算机科学, 2016, 43(Z6): 404-409. https://doi.org/10.11896/j.issn.1002-137X.2016.6A.096
[6] 蔡国永,裴广战.
Influence Maximization Based on LT+ Model in Social Networks
计算机科学, 2016, 43(9): 99-102. https://doi.org/10.11896/j.issn.1002-137X.2016.09.018
[7] 王俊,余伟,胡亚慧,李石君.
Heuristic Algorithm Based on 3-layer Centrality for Influence Maximization in Social Networks
计算机科学, 2014, 41(1): 59-63.
Full text



No Suggested Reading articles found!