Influence Maximization in Hypergraphs Using A Genetic Algorithm with New Initialization and Evaluation Methods

• URL: http://arxiv.org/abs/2405.09185v1
• Date: Wed, 15 May 2024 08:46:33 GMT
• Title: Influence Maximization in Hypergraphs Using A Genetic Algorithm with New Initialization and Evaluation Methods
• Authors: Xilong Qu, Wenbin Pei, Yingchao Yang, Xirong Xu, Renquan Zhang, Qiang Zhang,
• Abstract summary: Influence (IM) is a crucial optimization task related to analyzing complex networks in the real world. We propose a novel model that integrates the influences of both node and hyperedge failures. We then introduce genetic algorithms (GA) to identify the most influential nodes that leverage hypergraph collective influences.
• Score: 6.315027378756443
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Influence maximization (IM) is a crucial optimization task related to analyzing complex networks in the real world, such as social networks, disease propagation networks, and marketing networks. Publications to date about the IM problem focus mainly on graphs, which fail to capture high-order interaction relationships from the real world. Therefore, the use of hypergraphs for addressing the IM problem has been receiving increasing attention. However, identifying the most influential nodes in hypergraphs remains challenging, mainly because nodes and hyperedges are often strongly coupled and correlated. In this paper, to effectively identify the most influential nodes, we first propose a novel hypergraph-independent cascade model that integrates the influences of both node and hyperedge failures. Afterward, we introduce genetic algorithms (GA) to identify the most influential nodes that leverage hypergraph collective influences. In the GA-based method, the hypergraph collective influence is effectively used to initialize the population, thereby enhancing the quality of initial candidate solutions. The designed fitness function considers the joint influences of both nodes and hyperedges. This ensures the optimal set of nodes with the best influence on both nodes and hyperedges to be evaluated accurately. Moreover, a new mutation operator is designed by introducing factors, i.e., the collective influence and overlapping effects of nodes in hypergraphs, to breed high-quality offspring. In the experiments, several simulations on both synthetic and real hypergraphs have been conducted, and the results demonstrate that the proposed method outperforms the compared methods.

Related papers

• Influence Maximization via Graph Neural Bandits [54.45552721334886]
  We set the IM problem in a multi-round diffusion campaign, aiming to maximize the number of distinct users that are influenced. We propose the framework IM-GNB (Influence Maximization with Graph Neural Bandits), where we provide an estimate of the users' probabilities of being influenced.
  arXiv  Detail & Related papers  (2024-06-18T17:54:33Z)
• Influence Maximization in Hypergraphs using Multi-Objective Evolutionary Algorithms [2.726292320658314]
  The Influence Maximization (IM) problem is a well-known NP-hard problem over graphs. We propose a multi-objective EA for the IM problem over hypergraphs.
  arXiv  Detail & Related papers  (2024-05-16T15:31:28Z)
• Hypergraph Transformer for Semi-Supervised Classification [50.92027313775934]
  We propose a novel hypergraph learning framework, HyperGraph Transformer (HyperGT) HyperGT uses a Transformer-based neural network architecture to effectively consider global correlations among all nodes and hyperedges. It achieves comprehensive hypergraph representation learning by effectively incorporating global interactions while preserving local connectivity patterns.
  arXiv  Detail & Related papers  (2023-12-18T17:50:52Z)
• BOURNE: Bootstrapped Self-supervised Learning Framework for Unified Graph Anomaly Detection [50.26074811655596]
  We propose a novel unified graph anomaly detection framework based on bootstrapped self-supervised learning (named BOURNE) By swapping the context embeddings between nodes and edges, we enable the mutual detection of node and edge anomalies. BOURNE can eliminate the need for negative sampling, thereby enhancing its efficiency in handling large graphs.
  arXiv  Detail & Related papers  (2023-07-28T00:44:57Z)
• From Hypergraph Energy Functions to Hypergraph Neural Networks [94.88564151540459]
  We present an expressive family of parameterized, hypergraph-regularized energy functions. We then demonstrate how minimizers of these energies effectively serve as node embeddings. We draw parallels between the proposed bilevel hypergraph optimization, and existing GNN architectures in common use.
  arXiv  Detail & Related papers  (2023-06-16T04:40:59Z)
• Resisting Graph Adversarial Attack via Cooperative Homophilous Augmentation [60.50994154879244]
  Recent studies show that Graph Neural Networks are vulnerable and easily fooled by small perturbations. In this work, we focus on the emerging but critical attack, namely, Graph Injection Attack. We propose a general defense framework CHAGNN against GIA through cooperative homophilous augmentation of graph data and model.
  arXiv  Detail & Related papers  (2022-11-15T11:44:31Z)
• Learning Causal Effects on Hypergraphs [33.41001768564952]
  We study hypergraphs from the perspective of causality. In this work, we investigate high-order interference modeling, and propose a new causality learning framework powered by hypergraph neural networks.
  arXiv  Detail & Related papers  (2022-07-07T23:14:10Z)
• Adaptive Neural Message Passing for Inductive Learning on Hypergraphs [21.606287447052757]
  We present HyperMSG, a novel hypergraph learning framework. It adapts to the data and task by learning an attention weight associated with each node's degree centrality. It is robust and outperforms state-of-the-art hypergraph learning methods on a wide range of tasks and datasets.
  arXiv  Detail & Related papers  (2021-09-22T12:24:02Z)
• Learnable Hypergraph Laplacian for Hypergraph Learning [34.28748027233654]
  HyperGraph Convolutional Neural Networks (HGCNNs) have demonstrated their potential in modeling high-order relations preserved in graph structured data. We propose the first learning-based method tailored for constructing adaptive hypergraph structure, termed HypERgrAph Laplacian aDaptor (HERALD) HERALD adaptively optimize the adjacency relationship between hypernodes and hyperedges in an end-to-end manner and thus the task-aware hypergraph is learned.
  arXiv  Detail & Related papers  (2021-06-12T02:07:07Z)
• Learnable Hypergraph Laplacian for Hypergraph Learning [34.28748027233654]
  HyperGraph Convolutional Neural Networks (HGCNNs) have demonstrated their potential in modeling high-order relations preserved in graph structured data. We propose the first learning-based method tailored for constructing adaptive hypergraph structure, termed HypERgrAph Laplacian aDaptor (HERALD) HERALD adaptively optimize the adjacency relationship between hypernodes and hyperedges in an end-to-end manner and thus the task-aware hypergraph is learned.
  arXiv  Detail & Related papers  (2021-06-10T12:37:55Z)
• Unveiling Anomalous Edges and Nominal Connectivity of Attributed Networks [53.56901624204265]
  The present work deals with uncovering anomalous edges in attributed graphs using two distinct formulations with complementary strengths. The first relies on decomposing the graph data matrix into low rank plus sparse components to improve markedly performance. The second broadens the scope of the first by performing robust recovery of the unperturbed graph, which enhances the anomaly identification performance.
  arXiv  Detail & Related papers  (2021-04-17T20:00:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.