de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Influence Maximization in Continuous Time Diffusion Networks

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons75510

Gomez Rodriguez,  M
Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons84193

Schölkopf,  B
Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Gomez Rodriguez, M., & Schölkopf, B. (2012). Influence Maximization in Continuous Time Diffusion Networks. In 29th International Conference on Machine Learning (ICML 2012) (pp. 1-8). Madison, WI, USA: International Machine Learning Society.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0013-B6C4-D
Abstract
The problem of finding the optimal set of source nodes in a diffusion network that maximizes the spread of information, influence, and diseases in a limited amount of time depends dramatically on the underlying temporal dynamics of the network. However, this still remains largely unexplored to date. To this end, given a network and its temporal dynamics, we first describe how continuous time Markov chains allow us to analytically compute the average total number of nodes reached by a diffusion process starting in a set of source nodes. We then show that selecting the set of most influential source nodes in the continuous time influence maximization problem is NP-hard and develop an efficient approximation algorithm with provable near-optimal performance. Experiments on synthetic and real diffusion networks show that our algorithm outperforms other state of the art algorithms by at least ~20 and is robust across different network topologies.