論文の概要: Influence Maximization in Hypergraphs using Multi-Objective Evolutionary Algorithms
- arxiv url: http://arxiv.org/abs/2405.10187v1
- Date: Thu, 16 May 2024 15:31:28 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-17 13:52:46.342695
- Title: Influence Maximization in Hypergraphs using Multi-Objective Evolutionary Algorithms
- Title（参考訳）: 多目的進化アルゴリズムを用いたハイパーグラフの最大化
- Authors: Stefano Genetti, Eros Ribaga, Elia Cunegatti, Quintino Francesco Lotito, Giovanni Iacca,
- Abstract要約: 影響最大化(IM)問題はグラフ上のよく知られたNPハード問題である。
ハイパーグラフ上のIM問題に対する多目的EAを提案する。
- 参考スコア（独自算出の注目度）: 2.726292320658314
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: 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.
- Abstract（参考訳）: 影響最大化(imfect Maximization, IM)問題は、ネットワーク内のノードの集合を見つけることを目的とするグラフ上のNPハード組合せ問題としてよく知られている。
IM問題を解く様々な方法のうち、進化アルゴリズム(EA)は特に有効であることが示されている。
トピックに関する文献は特に豊富だが、高階ネットワーク上のIM問題を解決するための試みはわずかに行われており、これは2つ以上のノードを含むインタラクションをキャプチャできる標準グラフの拡張である。
ハイパーグラフは、様々な領域における複雑な相互作用ネットワークをモデル化するための貴重なツールであるが、IMを含むグラフベースの問題を再考する必要がある。
本研究では,ハイパーグラフに対する多目的EAを提案する。
既存の手法は欲張りやヒューリスティックな手法に依存していますが、私たちの知る限りでは、この問題にEAを適用する最初の試みです。
提案手法は,9つの実世界のデータセットと3つの伝播モデルに対して,5つのベースラインアルゴリズムと比較して,ほとんどの場合において,超体積および解の多様性の観点から,最先端の結果が得られることを示した。
関連論文リスト
- Network Interdiction Goes Neural [26.308933674471895]
ネットワーク断面積問題は、2人のプレイヤーが関与する最適化問題である。
1つは、ネットワーク上の最適化問題を解決することを目的としており、もう1つは、最初のプレイヤーの目的を阻止するためにネットワークを変更することを目的としている。
論文 参考訳（メタデータ） (2024-05-26T02:34:26Z) - Influence Maximization in Hypergraphs Using A Genetic Algorithm with New Initialization and Evaluation Methods [6.315027378756443]
インフルエンス(IM)は,実世界の複雑なネットワークを解析する上で重要な最適化課題である。
本稿では,ノード障害とハイパーエッジ障害の両方の影響を統合する新しいモデルを提案する。
次に、ハイパーグラフの集団的影響を利用する最も影響力のあるノードを特定するために遺伝的アルゴリズム(GA)を導入する。
論文 参考訳（メタデータ） (2024-05-15T08:46:33Z) - Many-Objective Evolutionary Influence Maximization: Balancing Spread, Budget, Fairness, and Time [3.195234044113248]
インフルエンス・最大化(IM)問題は、情報伝達を最大限に広めることのできるグラフ内のノードの集合を見つけ出そうとする。
この問題はNPハードであることが知られており、通常は第2の目的を最適化する影響(スプレッド)を最大化して研究される。
本研究では,シードセットサイズの影響と最小化に基づいて,予算の公平性,コミュニティ,時間といったIM固有の目的関数を最適化した最初のケーススタディを提案する。
論文 参考訳（メタデータ） (2024-03-27T16:54:45Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - MGNNI: Multiscale Graph Neural Networks with Implicit Layers [53.75421430520501]
暗黙グラフニューラルネットワーク(GNN)は、基礎となるグラフの長距離依存性をキャプチャするために提案されている。
暗黙的GNNの2つの弱点は、長距離依存を捉えるための限られた有効範囲による制約付き表現性と、複数の解像度でグラフ上のマルチスケール情報をキャプチャする能力の欠如である。
グラフ上のマルチスケール構造をモデル化できる暗黙の層(MGNNI)を持つマルチスケールグラフニューラルネットワークを提案する。
論文 参考訳（メタデータ） (2022-10-15T18:18:55Z) - GraMeR: Graph Meta Reinforcement Learning for Multi-Objective Influence
Maximization [1.7311053765541482]
インフルエンス(IM)とは、ネットワーク内のシードノードと呼ばれるノードのサブセットを特定する問題である(グラフ)。
IMには、バイラルマーケティング、疫病対策、センサー配置、その他のネットワーク関連タスクなど、数多くの応用がある。
我々は、本質的および影響的アクティベーションの両方を扱うマルコフ決定プロセスとして、一般的なIM問題を開発する。
論文 参考訳（メタデータ） (2022-05-30T03:48:51Z) - From Unsupervised to Few-shot Graph Anomaly Detection: A Multi-scale
Contrastive Learning Approach [49.439021563395976]
グラフデータからの異常検出は、ソーシャルネットワーク、金融、eコマースなど、多くのアプリケーションにおいて重要なデータマイニングタスクである。
マルチスケールcONtrastive lEarning(略してANEMONE)を用いた新しいフレームワーク, graph Anomaly dEtection フレームワークを提案する。
グラフニューラルネットワークをバックボーンとして、複数のグラフスケール(ビュー)から情報をエンコードすることで、グラフ内のノードのより良い表現を学習する。
論文 参考訳（メタデータ） (2022-02-11T09:45:11Z) - Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。
本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。
ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
論文 参考訳（メタデータ） (2021-12-03T14:23:05Z) - Residual Enhanced Multi-Hypergraph Neural Network [26.42547421121713]
HyperGraph Neural Network (HGNN) はハイパーグラフ表現学習のためのデファクト手法である。
本稿では,各ハイパーグラフからのマルチモーダル情報を効果的に融合できるResidual enhanced Multi-Hypergraph Neural Networkを提案する。
論文 参考訳（メタデータ） (2021-05-02T14:53:32Z) - Unveiling Anomalous Edges and Nominal Connectivity of Attributed
Networks [53.56901624204265]
本研究では、相補的な強さを持つ2つの異なる定式化を用いて、属性グラフの異常なエッジを明らかにする。
まず、グラフデータマトリックスを低ランクとスパースコンポーネントに分解することで、パフォーマンスを著しく向上させる。
第2は、乱れのないグラフを頑健に復元することにより、第1のスコープを広げ、異常識別性能を高める。
論文 参考訳（メタデータ） (2021-04-17T20:00:40Z) - Towards an Efficient and General Framework of Robust Training for Graph
Neural Networks [96.93500886136532]
グラフニューラルネットワーク(GNN)は、いくつかの基本的な推論タスクに大きく進歩している。
GNNの目覚ましい性能にもかかわらず、グラフ構造上の摂動を慎重に作り、誤った予測を下すことが観察されている。
我々は,強靭なGNNを得るために,欲求探索アルゴリズムとゼロ階法を利用する汎用フレームワークを提案する。
論文 参考訳（メタデータ） (2020-02-25T15:17:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。