无需感染时间信息的传播网络快速推断算法
|
摘要
现有的大多数传播网络推断方法需要节点的感染时间信息,但是在许多现实传播过程中,准确的感染时间信息往往是难以获得的。以准确、高效且无需感染时间信息的传播网络推断方法为目标,研究了如何仅利用多次传播过程结束时观测到的各节点的感染状态来推断节点间的影响关系和感染传播概率。为此,该方法首先利用节点感染状态间的互信息来量化它们之间的相互关联,找出可能的节点间影响关系。然后,构建以感染传播概率为变量的节点感染状态观测数据的对数似然函数,并采用期望最大化的方法最大化该对数似然函数并求解感染传播概率。实验结果表明,相较现有方法,该方法有效提高了传播网络推断的准确性,并且大幅缩短了算法运行所需时间。
Most existing approaches to diffusion network inference require the infection temporal information of nodes. But in many real-world diffusion processes, the exact infection temporal information is often unavailable.This paper aims at an effective, efficient and infection temporal information-free approach for diffusion network inference, and studies how to infer the influence relationships and transmission rates between the nodes based on only the final infection statuses of the nodes observed in a number of diffusion processes. To this end, the approach proposed in this paper first utilizes the mutual information of infection statuses among the nodes to quantify the correlation of the infections and reveal the underlying influence relationships between the nodes. Then, the proposed approach constructs the log-likelihood function of the observed infection statuses with transmission rates as the variables, and adopts the expectation-maximization algorithm to maximize the function and approximate the optimal transmission rates. Extensive experimental results demonstrate that compared against the existing approaches, the proposed approach has a reasonably better accuracy performance on diffusion network inference, and significantly reduces runtime.
Most existing approaches to diffusion network inference require the infection temporal information of nodes. But in many real-world diffusion processes, the exact infection temporal information is often unavailable.This paper aims at an effective, efficient and infection temporal information-free approach for diffusion network inference, and studies how to infer the influence relationships and transmission rates between the nodes based on only the final infection statuses of the nodes observed in a number of diffusion processes. To this end, the approach proposed in this paper first utilizes the mutual information of infection statuses among the nodes to quantify the correlation of the infections and reveal the underlying influence relationships between the nodes. Then, the proposed approach constructs the log-likelihood function of the observed infection statuses with transmission rates as the variables, and adopts the expectation-maximization algorithm to maximize the function and approximate the optimal transmission rates. Extensive experimental results demonstrate that compared against the existing approaches, the proposed approach has a reasonably better accuracy performance on diffusion network inference, and significantly reduces runtime.
引文
[1] Gomez-Rodriguez M, Leskovec J, Sch?lkopf B. Modeling information propagation with survival theory[C]//Proceedings of the 30th International Conference on Machine Learning,Atlanta, Jun 17-19, 2013:666-674.
[2] Wallinga J, Teunis P. Different epidemic curves for severe acute respiratory syndrome reveal similar impacts of control measures[J]. American Journal of Epidemiology, 2004, 160(6):509-516.
[3] Gomez-Rodriguez M, Sch?lkopf B. Submodular inference of diffusion networks from multiple trees[C]//Proceedings of the 29th International Conference on Machine Learning,Edinburgh, Jun 26-Jul 1, 2012. Madison:Omnipress, 2012:1587-1594.
[4] Gomez-Rodriguez M, Leskovec J, Krause A. Inferring networks of diffusion and influence[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, Jul 25-28, 2010.New York:ACM, 2010:1019-1028.
[5] Gomez-Rodrigue M, Balduzzi D, Sch?lkopf B. Uncovering the temporal dynamics of diffusion networks[C]//Proceedings of the 28th International Conference on Machine Learning,Bellevue, Jun 28-Jul 2, 2011. Madison:Omnipress, 2011:561-568.
[6] Gomez-Rodrigue M, Leskovec J, Sch?lkopf B. Structure and dynamics of information pathways in online media[C]//Proceedings of the 6th ACM International Conference on Web Search and Data Mining, Rome, Feb 4-8, 2013. New York:ACM, 2013:23-32.
[7] Mehmood Y, Barbieri N, Bonchi F, et al. CSI:communitylevel social influence analysis[C]//LNCS 8189:Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases, Prague, Sep 23-27, 2013.Berlin, Heidelberg:Springer, 2013:48-63.
[8] Amin K, Heidari H, Kearns M. Learning from contagion(without timestamps)[C]//Proceedings of the 31st International Conference on Machine Learning, Beijing, Jun 21-26, 2014:1845-1853.
[9] Kempe D, Kleinberg J, Tardosé. Maximizing the spread of influence through a social network[C]//Proceedings of the9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, Aug 24-27, 2003.New York:ACM, 2003:137-146.
[10] Wang S, Hu X, Yu P S, et al. MMRate:inferring multiaspect diffusion networks with multi-pattern cascades[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, Aug 24-27, 2014. New York:ACM, 2014:1246-1255.
[11] Du N, Song L, Smola A, et al. Learning networks of heterogeneous influence[C]//Proceedings of the 25th International Conference on Neural Information Processing Systems,Lake Tahoe, Dec 3-6, 2012. Red Hook:Curran Associates Inc, 2012:2780-2788.
[12] Daneshmand H, Gomez-Rodriguez M, Song L, et al. Estimating diffusion network structures:recovery conditions,sample complexity&soft-thresholding algorithm[C]//Proceedings of the 31st International Conference on Machine Learning, Beijing, Jun 21-26, 2014:793-801.
[13] Pouget-Abadie J, Horel T. Inferring graphs from cascades:a sparse recovery framework[C]//Proceedings of the 32nd International Conference on Machine Learning, Lille, Jul 7-9, 2015:977-986.
[14] Netrapalli P, Sanghavi S. Learning the graph of epidemic cascades[C]//Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems, London, Jun11-15, 2012. New York:ACM, 2012:211-222.
[15] 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, New York, Aug 24-27, 2014. New York:ACM,2014:1236-1245.
[16] Bourigault S, Lamprier S, Gallinari P. Representation learning for information diffusion through social networks:an embedded cascade model[C]//Proceedings of the 9th ACM International Conference on Web Search and Data Mining,San Francisco, Feb 22-25, 2016. New York:ACM, 2016:573-582.
[17] Gao S, Pang H C, Gallinari P, et al. A novel embedding method for information diffusion prediction in social network big data[J]. IEEE Transactions on Industrial Informatics, 2017,13(4):2097-2105.
[18] 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, New York, Feb 24-28,2014. New York:ACM, 2014:393-402.
[19] Abrahao B, Chierichetti F, Kleinberg R, et al. Trace complexity of network inference[C]//Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Chicago, Aug 11-14, 2013. New York:ACM, 2013:491-499.
[20] Lokhov A Y. Reconstructing parameters of spreading models from partial observations[C]//Proceedings of the 30th International Conference on Neural Information Processing Systems, Barcelona, Dec 5-10, 2016. Red Hook:Curran Associates Inc, 2016:3467-3475.
[21] Gripon V, Rabbat M. Reconstructing a graph from path traces[C]//Proceedings of the 2013 IEEE International Symposium on Information Theory, Istanbul, Jul 7-12, 2013.Piscataway:IEEE, 2013:2488-2492.
[22] Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E, 2008, 78(4):046110.
[2] Wallinga J, Teunis P. Different epidemic curves for severe acute respiratory syndrome reveal similar impacts of control measures[J]. American Journal of Epidemiology, 2004, 160(6):509-516.
[3] Gomez-Rodriguez M, Sch?lkopf B. Submodular inference of diffusion networks from multiple trees[C]//Proceedings of the 29th International Conference on Machine Learning,Edinburgh, Jun 26-Jul 1, 2012. Madison:Omnipress, 2012:1587-1594.
[4] Gomez-Rodriguez M, Leskovec J, Krause A. Inferring networks of diffusion and influence[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, Jul 25-28, 2010.New York:ACM, 2010:1019-1028.
[5] Gomez-Rodrigue M, Balduzzi D, Sch?lkopf B. Uncovering the temporal dynamics of diffusion networks[C]//Proceedings of the 28th International Conference on Machine Learning,Bellevue, Jun 28-Jul 2, 2011. Madison:Omnipress, 2011:561-568.
[6] Gomez-Rodrigue M, Leskovec J, Sch?lkopf B. Structure and dynamics of information pathways in online media[C]//Proceedings of the 6th ACM International Conference on Web Search and Data Mining, Rome, Feb 4-8, 2013. New York:ACM, 2013:23-32.
[7] Mehmood Y, Barbieri N, Bonchi F, et al. CSI:communitylevel social influence analysis[C]//LNCS 8189:Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases, Prague, Sep 23-27, 2013.Berlin, Heidelberg:Springer, 2013:48-63.
[8] Amin K, Heidari H, Kearns M. Learning from contagion(without timestamps)[C]//Proceedings of the 31st International Conference on Machine Learning, Beijing, Jun 21-26, 2014:1845-1853.
[9] Kempe D, Kleinberg J, Tardosé. Maximizing the spread of influence through a social network[C]//Proceedings of the9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, Aug 24-27, 2003.New York:ACM, 2003:137-146.
[10] Wang S, Hu X, Yu P S, et al. MMRate:inferring multiaspect diffusion networks with multi-pattern cascades[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, Aug 24-27, 2014. New York:ACM, 2014:1246-1255.
[11] Du N, Song L, Smola A, et al. Learning networks of heterogeneous influence[C]//Proceedings of the 25th International Conference on Neural Information Processing Systems,Lake Tahoe, Dec 3-6, 2012. Red Hook:Curran Associates Inc, 2012:2780-2788.
[12] Daneshmand H, Gomez-Rodriguez M, Song L, et al. Estimating diffusion network structures:recovery conditions,sample complexity&soft-thresholding algorithm[C]//Proceedings of the 31st International Conference on Machine Learning, Beijing, Jun 21-26, 2014:793-801.
[13] Pouget-Abadie J, Horel T. Inferring graphs from cascades:a sparse recovery framework[C]//Proceedings of the 32nd International Conference on Machine Learning, Lille, Jul 7-9, 2015:977-986.
[14] Netrapalli P, Sanghavi S. Learning the graph of epidemic cascades[C]//Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems, London, Jun11-15, 2012. New York:ACM, 2012:211-222.
[15] 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, New York, Aug 24-27, 2014. New York:ACM,2014:1236-1245.
[16] Bourigault S, Lamprier S, Gallinari P. Representation learning for information diffusion through social networks:an embedded cascade model[C]//Proceedings of the 9th ACM International Conference on Web Search and Data Mining,San Francisco, Feb 22-25, 2016. New York:ACM, 2016:573-582.
[17] Gao S, Pang H C, Gallinari P, et al. A novel embedding method for information diffusion prediction in social network big data[J]. IEEE Transactions on Industrial Informatics, 2017,13(4):2097-2105.
[18] 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, New York, Feb 24-28,2014. New York:ACM, 2014:393-402.
[19] Abrahao B, Chierichetti F, Kleinberg R, et al. Trace complexity of network inference[C]//Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Chicago, Aug 11-14, 2013. New York:ACM, 2013:491-499.
[20] Lokhov A Y. Reconstructing parameters of spreading models from partial observations[C]//Proceedings of the 30th International Conference on Neural Information Processing Systems, Barcelona, Dec 5-10, 2016. Red Hook:Curran Associates Inc, 2016:3467-3475.
[21] Gripon V, Rabbat M. Reconstructing a graph from path traces[C]//Proceedings of the 2013 IEEE International Symposium on Information Theory, Istanbul, Jul 7-12, 2013.Piscataway:IEEE, 2013:2488-2492.
[22] Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E, 2008, 78(4):046110.