Hierarchical cycle-tree packing model for $K$-core attack problem

• URL: http://arxiv.org/abs/2303.01007v2
• Date: Sat, 9 Dec 2023 07:16:48 GMT
• Title: Hierarchical cycle-tree packing model for $K$-core attack problem
• Authors: Jianwen Zhou, Hai-Jun Zhou
• Abstract summary: A hierarchical cycle-tree packing model is introduced here for this challenging optimization problem. We analyze this model through the replica-symmetric cavity method of statistical physics. The associated hierarchical cycle-tree guided attack (tt hCTGA) is able to construct nearly optimal attack solutions for regular random graphs.
• Score: 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.

Related papers

• Optimal spanning tree reconstruction in symbolic regression [2.553456266022125]
  A model is a superposition of primitive functions. The proposed algorithm reconstructs theminimum spanning tree from theweighted colored graph. This paper presents a novel solution based on the prize-collecting Steiner tree algorithm.
  arXiv  Detail & Related papers  (2024-06-25T13:22:13Z)
• Information-Theoretic Thresholds for Planted Dense Cycles [52.076657911275525]
  We study a random graph model for small-world networks which are ubiquitous in social and biological sciences. For both detection and recovery of the planted dense cycle, we characterize the information-theoretic thresholds in terms of $n$, $tau$, and an edge-wise signal-to-noise ratio $lambda$.
  arXiv  Detail & Related papers  (2024-02-01T03:39:01Z)
• Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More [30.919536115917726]
  We present a probabilistic model based on non-negative matrix factorization which unifies clustering and simplification. By relaxing the hard clustering to a soft clustering, our algorithm relaxes potentially hard clustering problems to a tractable ones.
  arXiv  Detail & Related papers  (2023-08-12T02:47:57Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing. The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph. For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain.
  arXiv  Detail & Related papers  (2023-02-08T08:17:43Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  Motivated by the problem of online correlation analysis, we propose the emphStochastic Scaled-Gradient Descent (SSD) algorithm. We bring these ideas together in an application to online correlation analysis, deriving for the first time an optimal one-time-scale algorithm with an explicit rate of local convergence to normality.
  arXiv  Detail & Related papers  (2021-12-29T18:46:52Z)
• AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution [79.44066256794187]
  We show how to convert a non-graph dataset into a graph by introducing the generative graph model, which is used to build graph convolution networks (GCNs) A bipartite graph constructed by anchors is updated dynamically to exploit the high-level information behind data. We theoretically prove that the simple update will lead to degeneration and a specific strategy is accordingly designed.
  arXiv  Detail & Related papers  (2021-11-12T07:08:13Z)
• Cycle-tree guided attack of random K-core: Spin glass model and efficient message-passing algorithm [0.0]
  A minimum attack set contains the smallest number of vertices whose removal induces complete collapse of the K-core. Here we tackle this optimal initial-condition problem from the spin-glass perspective of cycle-tree maximum packing. The good performance and time efficiency of CTGA are verified on the regular random and Erd"os-R'enyi random graph ensembles.
  arXiv  Detail & Related papers  (2021-10-12T12:28:05Z)
• Recurrently Predicting Hypergraphs [30.092688729343678]
  A problem arises from the number of possible multi-way relationships, or hyperedges, scaling in $mathcalO(2n)$ for a set of $n$ elements. We propose a recurrent hypergraph neural network that predicts the incidence matrix by iteratively refining an initial guess of the solution.
  arXiv  Detail & Related papers  (2021-06-26T01:12:41Z)
• Bayesian Inference of Random Dot Product Graphs via Conic Programming [1.7188280334580195]
  We present a convex cone program to infer the latent probability matrix of a random dot product graph (RDPG) We also demonstrate that the method recovers latent structure in the Karate Club Graph and synthetic U.S. Senate vote graphs.
  arXiv  Detail & Related papers  (2021-01-06T18:29:37Z)
• Scalable Deep Generative Modeling for Sparse Graphs [105.60961114312686]
  Existing deep neural methods require $Omega(n2)$ complexity by building up the adjacency matrix. We develop a novel autoregressive model, named BiGG, that utilizes this sparsity to avoid generating the full adjacency matrix. During training this autoregressive model can be parallelized with $O(log n)$ synchronization stages.
  arXiv  Detail & Related papers  (2020-06-28T04:37:57Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

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.