计算机科学

计算机科学 ›› 2022, Vol. 49 ›› Issue (8): 1-11.doi: 10.11896/jsjkx.210700240

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

基于大数据的进化网络影响力分析研究综述

何强1,2, 尹震宇1, 黄敏4, 王兴伟3, 王源田2, 崔硕2, 赵勇3   

  1. 1 中国科学院沈阳计算技术研究所有限公司 沈阳 110168
    2 东北大学医学与生物信息工程学院 沈阳 110169
    3 东北大学计算机科学与工程学院 沈阳 110169
    4 东北大学信息科学与工程学院 沈阳 110819
  • 收稿日期:2021-07-25 修回日期:2022-05-08 发布日期:2022-08-02
  • 通讯作者: 尹震宇(1164041005@qq.com)
  • 作者简介:(heqiang@bmic.neu.edu.cn)
  • 基金资助:
    国家重点研发计划(2021YFC3300300);辽宁省博士启动项目(2021-BS-055);中国博士后科学基金(2021M693318);中央高校基本业务费(N2119004,N2119007)

Survey of Influence Analysis of Evolutionary Network Based on Big Data

HE Qiang1,2, YIN Zhen-yu1, HUANG Min4, WANG Xing-wei3, WANG Yuan-tian2, CUI Shuo2, ZHAO Yong3   

  1. 1 Shenyang Institute of Computing Technology Co. Ltd.,CAS,Shenyang 110168,China
    2 College of Medicine and Biological Information Engineering,Northeastern University,Shenyang 110169,China
    3 College of Computer Science and Engineering,Northeastern University,Shenyang 110169,China
    4 College of Information Science and Engineering,Northeastern University,Shenyang 110819,China
  • Received:2021-07-25 Revised:2022-05-08 Published:2022-08-02
  • About author:HE Qiang,born in 1991,Ph.D,associate professor,is a member of China Computer Federation.His main research interests include social networks and machine learning.
    YIN Zhen-yu,born in 1979,Ph.D,is a senior member of China Computer Fe-deration.His main research interests include industrial embedded systems,industrial Internet of things,etc.
  • Supported by:
    National Key Research and Development Program(2021YFC3300300),Doctor Startup Foundation of Liaoning Province(2021-BS-055),China Postdoctoral Science Foundation(2021M693318) and Fundamental Funds for the Central Universities(N2119004,N2119007).

PDF (PC)

950

摘要： 社交影响力分析能够在社交网络中执行复杂行为分析,是现代信息和服务行业最重要的技术之一,越来越多的社交网络研究者把关注点放在社交影响力上。真实的社交网络是不断演化的而非静态的,进化网络的提出也带来了新的挑战和机遇,同时进化网络中海量的社交信息也为大数据分析技术的快速发展提供了强有力的支撑。文中对进化网络和影响最大化问题进行了论述,并讨论了社交影响力分析问题的传播模型和基于社交网络大数据的影响力分析方法,同时进一步整理了一些应用广泛的影响力算法。此外,还论述了大数据、进化网络与社交影响力最大化的关系。文中的目标是通过大规模社交网络中的影响力分析,帮助其他研究人员更好地理解现有的工作,为社交网络影响力分析提供新的思路。

关键词: 大数据, 机器学习, 进化网络, 社交影响力

Abstract: One of the most important technologies in modern information and service industry is social influence analysis.More and more researchers in social networks focus on social influence.Real social networks are evolving rather than static.The proposal of evolutionary network also brings new challenges and opportunities.At the same time,the massive social information in the evolutionary network also provides strong support for the rapid development of big data analysis technology.In this paper,evolutionary network and influence maximization are discussed.It also discusses the diffusion model of social influence analysis and the influence analysis method based on social network big data.At the same time,some widely used influence algorithms are further sorted out.In addition,this paper also discusses the relationship between big data,evolutionary networks,and social influence maximization.This paper aims to help other researchers to better understand the existing work and provide new ideas for the influence analysis of social networks through the influence analysis of large-scale social networks.

Key words: Big data, Evolutionary network, Machine learning, Social influence

中图分类号: 

  • TP393
