Back to the Past: Source Identification in Diffusion Networks from Partially Observed Cascades

Mehrdad Farajtabar, Manuel Gomez Rodriguez, Mohammad Zamani, Nan Du, Hongyuan Zha, Le Song
Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, PMLR 38:232-240, 2015.

Abstract

When a piece of malicious information becomes rampant in an information diffusion network, can we identify the source node that originally introduced the piece into the network and infer the time when it initiated this? Being able to do so is critical for curtailing the spread of malicious information, and reducing the potential losses incurred. This is a very challenging problem since typically only incomplete traces are observed and we need to unroll the incomplete traces into the past in order to pinpoint the source. In this paper, we tackle this problem by developing a two-stage framework, which first learns a continuous-time diffusion network based on historical diffusion traces and then identifies the source of an incomplete diffusion trace by maximizing the likelihood of the trace under the learned model. Experiments on both large synthetic and real-world data show that our framework can effectively go back to the past, and pinpoint the source node and its initiation time significantly more accurately than previous state-of-the-arts.

Cite this Paper


BibTeX
@InProceedings{pmlr-v38-farajtabar15, title = {{Back to the Past: Source Identification in Diffusion Networks from Partially Observed Cascades}}, author = {Mehrdad Farajtabar and Manuel Gomez Rodriguez and Mohammad Zamani and Nan Du and Hongyuan Zha and Le Song}, booktitle = {Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics}, pages = {232--240}, year = {2015}, editor = {Guy Lebanon and S. V. N. Vishwanathan}, volume = {38}, series = {Proceedings of Machine Learning Research}, address = {San Diego, California, USA}, month = {09--12 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v38/farajtabar15.pdf}, url = { http://proceedings.mlr.press/v38/farajtabar15.html }, abstract = {When a piece of malicious information becomes rampant in an information diffusion network, can we identify the source node that originally introduced the piece into the network and infer the time when it initiated this? Being able to do so is critical for curtailing the spread of malicious information, and reducing the potential losses incurred. This is a very challenging problem since typically only incomplete traces are observed and we need to unroll the incomplete traces into the past in order to pinpoint the source. In this paper, we tackle this problem by developing a two-stage framework, which first learns a continuous-time diffusion network based on historical diffusion traces and then identifies the source of an incomplete diffusion trace by maximizing the likelihood of the trace under the learned model. Experiments on both large synthetic and real-world data show that our framework can effectively go back to the past, and pinpoint the source node and its initiation time significantly more accurately than previous state-of-the-arts.} }
Endnote
%0 Conference Paper %T Back to the Past: Source Identification in Diffusion Networks from Partially Observed Cascades %A Mehrdad Farajtabar %A Manuel Gomez Rodriguez %A Mohammad Zamani %A Nan Du %A Hongyuan Zha %A Le Song %B Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2015 %E Guy Lebanon %E S. V. N. Vishwanathan %F pmlr-v38-farajtabar15 %I PMLR %P 232--240 %U http://proceedings.mlr.press/v38/farajtabar15.html %V 38 %X When a piece of malicious information becomes rampant in an information diffusion network, can we identify the source node that originally introduced the piece into the network and infer the time when it initiated this? Being able to do so is critical for curtailing the spread of malicious information, and reducing the potential losses incurred. This is a very challenging problem since typically only incomplete traces are observed and we need to unroll the incomplete traces into the past in order to pinpoint the source. In this paper, we tackle this problem by developing a two-stage framework, which first learns a continuous-time diffusion network based on historical diffusion traces and then identifies the source of an incomplete diffusion trace by maximizing the likelihood of the trace under the learned model. Experiments on both large synthetic and real-world data show that our framework can effectively go back to the past, and pinpoint the source node and its initiation time significantly more accurately than previous state-of-the-arts.
RIS
TY - CPAPER TI - Back to the Past: Source Identification in Diffusion Networks from Partially Observed Cascades AU - Mehrdad Farajtabar AU - Manuel Gomez Rodriguez AU - Mohammad Zamani AU - Nan Du AU - Hongyuan Zha AU - Le Song BT - Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics DA - 2015/02/21 ED - Guy Lebanon ED - S. V. N. Vishwanathan ID - pmlr-v38-farajtabar15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 38 SP - 232 EP - 240 L1 - http://proceedings.mlr.press/v38/farajtabar15.pdf UR - http://proceedings.mlr.press/v38/farajtabar15.html AB - When a piece of malicious information becomes rampant in an information diffusion network, can we identify the source node that originally introduced the piece into the network and infer the time when it initiated this? Being able to do so is critical for curtailing the spread of malicious information, and reducing the potential losses incurred. This is a very challenging problem since typically only incomplete traces are observed and we need to unroll the incomplete traces into the past in order to pinpoint the source. In this paper, we tackle this problem by developing a two-stage framework, which first learns a continuous-time diffusion network based on historical diffusion traces and then identifies the source of an incomplete diffusion trace by maximizing the likelihood of the trace under the learned model. Experiments on both large synthetic and real-world data show that our framework can effectively go back to the past, and pinpoint the source node and its initiation time significantly more accurately than previous state-of-the-arts. ER -
APA
Farajtabar, M., Gomez Rodriguez, M., Zamani, M., Du, N., Zha, H. & Song, L.. (2015). Back to the Past: Source Identification in Diffusion Networks from Partially Observed Cascades. Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 38:232-240 Available from http://proceedings.mlr.press/v38/farajtabar15.html .

Related Material