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

• arxiv url: http://arxiv.org/abs/2303.01007v1
• Date: Thu, 2 Mar 2023 06:47:33 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-03 15:41:14.504873
• Title: Hierarchical cycle-tree packing model for $K$-core attack problem
• Title（参考訳）: k$-core攻撃問題に対する階層的サイクルツリーパッキングモデル
• Authors: Jianwen Zhou, Hai-Jun Zhou
• Abstract要約: 我々は、長い範囲の相関した$K$-coreプルーニングプロセスを静的パターンに変換する階層的サイクルツリーパッキングモデルを構築した。 この研究のモデルは、他の不可逆な力学過程に対する最適初期条件を構築するために拡張することができる。
• 参考スコア（独自算出の注目度）: 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 at least $K$ other vertices. The $K$-core optimal attack problem asks to construct a minimum-sized set of vertices whose removal results in the complete collapse of the $K$-core. In this paper, we construct a hierarchical cycle-tree packing model which converts a long-range correlated $K$-core pruning process into static patterns and analyze this model through the replica-symmetric (RS) cavity method of statistical physics. The cycle-tree guided attack (CTGA) message-passing algorithm exhibits superior performance on random regular and Erdos-Renyi graphs. It provides new upper bounds on the minimal cardinality of the $K$-core attack set. The model of this work may be extended to construct optimal initial conditions for other irreversible dynamical processes.
• Abstract（参考訳）: グラフの$k$-coreは、各頂点が少なくとも$k$の他の頂点と接続する唯一の最大部分グラフである。 k$-coreの最適攻撃問題は、k$-coreの完全な崩壊をもたらす最小サイズの頂点の集合を構築することを要求する。 本稿では,長期相関した$K$-coreプルーニングプロセスを静的パターンに変換する階層型サイクルツリーパッキングモデルを構築し,統計物理学のレプリカ対称性(RS)キャビティ手法を用いて解析する。 サイクルツリー誘導攻撃(CTGA)メッセージパスアルゴリズムは、ランダム正規グラフとエルドス・レーニグラフに対して優れた性能を示す。 これは、$K$-core攻撃セットの最小濃度に関する新しい上限を提供する。 この研究のモデルは、他の不可逆な力学過程に対する最適初期条件を構築するために拡張することができる。

関連論文リスト

• 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)

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

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