=Paper=
{{Paper
|id=Vol-3915/paper-3
|storemode=property
|title=Heuristics Approaches for the Influence Maximization Problem on Hypergraphs (Short paper)
|pdfUrl=https://ceur-ws.org/Vol-3915/Paper-3.pdf
|volume=Vol-3915
|authors=Vincenzo Auletta,Francesco Cauteruccio,Diodato Ferraioli
|dblpUrl=https://dblp.org/rec/conf/aiia/AulettaCF24
}}
==Heuristics Approaches for the Influence Maximization Problem on Hypergraphs (Short paper)==
https://ceur-ws.org/Vol-3915/Paper-3.pdf
Heuristics Approaches for the Influence Maximization
Problem on Hypergraphs
(Discussion Paper)
Vincenzo Auletta1 , Francesco Cauteruccio1,* and Diodato Ferraioli1
1
Department of Information Engineering, Electrical Engineering and Applied Mathematics (DIEM), University of Salerno, I84084,
Fisciano, Italy
Abstract
While the Influence Maximization (IM) problem has been extensively studied in graph topologies, with numerous
algorithms and heuristics proposed, there has been relatively little focus on exploring this problem in the context
of hypergraphs, which, despite being more complex, offer greater expressiveness. In this paper, we consider the
current IM scenario considering hypergraph topologies, and we discuss two families of algorithms for the IM
problem. The first family uses node importance measures that are specifically defined for hypergraphs, leveraging
both topological characteristics and concepts from cooperative game theory. The second family addresses the
problem through two well-known metaheuristic approaches, namely, hill climbing and evolution strategy. An
initial experimental evaluation demonstrates that these approaches frequently outperform the leading algorithms
currently proposed in the literature.
Keywords
Influence Maximization, Hypergraphs, Shapley Value, Hill Climbing, Evolution Strategies
1. 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 higher-
order structure of hypergraphs. The computational challenges of IM in hypergraphs were rigorously
AIxIA 2024 Discussion Papers - 23rd International Conference of the Italian Association for Artificial Intelligence, Bolzano, Italy,
November 25β28, 2024
*
Corresponding author.
$ auletta@unisa.it (V. Auletta); fcauteruccio@unisa.it (F. Cauteruccio); dferraioli@unisa.it (D. Ferraioli)
0000-0002-7875-3366 (V. Auletta); 0000-0001-8400-1083 (F. Cauteruccio); 0000-0002-7962-5200 (D. Ferraioli)
Β© 2025 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
ceur-ws.org
Workshop ISSN 1613-0073
Proceedings
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 under-
studied 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 applica-
tion 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 properties-
based 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.
2. 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.
3. 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: HC1 , where a node
from π
is replaced with one of its neighbors chosen randomly from the largest hyperedge containing
the former; HC2 , similarly as HC1 but the node to be replaced is the one with the smaller degree value;
HC3 and HC4 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.
Algebra Bars-Rev Geometry Music-Rev
800 450 1000
200 400 800
700
150 350 600
H(S)
600 300
100 400
250 950
50 200 750 425 200
500 900
200 400
150 700 375 850
0 150 0
1 5 10 15 20 25 1 5 10 15 20 25 1 5 10 15 20 25 1 5 10 15 20 25
NDC Rest.-Rev iAF1260b iJO1366
100 100
300 150
80 250 80 125
200 60 100
60
H(S)
150 75
40 40
100 100 300
50 150
20 20 80 25
50 50 250 60 100
0 0 0 0
1 5 10 15 20 25 1 5 10 15 20 25 1 5 10 15 20 25 1 5 10 15 20 25
k k k k
Degree Adeff SmartDEG SmartSHAPDEG HC1
HADP Greedy SmartHYPERDEG SmartSHAPCLOSE ES1
Figure 1: Expected influence ππ» (π) obtained with different values of π (from 1 to 25), averaged over
100 runs, and with the SICP parameters being π½ = 0.01 and π = 25.
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 ES1 , ES2 , ES3 , and ES4 variants.
We now highlight some preliminary results of the proposed algorithms on eight real-world hyper-
graphs 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 HC1
and ES1 . 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, HC1 and ES1 perform effectively, together with the
Greedy one.
4. 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 hypergraph-
specific 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.
1
All algorithms have been implemented in Python 3.10
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 cam-
paigns, 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.
Acknowledgments
This work is supported by the PNRR project FAIRβFuture AI Research (PE00000013) under the NRRP
MUR program funded by NextGenerationEU.
References
[1] D. Kempe, J. Kleinberg, E. Tardos, Maximizing the spread of influence through a social network,
in: Proc. of the of the ninth ACM SIGKDD international conference on Knowledge discovery and
data mining (KDD), 2003, pp. 137β146. ACM.
[2] S. Banerjee, M. Jenamani, D. K. Pratihar, A survey on influence maximization in a social network,
Knowledge and Information Systems 62 (2020) 3417β3455. Springer.
[3] V. Auletta, D. Ferraioli, G. Greco, On the complexity of reasoning about opinion diffusion under
majority dynamics, Artificial Intelligence 284 (2020) 103288. Elsevier.
[4] M. Castiglioni, D. Ferraioli, N. Gatti, G. Landriani, Election manipulation on social networks:
Seeding, edge removal, edge addition, Journal of Artificial Intelligence Research 71 (2021) 1049β
1090. AI Access Foundation.
[5] G. Bonifazi, F. Cauteruccio, E. Corradini, M. Marchetti, A. Pierini, G. Terracina, D. Ursino, L. Virgili,
An approach to detect backbones of information diffusers among different communities of a social
platform, Data & Knowledge Engineering 140 (2022) 102048. Elsevier.
[6] W. Chen, C. Wang, Y. Wang, Scalable influence maximization for prevalent viral marketing
in large-scale social networks, in: Proc. of the ACM International Conference on Knowledge
Discovery and Data Mining (SIGKDD), 2010, pp. 1029β1038. ACM.
[7] B. Wilder, L. Onasch-Vera, J. Hudson, J. Luna, N. Wilson, R. Petering, D. Woo, M. Tambe, E. Rice,
End-to-end influence maximization in the field, in: Proc. of the International Conference on
Autonomous Agents and Multiagent Systems (AAMAS), volume 18, 2018, pp. 1414β1422.
[8] P. Liu, L. Li, Y. Wen, S. Fang, Identifying influential nodes in social networks: Exploiting self-voting
mechanism, Big Data 11 (2023) 296β306. Mary Ann Liebert.
[9] A. Goyal, W. Lu, L. V. Lakshmanan, Celf++ optimizing the greedy algorithm for influence maxi-
mization in social networks, in: Proc. of the 20th international conference companion on World
Wide Web (WWW), 2011, pp. 47β48. ACM.
[10] C. Wang, W. Chen, Y. Wang, Scalable influence maximization for independent cascade model in
large-scale social networks, Data Mining and Knowledge Discovery 25 (2012) 545β576. Springer.
[11] Y. Tang, Y. Shi, X. Xiao, Influence maximization in near-linear time: A martingale approach, in:
Proc. of the 2015 ACM International Conference on Management of Data (SIGMOD), 2015, pp.
1539β1554. ACM.
[12] W. Chen, Y. Yuan, L. Zhang, Scalable influence maximization in social networks under the linear
threshold model, in: Proc. of the 2010 IEEE International Conference on Data Mining (ICDM),
2010, pp. 88β97. IEEE.
[13] F. Battiston, G. Cencetti, I. Iacopini, V. Latora, M. Lucas, A. Patania, J.-G. Young, G. Petri, Networks
beyond pairwise interactions: Structure and dynamics, Physics Reports 874 (2020) 1β92. Elsevier.
[14] F. Amato, V. Moscato, A. Picariello, G. SperlΓ, Influence maximization in social media networks
using hypergraphs, in: Proc. of the International Conference on Green, Pervasive, and Cloud
Computing (GPC), 2017, pp. 207β221. Springer.
[15] J. Zhu, J. Zhu, S. Ghosh, W. Wu, J. Yuan, Social influence maximization in hypergraph in social
networks, IEEE Transactions on Network Science and Engineering 6 (2018) 801β811. IEEE.
[16] A. Antelmi, G. Cordasco, C. Spagnuolo, P. Szufel, Social influence maximization in hypergraphs,
Entropy 23 (2021) 796. MDPI.
[17] A. MA, A. Rajkumar, Hyper-imrank: Ranking-based influence maximization for hypergraphs, in:
Proc. of the 5th Joint International Conference on Data Science & Management of Data (9th ACM
IKDD CODS and 27th COMAD), 2022, pp. 100β104. ACM.
[18] M. Xie, X.-X. Zhan, C. Liu, Z.-K. Zhang, An efficient adaptive degree-based heuristic algorithm for
influence maximization in hypergraphs, Information Processing & Management 60 (2023) 103161.
[19] X. Gong, H. W. X., Wang, C. Chen, W. Zhang, Y. Zhang, Influence maximization on hypergraphs
via multi-hop influence estimation, Information Processing & Management 61 (2024) 103683.
[20] S. Li, X. Li, Influence maximization in hypergraphs: A self-optimizing algorithm based on
electrostatic field, Chaos, Solitons & Fractals 174 (2023) 113888. Elsevier.
[21] R. Zhang, X. Qu, Q. Zhang, X. Xu, S. Pei, Influence maximization based on threshold models in
hypergraphs, Chaos: An Interdisciplinary Journal of Nonlinear Science 34 (2024). AIP Publishing.
[22] Q. Pan, H. Wang, J. Tang, Z. Lv, Z. Wang, X. Wu, Y. Ruan, T. Yv, M. Lao, Eioa: A computing
expectation-based influence evaluation method in weighted hypergraphs, Information Processing
& Management 61 (2024) 103856. Elsevier.
[23] S. Genetti, E. Ribaga, E. Cunegatti, Q. F. Lotito, G. Iacca, Influence maximization in hypergraphs
using multi-objective evolutionary algorithms, in: Proc. of the 18th International Conference on
Parallel Problem Solving from Nature (PPSN), 2024, pp. 217β235. Springer.
[24] S. G. Aksoy, C. Joslyn, C. O. Marrero, B. Praggastis, E. Purvine, Hypernetwork science via
high-order hypergraph walks, EPJ Data Science 9 (2020) 16. Springer.
[25] L. Shapley, A value for n-person games, Contributions to the Theory of Games (1953) 307β317.
Princeton University Press.
[26] T. Michalak, K. Aadithya, P. Szczepanski, B. Ravindran, N. Jennings, Efficient computation of the
shapley value for game-theoretic network centrality, Journal of Artificial Intelligence Research 46
(2013) 607β650. AI Access Foundation.
[27] M. Gendreau, J.-Y. Potvin, Handbook of metaheuristics, volume 2, Springer, 2010.
[28] H. Li, Y. Liu, S. Yang, Y. Lin, Y. Yang, J. Yoo, An improved hill climbing algorithm for graph
partitioning, The Computer Journal 66 (2023) 1761β1776.
[29] C. Stamile, F. Cauteruccio, G. Terracina, D. Ursino, G. Kocevar, D. Sappey-Marinier, A model-guided
string-based approach to white matter fiber-bundles extraction, in: Proc. of 8th International
Conference on Brain Informatics and Health (BIH 2015), London, UK, August 30-September 2,
2015. Proceedings 8, 2015, pp. 135β144. Springer.
[30] T. Back, Evolutionary algorithms in theory and practice: evolution strategies, evolutionary pro-
gramming, genetic algorithms, Oxford University Press, 1996.
[31] D. Simon, Evolutionary optimization algorithms, John Wiley & Sons, 2013.