HEDV-Greedy: An Advanced Algorithm for Influence Maximization in Hypergraphs
Influence maximization (IM) has shown wide applicability in various fields over the past few decades, e.g., viral marketing, rumor control, and prevention of infectious diseases. Nevertheless, existing research on IM primarily focuses on ordinary networks with pairwise connections between nodes, whi...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-03-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/12/7/1041 |
| _version_ | 1797212271228747776 |
|---|---|
| author | Haosen Wang Qingtao Pan Jun Tang |
| author_facet | Haosen Wang Qingtao Pan Jun Tang |
| author_sort | Haosen Wang |
| collection | DOAJ |
| description | Influence maximization (IM) has shown wide applicability in various fields over the past few decades, e.g., viral marketing, rumor control, and prevention of infectious diseases. Nevertheless, existing research on IM primarily focuses on ordinary networks with pairwise connections between nodes, which fall short in the representation of higher-order relations. Influence maximization on hypergraphs (HIM) has received limited research attention. A novel evaluation function, which aims to evaluate the spreading influence of selected nodes on hypergraphs, i.e., expected diffusion value on hypergraph (HEDV), is proposed in this work. Then, an advanced greedy-based algorithm, termed HEDV-greedy, is proposed to select seed nodes with maximum spreading influence on the hypergraph. We conduct extensive experiments on eight real-world hypergraph datasets, benchmarking HEDV-greedy against eight state-of-the-art methods for the HIM problem. Extensive experiments conducted on real-world datasets highlight the effectiveness and efficiency of our proposed methods. The HEDV-greedy algorithm demonstrates a marked reduction in time complexity by two orders of magnitude compared to the conventional greedy method. Moreover, HEDV-greedy outperforms other state-of-the-art algorithms across all datasets. Specifically, under conditions of lower propagation probability, HEDV-greedy exhibits an average improvement in solution accuracy of 25.76%. |
| first_indexed | 2024-04-24T10:39:44Z |
| format | Article |
| id | doaj.art-05447cdc99384406ba353c4adfd70977 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-04-24T10:39:44Z |
| publishDate | 2024-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-05447cdc99384406ba353c4adfd709772024-04-12T13:22:43ZengMDPI AGMathematics2227-73902024-03-01127104110.3390/math12071041HEDV-Greedy: An Advanced Algorithm for Influence Maximization in HypergraphsHaosen Wang0Qingtao Pan1Jun Tang2College of Systems Engineering, National University of Defense Technology, Changsha 410073, ChinaCollege of Systems Engineering, National University of Defense Technology, Changsha 410073, ChinaCollege of Systems Engineering, National University of Defense Technology, Changsha 410073, ChinaInfluence maximization (IM) has shown wide applicability in various fields over the past few decades, e.g., viral marketing, rumor control, and prevention of infectious diseases. Nevertheless, existing research on IM primarily focuses on ordinary networks with pairwise connections between nodes, which fall short in the representation of higher-order relations. Influence maximization on hypergraphs (HIM) has received limited research attention. A novel evaluation function, which aims to evaluate the spreading influence of selected nodes on hypergraphs, i.e., expected diffusion value on hypergraph (HEDV), is proposed in this work. Then, an advanced greedy-based algorithm, termed HEDV-greedy, is proposed to select seed nodes with maximum spreading influence on the hypergraph. We conduct extensive experiments on eight real-world hypergraph datasets, benchmarking HEDV-greedy against eight state-of-the-art methods for the HIM problem. Extensive experiments conducted on real-world datasets highlight the effectiveness and efficiency of our proposed methods. The HEDV-greedy algorithm demonstrates a marked reduction in time complexity by two orders of magnitude compared to the conventional greedy method. Moreover, HEDV-greedy outperforms other state-of-the-art algorithms across all datasets. Specifically, under conditions of lower propagation probability, HEDV-greedy exhibits an average improvement in solution accuracy of 25.76%.https://www.mdpi.com/2227-7390/12/7/1041influence maximizationhypergraphspreading dynamiccomplex network |
| spellingShingle | Haosen Wang Qingtao Pan Jun Tang HEDV-Greedy: An Advanced Algorithm for Influence Maximization in Hypergraphs Mathematics influence maximization hypergraph spreading dynamic complex network |
| title | HEDV-Greedy: An Advanced Algorithm for Influence Maximization in Hypergraphs |
| title_full | HEDV-Greedy: An Advanced Algorithm for Influence Maximization in Hypergraphs |
| title_fullStr | HEDV-Greedy: An Advanced Algorithm for Influence Maximization in Hypergraphs |
| title_full_unstemmed | HEDV-Greedy: An Advanced Algorithm for Influence Maximization in Hypergraphs |
| title_short | HEDV-Greedy: An Advanced Algorithm for Influence Maximization in Hypergraphs |
| title_sort | hedv greedy an advanced algorithm for influence maximization in hypergraphs |
| topic | influence maximization hypergraph spreading dynamic complex network |
| url | https://www.mdpi.com/2227-7390/12/7/1041 |
| work_keys_str_mv | AT haosenwang hedvgreedyanadvancedalgorithmforinfluencemaximizationinhypergraphs AT qingtaopan hedvgreedyanadvancedalgorithmforinfluencemaximizationinhypergraphs AT juntang hedvgreedyanadvancedalgorithmforinfluencemaximizationinhypergraphs |