计算机科学

计算机科学 ›› 2024, Vol. 51 ›› Issue (1): 99-112.doi: 10.11896/jsjkx.230500127

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

信息传播网络推断综述

王宇辰1, 高超1, 王震1,2   

  1. 1 西北工业大学光电与智能研究院 西安710072
    2 西北工业大学网络空间安全学院 西安710072
  • 收稿日期:2023-05-01 修回日期:2023-10-07 出版日期:2024-01-15 发布日期:2024-01-12
  • 通讯作者: 高超(cgao@nwpu.edu.cn)
  • 作者简介:(wany810@mail.nwpu.edu.cn)
  • 基金资助:
    科技部重点研发(2022YFE0112300);国家自然科学基金(62261136549,61976181)

Survey of Inferring Information Diffusion Networks

WANG Yuchen1, GAO Chao1, WANG Zhen1,2   

  1. 1 School of Artificial Intelligence,OPtics and ElectroNics(iOPEN),Northwestern Polytechnical University,Xi’an 710072,China
    2 School of Cybersecurity,Northwestern Polytechnical University,Xi’an 710072,China
  • Received:2023-05-01 Revised:2023-10-07 Online:2024-01-15 Published:2024-01-12
  • About author:WANG Yuchen,born in 1999,postgra-duate.His main research interests include data mining and complex network analysis.
    GAO Chao,born in 1980,Ph.D,professor,Ph.D supervisor.His main research interests include artificial intelligence theory,social computing,system simulation,big data analysis,etc.
  • Supported by:
    National Key R & D Program of China(2022YFE0112300) and National Natural Science Foundation of China(62261136549,61976181).

PDF (PC)

1898

摘要： 信息的传播扩散可以建模为在潜在传播网络上发生的随机过程。由于在实际应用场景中,潜在的传播网络拓扑结构和清晰的传播过程往往是不可见的,因此根据观测到的传播结果,如节点感染时间、状态等信息,推断传播网络拓扑结构,对于分析与理解传播过程、跟踪传播路径以及预测未来传播事件起着重要作用。近年来,传播网络推断问题吸引了众多研究者的目光。文中对近年来的信息传播网络推断工作进行系统性的介绍和总结,为传播网络推断提供一个新视角。

关键词: 传播网络, 网络推断, 信息传播, 信息级联, 关系推断

Abstract: Information diffusion can be modeled as a stochastic process over a network.However,the topology of an underlying diffusion network and the pathways of spread are often not visible in real-world scenarios.Therefore,the inference of diffusion networks becomes critical in the analysis and understanding of the diffusion process,tracking the pathways of spread,and even predicting future contagion events.There has been a surge of interest in diffusion network inference over the past few years.This paper investigates and summarizes the representative research in the field of diffusion network inference.Finally,this paper analyzes the existing problems of diffusion network inference and provides a new perspective on this field.

Key words: Diffusion network, Network inference, Information diffusion, Information cascades, Relationship inference

中图分类号: 

  • TP181
