Introduction

The advent of social media and viral marketing has highlighted the critical need to understand how information, behaviors, and innovations propagate through networks. Central to this exploration is the influence maximization (IM) problem, a key concept in network theory, where the objective is to identify a group of key individuals in a network whose combined influence is maximized [1,2]. This problem has attracted substantial attention in different areas, and its implications are broad, impacting various applications, including opinion formation, combating misinformation, link recommendations, and even influencing election outcomes on social networks [3,4,5,6,7]. The primary goal is to identify the smallest set of nodes (or seeds) in a graph that can maximize the spread of information under specific propagation models. Traditionally, the IM problem has been studied within the context of standard networks with dyadic relationships [2,8], with the seminal work in [1] establishing hardness results and introducing an algorithm with a (1 − 1/𝑒) approximation guarantee under the independent cascade (IC) and linear threshold (LT) diffusion models. Over time, a variety of approaches tackling the IM problem have been developed [9,10,11,12]. However, recent advancements in hypernetwork science, a field that explores higher-order interactions within complex systems [13], have introduced new opportunities. Hypergraphs, the primary modeling tool in this field, extend traditional graph theory by enabling edges (which we now call hyperedges) to connect multiple vertices simultaneously, offering a richer representation of real-world phenomena. While the IM problem has been extensively studied in ordinary networks, its adaptation to hypergraphs remains a relatively nascent area of research. Early efforts focused on transforming hypergraphs into simpler structures, such as bipartite graphs, to leverage existing algorithms [14]. However, this approach often loses critical information encoded in the higherorder structure of hypergraphs. The computational challenges of IM in hypergraphs were rigorously explored in [15], which demonstrated the problem's NP-hardness and proposed an approximation framework with a (1 − 1/𝑒 − 𝜖) guarantee. Building on this foundation, recent studies have developed specialized algorithms tailored to specific diffusion models. For instance, [16] introduced heuristics under the LT diffusion model, while [17] proposed a ranking-based approach for the HyperCascade model. Algorithms like HADP [18] and MEI [19] have sought to minimize overlap between seeds to enhance influence spread, though both rely on transforming hypergraphs into simpler graph representations. Direct approaches to IM on hypergraphs have also gained traction. Similarly, [20] modeled hypergraphs as electrostatic fields, introducing a novel perspective for assessing node influence. Other contributions, such as [21], extended message-passing techniques from ordinary networks to hypergraphs, focusing on collective influence within hyperedges. Research on weighted hypergraphs, as in [22], has introduced adaptive dissemination models to better capture real-world dynamics. Despite these advancements, many existing methods either specialize in a single diffusion process or require structural transformations that limit their generality.

Furthermore, it is worth noting that, to the best of our knowledge, several aspects remain understudied in this context. First, traditional types of IM algorithms have yet to be thoroughly explored for hypergraph topologies. Generally, classical IM approaches are categorized into four main types: (i) simulation-based, (ii) proxy-based, (iii) sketch-based, and (iv) intelligent optimization-based approaches. The first category includes algorithms that utilize techniques such as Monte Carlo simulations to model information propagation across individual nodes. A notable example is the algorithm proposed in [1], which has also been extended to hypergraph topologies. The second category adopts proxy models to approximate the influence spread of a given seed set, thereby avoiding potentially time-consuming simulations. Several algorithms in this category, such as those proposed in [18,19], have been adapted for hypergraph topologies. The third category encompasses algorithms that evaluate influence spread by computing sketches based on the given graph and a specific diffusion model. While some classical approaches, such as reverse influence sampling, have been explored in the literature [18], their application to and formalization for hypergraph topologies remains an ongoing area of research. Finally, the fourth category involves the use of intelligent optimization algorithms, such as metaheuristic methods, to address the IM problem. Although a plethora of such approaches have been proposed in the classical setting, relatively few have been developed specifically for hypergraph topologies [23].

In this discussion paper, we illustrate an ongoing work focusing on the design and development of two families of approaches for tackling the IM problem on hypergraphs. These include node propertiesbased algorithms and metaheuristics-based algorithms. The former involves an algorithm that selects seed nodes by considering different centrality values, some of them also based on cooperative game theory. The latter consists of two metaheuristics algorithms based on hill climbing and evolutionary strategy, respectively. Also, we highlight an initial experimental evaluation, in which these algorithms are used, and we conclude by discussing several research directions that, in our opinion, are worth to be studied in the future.

The outline of the paper is as follows. In Section 2, we provide the background definitions and the problem statement. In Section 3, we discuss the two families of algorithms, and we briefly highlight an initial experimental evaluation assessing their performance. Finally, in Section 4, we draw our conclusion and discuss a series of future directions regarding this context.

Problem Statement

