Fast (1-1/e-epsilon)-approximation for the infuence maximization problem

Applications of Mathematics, Mathematics of Computation 1 Minute

You need to know: Directed graph, algorithm, approximation algorithm, polynomial-time algorithm, NP-hard problem.

Background: Let G be a directed graph, in which each directed edge w\to v has a weight b_{vw}\in[0,1]. Each vertex v has a threshold \theta_v, and the thresholds \theta_v are chosen independently and uniformly at random from the interval [0,1]. At time 0, we select some set A of vertices at mark them as “active”. At times t=1,2,\dots, vertex v become active if \sum\limits_{w\to v, \, w \text{ active}} b_{vw} \geq \theta_v, and if vertex become active at stays active forever. This process ends if no activations occur from round t to t+1. The influence \sigma(A) of a set A of vertices is the expected number of active nodes at the end of the process. The influence maximization problem asks, given graph G, weights b_{vw}, and parameter k, to find a k-vertex set A with maximal \sigma(A).

The Theorem: On 17th April 2014, David Kempe, Jon Kleinberg, and Éva Tardos submitted to arxiv a paper in which they proved that for any \epsilon>0, there is a polynomial-time algorithm approximating the maximum influence to within a factor of 1-1/e-\epsilon, where e=2.718... is the base of the natural logarithm.

Short context: The influence maximization problem has important practical applications. For example, G may model a social network, the “activation process” is when people start to use some product or service because their friends do, and the influence maximization problem asks which set A of individuals should we initially convince to use it, to maximize the “cascade effect”. The problem is NP-hard to solve exactly, but the Theorem provides an efficient approximation algorithm.

Links: The original paper is available here.

Go to the list of all theorems

Unknown's avatar

Published by Bogdan Grechuk

Published

Leave a comment