論文の概要: A Fast Algorithm for Moderating Critical Nodes via Edge Removal
- arxiv url: http://arxiv.org/abs/2309.06392v1
- Date: Sat, 9 Sep 2023 13:54:34 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-13 12:01:51.875620
- Title: A Fast Algorithm for Moderating Critical Nodes via Edge Removal
- Title（参考訳）: エッジ除去による臨界ノードをモデレートする高速化アルゴリズム
- Authors: Changan Liu, Xiaotian Zhou, Ahad N. Zehmakan, and Zhongzhi Zhang
- Abstract要約: 対象ノードの情報集中度を最小限に抑えるために,ネットワークから$k$エッジを除去する問題について検討する。
ランダムウォークに基づくシュア補数近似や高速和推定などの新しい手法を用いて、3つの近似グリードアルゴリズムを提案する。
理論的解析を補完するため、100万以上のノードを持つ合成および実ネットワークに関する包括的な実験を行う。
- 参考スコア（独自算出の注目度）: 19.130541561303293
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Critical nodes in networks are extremely vulnerable to malicious attacks to
trigger negative cascading events such as the spread of misinformation and
diseases. Therefore, effective moderation of critical nodes is very vital for
mitigating the potential damages caused by such malicious diffusions. The
current moderation methods are computationally expensive. Furthermore, they
disregard the fundamental metric of information centrality, which measures the
dissemination power of nodes.
We investigate the problem of removing $k$ edges from a network to minimize
the information centrality of a target node $\lea$ while preserving the
network's connectivity. We prove that this problem is computationally
challenging: it is NP-complete and its objective function is not supermodular.
However, we propose three approximation greedy algorithms using novel
techniques such as random walk-based Schur complement approximation and fast
sum estimation. One of our algorithms runs in nearly linear time in the number
of edges.
To complement our theoretical analysis, we conduct a comprehensive set of
experiments on synthetic and real networks with over one million nodes. Across
various settings, the experimental results illustrate the effectiveness and
efficiency of our proposed algorithms.
- Abstract（参考訳）: ネットワークのクリティカルノードは、誤った情報や病気の拡散などのネガティブなカスケードイベントを引き起こす悪意のある攻撃に対して極めて脆弱である。
したがって、このような有害な拡散による潜在的な損傷を緩和するためには、クリティカルノードの効果的なモデレーションが不可欠である。
現在のモデレーション手法は計算コストが高い。
さらに、ノードの拡散力を測定する情報中心性の基本指標を無視している。
本研究では,ネットワークの接続性を維持しつつ,対象ノードの情報集中性を最小限に抑えるために,ネットワークから$k$エッジを除去する問題を検討する。
これはnp完全であり、目的関数は超モジュラーではない。
しかし,ランダムウォークに基づくschur補間近似や高速和推定などの新しい手法を用いた3つの近似グリーディアルゴリズムを提案する。
私たちのアルゴリズムの1つは、エッジの数でほぼ線形に実行される。
理論解析を補完するため,我々は100万以上のノードを有する合成および実ネットワークに関する実験を包括的に実施する。
各種設定において,提案アルゴリズムの有効性と有効性を示す実験結果が得られた。
関連論文リスト
- Minimum Topology Attacks for Graph Neural Networks [70.17791814425148]
グラフニューラルネットワーク(GNN)は、敵対的トポロジ攻撃に対する堅牢性において大きな注目を集めている。
本稿では,各ノードに対する攻撃を成功させるのに十分な最小摂動を適応的に見つけることを目的とした,最小予算トポロジ攻撃という新しいタイプのトポロジ攻撃を提案する。
論文 参考訳（メタデータ） (2024-03-05T07:29:12Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - LGTBIDS: Layer-wise Graph Theory Based Intrusion Detection System in
Beyond 5G [9.63617966257402]
侵入検知は、通信ネットワークのセキュリティを確保するための中心的なアプローチを示す。
The Layerwise Graph Theory-Based Intrusion Detection System (LGTBIDS) algorithm is designed to detect the attacked node。
結果は、より良いパフォーマンス、低い時間計算、低い複雑さを検証します。
論文 参考訳（メタデータ） (2022-10-06T05:32:03Z) - A Systematic Evaluation of Node Embedding Robustness [77.29026280120277]
本研究では,ノード埋め込みモデルのランダムおよび逆毒攻撃に対する経験的ロバスト性を評価する。
ネットワーク特性とノードラベルを用いて計算したエッジの追加,削除,再切り替えの戦略を比較した。
その結果,ノード分類はネットワーク再構成とは対照的に,高い性能劣化に悩まされていることがわかった。
論文 参考訳（メタデータ） (2022-09-16T17:20:23Z) - Robust Training and Verification of Implicit Neural Networks: A
Non-Euclidean Contractive Approach [64.23331120621118]
本稿では,暗黙的ニューラルネットワークのトレーニングとロバスト性検証のための理論的および計算的枠組みを提案する。
組込みネットワークを導入し、組込みネットワークを用いて、元のネットワークの到達可能な集合の超近似として$ell_infty$-normボックスを提供することを示す。
MNISTデータセット上で暗黙的なニューラルネットワークをトレーニングするためにアルゴリズムを適用し、我々のモデルの堅牢性と、文献における既存のアプローチを通じてトレーニングされたモデルを比較する。
論文 参考訳（メタデータ） (2022-08-08T03:13:24Z) - Identifying critical nodes in complex networks by graph representation
learning [2.304938062591095]
影響は臨界ノードの採掘における主要な問題の一つである。
IMGNNは、ネットワーク内のノードの集中度を入力とし、最適な初期スプレッドラー内のノードを出力とするグラフ学習フレームワークである。
IMGNNは、ヒトベースのアルゴリズムよりも、固定感染規模で初期スプレッドラーのサイズを最小化するのに効率的である。
論文 参考訳（メタデータ） (2022-01-20T03:41:22Z) - Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。
本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。
ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
論文 参考訳（メタデータ） (2021-12-03T14:23:05Z) - Efficiently Learning Any One Hidden Layer ReLU Network From Queries [27.428198343906352]
ネットワークへのブラックボックスアクセスを提供するニューラルネットワークアクティベーションを任意の1つの隠蔽層で学習するアルゴリズムを初めて提供する。
最悪のネットワークであっても、完全時間で効率を保証できるのはこれが初めてです。
論文 参考訳（メタデータ） (2021-11-08T18:59:40Z) - Multiple Node Immunisation for Preventing Epidemics on Networks by Exact
Multiobjective Optimisation of Cost and Shield-Value [0.0]
本稿では,複数のノードを選択して削除する問題に対処する。
複数ノード選択に関するこれまでの作業と比較すると、コストと利益の間のトレードオフが考慮されている。
この論文の主な貢献は、もし時間が許せば、正確で問題固有の手法が使われるべきであるという洞察である。
論文 参考訳（メタデータ） (2020-10-13T15:49:00Z) - Bayesian Optimization with Machine Learning Algorithms Towards Anomaly
Detection [66.05992706105224]
本稿では,ベイズ最適化手法を用いた効果的な異常検出フレームワークを提案する。
ISCX 2012データセットを用いて検討したアルゴリズムの性能を評価する。
実験結果から, 精度, 精度, 低コストアラームレート, リコールの観点から, 提案手法の有効性が示された。
論文 参考訳（メタデータ） (2020-08-05T19:29:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。