A hypergraph 𝐻 = (𝑉, 𝐸) is a pair consisting of a set 𝑉 = {𝑣 1 , . . . , 𝑣 𝑛 } of elements called nodes, and a family of sets 𝐸 = (𝑒 1 , . . . , 𝑒 𝑚 ) called hyperedges. A hyperedge represents a relation among a subset of vertices in 𝑉 , i.e., 𝑒 𝑗 ⊆ 𝑉 , for all 𝑗 = 1, . . . , 𝑚. The order of a hypergraph is its number of nodes, i.e., 𝑛 = |𝑉 |, while the size of a hypergraph is 𝑚 = |𝐸|. A node 𝑣 𝑖 ∈ 𝑉 belongs to a hyperedge 𝑒 𝑗 ∈ 𝐸 if 𝑣 𝑗 ∈ 𝑒 𝑗 . The degree of a node 𝑣 𝑖 is the number 𝑑(𝑣 𝑖 ) of neighbors of 𝑣 𝑖 ; a node 𝑣 𝑙 ∈ 𝑉 is the neighbor of node 𝑣 𝑖 iff there exists at least one hyperedge 𝑒 𝑗 which 𝑣 𝑙 and 𝑣 𝑖 both belong to. The hyperdegree of a node 𝑣 𝑖 is the number 𝑑 𝐻 (𝑣 𝑖 ) of hyperedges to which 𝑣 𝑖 belongs. The line graph 𝐿(𝐻) of 𝐻 is the graph on node set 𝐸 ′ = {𝑒 ′ 1 , . . . , 𝑒 ′ 𝑚 } and edge set 𝑉 ′ = {{𝑒 ′ 𝑖 , 𝑒 ′ 𝑗 } : 𝑒 𝑖 ∩ 𝑒 𝑗 ̸ = ∅ for 𝑖 ̸ = 𝑗} [24]. In other words, 𝐿(𝐻) is the graph where nodes represent the hyperedges, and there is an edge between two nodes if the two hyperedges share at least one common node in 𝐻. Furthermore, given a set 𝑉 of nodes and a function 𝜈 : 2 𝑉 → R, that assigns a measure of importance to each subset of nodes, the Shapley value of 𝑣 ∈ 𝑉 [25] with respect to 𝜈 is defined as the average of the marginal contribution of 𝑣 to the subsets at which she belongs, i.e., how much she increases the importance of these groups. The Shapley value can be efficiently computed for the following specific choices of 𝜈 [26], namely: (i) 𝜈 𝑑𝑒𝑔 (𝑆), that measures the importance of a subset 𝑆 of nodes as its size and the number of neighbors; (ii) 𝜈 𝑐𝑙𝑜𝑠𝑒 (𝑆), that measures the importance of a subset 𝑆 of nodes as the inverse of the minimum distance between nodes outside 𝑆 from nodes in 𝑆. Given a hypergraph 𝐻 = (𝑉, 𝐸), a value 𝑘 ∈ Z >0 , and a diffusion process model on hypergraph 𝜎 𝐻 , the Influence Maximization (IM) problem on hypergraphs consists in finding a subset 𝑆 * ⊆ 𝑉 of 𝑘 nodes, called seed node set, such that the expected number of infected nodes is maximized. Formally, 𝑆 * = arg max 𝑆⊆𝑉,|𝑆|=𝑘 𝜎 𝐻 (𝑆), where 𝜎 𝐻 (𝑆) indicates the expected influence (i.e., the number of reached nodes) of the seed node set 𝑆 at the end of the process. In line with the literature [18,19], we use the Susceptible-Infected (SI) model with Contact Process (CP) dynamics on hypergraphs (SICP [18]). In this model, a node can be either in a susceptible (S) or infected (I) state. An S-state node can be infected by each of its neighbors in the I-state with a given infection rate 𝛽. The model works as follows: (i) nodes in the seed set are set to be infected (I-state), and the remaining nodes are susceptible (S-state); (ii) at each time step 𝑡, we find the I-state nodes. For each I-state node 𝑣 𝑖 , we find all hyperedges 𝐸 𝑖 containing the node 𝑣 𝑖 . Then, a hyperedge 𝑒 𝑗 is chosen from 𝐸 𝑖 uniformly at random. Then, each of the S-state nodes in 𝑒 𝑗 will be infected by 𝑣 𝑖 with probability 𝛽; (iii) the process terminates after 𝑇 steps, and we set 𝜎 𝐻 (𝑆) to be the number of nodes in I-state.

Algorithms and Results

