Adaptive Influence Maximization on Hypergraph Topologies

Influence maximization (IM) is a fundamental problem in computer and network science, with a plethora of applications. In this problem, you have to select a set of seeds to start an information diffusion campaign in order to maximize the number of influenced agents. In this paper, we consider the adaptive version of the problem where the campaign can be organized in several rounds and at the beginning of each round a different set of seeds can be selected, depending on the results of the previous rounds. The IM problem has been generally studied on networks, represented by graphs, where there are only binary relations among the nodes. However, real-world scenarios often involve more complex, multiway relationships, which can be better represented by hypergraphs rather than graphs. In this paper, we address these limitations by introducing the Adaptive Influence Maximization problem on Hypergraphs (AdaptHIM) which, to the best of our knowledge, has not been studied before. In particular, we introduce a formal framework to generalize it, and we propose a novel approach, based on the Elephant Herding Optimization algorithm, to address it, which we call AdaptEHO. This approach adaptively selects seeds by leveraging observed influence spread from prior rounds, and aims to balance exploration and exploitation. Through a comprehensive experimental campaign on real-world hypergraph datasets, we demonstrate that AdaptEHO outperforms baseline methods in influence spread while maintaining computational efficiency, thus resulting in a suitable trade-off for different scenarios of application.