論文の概要: Hierarchical cycle-tree packing model for $K$-core attack problem

• arxiv url: http://arxiv.org/abs/2303.01007v2
• Date: Sat, 9 Dec 2023 07:16:48 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-13 03:09:30.798782
• Title: Hierarchical cycle-tree packing model for $K$-core attack problem
• Title（参考訳）: k$-core攻撃問題に対する階層的サイクルツリーパッキングモデル
• Authors: Jianwen Zhou, Hai-Jun Zhou
• Abstract要約: ここでは、この挑戦的な最適化問題に対して、階層的なサイクルツリーパッキングモデルを導入している。 統計物理学のレプリカ対称キャビティ法を用いて,このモデルを解析する。 関連する階層的サイクルツリー誘導攻撃(tt hCTGA)は、通常のランダムグラフに対するほぼ最適な攻撃解を構築することができる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The $K$-core of a graph is the unique maximum subgraph within which each vertex connects to $K$ or more other vertices. The optimal $K$-core attack problem asks to delete the minimum number of vertices from the $K$-core to induce its complete collapse. A hierarchical cycle-tree packing model is introduced here for this challenging combinatorial optimization problem. We convert the temporally long-range correlated $K$-core pruning dynamics into locally tree-like static patterns and analyze this model through the replica-symmetric cavity method of statistical physics. A set of coarse-grained belief propagation equations are derived to predict single vertex marginal probabilities efficiently. The associated hierarchical cycle-tree guided attack ({\tt hCTGA}) algorithm is able to construct nearly optimal attack solutions for regular random graphs and Erd\"os-R\'enyi random graphs. Our cycle-tree packing model may also be helpful for constructing optimal initial conditions for other irreversible dynamical processes on sparse random graphs.
• Abstract（参考訳）: グラフの$k$-coreは、各頂点が$k$またはそれ以上の頂点に接続する唯一の最大部分グラフである。 最適な$K$-core攻撃問題は、その完全な崩壊を引き起こすために$K$-coreから最小の頂点数を削除するよう要求する。 この難解な組合せ最適化問題に対して階層的サイクルツリーパッキングモデルが導入された。 時間的長距離相関を持つk$-core pruningダイナミクスを局所木状静的パターンに変換し,統計物理学のレプリカ対称キャビティ法を用いて解析する。 粗い信念伝播方程式の集合を導出し、単一の頂点境界確率を効率的に予測する。 関連する階層的サイクルツリー誘導攻撃({\tt hctga})アルゴリズムは、正則ランダムグラフとerd\"os-r\'enyiランダムグラフのほぼ最適な攻撃ソリューションを構築することができる。 我々のサイクルツリーパッキングモデルは、スパースランダムグラフ上の他の可逆的動的プロセスに対する最適初期条件を構築するのにも役立ちます。

関連論文リスト

• Optimal spanning tree reconstruction in symbolic regression [2.553456266022125]
  モデルは原始関数の重ね合わせである。 提案アルゴリズムは, 加重色グラフからスパンニング木を再構成する。 本稿では,Steiner 木木アルゴリズムを応用した新しい手法を提案する。
  論文  参考訳（メタデータ） (2024-06-25T13:22:13Z)
• Information-Theoretic Thresholds for Planted Dense Cycles [52.076657911275525]
  本研究では,社会科学や生物科学においてユビキタスな小世界ネットワークのランダムグラフモデルについて検討する。 植え込み高密度サイクルの検出と回復の両面において、情報理論の閾値を$n$, $tau$、エッジワイド信号対雑音比$lambda$で特徴づける。
  論文  参考訳（メタデータ） (2024-02-01T03:39:01Z)
• Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More [30.919536115917726]
  クラスタリングと単純化を統一する非負行列分解に基づく確率モデルを提案する。 ハードクラスタリングをソフトクラスタリングに緩和することにより、ハードクラスタリングの潜在的な問題をトラクタブルクラスタに緩和する。
  論文  参考訳（メタデータ） (2023-08-12T02:47:57Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。 キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。 オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
  論文  参考訳（メタデータ） (2023-02-08T08:17:43Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。 我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
  論文  参考訳（メタデータ） (2021-12-29T18:46:52Z)
• AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution [79.44066256794187]
  我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。 アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。 理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
  論文  参考訳（メタデータ） (2021-11-12T07:08:13Z)
• Cycle-tree guided attack of random K-core: Spin glass model and efficient message-passing algorithm [0.0]
  最小攻撃セットは、Kコアの完全な崩壊を引き起こす最小数の頂点を含む。 ここでは、この最適初期条件問題に、サイクルツリー最大パッキングのスピングラスの観点から取り組む。 CTGAの性能と時間効率は、正規ランダムおよびエルド・オス・レニイランダムグラフアンサンブルで検証される。
  論文  参考訳（メタデータ） (2021-10-12T12:28:05Z)
• Recurrently Predicting Hypergraphs [30.092688729343678]
  問題は、$n$要素の集合に対して$mathcalO(2n)$でスケーリング可能なマルチウェイ関係(ハイパーエッジ)の数から生じる。 そこで本研究では,提案手法の初期推定を反復的に精算することにより,入射行列を予測する再帰型ハイパーグラフニューラルネットワークを提案する。
  論文  参考訳（メタデータ） (2021-06-26T01:12:41Z)
• Bayesian Inference of Random Dot Product Graphs via Conic Programming [1.7188280334580195]
  本稿では,ランダムドット積グラフ(RDPG)の潜在確率行列を推定する凸コーンプログラムを提案する。 また、この手法がケイトクラブグラフと米国上院の投票グラフの潜在構造を復元することを示した。
  論文  参考訳（メタデータ） (2021-01-06T18:29:37Z)
• Scalable Deep Generative Modeling for Sparse Graphs [105.60961114312686]
  既存のディープニューラルネットワーク手法では、隣接行列を構築することで、$Omega(n2)$複雑さを必要とする。 我々は,この空間を利用して完全隣接行列を生成する新しい自己回帰モデルBiGGを開発した。 トレーニング中、この自己回帰モデルは$O(log n)$同期ステージで並列化できる。
  論文  参考訳（メタデータ） (2020-06-28T04:37:57Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。