HEDV-Greedy: An Advanced Algorithm for Influence Maximization in Hypergraphs

Haosen Wang, Qingtao Pan and Jun Tang ()
Additional contact information
Haosen Wang: College of Systems Engineering, National University of Defense Technology, Changsha 410073, China
Qingtao Pan: College of Systems Engineering, National University of Defense Technology, Changsha 410073, China
Jun Tang: College of Systems Engineering, National University of Defense Technology, Changsha 410073, China

Mathematics, 2024, vol. 12, issue 7, 1-18

Abstract: 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%.

Keywords: influence maximization; hypergraph; spreading dynamic; complex network (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/7/1041/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/7/1041/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:7:p:1041-:d:1367731

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().