[1]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.
[2]NEWMAN M E J.The structure of scientific collaboration networks[J].Proceedings of the National Academy of Sciences,2001,98(2):404-409.
[3]GAO N,WANG B,LU K,et al.Teaching-learning-based optimi-zation of an ultra-broadband parallel sound absorber[J/OL].Applied Acoustics,2021,178:107969.https://doi.org/10.1016/j.apacoust.2021.107969.
[4]BANERJEE A V.A simple model of herd behavior[J].TheQuarterly Journal of Economics,1992,107(3):797-817.
[5]DAS K,PACHORI R B.Schizophrenia detection technique using multivariate iterative filtering and multichannel EEG signals[J/OL].Biomedical Signal Processing and Control,2021,67:102525.https://doi.org/10.1016/j.knosys.2019.07.004.
[6]LESKOVEC J,KRAUSE A,GUESTRIN C,et al.Cost-effective outbreak detection in networks[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Disco-very and Data Mining.2007:420-429.
[7]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.2016:695-710.
[8]DAGUM P,KARP R,LUBY M,et al.An optimal algorithm for Monte Carlo estimation[J].SIAM Journal on Computing,2000,29(5):1484-1496.
[9]LV J,YANG B,YANG Z,et al.A community-based algorithm for influence blocking maximization in social networks[J].Cluster Computing,2019,22(3):5587-5602.
[10]WANG X G.A new algorithm for the influence maximization problem in dynamic networks or traffic sensor networks[J].Multimedia Tools and Applications,2016,75(8):4833-4844.
[11]LI W M,LI Z,LUVEMBE A M,et al.Influence maximization algorithm based on Gaussian propagation model[J/OL].Information Sciences,2021,568:386-402.https://doi.org/10.1016/j.ins.2021.04.061.
[12]TANG J,ZHANG R,WANG P,et al.A discrete shuffled frog-leaping algorithmto identify influential nodes for influence maximization in social networks[J/OL].Knowledge-Based Systems,2020,187:104833.https://doi.org/10.1016/j.knosys.2019.07.004.
[13]WU Y Z.Research on sequential regression technology based on evolutionary algorithm[D].Heifei:University of Science and Technology of China,2016.
[14]WANG X,ZHANG Y,ZHANG W,et al.Efficient distance-aware influence maximization in geo-social networks[J].IEEE Transactions on Knowledge and Data Engineering,2016,29(3):599-612.
[15]LIU B,CONG G,XU D,et al.Time constrained influence maximization in social networks[C]//2012 IEEE 12th International Conference on Data Mining.IEEE,2012:439-448.
[16]MOHAMMADI A,SARAEE M,MIRZAEI A.Time-sensitiveinfluence maximization in social networks[J].Journal of Information Science,2015,41(6):765-778.
[17]BARBIERI N,BONCHI F,MANCO G.Topic-aware social influence propagation models[J].Knowledge and Information Systems,2013,37(3):555-584.
[18]HE Q,FANG H,ZHANG J,et al.Dynamic Opinion Maximization in Social Networks[J/OL].IEEE Transactions on Know-ledge and Data Engineering,2021.https://ieeexplore.ieee.org/abstract/document/9423621.
[19]SHU R,CHENG P,CHEN G,et al.Direct Universal Access:Making Data Center Resources Available to {FPGA}[C]//16th {USENIX} Symposium on Networked Systems Design and Implementation({NSDI} 19).2019:127-140.
[20]HUNTER II T.Advanced microservices:a hands-on approach to microservice infrastructure and tooling[M].Apress,2017.
[21]HE Q,WANG X,ZHAO Y,et al.Reinforcement LearningBased Competitive Opinion Maximization Approach in Signed Social Networks[J/OL].IEEE Transactions on Computational Social Systems,2021.https://ieeexplore.ieee.org/abstract/document/9611781.
[22]HUDSON N,KHAMFROUSH H.Behavioral Information Diffusion for Opinion Maximization in Online Social Networks[J].IEEE Transactions on Network Science and Engineering,2020,8(2):1259-1268.
[23]MA H,LYU M R,KING I.Learning to recommend with trust and distrust relationships[C]//Proceedings of the Third ACM Conference on Recommender Systems.2009:189-196.
[24]MORRIS M,KRETZSCHMAR M.Concurrent partnerships and transmission dynamics in networks[J].Social networks,1995,17(3/4):299-318.
[25]PAGE L,BRIN S,MOTWANI R,et al.The PageRank citation ranking:Bringing order to the web[R].Stanford InfoLab,1999.
[26]HE Q,SUN L,WANG X,et al.Positive opinion maximization insigned social networks[J/OL].Information Sciences,2021,558:34-49.https://doi.org/10.1016/j.ins.2020.12.091.
[27]HE Q,WANG X,HUANG M,et al.Multi-stage opinion maximization in social networks[J].Neural Computing and Applications,2021,33(19):12367-12380.
[28]LI H,PAN L,WU P.Dominated competitive influence maximization with time-critical and time-delayed diffusion in social networks[J/OL].Journal of computational science,2018,28:318-327.https://doi.org/10.1016/j.jocs.2017.10.015.
[29]GOMEZ-RODRIGUEZ M,SCHÖLKOPF B.Influence Maximization in Continuous Time Diffusion Networks[J].arXiv:1205.1682,2012.
[30]LI J,SELLIS T,CULPEPPER J S,et al.Geo-social influence spanning maximization[J].IEEE Transactions on Knowledge and Data Engineering,2017,29(8):1653-1666.
[31]NEMHAUSER G L,WOLSEY L A,FISHER M L.An analysis of approximations for maximizing submodular set functions—I[J].Mathematical Programming,1978,14(1):265-294.
[32]ALI K,WANG C Y,CHEN Y S.A novel nested q-learningmethod to tackle time-constrained competitive influence maximization[J/OL].IEEE Access,2018,7:6337-6352.https://ieee-xplore.ieee.org/abstract/document/8584421.
[33]QIU L Q,YU J F,FAN X,et al.Analysis of influence maximization in temporal social networks[J/OL].IEEE Access,2019,7:42052-42062.https://ieeexplore.ieee.org/abstract/document/8620999.
[34]CHEN W,LIN T,YANG C.Real-time topic-aware influencemaximization using preprocessing[J].Computational social networks,2016,3(1):1-19.
[35]ZHANG Z K,LIU C,ZHAN X X,et al.Dynamics of information diffusion and its applications on complex networks[J/OL].Physics Reports,2016,651:1-34.https://doi.org/10.1016/j.physrep.2016.07.002.
[36]LIN Y,LUI J C S.Analyzing competitive influence maximization problems with partial information:An approximation algorithmic framework[J/OL].Performance Evaluation,2015,91:187-204.https://doi.org/10.1016/j.peva.2015.06.012.
[37]ZHANG Y,BURER S,NICK STREET W,et al.EnsemblePruning Via Semi-definite Programming[J].Journal of Machine Learning Research,2006,7(7):1315-1338.
[38]RICHARDSON M,DOMINGOS P.Mining knowledge-sharing sites for viral marketing[C]//Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2002:61-70.
[39]MYERS S A,LESKOVEC J.On the convexity of latent social network inference[J].arXiv:1010.5504,2010.
[40]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:Springer,2012:499-514.
[41]JACCARD P.The distribution of the flora in the alpine zone.1[J].New Phytologist,1912,11(2):37-50.
[42]GOEMANS M X,WILLIAMSON D P.Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming[J].Journal of the ACM(JACM),1995,42(6):1115-1145.
[43]DU N,SONG L,YUAN M,et al.Learning networks of heterogeneous influence[J/OL].Advances in Neural Information Processing Systems,2012,25:2780-2788.https://dl.acm.org/doi/abs/10.5555/2999325.2999445.
[44]DU N,LIANG Y,BALCAN M,et al.Influence function learning in information diffusion networks[C]//International Conference on Machine Learning.PMLR,2014:2016-2024.
[45]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.
[46]NETRAPALLI P,SANGHAVI S.Learning the graph of epidemic cascades[J].ACM SIGMETRICS Performance Evaluation Review,2012,40(1):211-222.
[47]D’ASPREMONT A,EL GHAOUI L,JORDAN M I,et al.A direct formulation for sparse PCA using semidefinite programming[J].SIAM Review,2007,49(3):434-448.
[48]LANCKRIET G R G,CRISTIANINI N,BARTLETT P,et al.Learning the kernel matrix with semidefinite programming[J].Journal of Machine Learning Research,2004,5(Jan):27-72.
[49]FUJISAWA K,FUKUDA M,KOJIMA M,et al.SDPA-C(semidefinite Programming Algorithm-Completion Method).User’s Manual-Version 6-10[M].Inst.of Technology,2004.
[50]LAGRÉE P,CAPPÉ O,CAUTIS B,et al.Algorithms for online in-fluencer marketing[J].ACM Transactions on Knowledge Discovery from Data(TKDD),2018,13(1):1-30.
[51]COHEN E,DELLING D,PAJOR T,et al.Sketch-based influen-ce maximization and computation:Scaling up with guarantees[C]//Proceedings of the 23rd ACM International Conferenceon Information and Knowledge Management.2014:629-638.
[52]GOYAL A,LU W,LAKSHMANAN L V S.Celf++ optimizing the greedy algorithm for influence maximization in social networks[C]//Proceedings of the 20th International Conference Companion on World Wide Web.2011:47-48.
[53]COHEN E,DELLING D,PAJOR T,et al.Sketch-based in-fluence maximization and computation:Scaling up with guarantees[C]//Proceedings of the 23rd ACM International Confe-rence on Information and Knowledge Management.2014:629-638.
[54]BAO Z K,LIU J G,ZHANG H F.Identifying multiple influential spreaders by a heuristic clustering algorithm[J].Physics Letters A,2017,381(11):976-983.
[55]WANG X,SU Y,ZHAO C,et al.Effective identification of multiple influential spreaders by Degree Punishment[J/OL].Physica A:Statistical Mechanics and its Applications,2016,461:238-247.https://doi.org/10.1016/j.physa.2016.05.020.
[56]CHEN W,WANG Y,YANG S.Efficient influence maximizationin social networks[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2009:199-208.
[57]FREEMAN L C.Centrality in social networks conceptual clarifi-cation[J].Social Networks,1978,1(3):215-239.
[58]BUCUR D,IACCA G.Influence maximization in social networkswith genetic algorithms[C]//European Conference on the Applications of Evolutionary Computation.Cham:Springer,2016:379-392.
[59]JIANG Q,SONG G,GAO C,et al.Simulated annealing based influence maximization in social networks[C]//Twenty-fifth AAAI Conference on Artificial Intelligence.2011.
[60]TSAI C W,YANG Y C,CHIANG M C.A genetic newgreedy algorithm for influence maximization in social network[C]//2015 IEEE International Conference on Systems,Man,and Cybernetics.IEEE,2015:2549-2554.
[61]GONG M,YAN J,SHEN B,et al.Influence maximization in social networks based on discrete particle swarm optimization[J/OL].Information Sciences,2016,367:600-614.https://doi.org/10.1016/j.physa.2016.05.020.
[62]ERDOS P,RÉNYI A.On the evolution of random graphs[J].Publ.Math.Inst.Hung.Acad.Sci,1960,5(1):17-60.
[63]GOLDENBERG J,LIBAI B,MULLER E.Using complex systems analysis to advance marketing theory development:Mode-ling heterogeneity effects on new productgrowth through stochastic cellular automata[J].Academy of Marketing Science Review,2001,9(3):1-18.
[64]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.
[65]DANESHMAND H,GOMEZ-RODRIGUEZ M,SONG L,et al.Estimating diffusion network structures:Recovery conditions,sample complexity & soft-thresholding algorithm[C]//International Conference on Machine Learning.PMLR,2014:793-801.
[66]LESKOVEC J,BACKSTROM L,KLEINBERG J.Meme-tra-cking and the dynamics of the news cycle[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2009:497-506.
[67]NAKATA K,FUJISAWA K,FUKUDA M,et al.Exploitingsparsity insemidefinite programming via matrix completion II:Implementation and numerical results[J].Mathematical Programming,2003,95(2):303-327.
[68]DU N,SONG L,GOMEZ-RODRIGUEZ M,et al.Scalable influen-ce estimation in continuous-time diffusion networks[J/OL].Advances in Neural Information Processing Systems,2013,26:3147.https://dl.acm.org/doi/abs/10.5555/2999792.2999963.
[69]BISWAS T K,ABBASI A,CHAKRABORTTY R K.An MCDM integrated adaptive simulated annealing approach for influence maximization in social networks[J/OL].Information Sciences,2021,556:27-48.https://doi.org/10.1016/j.ins.2020.12.048.
[70]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.
[71]SAITO K,KIMURA M,OHARA K,et al.Learning continuous-time information diffusion model for social behavioral data ana-lysis[C]//Asian Conference on Machine Learning.Berlin:Springer,2009:322-337.
[72]YANG G,CAO Y,TAO H.A method for multi-objective optimization and application in automobile impact[J/OL].Journal of Physics:Conference Series.2021,1802(3):032129.https://doi.org/10.1088/1742-6596/1802/3/032129.
[1] 冷典典, 杜鹏, 陈建廷, 向阳.
面向自动化集装箱码头的AGV行驶时间估计
Automated Container Terminal Oriented Travel Time Estimation of AGV
计算机科学, 2022, 49(9): 208-214. https://doi.org/10.11896/jsjkx.210700028
[2] 宁晗阳, 马苗, 杨波, 刘士昌.
密码学智能化研究进展与分析
Research Progress and Analysis on Intelligent Cryptology
计算机科学, 2022, 49(9): 288-296. https://doi.org/10.11896/jsjkx.220300053
[3] 陈晶, 吴玲玲.
多源异构环境下的车联网大数据混合属性特征检测方法
Mixed Attribute Feature Detection Method of Internet of Vehicles Big Datain Multi-source Heterogeneous Environment
计算机科学, 2022, 49(8): 108-112. https://doi.org/10.11896/jsjkx.220300273
[4] 李瑶, 李涛, 李埼钒, 梁家瑞, Ibegbu Nnamdi JULIAN, 陈俊杰, 郭浩.
基于多尺度的稀疏脑功能超网络构建及多特征融合分类研究
Construction and Multi-feature Fusion Classification Research Based on Multi-scale Sparse Brain Functional Hyper-network
计算机科学, 2022, 49(8): 257-266. https://doi.org/10.11896/jsjkx.210600094
[5] 张光华, 高天娇, 陈振国, 于乃文.
基于N-Gram静态分析技术的恶意软件分类研究
Study on Malware Classification Based on N-Gram Static Analysis Technology
计算机科学, 2022, 49(8): 336-343. https://doi.org/10.11896/jsjkx.210900203
[6] 陈明鑫, 张钧波, 李天瑞.
联邦学习攻防研究综述
Survey on Attacks and Defenses in Federated Learning
计算机科学, 2022, 49(7): 310-323. https://doi.org/10.11896/jsjkx.211000079
[7] 李亚茹, 张宇来, 王佳晨.
面向超参数估计的贝叶斯优化方法综述
Survey on Bayesian Optimization Methods for Hyper-parameter Tuning
计算机科学, 2022, 49(6A): 86-92. https://doi.org/10.11896/jsjkx.210300208
[8] 赵璐, 袁立明, 郝琨.
多示例学习算法综述
Review of Multi-instance Learning Algorithms
计算机科学, 2022, 49(6A): 93-99. https://doi.org/10.11896/jsjkx.210500047
[9] 王飞, 黄涛, 杨晔.
基于Stacking多模型融合的IGBT器件寿命的机器学习预测算法研究
Study on Machine Learning Algorithms for Life Prediction of IGBT Devices Based on Stacking Multi-model Fusion
计算机科学, 2022, 49(6A): 784-789. https://doi.org/10.11896/jsjkx.210400030
[10] 肖治鸿, 韩晔彤, 邹永攀.
基于多源数据和逻辑推理的行为识别技术研究
Study on Activity Recognition Based on Multi-source Data and Logical Reasoning
计算机科学, 2022, 49(6A): 397-406. https://doi.org/10.11896/jsjkx.210300270
[11] 姚烨, 朱怡安, 钱亮, 贾耀, 张黎翔, 刘瑞亮.
一种基于异质模型融合的 Android 终端恶意软件检测方法
Android Malware Detection Method Based on Heterogeneous Model Fusion
计算机科学, 2022, 49(6A): 508-515. https://doi.org/10.11896/jsjkx.210700103
[12] 许杰, 祝玉坤, 邢春晓.
机器学习在金融资产定价中的应用研究综述
Application of Machine Learning in Financial Asset Pricing:A Review
计算机科学, 2022, 49(6): 276-286. https://doi.org/10.11896/jsjkx.210900127
[13] 李野, 陈松灿.
基于物理信息的神经网络:最新进展与展望
Physics-informed Neural Networks:Recent Advances and Prospects
计算机科学, 2022, 49(4): 254-262. https://doi.org/10.11896/jsjkx.210500158
[14] 王美珊, 姚兰, 高福祥, 徐军灿.
面向医疗集值数据的差分隐私保护技术研究
Study on Differential Privacy Protection for Medical Set-Valued Data
计算机科学, 2022, 49(4): 362-368. https://doi.org/10.11896/jsjkx.210300032
[15] 孙轩, 王焕骁.
政务大数据安全防护能力建设:基于技术和管理视角的探讨
Capability Building for Government Big Data Safety Protection:Discussions from Technologicaland Management Perspectives
计算机科学, 2022, 49(4): 67-73. https://doi.org/10.11896/jsjkx.211000010
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
本系统由北京玛格泰克科技发展有限公司设计开发