[1]FANG D,CHEN B.Ecological network analysis for a virtual water network[J].Environmental Science & Technology,2015,49(11):6722-6730.
[2]HUANG I B,KEISLER J,LINKOV I.Multi-criteria decisionanalysis in environmental sciences:Ten years of applications and trends[J].Science of the Total Environment,2011,409(19):3578-3594.
[3]SPORNS O.Contributions and challenges for network models in cognitive neuroscience[J].Nature Neuroscience,2014,17(5):652-660.
[4]PARK J Y,CHOI J,CHOI J Y.Network analysis in systemsepidemiology[J].Journal of Preventive Medicine and Public Health,2021,54(4):259.
[5]KUMAR P,SINHA A.Information diffusion modeling and ana-lysis for socially interacting networks[J].Social Network Ana-lysis and Mining,2021,11(1):1-18.
[6]HETHOTE H W.The mathematics of infectious diseases[J].SIAM Review,2000,42(4):599-653.
[7]ADAR E,ADAMIC L A.Tracking information epidemics inblogspace[C]//The 2005 IEEE/WIC/ACM International Conference on Web Intelligence(WI’05).IEEE,2005:207-214.
[8]ZHOU J,LIU Z,LI B.Influence of network structure on rumor propagation[J].Physics Letters A,2007,368(6):458-463.
[9]TANG J,SUN J,WANG C,et al.Social influence analysis in large-scale networks[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2009:807-816.
[10]SUN J,TANG J.A survey of models and algorithms for social influence analysis[C]//Proceedings of the Sixth ACM International Conference on Web Search and Data Mining(WSDM’13).2011:177-214.
[11]SADRI A M,UKKUSURI S V,AHMED M A.Review of social influence in crisis communications and evacuation decision-ma-king[J].Transportation Research Interdisciplinary Perspectives,2021,9:100325.
[12]LESKOVEC J,ADAMIC L A,HUBERMAN B A.The dyna-mics of viral marketing[J].ACM Transactions on the Web(TWEB),2007,1(1):5-es.
[13]BHATTACHARYA S,GAURAV K,GHOSH S.Viral marke-ting on social networks:An epidemiological perspective[J].Phy-sica A:Statistical Mechanics and its Applications,2019,525:478-490.
[14]WANG X,ZHU X,TAO X,et al.Anomalous role of information diffusion in epidemic spreading[J].Physical Review Research,2021,3(1):013157.
[15]ZHU L,YANG F,GUAN G,et al.Modeling the dynamics of rumor diffusion over complex networks[J].Information Sciences,2021,562:240-258.
[16]VAN DER LINDEN S.Misinformation:susceptibility,spread,and interventions to immunize the public[J].Nature Medicine,2022,28(3):460-467.
[17]ZAREIE A,SAKELLARIOU R.Minimizing the spread of misinformation in online social networks:A survey[J].Journal of Network and Computer Applications,2021,186:103094.
[18]PENG S,ZHOU Y,CAO L,et al.Influence analysis in social networks:A survey[J].Journal of Network and Computer Applications,2018,106:17-32.
[19]WANG J,WANG Y C,HUANG M J.False information in social networks:Definition,detection and control[J].Computer Science,2021,48:263-277.
[20]ADAR E,ADAMIC L A.Tracking information epidemics inblogspace[C]//The 2005 IEEE/WIC/ACM International Conference on Web Intelligence(WI’05).IEEE,2005:207-214.
[21]GOMEZ-RODRIGUEZ M,LESKOVEC J,KRAUSE A.Inferring networks of diffusion and influence[J].ACM Transactions on Knowledge Discovery from Data(TKDD),2012,5(4):1-37.
[22]MYERS S,LESKOVEC J.On the convexity of latent social network inference[J].Advances in Neural Information Processing Systems,2010:1741-1749.
[23]LI H,XIA C,WANG T,et al.Capturing dynamics of information diffusion in SNS:A survey of methodology and techniques[J].ACM Computing Surveys(CSUR),2021,55(1):1-51.
[24]GUILLE A,HACID H,FAVRE C,et al.Information diffusion in online social networks:A survey[J].ACM Sigmod Record,2013,42(2):17-28.
[25]LI M,WANG X,GAO K,et al.A survey on information diffusion in online social networks:Models and methods[J].Information,2017,8(4):118.
[26]PASTOR-SATORRAS R,VESPIGNANI A.Epidemic sprea-ding in scale-free networks[J].Physical Review Letters,2001,86(14):3200.
[27]LIU D,YIN Y W,SONG M.Microblog information diffusion:Simulation based on sir model[J].Journal of Beijing University of Posts and Telecommunications(Social Sciences Edition),2014,16(3):28.
[28]NAZEMIAN A,TAGHIYAREH F.Influence maximization inindependent cascade model with positive and negative word of mouth[C]//6th International Symposium on Telecommunications(IST).IEEE,2012:854-860.
[29]LI S,KONG F,TANG K,et al.Online influence maximizationunder linear threshold model[J].Advances in Neural Information Processing Systems,2020,33:1192-1204.
[30]ZHOU F,JIAO J R,LEI B.A linear threshold-hurdle model for product adoption prediction incorporating social network effects[J].Information Sciences,2015,307:95-109.
[31]TRIVEDI N,SINGH A.Efficient influence maximization in social-networks under independent cascade model[J].Procedia Computer Science,2020,173:315-324.
[32]KEMPE D,KLEINBERG J,TARDOSÉ.Maximizing the spread of influence through a social network[C]//Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2003:137-146.
[33]GRANOVETTER M.Threshold models of collective behavior[J].American Journal of Sociology,1978,83(6):1420-1443.
[34]SERRANO E,IGLESIAS C Á,GARIJO M.A novel agent-based rumor spreading model in twitter[C]//Proceedings of the 24th International Conference on World Wide Web.2015:811-814.
[35]RODRIGUEZ M G,SCHÖLKOPF B.Submodular inference ofdiffusion networks from multiple trees[J].arXiv:1205.1671,2012.
[36]GRAY C,MITCHIELL L,ROUGHAN M.Bayesian inferenceof network structure from information cascades[J].IEEE Transactions on Signal and Information Processing over Networks,2020,6:371-381.
[37]GHALEBI E,MIRZASOLEIMAN B,GROSU R,et al.Dynamic network model from partial observations[C]//Proceedings of the 32nd International Conference on Neural Information Processing Systems(NIPS’18).2018:9884-9894.
[38]DJOLONGA J,KRAUSE A.Learning implicit generative mo-dels using differentiable graph tests[J].arXiv:1709.01006,2017.
[39]HAO X,LI X.Network topology inference with estimated node importance[J].Europhysics Letters,2021,134(5):58001.
[40]XU S,SMITH D.Contrastive training for models of information cascades[C]//Proceedings of the AAAI Conference on Artificial Intelligence.2018.
[41]DOU P,SONG G,ZHAO T.Network topology inference from incomplete observation data[J].Science China Information Sciences,2018,61(2):028102:1-028102:3.
[42]KONG L,GAO C,PENG S.Clustering-Based Network Infe-rence with Submodular Maximization[C]//Pacific Rim International Conference on Artificial Intelligence.2022:118-131.
[43]RODRIGUEZ M G,BALDUZZI D,SCHÖLKOPF B.Uncovering the temporal dynamics of diffusion networks[J].arXiv:1105.0697,2011.
[44]GOMEZ-RODRIGUEZ M,SONG L,DANESHMAND H,et al.Estimating diffusion networks:Recovery conditions,sample complexity & soft-thresholding algorithm[J].The Journal of Machine Learning Research,2016,17(1):3092-3120.
[45]GOMEZ-RODRIGUEZ M,LESKOVVEC J,SCHÖLKOPF B.Structure and dynamics of information pathways in online media[C]//Proceedings of the Sixth ACM International Conference on Web Search and Data Mining.2013:23-32.
[46]DU N,SONG L,YUAN M,et al.Learning networks of heterogeneous influence[C]//Proceedings of the 25th International Conference on Neural Information Processing Systems(NIPS’12).2012:2780-2788.
[47]WANG S,HU X,YU P S,et al.MMRate:inferring multi-aspect diffusion networks with multi-pattern cascades[C]//Procee-dings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2014:1246-1255.
[48]TAN Q,LIU Y,LIU J.Motif-aware diffusion network inference[J].International Journal of Data Science and Analytics,2020,9(4):375-387.
[49]ZHAO T,SONG G,HE X.Inferring diffusion networks with life stage heterogeneity[J].Science China Information Sciences,2018,61:1-16.
[50]GAO C,WANG Y,WANG Z,et al.Pairwise-interactions-based Bayesian Inference of Network Structure from Information Cascades[C]//Proceedings of the ACM Web Conference 2023.2023:102-110.
[51]ESLAMI M,RABIEE H R,SALEHI M.Dne:A method for extracting cascaded diffusion networks from social networks[C]//2011 IEEE Third International Conference on Privacy,Security,Risk and Trust and 2011 IEEE Third International Conference on Social Computing.IEEE,2011:41-48.
[52]RAMEZANI M,RABIEE H R,TAHANI M,et al.Dani:A fast diffusion aware network inference algorithm[J].arXiv:1706.00941,2017.
[53]FOROUTAIN N,HAMZEH A.Discovering the hidden struc-ture of a social network:A semi supervised approach[J].IEEE Transactions on Computational Social Systems,2017,4(1):14-25.
[54]CRAWFORD F W.Hidden network reconstruction from information diffusion[C]//2015 18th International Conference on Information Fusion(Fusion).IEEE,2015:180-185.
[55]TAHANI M,HEMMATYAR A M A,RABIEE H R,et al.Inferring dynamic diffusion networks in online media[J].ACM Transactions on Knowledge Discovery from Data(TKDD),2016,10(4):1-22.
[56]BOURIGAULT S,LAGNIER C,LAMPRIER S,et al.Learning social network embeddings for predicting information diffusion[C]//Proceedings of the 7th ACM International Conference on Web Search and Data Mining.2014:393-402.
[57]HU Q,XIE S,LIN S,et al.Clustering embedded approaches for efficient information network inference[J].Data Science and Engineering,2016,1(1):29-40.
[58]BOURIGAULT S,LAMPRIER S,GALLINARI P.Representation learning for information diffusion through social networks:an embedded cascade model[C]//Proceedings of the Ninth ACM International Conference on Web Search and Data Mi-ning.2016:573-582.
[59]KURASHIMA T,IWATA T,TAKAYA N,et al.Probabilistic latent network visualization:Inferring and embedding diffusion networks[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2014:1236-1245.
[60]ZHANG Y,LYU T,ZHANG Y.Cosine:Community-preserving social network embedding from information diffusion cascades[C]//Proceedings of the AAAI Conference on Artificial Intelligence.2018,32(1).
[61]ZHUO W,ZHAO Y,ZHAN Q,et al.DiffusionGAN:Networkembedding for information diffusion prediction with generative adversarial nets[C]//2019 IEEE International Conference on Parallel & Distributed Processing with Applications,Big Data &Cloud Computing,Sustainable Computing & Communications,Social Computing & Networking(ISPA/BDCloud/SocialCom/SustainCom).IEEE,2019:808-816.
[62]RONG Y,ZHU Q,CHENG H.A model-free approach to infer the diffusion network from event cascade[C]//Proceedings of the 25th ACM International on Conference on Information and Knowledge Management.2016:1653-1662.
[63]HU S,CAUTIS B,CHEN Z,et al.Model-free inference of diffusion networks using RKHS embeddings[J].Data Mining and Knowledge Discovery,2019,33(2):499-525.
[64]LAMPRIER S,BOURIGAULT S,GALLINARI P.Extracting diffusion channels from real-world social data:a delay-agnostic learning of transmission probabilities[C]//Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2015.2015:178-185.
[65]GRIPON V,RANNAT M.Reconstructing a graph from pathtraces[C]//2013 IEEE International Symposium on Information Theory.IEEE,2013:2488-2492.
[66]AMIN K,HEIDARI H,KEARNS M.Learning from contagion(without timestamps)[C]//International Conference on Machine Learning.PMLR,2014:1845-1853.
[67]HUANG H,YAN Q,GAN T,et al.Learning diffusions without timestamps[C]//Proceedings of the AAAI Conference on Artificial Intelligence.2019:582-589.
[68]HUANG H,YAN Q,CHEN L,et al.Statistical inference of diffusion networks[J].IEEE Transactions on Knowledge and Data Engineering,2019,33(2):742-753.
[69]HAN K,TIAN Y,ZHANG Y,et al.Statistical estimation of diffusion network topologies[C]//2020 IEEE 36th International Conference on Data Engineering(ICDE).IEEE,2020:625-636.
[70]GAN T,HAN K,HUANG H,et al.Diffusion Network Infe-rence from Partial Observations[C]//Proceedings of the AAAI Conference on Artificial Intelligence.2021,35(9):7493-7500.
[71]SUN Y,ZHANG Y,YAN Q,et al.Fast inference algorithm of diffusion networks without infection temporal information[J].Journal of Frontiers of Computer Science & Technology,2019,13(4):541.
[72]WANG L,ERMON S,HOPCROFT J E.Feature-enhancedprobabilistic models for diffusion network inference[C]//Joint European Conference on Machine Learning and Knowledge Discovery in Databases.Berlin,Heidelberg:Springer,2012:499-514.
[73]DU N,SONG L,WOO H,et al.Uncover topic-sensitive information diffusion networks[C]//Artificial Intelligence and Statistics.PMLR,2013:229-237.
[74]ZHOU D H,HAN W B,WANG Y J,et al.Information diffusion network inferring and pathway tracking[J].Science China Information Sciences,2015,58(9):1-15.
[75]MANCO G,RITACCO E,BARBIERI N.A Factorization Approach for Survival Analysis on Diffusion Networks[J].IEEE Transactions on Knowledge and Data Engineering,2019,33(1):1-13.
[76]ULLMAN J B,BENTLER P M.Structural equation modeling[M]//Handbook of Psychology,Second Edition,2012,2.
[77]BAINGANA B,MATEOS G,GIANNAKIS G B.Proximal-gradient algorithms for tracking cascades over social networks[J].IEEE Journal of Selected Topics in Signal Processing,2014,8(4):563-575.
[78]BAINGANA B,GIANNAKIS G B.Tracking switched dynamic network topologies from information cascades[J].IEEE Transa-ctions on Signal Processing,2016,65(4):985-997.
[79]SHEN Y,BAINGAGA B,GIANNAKIS G B.Tensor decompositions for identifying directed graph topologies and tracking dynamic networks[J].IEEE Transactions on Signal Processing,2017,65(14):3675-3687.
[80]GAO S,PANG H,GALLINAR P,et al.A novel embeddingmethod for information diffusion prediction in social network big data[J].IEEE Transactions on Industrial Informatics,2017,13(4):2097-2105.
[81]WANG D,ZHOU W,ZHENG J X,et al.Who spread to whom? Inferring online social networks with user features[C]//2018 IEEE International Conference on Communications(ICC).IEEE,2018:1-6.
[82]YANG X,DONG M,CHEN X,et al.Recommender system-based diffusion inferring for open social networks[J].IEEE Transactions on Computational Social Systems,2019,7(1):24-34.
[83]ERDO″S P,RÉNYI A.On the evolution of random graphs[J].Publications of the Mathematical Institute of the Hungarian Academy of Sciences,1960,5(1):17-60.
[84]BORGATII S P,EVERETT M G.Models of core/peripherystructures[J].Social Networks,2000,21(4):375-395.
[85]CLAUSET A,MOORE C,NEWMAN M E J.Hierarchicalstructure and the prediction of missing links in networks[J].Nature,2008,453(7191):98-101.
[86]LESKOVEC J,KLEINBERG J,FALOUTSOS C.Graphs overtime:densification laws,shrinking diameters and possible explanations[C]//Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining.2005:177-187.
[87]LANCICHINETTI A,FORTUNATO S,RADICCHI F.Benchmark graphs for testing community detection algorithms[J].Physical Review E,2008,78(4):046110.
[88]LESKOVEC J,FALOUTSOS C.Scalable modeling of realgraphs using kronecker multiplication[C]//Proceedings of the 24th International Conference on Machine Learning.2007:497-504.
[89] LESKOVEC J,KLEINBERG J,FALOUTSO C.Graph evolution:Densification and shrinking diameters[J].ACM transactions on Knowledge Discovery from Data(TKDD),2007,1(1):2-es.
[90]CHEN W,YUAN Y,ZHANG L.Scalable influence maximization in social networks under the linear threshold model[C]//2010 IEEE International Conference on Data Mining.IEEE,2010:88-97.
[91]PEEL L,PEIXOTO T P,DE DOMENICO M.Statistical infe-rence links data and theory in network science[J].Nature Communications,2022,13(1):1-15.
[92]PEIXOTO T P.Reconstructing networks withunknown and he-terogeneous errors[J].Physical Review X,2018,8(4):041011.
[93]ZHOU F,XU X,TRAJCEVSKI G,et al.A survey of information cascade analysis:Models,predictions,and recent advances[J].ACM Computing Surveys(CSUR),2021,54(2):1-36.
[94]GAO X,CAO Z,LI S,et al.Taxonomy and evaluation for microblog popularity prediction[J].ACM Transactions on Know-ledge Discovery from Data(TKDD),2019,13(2):1-40.
[95]LI Y,FAN J,WANG Y,et al.Influence maximization on social graphs:A survey[J].IEEE Transactions on Knowledge and Data Engineering,2018,30(10):1852-1872.
[96]JIANG J,WEN S,YU S,et al.Identifying propagation sources in networks:State-of-the-art and comparative studies[J].IEEE Communications Surveys & Tutorials,2016,19(1):465-481.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发