BOPIM: Bayesian Optimization for influence maximization on temporal networks

Researcher Eric Yanchenko has introduced BOPIM (Bayesian Optimization for Influence Maximization), a novel algorithm designed to solve the complex problem of influence maximization on temporal networks. The core challenge is selecting a small set of 'seed' nodes that will maximize the spread of information or influence through a network over time. Traditional methods for this combinatorial optimization problem are computationally expensive. BOPIM frames it as a Bayesian Optimization (BO) task, which is well-suited for expensive, black-box objective functions.

BOPIM overcomes two key challenges: constructing a kernel function for the Gaussian Process model and designing an effective acquisition function. The research proposes two kernels—one based on Hamming distance between seed sets and another using the Jaccard coefficient between nodes' neighbors. Surprisingly, the simpler Hamming kernel performed better in most tests. For optimization, BOPIM uses an Expected Improvement acquisition function, adjusted for noise and optimized with a greedy algorithm.

In numerical experiments on real-world networks, BOPIM proved its practical value. It matched the influence spread accuracy of a gold-standard greedy algorithm while being up to ten times faster, a significant efficiency gain. Furthermore, the paper presents a pioneering contribution: BOPIM provides a way to quantify uncertainty in the identified optimal seed sets, offering users insight into the confidence of the solution. This is the first method to address uncertainty quantification in this domain.