We consider a cost model for diffusion in a network that captures both the scope of infection and its propagation time: The edges of the network have associated lengths which model transmission times, and influence scores are higher for faster propagation. We propose an intuitive measure of timed influence, which extends and unifies several classic measures, including the well-studied “binary” influence [Richardson and Domingos 2002; Kempe et al. 2003] (which only measures scope), a recently-studied threshold model of timed influence [Gomez-Rodriguez et al. 2011] (which considers a node influenced only within a fixed time horizon), and closeness centrality (which is extended from being defined for a single node to multiple seed nodes and from a fixed network to distributions). Finally, we provide the first highly scalable algorithms for timed influence computation and maximization. In particular, we improve by orders of magnitude the scalability of state-of-the-art threshold timed influence computation. Moreover, our design provides robust guarantees and is novel also as a theoretical contribution.
['Edith Cohen', 'Daniel Delling', 'Thomas Pajor', 'Renato F. Werneck']
Timed Influence: Computation and Maximization