We discuss two families of algorithms to tackle the IM problem on hypergraphs. The first one consists of an algorithm called SmartPROPS. It leverages node centrality to construct an optimal seed set, based on a node property function 𝜑 : 𝑉 → R and a threshold function 𝜌 : 𝑉 → R. The idea behind the algorithm is to use 𝜑 to sort nodes, and then iteratively select the most important one based on 𝜌, which ensures that nodes with a considerable number of overlapping hyperedges are discarded. We propose four different variants of SmartPROPS, namely: (i) SmartDEG, in which the seeds coincide with the top-𝑘 highest degree nodes [2], and 𝜑 is the degree centrality; (ii) SmartHYPERDEG, similar as the previous one, it exploits the hyperdegree of each node; (iii) SmartSHAPDEG, the Shapley Degree value, computed on 𝐿(𝐻), is used as the node property; (iv) SmartSHAPCLOSE, here the Shapley Closeness is used as the node property instead. The second family of algorithms is metaheuristics-based, and includes two algorithms, HC and ES. The former is based on a random-restart steepest ascent hill climbing approach. It is a simple yet powerful and versatile metaheuristic optimization algorithm that iteratively seeks to improve a solution with respect to a given measure of quality; it has been used extensively in disparate contexts [27,28,29]. The algorithm begins by randomly selecting an initial solution and iteratively improves it by generating neighbor solutions, via a perturbation function, and upgrading it accordingly to the calculated expected influence. Eventually, a global best solution is obtained when no further improvements are possible. Four variants can be defined: HC 1 , where a node from 𝑅 is replaced with one of its neighbors chosen randomly from the largest hyperedge containing the former; HC 2 , similarly as HC 1 but the node to be replaced is the one with the smaller degree value; HC 3 and HC 4 replace the node having respectively the smallest Shapley Degree value and the smallest Shapley Closeness value. Instead, ES draws inspiration from a population-based metaheuristic inspired by the principles of biological evolution, called evolution strategy [30], and it is based in particular on a variant called (𝜇 + 𝜆) [31], where 𝜇 is the number of candidate solutions in the parent generation, and 𝜆 is the number of candidate solutions obtained from the parent generation. The algorithm iterates for a given number of generations. At each generation, the best 𝜇 solutions are kept from the 𝜆 candidates and their parents. At the start, ES initializes a population of 𝜇 individuals, chosen uniformly at random. In each generation, the algorithms iterates over 𝜆 to generate the same amounts of new solutions via a mutation operator. This operator implements the same variations proposed for the HC algorithm, leading to the ES 1 , ES 2 , ES 3 , and ES 4 variants. We now highlight some preliminary results of the proposed algorithms on eight real-world hypergraphs used as benchmarks in the literature [18,19]. Different baselines are considered, namely, Degree, Greedy, HADP [18], and Adeff [19] 1 . The first is a common baseline based on selecting the top-𝑘 nodes with the maximal degree. The second one is drawn by the approach in [1], and selects the node with maximal influence in each iteration. The last two are recently proposed algorithms for the problem. For the discussed algorithms, we set parameters as follows: for HC, we set the number of restarts to 25, while for ES, we set 𝜇 = 4, 𝜆 = 10, and the maximum number of generations to 25. The obtained influence spread curve is presented in Figure 1, averaged over 100 runs. For variants, we only show HC 1 and ES 1 . The 𝑥-axis refers to the value of 𝑘, while the 𝑦-axis reports the average expected influence 𝜎 𝐻 (𝑆). Inside each plot, a smaller one reports the obtained value at 𝑘 = 25. We can see how the metaheuristics-based algorithms generally perform better than the remaining ones. Also, they achieve the largest expected influence when 𝑘 = 1. Except for some cases where the Greedy reaches similar values, no other algorithms perform in the same manner. As far as 𝑘 = 25 is concerned, we observe almost identical behavior to the previous one. Here, HC 1 and ES 1 perform effectively, together with the Greedy one.

Conclusion and Future Directions

This discussion paper explores the Influence Maximization (IM) problem within hypergraph topologies, an area that remains largely understudied despite its significant potential for capturing higher-order interactions in complex systems. In this paper, we critically discuss two families of algorithms, namely, (i) node properties-based, (ii) and metaheuristics-based ones, designed to address the challenges of the IM problem on hypergraph topologies. The first family involves an algorithm that leverages hypergraphspecific features, such as Shapley-based centrality measures, to select the seed set, while the second one includes metaheuristics algorithms, and in particular hill climbing and evolutionary strategies, to tackle the problem. Our initial analysis, supported by experimental observations, provides insight into the potential of these approaches while highlighting areas where further refinement is needed.

As this is an ongoing effort, several directions for future research emerge. First, we aim to deepen our understanding of the problem by performing a comprehensive evaluation across diverse hypergraph structures and diffusion models. This includes investigating settings with different conditions, such as hypergraphs evolving over time, and hypergraphs presenting weights and other dynamic features.

Second, a critical area of future work lies in designing scalable algorithms suitable for large-scale hypergraphs. Indeed, such algorithms could require exploring parallelization techniques and designing more efficient heuristics. Furthermore, incorporating adaptive mechanisms to optimize parameter selection dynamically could improve algorithmic robustness and applicability. Third, an understudied aspect is investigating practical applications of the IM problem in domains such as social influence campaigns, biological networks, and knowledge graph propagation. Bridging the gap between theoretical discussions and real-world deployment is essential for demonstrating the utility of hypergraph-based IM approaches. Finally, future work could also explore the integration of these algorithms with machine learning models to predict influence spread, potentially combining traditional IM techniques with data-driven approaches.