Optima Network Science Seminar
Faculty Advisor: My T. Thai
Coordinator: Thang N. Dinh
Time and place: 1:50pm Wed, E520A CSE Building
Note:
If you are
interested in participating in the activities of the seminar and/or wish to
receive emails about
upcoming events please send an email to tdinh@cise.ufl.edu.
by Thang Dinh on Mar 27, 2013
Diffusion is a fundamental graph process, underpinning such phenomena as epidemic disease contagion and the spread of innovation by word-of-mouth. We address the algorithmic problem of finding a set of k initial seed nodes in a network so that the expected size of the resulting cascade is maximized, under the standard independent cascade model of network diffusion. Our main result is an algorithm for the influence maximization problem that obtains the near-optimal approximation factor of (1 - 1/e - epsilon), for any epsilon > 0, in time O((m+n)log(n) / epsilon^3) where n and m are the number of vertices and edges in the network. Our algorithm is nearly runtime-optimal (up to a logarithmic factor) as we establish a lower bound of Omega(m+n) on the runtime required to obtain a constant approximation. Our method also allows a provable tradeoff between solution quality and runtime: we obtain an O(1/beta)-approximation in time O(n log^3(n) * a(G) / beta) for any beta > 1, where a(G) denotes the arboricity of the diffusion network G. Our approach is based on a novel preprocessing scheme that generates a sparse hypergraph representation of the underlying network via sampling.
Influence Maximization in Social Networks: Towards an Optimal Algorithmic Solution
Christian Borgs, Michael Brautbar, Jennifer Chayes, Brendan Lucier,[PDF]
AbstractDiffusion is a fundamental graph process, underpinning such phenomena as epidemic disease contagion and the spread of innovation by word-of-mouth. We address the algorithmic problem of finding a set of k initial seed nodes in a network so that the expected size of the resulting cascade is maximized, under the standard independent cascade model of network diffusion. Our main result is an algorithm for the influence maximization problem that obtains the near-optimal approximation factor of (1 - 1/e - epsilon), for any epsilon > 0, in time O((m+n)log(n) / epsilon^3) where n and m are the number of vertices and edges in the network. Our algorithm is nearly runtime-optimal (up to a logarithmic factor) as we establish a lower bound of Omega(m+n) on the runtime required to obtain a constant approximation. Our method also allows a provable tradeoff between solution quality and runtime: we obtain an O(1/beta)-approximation in time O(n log^3(n) * a(G) / beta) for any beta > 1, where a(G) denotes the arboricity of the diffusion network G. Our approach is based on a novel preprocessing scheme that generates a sparse hypergraph representation of the underlying network via sampling.