基于感染结果的传播网络推断方法
作者:
作者简介:

赛影辉(1983-),女,博士生,主要研究领域为数据挖掘;
侯叶俏(1996-),女,博士生,主要研究领域为数据挖掘;
王明鑫(1995-),女,博士生,主要研究领域为数据挖掘;
李翔翔(1982-),女,高级工程师,主要研究领域为海量遥感数据处理与服务,数据挖掘;
陈畅(1983-),男,博士,讲师,主要研究领域为复杂网络,众包;
孙月明(1992-),女,硕士,主要研究领域为数据挖掘;
雷伯涵(1997-),男,博士生,CCF学生会员,主要研究领域为数据挖掘,自然语言处理;
陈旭(1982-),男,博士,副教授,主要研究领域为海量遥感数据处理与服务,数据挖掘.

通讯作者:

陈旭,E-mail:xuchen@whu.edu.cn

中图分类号:

TP309

基金项目:

民用航天“十三五”技术预先研究项目(B0301);湖北省技术创新专项重大项目(2017AAA125);武汉市应用基础前沿项目(2018010401011288)


Diffusion Network Inference Based on Infection Results
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [40]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    为揭示传播网络中节点之间的父子影响关系,现有工作大多需要知道节点的感染时间,而该信息往往只有通过对传播过程进行实时监控才能获得.研究如何基于传播结果来学习获得传播网络中节点之间的父子影响关系.传播结果只包含每个传播过程中节点的最终感染状态,而节点的最终感染状态在实际中往往比节点的感染时间更容易获得.提出了一种基于条件熵的方法来推断网络中每个节点的潜在候选父节点.此外,能够通过从基于条件熵的推断结果中发现并修剪那些实际不太可能存在的父子影响关系来优化最终的影响关系推断结果.在人工网络和真实网络上的大量实验,验证了该方法的有效性和运行效率.

    Abstract:

    To reveal parent-child influence relationships between nodes in a diffusion network, most prior work requires knowledge of node infection time, which is possible only by carefully monitoring the diffusion process. This work investigates how to solve this problem by learning from diffusion results, which contain only the final infection statuses of nodes in each diffusion process and are often more easily accessible in practice. A conditional entropy-based method is presented to infer potential candidate parent nodes for each node in the network. Furthermore, the inference results are able to be refined by identifying and pruning the inferred influence relations that are unlikely to exist in reality. Experimental results on both synthetic and real-world networks verify the effectiveness and efficiency of our approach.

    参考文献
    [1] Gao S, Pang H, Gallinari P, et al.A novel embedding method for information diffusion prediction in social network bid data.IEEE Trans.on Industrial Informatics, 2017, 13(4):2097-2105.[doi:10.1109/TII.2017.2684160]
    [2] Gomez-Rodriguez M, Leskovec J, Schölkopf B.Modeling information propagation with survival theory.In:Proc.of the ICML 2013.2013.666-674.http://proceedings.mlr.press/v28/gomez-rodriguez13.pdf
    [3] Wallinga J, Teunis P.Different epidemic curves for severe acute respiratory syndrome reveal similar impacts of control measures.American Journal of Epidemiology, 2004, 160(6):509-516.[doi:10.1093/aje/kwh255]
    [4] Leskovec J, Adamic LA, Huberman BA.The dynamics of viral marketing.ACM Trans.on the Web, 2007, 1(1):5.[doi:10.1145/1134707.1134732]
    [5] Mehmood Y, Barbieri N, Bonchi F, et al.CSI:Community-level social influence analysis.In:Proc.of the ECML PKDD 2013.2013.48-63.[doi:10.1007/978-3-642-40991-2_4]
    [6] Han K, Tian Y, Zhang Y, et al.Statistical estimation of diffusion network topologies.In:Proc.of the ICDE 2020.2020.625-636.[doi:10.1109/ICDE48307.2020.00060]
    [7] Huang H, Yan Q, Chen L, et al.Statistical inference of diffusion networks.IEEE Trans.on Knowledge and Data Engineering, 2021, 33(2):742-753.[doi:10.1109/TKDE.2019.2930060]
    [8] Huang H, Yan Q, Gan T, et al.Learning diffusions without timestamps.In:Proc.of the AAAI 2019.2019.582-589.https://aaai.org/ojs/index.php/AAAI/article/view/3833/3711
    [9] Sun Y, Zhang Y, Yan Q, et al.Fast inference algorithm of diffusion networks without infection temporal information.Journal of Frontiers of Computer Science and Technology, 2019, 13(4):541-553(in Chinese with English abstract).[doi:10.3778/j.issn.1673-9418.1807046]
    [10] Amin K, Heidari H, Kearns M.Learning from contagion (without timestamps).In:Proc.of the ICML 2014.2014.1845-1853.http://proceedings.mlr.press/v32/amin14.pdf
    [11] Gripon V, Rabbat M.Reconstructing a graph from path traces.In:Proc.of the ISIT 2013.2013.2488-2492.[doi:10.1109/ISIT.2013.6620674]
    [12] Gomez-Rodriguez M, Balduzzi D, Schölkopf B.Uncovering the temporal dynamics of diffusion networks.In:Proc.of the ICML 2011.2011.561-568.http://icml-2011.org/papers/354_icmlpaper.pdf
    [13] Wang S, Hu X, Yu P, et al.MMRate:Inferring multi-aspect diffusion networks with multi-pattern cascades.In:Proc.of the KDD 2014.2014.1246-1255.[doi:10.1145/2623330.2623728]
    [14] Du N, Song L, Smola A, et al.Learning networks of heterogeneous influence.In:Proc.of NIPS the 2012.2012.2780-2788.http://papers.nips.cc/paper/4582-learning-networks-of-heterogeneous-influence.pdf
    [15] Gomez-Rodriguez M, Leskovec J, Schölkopf B.Structure and dynamics of information pathways in online media.In:Proc.of the WSDM 2013.2013.23-32.[doi:10.1145/2433396.2433402]
    [16] Daneshmand H, Gomez-Rodriguez M, Song L, et al.Estimating diffusion network structures:Recovery conditions, sample complexity&soft-thresholding algorithm.In:Proc.of the ICML 2014.2014.793-801.http://proceedings.mlr.press/v32/daneshmand14.pdf
    [17] Pouget-Abadie J, Horel T.Inferring graphs from cascades:A sparse recovery framework.In:Proc.of the ICML 2015.2015.977-986.[doi:10.1145/2740908.2744107]
    [18] Netrapalli P, Sanghavi S.Learning the graph of epidemic cascades.In:Proc.of the SIGMETRICS 2012.2012.211-222.[doi:10.1145/2318857.2254783]
    [19] Gomez-Rodriguez M, Leskovec J, Krause A.Inferring networks of diffusion and influence.In:Proc.of the KDD 2010.2010.1019-1028.[doi:10.1145/2086737.2086741]
    [20] Gomez-Rodriguez M, Schölkopf B.Submodular inference of diffusion networks from multiple trees.In:Proc.of the ICML 2012.2012.489-496.https://icml.cc/2012/papers/281.pdf
    [21] Kurashima T, Iwata T, Takaya N, et al.Probabilistic latent network visualization:Inferring and embedding diffusion networks.In:Proc.of the KDD 2014.2014.1236-1245.[doi:10.1145/2623330.2623646]
    [22] Bourigault S, Lamprier S, Gallinari P.Representation learning for information diffusion through social networks:An embedded cascade model.In:Proc.of the WSDM 2016.2016.573-582.[doi:10.1145/2835776.2835817]
    [23] Bourigault S, Lagnier C, Lamprier S, et al.Learning social network embeddings for predicting information diffusion.In:Proc.of the WSDM 2014.2014.393-402.[doi:10.1145/2556195.2556216]
    [24] Abrahao B, Chierichetti F, Kleinberg R, et al.Trace complexity of network inference.In:Proc.of the KDD 2013.2013.491-499.[doi:10.1145/2487575.2487664]
    [25] Lokhov A.Reconstructing parameters of spreading models from partial observations.In:Proc.of the NIPS 2016.2016.3467-3475
    [26] Sefer E, Kingsford C.Convex risk minimization to infer networks from probabilistic diffusion data at multiple scales.In:Proc.of the ICDE 2015.2015.663-674.[doi:10.1109/ICDE.2015.7113323]
    [27] Gan T, Han K, Huang H, et al.Diffusion network inference from partial observations.In:Proc.of AAAI 2021.2021.7493-7500.https://ojs.aaai.org/index.php/AAAI/article/view/16918/16725
    [28] Shaghaghian S, Coates M.Bayesian inference of diffusion networks with unknown infection times.In:Proc.of the SSP 2016.2016.[doi:10.1109/SSP.2016.7551716]
    [29] Shaghaghian S, Coates M.Online bayesian inference of diffusion networks.IEEE Trans.on Signal and Information Processing over Networks, 2017, 500-512.[doi:10.1109/TSIPN.2017.2731160]
    [30] Yan Q, Huang H, Gao Y, et al.Group-Level influence maximization with budget constraint.In:Proc.of the DASFAA 2017.LNCS 10177.2017.625-641.[doi:10.1007/978-3-319-55753-3_39]
    [31] Sun Y.Research of diffusion network inference technology based on infection state results[MS.Thesis].Wuhan:Wuhan University, 2019(in Chinese with English abstract).
    [32] De Campos LM.A scoring function for learning Bayesian networks based on mutual information and conditional independence tests.Journal of Machine Learning Research, 2006, 7(7):2149-2187.[doi:10.1007/s10846-006-9082-0]
    [33] Kempe D, Kleinberg J, Tardos É.Maximizing the spread of influence through a social network.In:Proc.of the KDD 2003.2003.137-146.[doi:10.1145/956750.956769]
    [34] Pavan M, Pelillo M.Dominant sets and pairwise clustering.IEEE Trans.on Pattern Analysis and Machine Intelligence, 2007, 29(1):167-172.[doi:10.1109/TPAMI.2007.10]
    [35] Bulò SR, Pelillo M, Bomze IM.Graph-based quadratic optimization:A fast evolutionary approach.Computer Vision and Image Understanding, 2011, 115(7):984-995.[doi:10.1016/j.cviu.2010.12.004]
    [36] Lancichinetti A, Fortunato S, Radicchi F.Benchmark graphs for testing community detection algorithms.Physical Review E, 2008, 78(4).[doi:10.1103/PhysRevE.78.046110]
    [37] Newman MEJ.Finding community structure in networks using the eigenvectors of matrices.Physical Review E, 2006, 74(3):036104.[doi:10.1103/PhysRevE.74.036104]
    附中文参考文献:
    [9] 孙月明,张运加,颜钱,等.无需感染时间信息的传播网络快速推断算法.计算机科学与探索, 2019, 13(4):541-553.[doi:10.3778/j.issn.1673-9418.1807046]
    [31] 孙月明.基于感染状态结果的传播网络推断技术研究[硕士学位论文].武汉:武汉大学, 2019.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

赛影辉,王明鑫,陈畅,雷伯涵,侯叶俏,李翔翔,孙月明,陈旭.基于感染结果的传播网络推断方法.软件学报,2022,33(8):3103-3114

复制
分享
文章指标
  • 点击次数:960
  • 下载次数: 2685
  • HTML阅读次数: 1546
  • 引用次数: 0
历史
  • 收稿日期:2019-09-27
  • 最后修改日期:2020-09-09
  • 在线发布日期: 2021-08-02
  • 出版日期: 2022-08-06
文章二维码
您是第19791708位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号