用户行为驱动的时序影响力最大化问题研究

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

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

用户行为驱动的时序影响力最大化问题研究

魏鹏¹, 马玉亮², 袁野³, 吴安彪¹

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)
基金资助:
国家自然科学基金(61932004,62002054);中国博士后科学基金(2020M670780);东北大学博士后科研基金

Study on Temporal Influence Maximization Driven by User Behavior

WEI Peng¹, MA Yu-liang², YUAN Ye³, WU An-biao¹

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.

摘要/Abstract

摘要： 影响力最大化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

魏鹏, 马玉亮, 袁野, 吴安彪. 用户行为驱动的时序影响力最大化问题研究[J]. 计算机科学, 2022, 49(6): 119-126. https://doi.org/10.11896/jsjkx.210700145

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. https://doi.org/10.11896/jsjkx.210700145

参考文献

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

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed