Influence Maximization in Hypergraphs using Multi-Objective Evolutionary Algorithms
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929346052096000 |
|---|---|
| author | Genetti, Stefano Ribaga, Eros Cunegatti, Elia Lotito, Quintino Francesco Iacca, Giovanni |
| author_facet | Genetti, Stefano Ribaga, Eros Cunegatti, Elia Lotito, Quintino Francesco Iacca, Giovanni |
| contents | The Influence Maximization (IM) problem is a well-known NP-hard combinatorial problem over graphs whose goal is to find the set of nodes in a network that spreads influence at most. Among the various methods for solving the IM problem, evolutionary algorithms (EAs) have been shown to be particularly effective. While the literature on the topic is particularly ample, only a few attempts have been made at solving the IM problem over higher-order networks, namely extensions of standard graphs that can capture interactions that involve more than two nodes. Hypergraphs are a valuable tool for modeling complex interaction networks in various domains; however, they require rethinking of several graph-based problems, including IM. In this work, we propose a multi-objective EA for the IM problem over hypergraphs that leverages smart initialization and hypergraph-aware mutation. While the existing methods rely on greedy or heuristic methods, to our best knowledge this is the first attempt at applying EAs to this problem. Our results over nine real-world datasets and three propagation models, compared with five baseline algorithms, reveal that our method achieves in most cases state-of-the-art results in terms of hypervolume and solution diversity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_10187 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Influence Maximization in Hypergraphs using Multi-Objective Evolutionary Algorithms Genetti, Stefano Ribaga, Eros Cunegatti, Elia Lotito, Quintino Francesco Iacca, Giovanni Social and Information Networks Neural and Evolutionary Computing The Influence Maximization (IM) problem is a well-known NP-hard combinatorial problem over graphs whose goal is to find the set of nodes in a network that spreads influence at most. Among the various methods for solving the IM problem, evolutionary algorithms (EAs) have been shown to be particularly effective. While the literature on the topic is particularly ample, only a few attempts have been made at solving the IM problem over higher-order networks, namely extensions of standard graphs that can capture interactions that involve more than two nodes. Hypergraphs are a valuable tool for modeling complex interaction networks in various domains; however, they require rethinking of several graph-based problems, including IM. In this work, we propose a multi-objective EA for the IM problem over hypergraphs that leverages smart initialization and hypergraph-aware mutation. While the existing methods rely on greedy or heuristic methods, to our best knowledge this is the first attempt at applying EAs to this problem. Our results over nine real-world datasets and three propagation models, compared with five baseline algorithms, reveal that our method achieves in most cases state-of-the-art results in terms of hypervolume and solution diversity. |
| title | Influence Maximization in Hypergraphs using Multi-Objective Evolutionary Algorithms |
| topic | Social and Information Networks Neural and Evolutionary Computing |
| url | https://arxiv.org/abs/2405.10187 |