2303/2303.01007.md

Title: Hierarchical cycle-tree packing model for optimal K-core attack

URL Source: https://arxiv.org/html/2303.01007

Markdown Content: Back to arXiv

This is experimental HTML to improve accessibility. We invite you to report rendering errors. Use Alt+Y to toggle on accessible reporting links and Alt+Shift+Y to toggle off. Learn more about this project and help improve conversions.

Why HTML? Report Issue Back to Abstract Download PDF 1Introduction 2Model and coarse-grained belief propagation equations 3Results 4Conclusion and discussion 5Appendix 6Acknowledgments 7Data availability statement 8Conflict of interest statement License: arXiv.org perpetual non-exclusive license arXiv:2303.01007v2 [cond-mat.dis-nn] 09 Dec 2023 \jyear

2023

[1,2,3] Hai-Jun Zhou

1]\orgdivCAS Key Laboratory for Theoretical Physics, Institute of Theoretical Physics, \orgnameChinese Academy of Sciences, \orgaddress\cityBeijing, \postcode100190, \countryChina 2]\orgdivSchool of Physical Sciences, \orgnameUniversity of Chinese Academy of Sciences, \orgaddress\cityBeijing, \postcode100049, \countryChina 3]\orgdivMinJiang Cooperative Center for Theoretical Physics, \orgnameMinJiang University, \orgaddress\cityFuzhou, \postcode350108, \countryChina

Hierarchical cycle-tree packing model for optimal K-core attack Jianwen Zhou zhoujianwen@itp.ac.cn zhouhj@itp.ac.cn [ [ [ Abstract

The 𝐾 -core of a graph is the unique maximum subgraph within which each vertex connects to 𝐾 or more other vertices. The optimal 𝐾 -core attack problem asks to delete the minimum number of vertices from the 𝐾 -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 𝐾 -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 (hCTGA) algorithm is able to construct nearly optimal attack solutions for regular random graphs and Erdös-Rényi 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.

keywords: 𝐾 -core attack; cycle-tree packing model; cavity method; irreversible dynamics; optimal initial condition 1Introduction

𝐾 -core is a fundamental graph concept. For a given graph 𝐺 formed by a set of vertices and a set of edges between these vertices, its 𝐾 -core is unique and it is the maximum subgraph in which each vertex is connected to at least 𝐾 other vertices of this same subgraph. The cardinality of a 𝐾 -core is simply the number of vertices in this maximum subgraph. If all the vertices in graph 𝐺 have at least 𝐾 attached edges, then the whole graph is a 𝐾 -core. The 𝐾 -core of a general graph can be obtained by deleting from the graph, in an iterative manner, all the vertices which have less than 𝐾 attached edges together with these associated edges. The final surviving subgraph at the end of this pruning process is then the 𝐾 -core.

The 𝐾 -core concept was initially introduced to study magnetization in lattices Pollak-1975; Chalupa-1979 and collective behavior in social networks Granovetter-1978; Seidman-1983. The 𝐾 -core captures some of the key properties of many complex networks and has a wide range of applications Kong-2019. In statistical physics, the kinetically constrained models (e.g., the one introduced by Fredrickson and Andersen Fredrickson-1984) as stochastic models for the liquid–glass transition are intimately related to 𝐾 -core percolation Sellitto-2005; Rizzo-2019; Rizzo-2020; Perrupato-2022. In biology, the 𝐾 -cores of protein-protein interaction networks have been exploited along with phylogenetic analysis to predict the functions of certain proteins Altaf-Ul-Amine-2003, and the innermost 𝐾 -cores are found to be prolific, essential, and evolutionary conserved which might constitute a putative evolutionary backbone of the proteome Stefan-2005. The conscious-to-subliminal transition in the brain was recently studied as a 𝐾 -core percolation process Lucini-2019, and 𝐾 -core decomposition of the brain network suggests that 𝐾 -cores might help protect against cognitive decline in aging Stanford-2022. In ecology, 𝐾 -core is utilized to understand the robustness of bipartite mutualistic networks and to help identify the key species to preserve Garcia-Algarra-2017. In social networks, 𝐾 -core analysis shows that the most efficient spreaders are those located within the most densely connected 𝐾 -core Kitsak-2010. As the 𝐾 -core structure plays important roles in numerous domains, it would be of great interest to perform efficient adversarial attacks to evaluate its robustness and resilience. An interesting optimization goal is to bring the 𝐾 -core to a complete collapse by removing the minimum number of vertices from it. We refer to this minimum-sized vertex set Γ as an optimal attack set.

The collapse transition of kinetic 𝐾 -core induced by random removal of vertices has been studied extensively in the literature Dorogovtsev-2006; Dorogovtsev-2006b; Azimi-Tafreshi-2014; Baxter-2015; Rui-Jie-2022; Zhao-Zhou-Liu-2013; Zhao-2017. The vulnerability and resilience of equilibrium 𝐾 -core configurations were also investigated by statistical physics methods Wang-etal-2020. However, the optimal 𝐾 -core attack problem is much more challenging to investigate, and theoretical and algorithmic studies are still relatively sparse Guggiola-2015; Schmidt-2019; Zhou-2022; Ma-etal-2023. For the special case of 𝐾

2 , the problem is known as the minimum feedback vertex set (or decycling) problem. It is one of the classic nondeterministic polynomial-complete (NP-complete) optimization problems, aiming at destroying all the loops of the graph in the most economical way Karp-1972; Fomin-etal-2008; Sheng-2002. Heuristic algorithms inspired by statistical physics, such as the BPD (belief propagation guided decimation) and the Min-Sum algorithms Zhou-2013; Zhou-2016; Braunstein-2016, have achieved remarkable success on random graph instances. For general 𝐾 , the CoreHD (highest degree in core) algorithm Lenka-2016 servers as a simple and effective strategy which iteratively removes one of the vertices with the highest degree in the remaining 𝐾 -core. The performance of CoreHD was further improved by the WN (weak-neighbor) algorithm Schmidt-2019, which iteratively removes one of the vertices which has high degree but whose neighbors have low degrees. Though very simple, the WN algorithm appears to outperform the more sophisticated local algorithm CI-TM (collective information in threshold models) Sen-2017 and some message-passing algorithms Altarelli-2013; Altarelli-2013b.

The 𝐾 -core attack problem can be understood as an optimal initial condition problem for an irreversible dynamics on a graph Reichman-2012; Amin-2014; Dreyer-2009; Zhang-2017. The local rule of the dynamics is very simple: an inactive vertex will remain inactive (irreversibility), while an active vertex will decay to be inactive if it has less than 𝐾 active nearest neighbors (threshold and nonlinearity). Constructing a minimum set of initially inactive vertices is known to be a NP-complete challenge Dreyer-2009. To study this optimal initial condition problem by statistical physics methods, a straightforward modeling approach is to map the threshold dynamics into a static Potts model with 𝑇 + 1 discrete vertex states 𝑡 𝑖 ∈ { 0 , 1 , ⋯ , 𝑇 } , where 𝑡 𝑖

0 means that vertex 𝑖 is the seed of the dynamics (i.e., it is inactive from the beginning), and 𝑡 𝑖 ≥ 1 means that vertex 𝑖 becomes inactive at the 𝑡 𝑖 -th time step following the local dynamical rule Altarelli-2013; Altarelli-2013b; Zhao-2016. Although this strategy is conceptually simple, it becomes computationally inefficient as the value of maximum time step 𝑇 becomes large (a large 𝑇 value is necessary to guarantee good predictive power). A different modeling strategy was introduced in Ref. Zhou-2022, which viewed the 𝐾 -core collapse dynamics from the static view of cycle-tree packing and compressed all the different time steps 𝑡 𝑖 ≥ 1 into a single layer of the packing model. The associated message-passing algorithm of this packing model is very efficient, yet it was able to achieve better solutions than those obtained by the WN algorithm.

The present work extends the single-layer cycle-tree packing model into a hierarchical multi-layer model, and solves this hierarchical model by the replica-symmetric (RS) cavity method of statistical physics Mezard-2009; Zhou-book-2015. The minimum energy density of the model is evaluated through a set of coarse-grained belief propagation equations, and a message-passing algorithm hCTGA (hierarchical cycle-tree guided attack) is implemented for constructing close-to-optimal 𝐾 -core attack sets. Both the theoretical predictions and the algorithmic results of the new model are more refined in comparison with those of the original single-layer model. With the maximum layer number 𝐻 being only slightly greater than unity (typically 𝐻

3 ), the hCTGA algorithm consistently beats the WN algorithm on all the random graph instances tested in this work. Besides its relevance to the optimal 𝐾 -core attack problem, our hierarchical cycle-tree packing problem has also independent value as a new spin glass model system. The model may be adapted to tackle optimal initial-condition problems for other irreversible dynamical processes on sparse random graphs. It can also help to solve hard random combinatorial optimization problems with a global constraint such as the connected dominating set problem Habibulla-2023.

The next Section 2 will describe the hierarchical cycle-tree packing model in detail and outline the RS mean field theory. Section 3 reports some of the theoretical and algorithmic results obtained on the ensembles of regular random graphs and Erdös-Rényi random graphs and compares them with the results achieved in prior efforts Guggiola-2015; Schmidt-2019; Zhou-2022. We conclude this work in Section 4. The technical details of the coarse-grained belief propagation equations are deferred to the Appendices 5.1–5.6.

Figure 1: Example of hierarchical cycle-tree packing with 𝐻

2 and 𝐾

3 . The three seed vertices at the lowest layer ℎ

0 form the attack set. The edges attached to these seed vertices are drawn as dashed lines. Each normal (non-seed) vertex chooses one of its normal nearest neighbors or itself as the target and this is indicated by an arrow, leading to the formation of a directed tree at layer ℎ

1 and a directed cycle-tree at layer ℎ

2 . 2Model and coarse-grained belief propagation equations

We consider a graph 𝐺 consisting of 𝑁 vertices and 𝑀 undirected edges. The vertices are indexed by positive integers 𝑖 , 𝑗 , … ∈ { 1 , 2 , … , 𝑁 } , and an edge between two vertices 𝑖 and 𝑗 is denoted by ( 𝑖 , 𝑗 ) . The neighborhood of vertex 𝑖 is denoted as ∂ 𝑖 ≡ { 𝑗 : ( 𝑖 , 𝑗 ) ∈ 𝐺 } which contains all of its nearest neighbors, and the cardinality of this set is defined as the degree 𝑑 𝑖 of vertex 𝑖 .

With the optimal 𝐾 -core attack problem in mind, we now introduce a hierarchical cycle-tree packing model for a general graph 𝐺 . There are ( 𝐻 + 1 ) horizontal layers to accommodate all the 𝑁 vertices, and every vertex is allocated to one and only one of these layers (Fig. 1). If vertex 𝑖 stays at the bottom layer with index ℎ

0 , we assign it the state 𝐴 𝑖

0 and say that it is a seed. If vertex 𝑖 stays at one of the remaining layers (whose index ℎ is a positive integer, 1 ≤ ℎ ≤ 𝐻 ), we say that it is a normal vertex. In this latter case, vertex 𝑖 needs to choose one of its normal nearest neighbors as its ‘target’. This target vertex (say 𝑗 ) must also be staying at the same layer ℎ as vertex 𝑖 and furthermore it must not choose 𝑖 as its target. If 𝑗 is the target of 𝑖 , then vertex 𝑖 is said to be a ‘driver’ of vertex 𝑗 . We denote this driver-target relation by adding an arrow pointing from 𝑖 to 𝑗 on the edge ( 𝑖 , 𝑗 ) and say that ‘ 𝑖 points to 𝑗 ’. Since each normal vertex 𝑖 is staying at a specific layer with positive index ℎ and it has a unique target vertex 𝑗 , we assign its state as 𝐴 𝑖

𝑗 ℎ (the superscript ℎ indicates the specific layer). A normal vertex 𝑖 at layer ℎ will choose itself as the target if and only if all its nearest neighbors at the same layer ℎ are pointing to 𝑖 (namely, choosing 𝑖 as the target). The state of 𝑖 in this special situation is defined as 𝐴 𝑖

𝑖 ℎ and vertex 𝑖 is then referred to as a root of layer ℎ (there might be no root or be many roots in one single layer).

Consider all the vertices which are staying at the same positive layer ℎ . Since each of these vertices is pointing to another vertex of this layer or to itself, these vertices together with the arrow-decorated edges will form one or more tree or cycle-tree components (Fig. 1). A tree is a connected subgraph containing 𝑛 vertices and ( 𝑛 − 1 ) edges, while a cycle-tree is a connected subgraph of 𝑛 vertices and 𝑛 edges containing a single loop and some tree branches attached to this loop Zhou-2013; Zhou-2022.

Besides the edges decorated by arrows, there are other edges within each single layer of vertices and between two different layers of vertices. In the example of Fig. 1, these undecorated edges are drawn as solid lines if the vertices at both ends are normal vertices and are drawn as dashed lines if at least one of the end vertices is a seed.

According to the above definitions, each vertex 𝑖 has a Potts state 𝐴 𝑖 which can take [ ( 𝑑 𝑖 + 1 ) ⁢ 𝐻 + 1 ] different values. A microscopic configuration is then an 𝑁 -dimensional vector ( 𝐴 1 , … , 𝐴 𝑁 ) . It is obvious that not all the possible configurations are valid packing configurations. For any vertex 𝑖 , according to the definition of its state 𝐴 𝑖 , we know that it imposes the following restrictions on the state 𝐴 𝑗 of its nearest neighbor 𝑗 :

(a)

If 𝐴 𝑖

0 , then 𝐴 𝑗 ≠ 𝑖 ℎ for any ℎ .

(b)

If 𝐴 𝑖

𝑗 ℎ with ℎ ≥ 1 , then 𝐴 𝑗

𝑗 ℎ or 𝐴 𝑗

𝑘 ℎ with 𝑘 ∈ ∂ 𝑗
𝑖 (here ∂ 𝑗
𝑖 excludes vertex 𝑖 from the vertex set ∂ 𝑗 ).

(c)

If 𝐴 𝑖

𝑖 ℎ with ℎ ≥ 1 , then if 𝐴 𝑗

𝑘 ℎ then the vertex index 𝑘 must be identical to 𝑖 ( 𝑘

𝑖 ).

These three local rules are constraints concerning two neighboring vertices. They ensure that vertices of each positive layer ℎ organize into cycle-tree static patterns. To implement the 𝐾 -core pruning rule in our static model, we also need the following local rule concerning a vertex 𝑖 and all its nearest neighbors:

(d)

If vertex 𝑖 is staying at layer ℎ ≥ 1 (i.e., 𝐴 𝑖

𝑘 ℎ with 𝑘

𝑖 or 𝑘 ∈ ∂ 𝑖 ), the summed number ( 𝑑 1 ) of its nearest neighbors which are staying at layers ℎ ′ ≥ ℎ but are not pointing to 𝑖 must be less than 𝐾 ( 𝑑 1 < 𝐾 ); in addition, if vertex 𝑖 is staying at layer ℎ ≥ 2 , the summed number ( 𝑑 2 ) of its nearest neighbors which are staying at layers ℎ ′′ ≥ ℎ − 1 but are not pointing to 𝑖 must be at least 𝐾 ( 𝑑 2 ≥ 𝐾 ).

Such many-body constraints ensure that after all the seed vertices (which stay at the bottom layer) are deleted from graph 𝐺 , the vertices at tree branches of the next layer ℎ

1 will all be pruned from the graph following the 𝐾 -core local rule. If the closed loop of a cycle-tree survives this pruning process, we can delete a single vertex from this loop to break it down. After all the vertices in layer ℎ

1 are pruned, the vertices in the upper layers ℎ

2 , … , 𝐻 can be pruned consecutively in the same way, leading to the evaporation of the whole 𝐾 -core [Fig. 1].

Let us define the energy of a microscopic configuration as

𝐸 ⁢ ( 𝐴 1 , … , 𝐴 𝑁 )

∑ 𝑖

1 𝑁 𝛿 𝐴 𝑖 0 ,

(1)

which is simply the total number of seed vertices. Here 𝛿 𝑥 𝑦 is the Kronecker symbol such that 𝛿 𝑥 𝑦

1 if 𝑥 and 𝑦 are identical and 𝛿 𝑥 𝑦

0 if otherwise. Let us introduce a constraint factor 𝐶 𝑖 ⁢ ( 𝐴 𝑖 , 𝐴 ¯ ∂ 𝑖 ) for each vertex 𝑖 such that 𝐶 𝑖

1 if the above-mentioned rules (a)–(d) are locally satisfied and 𝐶 𝑖

0 if at least one of them is violated. Here 𝐴 ¯ ∂ 𝑖 ≡ { 𝐴 𝑗 : 𝑗 ∈ ∂ 𝑖 } denotes a composite state of the neighboring vertices 𝑗 of vertex 𝑖 . The explicit expression for the constraint factor 𝐶 𝑖 ⁢ ( 𝐴 𝑖 , 𝐴 ¯ ∂ 𝑖 ) could be written down (see Appendix 5.1). Then the partition function of the model is written as

𝑍 ⁢ ( 𝛽 )

∑ 𝐴 1 , … , 𝐴 𝑁 ∏ 𝑖

1 𝑁 [ 𝑒 − 𝛽 ⁢ 𝛿 𝐴 𝑖 0 ⁢ 𝐶 𝑖 ⁢ ( 𝐴 𝑖 , 𝐴 ¯ ∂ 𝑖 ) ] ,

(2)

where 𝛽 is the inverse temperature parameter. Each seed vertex contributes a penalty factor 𝑒 − 𝛽 to the total Boltzmann weight of a microscopic configuration. The equilibrium probability of observing a specific microscopic configuration is

𝑃 ⁢ ( 𝐴 1 , … , 𝐴 𝑁 )

1 𝑍 ⁢ ( 𝛽 ) ⁢ ∏ 𝑖

1 𝑁 [ 𝑒 − 𝛽 ⁢ 𝛿 𝐴 𝑖 0 ⁢ 𝐶 𝑖 ⁢ ( 𝐴 𝑖 , 𝐴 ¯ ∂ 𝑖 ) ] .

(3)

Because of the 0 / 1 constraint factors 𝐶 𝑖 , only those microscopic configurations which satisfy the local constraints of all the 𝑁 vertices will have nonvanishing contribution to 𝑍 ⁢ ( 𝛽 ) , and this contribution is 𝑒 − 𝛽 ⁢ 𝐸 ⁢ ( 𝐴 1 , … , 𝐴 𝑁 ) . When 𝛽 becomes sufficiently large, the partition function will be contributed almost completely by the minimum-energy cycle-tree packing configurations.

We can solve this hierarchical cycle-tree packing model by the standard RS cavity method of statistical physics. The details of the resulting belief propagation (BP) equations are presented in Appendix 5.2, and the coarse-grained BP equations are presented in Appendix 5.4. A nice property of the coarse-grained BP equations is that there are only five different coarse-grained states at each positive layer ℎ ≥ 1 , for the vector-formed cavity message 𝑄 𝑖 → 𝑗 from a vertex 𝑖 to its nearest neighbor 𝑗 . This property greatly simplifies the numerical computations. Another advantage of this hierarchical cycle-tree packing model is that the maximum layer value 𝐻 does not need to be large. Our empirical experiences suggest that, in algorithmic applications, a value of 𝐻

3 or 𝐻

4 will be sufficient for many large graph instances (see Section 3.2).

If 𝐾

2 , our model reduces to the feedback vertex set model of Ref. Zhou-2013. In this special case the exact value of the layer number 𝐻 becomes irrelevant and we can simply set 𝐻

1 . The reason is simple: For 𝐾

2 , after the removal of all the seed vertices, all the edges between the active vertices will be arrow-decorated, except for the few edges between two root vertices at different layers; these connected root vertices must form tree subgraphs due to the local constraints of our model, so we can add an arrow to each such edge pointing from lower layer to higher layer and reduce the total number of hierarchical level to 𝐻

1 .

When 𝐾 ≥ 3 , the models with different values of 𝐻 are different. If we fix 𝐻

1 , our present model reduces to the single-layer cycle-tree packing model of Ref. Zhou-2022.

3Results 3.1Theoretical predictions for regular random graphs

Each vertex in a regular random (RR) graph is connected to the same integer number 𝐷 of other vertices in the graph. Except for this uniformity of vertex degrees, the connectivity structure of the graph is completely random. Naturally, we assume that the cavity probabilities of the coarse-grained BP equations are independent of the specific edge indices ( 𝑖 , 𝑗 ) . Then the coarse-grained BP equations are simplified into 5 ⁢ 𝐻 − 1 coupled equations, which are listed in Appendix 5.6. We determine the fixed point of this set of self-consistent equations by the Newton-Raphson iterative method, and then compute the ensemble-averaged mean energy density 𝜌 , free energy density 𝑓 , and entropy density 𝑠 as a function of inverse temperature 𝛽 .

Figure 2: Theoretical predictions for the regular random graph ensemble of degree 𝐷

7 at different values of layer number 𝐻 . The 𝐾 -core threshold is 𝐾

3 . (a) Energy density 𝜌 versus inverse temperature 𝛽 . (b) Entropy density 𝑠 versus 𝛽 . (c) Entropy density 𝑠 versus energy density 𝜌 . (d) Minimum energy density 𝜌 min versus the value of 𝐻 . As a comparison, the gray points are the results obtained by the model of Ref. Guggiola-2015 using the maximum time step 𝑇 as the hyperparameter.

Figure 2 summarizes the theoretical results obtained for the RR ensemble of degree 𝐷

7 at threshold value 𝐾

3 . (The results obtained at other values of 𝐷 and 𝐾 ≥ 3 are qualitatively similar.) At each fixed value of level number 𝐻 the mean energy density 𝜌 [Fig. 2] and the entropy density 𝑠 [Fig. 2] both are decreasing functions of inverse temperature 𝛽 . The entropy density reaches zero as 𝛽 increases to certain 𝐻 -dependent value and it then becomes negative as 𝛽 further increases. The curves of 𝑠 versus 𝜌 at different values of 𝐻 are concave in the region of 𝑠 ≥ 0 [Fig. 2]. Negative values of the entropy density indicate that the system enters into the spin glass phase and that the RS mean field theory (which builds on the assumption of only one macroscopic state) is no longer valid at sufficiently low temperatures. Since the true entropy density should be non-negative, within the framework of the RS theory, the value of 𝜌 corresponding to the point of zero entropy density is taken as the predicted minimum energy density and this value is denoted as 𝜌 min . As anticipated, this minimum energy density 𝜌 min saturates rather quickly with 𝐻 [Fig. 2]. The limiting value of 𝜌 min at 𝐻 ≫ 1 offers a theoretical estimate for the relative size of minimum (optimal) 𝐾 -core attack sets. For 𝐷

7 and 𝐾

3 the limiting value of 𝜌 min is ≈ 0.3000 .

For the special case of 𝐾

2 , the thermodynamic quantities computed at different values of 𝐻 ≥ 1 are identical, so the value of 𝜌 min does not depend on 𝐻 . For this special value of 𝐾

2 , the model of the present work and that of Ref. Zhou-2022 reduce to the feedback vertex set model of Ref. Zhou-2013.

From Fig. 2 we see that the biggest drop in the minimum energy density 𝜌 min occurs as 𝐻 changes from the minimum value 𝐻

1 to 𝐻

2 . We also observe that the converging speed of 𝜌 min with level number 𝐻 of the present model is much faster than that of 𝜌 min with the maximum time step 𝑇 of the conventional propagation model Guggiola-2015. The reason behind this speedy convergence is that our hierarchical packing model has the effect of compressing many time steps of the directional 𝐾 -core pruning (propagation) process into a single hierarchical layer. In our model the coarse-grained cavity message on each edge is a vector of dimension ( 5 ⁢ 𝐻 − 1 ) , while the corresponding cavity message of the propagation model is a vector of dimension ( 2 ⁢ 𝑇 − 1 ) .

The minimum relative size of 𝐾 -core attack sets is predicted to be 0.3000897 in Ref. Guggiola-2015 for 𝐾

3 and 𝐷

7 , by taking the 𝑇 → ∞ limit of the propagation model. The predicted value by our present model is slightly lower (the value obtained at 𝐻

16 is 0.3000870 ). For 𝐾

2 , the predicted minimum relative sizes are 𝜌

0.25000 at degree 𝐷

3 , 0.33333 at 𝐷

4 , 0.37837 at 𝐷

5 , 0.42199 at 𝐷

6 and 0.45892 at 𝐷

7 , which are either identical to or slightly below the the corresponding theoretical predictions of Ref. Guggiola-2015 (see the last column of Table 1). These quantitative comparative results confirm that the hierarchical cycle-tree packing model is a good quantitative model for solving the optimal 𝐾 -core attack problem, even though it is not exactly equivalent to the conventional propagation model of Ref. Guggiola-2015.

The quick convergence of 𝜌 min with 𝐻 suggests that we will be able to get close-to-optimal solutions with small values of 𝐻 . We now continue to explore this point in the next subsection.

Algorithm 1 Hierarchical Cycle-Tree Guided Attack (hCTGA). The main hyperparameter is the maximum number 𝐻 of layers and the inverse temperature 𝛽 . The marginal probability 𝑞 𝑖 0 of a vertex 𝑖 belonging to the attack set Γ is estimated through Eq. (37). 1:Read graph 𝐺 with undirected edges and the vertex set 𝑉 2:Initialize coarse-grained BP messages 3:Initialize the attack set Γ

∅ 4:while  𝑉 ≠ ∅  do 5:     Iterate the coarse-grained BP equations for certain repeats 𝑟 6:     Calculate the BP marginals { 𝑞 𝑖 0 ; 𝑖 ∈ 𝑉 } 7:     Choose vertex index 𝑖

arg ⁡ max 𝑗 ⁡ ( 𝑞 𝑗 0 ) 8:     if  rand() < 𝑞 𝑖 0  then 9:         Set Γ ← Γ ∪ { 𝑖 } 10:         Set 𝑉 ← 𝑉
𝑖 11:         Set 𝐺 ← 𝐾 ⁢ -core ⁢ ( 𝐺 ) 12:     end if 13:end while 14:Return the final attack set Γ 3.2Algorithmic results

We run the coarse-grained belief propagation equations (listed in Appendix 5.4) on single graph instances 𝐺 to estimate the marginal probabilities 𝑞 𝑖 0 of being the seed for all the vertices 𝑖 [see Eq. (37)]. When the inverse temperature 𝛽 is relatively large, the value of 𝑞 𝑖 0 offers valuable information about the probability of vertex 𝑖 belonging to an optimal 𝐾 -core attack set. Following the earlier attempt in Ref. Zhou-2022, here we implement a hierarchical cycle-tree guided attack algorithm to construct a close-to-minimum 𝐾 -core attack set Γ by sequentially adding vertices to this set under the guidance of the 𝑞 𝑖 0 marginal probabilities. The pseudo-code is listed in Algorithm 1, where rand( ) means a random number generator returning a uniformly distributed real value 𝑥 ∈ ( 0 , 1 ) , and 𝐾 ⁢ -core ⁢ ( 𝐺 ) means returning the 𝐾 -core of a graph 𝐺 . The time complexity of this algorithm is approximately 𝑂 ⁢ ( 𝑟 ⁢ 𝐻 ⁢ 𝑁 2 ) , where 𝑟 is the number of repeats of the coarse-grained BP iterations at each decimation step (we simply fix 𝑟

1 in our numerical experiments, without waiting for the convergence of the BP iterations). The time complexity could be further reduced to be 𝑂 ⁢ ( 𝑟 ⁢ 𝐻 ⁢ 𝑁 ) if we fix a small fraction of the remaining vertices at each decimation step instead of fixing only a single vertex Zhou-2022.

The performance of hCTGA has a slight dependence on the inverse temperature and it works best at intermediate 𝛽 values [Fig. 3]. The non-monotonic ‘V’ shape of 𝜌 versus 𝛽 may be due to two competing factors. On the one hand, increasing 𝛽 is beneficial for sampling low-energy configurations; but on the other hand, when 𝛽 becomes large, the system enters the spin glass phase with broken ergodicity and strong frustration. Since the optimal value of 𝛽 might be different for different graph instances, for a given graph 𝐺 , we run the hCTGA algorithm over a range of inverse temperature values and report the minimum-sized attack set Γ out of these independent runs.

Figure 3: Sensitivity of the results of the hCTGA algorithm on the inverse temperature 𝛽 and on the number 𝑁 of vertices in the graph. The mean values averaged over 12 regular random graph instances of degree 𝐷 and size 𝑁 are shown, and the error bars indicate standard error of the mean. The maximum number 𝐻 of layers is fixed to 𝐻

3 . (a) Relative size 𝜌 of constructed attack set versus 𝛽 on graphs of size 𝑁

10 , 000 and degree 𝐷

6 with threshold value 𝐾

5 . (b) Relative size 𝜌 versus graph size 𝑁 , obtained on graphs of degree 𝐷

4 with threshold value 𝐾

3 and 𝛽

23 . The algorithmic results obtained by the WN algorithm Schmidt-2019 are also shown as a comparison.

We also observe that the performance of hCTGA improves as the graph size 𝑁 increases [Fig. 3]. This trend may be a manifest of the fact that the mean-field theory behind this algorithm becomes more precise when the typical length of the short loops in the graph increases.

𝐷
𝐾 hCTGA WN prediction 3 2 0.2501 0.2503 0.25000 4 2 0.3335 0.3378 0.33333 3 0.0718 0.0747 0.04628 5 2 0.3793 0.3964 0.37847 3 0.1877 0.1878 0.16668 4 0.0264 0.0281 0.01311 6 2 0.4252 0.4444 0.42262 3 0.2621 0.2649 0.25000 4 0.1075 0.1085 0.07623 5 0.0128 0.0138 0.00572 7 2 0.4641 0.4836 0.46001 3 0.3115 0.3209 0.30009 4 0.1801 0.1817 0.15005 5 0.0691 0.0694 0.04283 6 0.0075 0.0080 0.00310 Table 1: Algorithmic results on the relative size of 𝐾 -core attack set, obtained by the hCTGA and the WN Schmidt-2019 algorithms on regular random graphs of degree 𝐷 . The hyperparameter 𝐻 of hCTGA is 𝐻

3 except for the case 𝐷

7 , 𝐾

4 where it is 𝐻

4 . The algorithmic results are averaged over 12 independent runs on a single graph instance containing 𝑁

10 , 000 vertices. The last column list the minimum relative size of 𝐾 -core attack sets as predicted by the replica-symmetric mean field theory of Ref. Guggiola-2015. D K hCTGA WN 3 2 0.1353 0.1394 4 2 0.2138 0.2198 3 0.0345 0.0357 5 2 0.2790 0.2874 3 0.1016 0.1019 6 2 0.3343 0.3438 3 0.1630 0.1645 4 0.0419 0.0433 7 2 0.3808 0.3907 3 0.2180 0.2196 4 0.0976 0.0987 5 0.0069 0.0083 Table 2: Algorithmic results on the relative size of the 𝐾 -core attack set, obtained by the hCTGA and the WN Schmidt-2019 algorithms on Erdös-Rényi random graphs of mean degree 𝐷 and size 𝑁

10 , 000 . The hyperparameter 𝐻 of hCTGA is fixed to 𝐻

3 . Each data is the mean value averaged over 12 random graph instances.

The algorithmic results of hCTGA on single regular random graph instances are displayed in Table 1. The layer number is typically set as 𝐻

3 to reduce computational cost. As a comparison we also list the results obtained by the WN algorithm of Ref. Schmidt-2019 and the theoretical predictions of Ref. Guggiola-2015. The hCTGA algorithm outperforms the WN algorithm in all the studied graph instances. The hCTGA algorithmic results are close to but yet still noticeably exceeding the predicted minimum values. (The performance of hCTGA can be further enhanced by increasing 𝐻 , at the cost of an increase in computational time.)

We also run hCTGA on Erös-Rényi random graphs. Such graphs are characterized by a single real-valued parameter, the mean degree 𝐷 . The ( 𝐷 / 2 ) ⁢ 𝑁 edges of the graph are chosen uniformly at random out of the 𝑁 ⁢ ( 𝑁 − 1 ) / 2 possible edges. As the results of Table 2 demonstrate, our hCTGA algorithm (with 𝐻

3 ) again outperforms WN on this these random graph instances.

4Conclusion and discussion

The optimal 𝐾 -core attack problem is a prototypical optimization and control task. It is about assigning an optimal initial condition for an irreversible dynamical process to achieve an objective final state many time steps later. In this paper, we generalized the cycle-tree packing model with only a single layer of normal (non-seed) vertices ( 𝐻

1 ) Zhou-2022 to the hierarchical version containing multiple layers of normal vertices ( 𝐻 ≥ 2 ), to better address the optimal 𝐾 -core attack problem. We solved this hierarchical cycle-tree packing model by the replica-symmetric mean field theory of spin glass physics, and implemented a message-passing algorithm hCTGA to tackle single graph instances. For regular random graphs, the theoretically predicted minimum energy density of this model decreases with the number 𝐻 of layers and converges to an asymptotic value as 𝐻 becomes large. The hCTGA algorithm has good performance on regular random graphs and Erdös-–Rényi random graphs, outperforming the original CTGA algorithm with 𝐻

1  Zhou-2022 and the simple and striking WN heuristic algorithm Schmidt-2019.

The hierarchical cycle-tree packing model is a new member in the zoo of spin glass models. It offered a new perspective on the 𝐾 -core collapse process. The central idea is to represent irreversible 𝐾 -core pruning dynamics by the static and hierarchical cycle-trees patterns in the graph. This strategy of transforming a long-range time-correlated dynamical process into static structural patterns may also be promising for some other hard optimization problems, such as the generalized 𝐾 -core percolation problem on directed graphs Zhao-2017, the directed feedback vertex set and arc set problems Zhou-2016; Xu-2017, and the 𝐾 -core attack by deleting edges ZhouBo-2021. In our model, the hierarchical level ℎ 𝑖 of each vertex 𝑖 is determined by the optimization goal of achieving a percolation of threshold nonlinear dynamics with the minimum initial driving effort. For biological networked systems such as the brain Lucini-2019; Wang-2023, the observed hierarchical organizations in the network might be the result of natural selection over evolutionary time scales. Our hierarchical cycle-tree packing model may also be useful for detecting the hidden hierarchical organization in complex dynamical systems.

In the present work, we carried out the theoretical analysis only at the replica-symmetric level but not at the replica-symmetry-broken levels. The first-step replica-symmetry-breaking mean field theoretical investigation is surely needed to better understand the low-energy landscape of this hierarchical packing model. We expect that the theoretical results will be more precise if the competition effect among different spin glass macroscopic states is taken into account. There are other ways to improve the hCTGA algorithm, such as adjusting the value of the inverse temperature 𝛽 at each step of the decimation process, and improving the convergence of the belief propagation iteration dynamics. It will also be interesting to construct the max-sum algorithm Altarelli-2013; Altarelli-2013b, which considers the limit 𝛽 → ∞ , and to adapt the reinforcement technique Altarelli-2013; Altarelli-2013b, which uses the noisy information in updating the max-sum equations to force the system to converge to higher energy values. We leave such algorithmic issues for future explorations in combination with practical applications.

5Appendix 5.1 The constraint factor 𝐶 𝑖 associated with vertex 𝑖

Each vertex 𝑖 brings a local constraint to its state 𝐴 𝑖 and the states 𝐴 ¯ ∂ 𝑖 of all its nearest neighbors. Here we describe this constraint in some detail.

(1) If vertex 𝑖 is seed ( 𝐴 𝑖

0 ), its neighbors are prohibited from pointing to it. Then the constraint factor 𝐶 𝑖 is

𝐶 𝑖 ⁢ ( 0 , 𝐴 ¯ ∂ 𝑖 )

∏ 𝑗 ∈ ∂ 𝑖 ( 𝛿 𝐴 𝑗 0 + ∑ ℎ

1 𝐻 [ 𝛿 𝐴 𝑗 𝑗 ℎ + ∑ 𝑙 ∈ ∂ 𝑗
𝑖 𝛿 𝐴 𝑗 𝑙 ℎ ] ) ,

(4)

where ∂ 𝑗
𝑖 contains all the nearest neighbors of vertex 𝑗 , except for vertex 𝑖 . Notice that 𝐶 𝑖

0 if 𝐴 𝑗

𝑖 ℎ for any 𝑗 ∈ ∂ 𝑖 and any ℎ ≥ 1 , otherwise 𝐶 𝑖

1 .

(2) If vertex 𝑖 is a root at layer ℎ

1 ( 𝐴 𝑖

𝑖 1 ), then a nearest neighbor 𝑗 of this vertex is either a seed ( 𝐴 𝑗

0 ) or it is staying at the same layer and is pointing to it ( 𝐴 𝑗

𝑖 1 ), or it is staying at a higher layer ℎ ≥ 2 . The total number of nearest neighbors staying at the higher layers must be less than 𝐾 . Then we can write down the following expression

𝐶 𝑖 ⁢ ( 𝑖 1 , 𝐴 ¯ ∂ 𝑖 )

∏ 𝑗 ∈ ∂ 𝑖 [ 𝛿 𝐴 𝑗 0 + 𝛿 𝐴 𝑗 𝑖 1 + ∑ ℎ

2 𝐻 ( 𝛿 𝐴 𝑗 𝑗 ℎ + ∑ 𝑙 ∈ ∂ 𝑗
𝑖 𝛿 𝐴 𝑗 𝑙 ℎ ) ] ×

(5)

Θ ⁢ ( 𝐾 − 1 − ∑ 𝑘 ∈ ∂ 𝑖 ∑ ℎ

2 𝐻 ( 𝛿 𝐴 𝑘 𝑘 ℎ + ∑ 𝑙 ∈ ∂ 𝑘
𝑖 𝛿 𝐴 𝑘 𝑙 ℎ ) ) ,

where the Heaviside step function Θ ⁢ ( 𝑥 )

1 if 𝑥 ≥ 0 and otherwise Θ ⁢ ( 𝑥 )

0 .

(3) If vertex 𝑖 is staying at layer ℎ

1 and is pointing to vertex 𝑗 ( 𝐴 𝑖

𝑗 1 ), then vertex 𝑗 must also be staying at the same layer and it must not be pointing to 𝑖 . The total number of other nearest neighbors 𝑘 of vertex 𝑖 which are staying at higher layers or which are staying at the same layer but are not pointing to 𝑖 must be most 𝐾 − 2 . Then

𝐶 𝑖 ( 𝑗 1 , 𝐴 ¯ ∂ 𝑖 )

( 𝛿 𝐴 𝑗 𝑗 1 + ∑ 𝑙 ∈ ∂ 𝑗
𝑖 𝛿 𝐴 𝑗 𝑙 1 ) ×

∏ 𝑘 ∈ ∂ 𝑖
𝑗 [ 𝛿 𝐴 𝑘 0 + 𝛿 𝐴 𝑘 𝑖 1 + ∑ 𝑙 ∈ ∂ 𝑘
𝑖 𝛿 𝐴 𝑘 𝑙 1 + ∑ ℎ

2 𝐻 ( 𝛿 𝐴 𝑘 𝑘 ℎ + ∑ 𝑙 ∈ ∂ 𝑘
𝑖 𝛿 𝐴 𝑘 𝑙 ℎ ) ] ×

Θ ⁢ ( 𝐾 − 2 − ∑ 𝑚 ∈ ∂ 𝑖
𝑗 [ ∑ 𝑛 ∈ ∂ 𝑚
𝑖 𝛿 𝐴 𝑚 𝑛 1 + ∑ ℎ

2 𝐻 ( 𝛿 𝐴 𝑚 𝑚 ℎ + ∑ 𝑛 ∈ ∂ 𝑚
𝑖 𝛿 𝐴 𝑚 𝑛 ℎ ) ] ) .

(6)

(4) If vertex 𝑖 is a root at layer ℎ ≥ 2 , then all its nearest neighbors at this same layer must be pointing to 𝑖 . The total number of its nearest neighbors staying at layers 𝑡 ≥ ( ℎ − 1 ) must be at least 𝐾 , while the total number of its nearest neighbors staying at layers 𝑠 ≥ ( ℎ + 1 ) must be less than 𝐾 . Therefore for 2 ≤ ℎ ≤ 𝐻 , we have

𝐶 𝑖 ( 𝑖 ℎ , 𝐴 ¯ ∂ 𝑖 )

∏ 𝑗 ∈ ∂ 𝑖 [ 𝛿 𝐴 𝑗 0 + 𝛿 𝐴 𝑗 𝑖 ℎ + ∑ 𝑡 ≠ ℎ ( 𝛿 𝐴 𝑗 𝑗 𝑡 + ∑ 𝑙 ∈ ∂ 𝑗
𝑖 𝛿 𝐴 𝑗 𝑙 𝑡 ) ] ×

Θ ( ∑ 𝑘 ∈ ∂ 𝑖 [ 𝛿 𝐴 𝑘 𝑖 ℎ + ∑ 𝑡

ℎ 𝛿 𝐴 𝑘 𝑘 𝑡 + ∑ 𝑙 ∈ ∂ 𝑘
𝑖 ( 𝛿 𝐴 𝑘 𝑙 ℎ − 1 + ∑ 𝑡

ℎ 𝛿 𝐴 𝑘 𝑙 𝑡 ) ] − 𝐾 ) ×

Θ ⁢ ( 𝐾 − 1 − ∑ 𝑘 ∈ ∂ 𝑖 ∑ 𝑡

ℎ [ 𝛿 𝐴 𝑘 𝑘 𝑡 + ∑ 𝑙 ∈ ∂ 𝑘
𝑖 𝛿 𝐴 𝑘 𝑙 𝑡 ] ) .

(7)

(5) If vertex 𝑖 is staying at layer ℎ ≥ 2 and it is pointing to vertex 𝑗 , then vertex 𝑗 must also be staying at layer ℎ and all the other nearest neighbors 𝑘 of vertex 𝑖 must not be a root of layer ℎ ( 𝐴 𝑘 ≠ 𝑘 ℎ ) or be taking the states 𝐴 𝑘

𝑖 𝑡 with 𝑡 ≠ ℎ (because such states are meaningless when vertex 𝑖 is staying at layer ℎ ). The total number of nearest neighbors of vertex 𝑖 staying at layers 𝑡 ≥ ℎ − 1 must be at least 𝐾 , while the total number of nearest neighbors staying at layers 𝑠

ℎ must be at most 𝐾 − 2 . The corresponding expression for 𝐶 𝑖 is

𝐶 𝑖 ( 𝑗 ℎ , 𝐴 ¯ ∂ 𝑖 )

( 𝛿 𝐴 𝑗 𝑗 ℎ + ∑ 𝑙 ∈ ∂ 𝑗
𝑖 𝛿 𝐴 𝑗 𝑙 ℎ ) × ∏ 𝑘 ∈ ∂ 𝑖
𝑗 ( 1 − 𝛿 𝐴 𝑘 𝑘 ℎ − ∑ 𝑡 ≠ ℎ 𝛿 𝐴 𝑘 𝑖 𝑡 ) ×

Θ ( ∑ 𝑙 ∈ ∂ 𝑖
𝑗 [ 𝛿 𝐴 𝑙 𝑖 ℎ + ∑ 𝑡

ℎ 𝛿 𝐴 𝑙 𝑙 𝑡 + ∑ 𝑡 ≥ ℎ − 1 ∑ 𝑚 ∈ ∂ 𝑙
𝑖 𝛿 𝐴 𝑙 𝑚 𝑡 ] + 1 − 𝐾 ) ×

Θ ⁢ ( 𝐾 − 2 − ∑ 𝑙 ∈ ∂ 𝑖
𝑗 [ ∑ 𝑡

ℎ 𝛿 𝐴 𝑙 𝑙 𝑡 + ∑ 𝑡 ≥ ℎ ∑ 𝑚 ∈ ∂ 𝑙
𝑖 𝛿 𝐴 𝑙 𝑚 ℎ ] ) .

(8) 5.2 Belief propagation equations

We apply the standard cavity method of statistical physics Mezard-2009; Zhou-book-2015 to the hierarchical cycle-tree packing model. By following the same procedure of Refs. Zhou-2016; Altarelli-2013, the self-consistent belief propagation equations can be derived. Because the constraint factors 𝐶 𝑖 and 𝐶 𝑗 of two nearest neighboring vertices 𝑖 and 𝑗 both involve 𝐴 𝑖 and 𝐴 𝑗 , it is most convenient to define for each ( 𝑖 , 𝑗 ) a composite state ( 𝐴 𝑖 , 𝐴 𝑗 ) . Then the original graph 𝐺 can be mapped to a factor graph of variable nodes and factor nodes. Each variable node corresponds to an edge ( 𝑖 , 𝑗 ) , it has a composite state ( 𝐴 𝑖 , 𝐴 𝑗 ) , and it is drawn as an ellipse in the factor graph (Fig. 4). Each factor node corresponds to the constraint 𝐶 𝑖 of a vertex 𝑖 , it is drawn as a square and it connects to the variable nodes representing the edges ( 𝑖 , 𝑗 ) with 𝑗 ∈ ∂ 𝑖 .

Figure 4: Factor-graph representation for deriving the mean field equations. (top) Vertices and edges in the original graph 𝐺 , with ∂ 𝑖

{ 𝑗 , 𝑘 , 𝑙 } and ∂ 𝑗

{ 𝑖 , 𝑚 , 𝑛 } . (bottom) Variable nodes and factor nodes in the factor graph. Each variable node corresponds to an edge of graph 𝐺 , and each factor node corresponds to the local constraint induced by a vertex of graph 𝐺 . Notice that each variable node is linked to exactly two factor nodes.

We denote by 𝑞 𝑖 → 𝑗 ⁢ ( 𝐴 𝑖 , 𝐴 𝑗 ) the cavity marginal (or belief), the marginal probability of composite state ( 𝐴 𝑖 , 𝐴 𝑗 ) in the absence of the constraint factor 𝐶 𝑗 . The BP equations on the factor graph are written down as

𝑞 𝑖 → 𝑗 ⁢ ( 𝐴 𝑖 , 𝐴 𝑗 )

1 𝑧 𝑖 → 𝑗 ⁢ ∑ 𝐴 ¯ ∂ 𝑖
𝑗 𝑒 − 𝛽 ⁢ 𝛿 𝐴 𝑖 0 ⁢ 𝐶 𝑖 ⁢ ( 𝐴 𝑖 , 𝐴 ¯ ∂ 𝑖 ) ⁢ ∏ 𝑘 ∈ ∂ 𝑖
𝑗 𝑞 𝑘 → 𝑖 ⁢ ( 𝐴 𝑘 , 𝐴 𝑖 ) ,

(9)

where 𝑧 𝑖 → 𝑗 is a normalization constant to ensure that ∑ 𝐴 𝑖 , 𝐴 𝑗 𝑞 𝑖 → 𝑗 ⁢ ( 𝐴 𝑖 , 𝐴 𝑗 )

1 , and the composite state 𝐴 ¯ ∂ 𝑖
𝑗 ≡ { 𝐴 𝑘 : 𝑘 ∈ ∂ 𝑖
𝑗 } contains the states 𝐴 𝑘 of all the nearest neighbors 𝑘 of vertex 𝑖 , except for that of vertex 𝑗 . The marginal probability of the state 𝐴 𝑖 of vertex 𝑖 can be calculated as

𝑞 𝑖 𝐴 𝑖

1 𝑧 𝑖 ⁢ ∑ 𝐴 ¯ ∂ 𝑖 𝑒 − 𝛽 ⁢ 𝛿 𝐴 𝑖 0 ⁢ 𝐶 𝑖 ⁢ ( 𝐴 𝑖 , 𝐴 ¯ ∂ 𝑖 ) ⁢ ∏ 𝑘 ∈ ∂ 𝑖 𝑞 𝑘 → 𝑖 ⁢ ( 𝐴 𝑘 , 𝐴 𝑖 ) ,

(10)

where 𝑧 𝑖 is again a normalization constant, and 𝐴 ¯ ∂ 𝑖 ≡ { 𝐴 𝑗 : 𝑗 ∈ ∂ 𝑖 } .

The mean energy density 𝜌 , which is simply the mean fraction of seed vertices 𝑖 (with state 𝐴 𝑖

0 ), is computed through

𝜌

1 𝑁 ⁢ ∑ 𝑖 𝑞 𝑖 0 .

(11)

The marginal probability of the composite state ( 𝐴 𝑖 , 𝐴 𝑗 ) of an edge (a variable node of the factor graph, Fig. 4) is evaluated through

𝑞 𝑖 ⁢ 𝑗 ⁢ ( 𝐴 𝑖 , 𝐴 𝑗 )

1 𝑧 𝑖 ⁢ 𝑗 ⁢ 𝑞 𝑖 → 𝑗 ⁢ ( 𝐴 𝑖 , 𝐴 𝑗 ) ⁢ 𝑞 𝑗 → 𝑖 ⁢ ( 𝐴 𝑗 , 𝐴 𝑖 ) ,

(12)

with normalization constant 𝑧 𝑖 ⁢ 𝑗 . The free energy density 𝑓 of the system is computed through

𝑓

− 1 𝑁 ⁢ 𝛽 ⁢ ∑ 𝑖 𝑁 ln ⁡ 𝑧 𝑖 + 1 𝑁 ⁢ 𝛽 ⁢ ∑ ( 𝑖 , 𝑗 ) ∈ 𝐺 ln ⁡ 𝑧 𝑖 ⁢ 𝑗 .

(13)

The entropy density 𝑠 at each value of the inverse temperature 𝛽 is simply computed by

𝑠

𝛽 ⁢ ( 𝜌 − 𝑓 ) .

(14)

After we obtain the values of 𝜌 and 𝑠 at different values of 𝛽 , we can obtain the relationship of 𝑠 versus 𝜌 , which quantifies the abundance of packing configurations at each fraction of seed vertices. The entropy density needs to be non-negative.

5.3The coarse-grained cavity probabilities

It turns out the BP equations can be simplified considerably by focusing on coarse-grained cavity probabilities. Based on a careful analysis of the BP equations, here we define these coarse-grained probabilities as follows. First for the seed layer ℎ

0 , we define

𝑄 𝑖 → 𝑗 0 ≡ 1 1 + 𝐻 ⁢ 𝑑 𝑗 ⁢ [ 𝑞 𝑖 → 𝑗 ⁢ ( 0 , 0 ) + ∑ ℎ

1 𝐻 [ 𝑞 𝑖 → 𝑗 ⁢ ( 0 , 𝑗 ℎ ) + ∑ 𝑙 ∈ ∂ 𝑗
𝑖 𝑞 𝑖 → 𝑗 ⁢ ( 0 , 𝑙 ℎ ) ] ] .

(15)

Here 𝑑 𝑗 is the degree of vertex 𝑗 . We could interpret 𝑄 𝑖 → 𝑗 0 as the marginal probability of vertex 𝑖 being a seed in the absence of the constraint factor 𝐶 𝑗 .

Second, for the lowest active layer ℎ

1 , we define the probabilities 𝑄 𝑖 → 𝑗 𝑥 , ℎ

1 with inter index 𝑥 ∈ { 1 , … , 5 } as

𝑄 𝑖 → 𝑗 1 , 1

≡

1 2 ⁢ [ 𝑞 𝑖 → 𝑗 ⁢ ( 𝑖 1 , 0 ) + 𝑞 𝑖 → 𝑗 ⁢ ( 𝑖 1 , 𝑖 1 ) + ∑ 𝑘 ∈ ∂ 𝑖
𝑗 [ 𝑞 𝑖 → 𝑗 ⁢ ( 𝑘 1 , 0 ) + 𝑞 𝑖 → 𝑗 ⁢ ( 𝑘 1 , 𝑖 1 ) ] ] ,

𝑄 𝑖 → 𝑗 2 , 1

≡

0 ,

(17)

𝑄 𝑖 → 𝑗 3 , 1
≡
1 ( 𝐻 − 1 ) ⁢ 𝑑 𝑗 ⁢ ∑ 𝑡

2 𝐻 [ 𝑞 𝑖 → 𝑗 ⁢ ( 𝑖 1 , 𝑗 𝑡 ) + ∑ 𝑙 ∈ ∂ 𝑗
𝑖 𝑞 𝑖 → 𝑗 ⁢ ( 𝑖 1 , 𝑙 𝑡 ) ] ,

(18)

𝑄 𝑖 → 𝑗 4 , 1

≡

1 𝑑 𝑗 ⁢ [ 𝑞 𝑖 → 𝑗 ⁢ ( 𝑗 1 , 𝑗 1 ) + ∑ 𝑙 ∈ ∂ 𝑗
𝑖 𝑞 𝑖 → 𝑗 ⁢ ( 𝑗 1 , 𝑙 1 ) ] ,

(19)

𝑄 𝑖 → 𝑗 5 , 1

1 𝐻 ⁢ 𝑑 𝑗 − 1 ⁢ ∑ 𝑘 ∈ ∂ 𝑖
𝑗 [ ∑ 𝑡

2 𝐻 𝑞 𝑖 → 𝑗 ⁢ ( 𝑘 1 , 𝑗 𝑡 ) + ∑ 𝑡

1 𝐻 ∑ 𝑙 ∈ ∂ 𝑗
𝑖 𝑞 𝑖 → 𝑗 ⁢ ( 𝑘 1 , 𝑙 𝑡 ) ] .

(20)

We see that 𝑄 𝑖 → 𝑗 1 , 1 corresponds to the situation of vertex 𝑖 staying in layer ℎ

1 and vertex 𝑗 being a seed or being targeted at 𝑖 ; 𝑄 𝑖 → 𝑗 3 , 1 corresponds to vertex 𝑖 being a root of layer ℎ

1 and vertex 𝑗 staying at a higher layer; 𝑄 𝑖 → 𝑗 4 , 1 corresponds to vertex 𝑖 staying at layer ℎ

1 and pointing to vertex 𝑗 of the same layer; and 𝑄 𝑖 → 𝑗 5 , 1 corresponds to the situation of vertex 𝑖 pointing to a nearest neighbor 𝑘 other than 𝑗 and vertex 𝑗 staying at a higher layer or being staying at the same layer ℎ

1 but are not pointing to 𝑖 .

Third, for all the upper active layers with ℎ

2 , … , 𝐻 , we define

𝑄 𝑖 → 𝑗 1 , ℎ

1 ( ℎ − 2 ) ⁢ 𝑑 𝑗 + 2 [ 𝑞 𝑖 → 𝑗 ( 𝑖 ℎ , 0 ) + ∑ 𝑘 ∈ ∂ 𝑖
𝑗 𝑞 𝑖 → 𝑗 ( 𝑘 ℎ , 0 )

(21)

• ∑ 𝑡

  1 ℎ − 1 [ 𝑞 𝑖 → 𝑗 ⁢ ( 𝑖 ℎ , 𝑗 𝑡 )

• ∑ 𝑘 ∈ ∂ 𝑖
  𝑗 𝑞 𝑖 → 𝑗 ⁢ ( 𝑘 ℎ , 𝑗 𝑡 ) ]

• ∑ 𝑡 ≥ 1 ℎ − 2 ∑ 𝑙 ∈ ∂ 𝑗
  𝑖 [ 𝑞 𝑖 → 𝑗 ( 𝑖 ℎ , 𝑙 𝑡 )

• ∑ 𝑘 ∈ ∂ 𝑖
  𝑗 𝑞 𝑖 → 𝑗 ( 𝑘 ℎ , 𝑙 𝑡 ) ] ] ,

𝑄 𝑖 → 𝑗 2 , ℎ

1 𝑑 𝑗 [ 𝑞 𝑖 → 𝑗 ( 𝑖 ℎ , 𝑖 ℎ ) + ∑ 𝑙 ∈ ∂ 𝑗
𝑖 𝑞 𝑖 → 𝑗 ( 𝑖 ℎ , 𝑙 ℎ − 1 )

(22)

• ∑ 𝑘 ∈ ∂ 𝑖
  𝑗 [ 𝑞 𝑖 → 𝑗 ( 𝑘 ℎ , 𝑖 ℎ )
• ∑ 𝑙 ∈ ∂ 𝑗
  𝑖 𝑞 𝑖 → 𝑗 ( 𝑘 ℎ , 𝑙 ℎ − 1 ) ] ] ,

𝑄 𝑖 → 𝑗 3 , ℎ

1 ( 𝐻 − ℎ ) ⁢ 𝑑 𝑗 ⁢ ∑ 𝑡

ℎ + 1 𝐻 [ 𝑞 𝑖 → 𝑗 ⁢ ( 𝑖 ℎ , 𝑗 𝑡 ) + ∑ 𝑙 ∈ ∂ 𝑗
𝑖 𝑞 𝑖 → 𝑗 ⁢ ( 𝑖 ℎ , 𝑙 𝑡 ) ] ,

(23)

𝑄 𝑖 → 𝑗 4 , ℎ

1 𝑑 𝑗 ⁢ [ 𝑞 𝑖 → 𝑗 ⁢ ( 𝑗 ℎ , 𝑗 ℎ ) + ∑ 𝑙 ∈ ∂ 𝑗
𝑖 𝑞 𝑖 → 𝑗 ⁢ ( 𝑗 ℎ , 𝑙 ℎ ) ] ,

(24)

𝑄 𝑖 → 𝑗 5 , ℎ

1 ( 𝐻 − ℎ + 1 ) ⁢ 𝑑 𝑗 − 1 ∑ 𝑘 ∈ ∂ 𝑖
𝑗 [ ∑ 𝑡

ℎ + 1 𝐻 𝑞 𝑖 → 𝑗 ( 𝑘 ℎ , 𝑗 𝑡 )

(25)

• ∑ 𝑡

  ℎ 𝐻 ∑ 𝑙 ∈ ∂ 𝑗
  𝑖 𝑞 𝑖 → 𝑗 ( 𝑘 ℎ , 𝑙 𝑡 ) ] .

The summed probability ( 𝑄 𝑖 → 𝑗 1 , ℎ + 𝑄 𝑖 → 𝑗 2 , ℎ ) corresponds to the situation of vertex 𝑖 staying at layer ℎ , and vertex 𝑗 staying at a lower layer 𝑡 (with 0 ≤ 𝑡 ≤ ℎ − 1 ) or staying the same layer ℎ and pointing to vertex 𝑘 ; 𝑄 𝑖 → 𝑗 2 , ℎ corresponds to vertex 𝑖 staying at layer ℎ and vertex 𝑗 pointing to 𝑖 or being staying at the layer 𝑡 immediately below ( 𝑡

( ℎ − 1 ) ); 𝑄 𝑖 → 𝑗 3 , ℎ corresponds to vertex 𝑖 being a root of layer ℎ and vertex 𝑗 staying at a higher layer; 𝑄 𝑖 → 𝑗 4 , ℎ corresponds to vertex 𝑖 staying at layer ℎ and pointing to vertex 𝑗 of the same layer; and 𝑄 𝑖 → 𝑗 5 , ℎ corresponds to the situation of vertex 𝑖 staying at layer ℎ and pointing to a nearest neighbor 𝑘 other than 𝑗 and vertex 𝑗 staying at a higher layer 𝑡 or staying at the same layer ℎ but are not pointing to 𝑖 .

5.4 The coarse-grained belief propagation equations

Based on the BP equation (9) for the 𝑞 𝑖 → 𝑗 ⁢ ( 𝐴 𝑖 , 𝐴 𝑗 ) probabilities, we can derive the BP equations for the coarse-grained 𝑄 𝑖 → 𝑗 0 and 𝑄 𝑖 → 𝑗 𝑥 , ℎ probabilities. We list these coarse-grained BP message-passing equations here.

First, for the seed layer ℎ

0 , the self-consistent equation is

𝑄 𝑖 → 𝑗 0

1 𝑧 𝑖 → 𝑗 ⁢ 𝑒 − 𝛽 ⁢ ∏ 𝑘 ∈ ∂ 𝑖
𝑗 [ 𝑄 𝑘 → 𝑖 0 + 𝑄 𝑘 → 𝑖 1 , 1 + ∑ ℎ

2 𝐻 𝑄 𝑘 → 𝑖 1 , ℎ ] .

(26)

Second, for the next lowest layer ℎ

1 , besides the trivial expression 𝑄 𝑖 → 𝑗 2 , 1

0 , we have

𝑄 𝑖 → 𝑗 1 , 1

1 𝑧 𝑖 → 𝑗 ⁢ [ 𝐺 𝑖 1 ⁢ ( 𝐾 − 1 , ∂ 𝑖
𝑗 ) + ∑ 𝑘 ∈ ∂ 𝑖
𝑗 𝑄 𝑘 → 𝑖 1 , 1 ⁢ 𝐺 𝑖 2 ⁢ ( 𝐾 − 2 , ∂ 𝑖
{ 𝑗 , 𝑘 } ) ] ,

(27a)

𝑄 𝑖 → 𝑗 3 , 1

1 𝑧 𝑖 → 𝑗 ⁢ 𝐺 𝑖 1 ⁢ ( 𝐾 − 2 , ∂ 𝑖
𝑗 ) ,

(27b)

𝑄 𝑖 → 𝑗 4 , 1

1 𝑧 𝑖 → 𝑗 ⁢ 𝐺 𝑖 2 ⁢ ( 𝐾 − 2 , ∂ 𝑖
𝑗 ) ,

(27c)

𝑄 𝑖 → 𝑗 5 , 1

1 𝑧 𝑖 → 𝑗 ⁢ ∑ 𝑘 ∈ ∂ 𝑖
𝑗 𝑄 𝑘 → 𝑖 1 , 1 ⁢ 𝐺 𝑖 2 ⁢ ( 𝐾 − 3 , ∂ 𝑖
{ 𝑗 , 𝑘 } ) .

(27d)

In the above iterative equations, the function 𝐺 𝑖 1 ⁢ ( 𝑛 , 𝑉 ) , with 𝑛 being a positive integer and 𝑉 being a set of vertices, is defined as

𝐺 𝑖 1 ⁢ ( 𝑛 , 𝑉 )

∑ 𝑈 ⊂ 𝑉 , | 𝑈 | ≤ 𝑛 ∏ 𝑗 ∈ 𝑈 ( ∑ ℎ

2 𝐻 𝑄 𝑗 → 𝑖 1 , ℎ ) ⁢ ∏ 𝑘 ∈ 𝑉
𝑈 ( 𝑄 𝑘 → 𝑖 0 + 𝑄 𝑘 → 𝑖 4 , 1 ) .

(28)

Here the summation is over all the subsets 𝑈 of vertex set 𝑉 under the constraint of the cardinality of 𝑈 should not exceed 𝑛 ; and 𝑉
𝑈 means the subset of 𝑉 that is complementary to subset 𝑈 . Similarly the function 𝐺 𝑖 2 ⁢ ( 𝑛 , 𝑉 ) is defined as

𝐺 𝑖 2 ⁢ ( 𝑛 , 𝑉 )

∑ 𝑈 ⊂ 𝑉 , | 𝑈 | ≤ 𝑛 ∏ 𝑗 ∈ 𝑈 ( 𝑄 𝑗 → 𝑖 5 , 1 + 𝑄 𝑗 → 𝑖 2 , 2 + ∑ ℎ

3 𝐻 𝑄 𝑗 → 𝑖 1 , ℎ )

(29)

× ∏ 𝑘 ∈ 𝑉
𝑈 ( 𝑄 𝑘 → 𝑖 0 + 𝑄 𝑘 → 𝑖 4 , 1 ) .

Third, for all the upper layers with ℎ ≥ 2 , we have

𝑄 𝑖 → 𝑗 1 , ℎ

1 𝑧 𝑖 → 𝑗 [ 𝐺 𝑖 3 , ℎ ( 𝐾 − 1 , 𝐾 , ∂ 𝑖
𝑗 )

• ∑ 𝑘 ∈ ∂ 𝑖
  𝑗 𝑄 𝑘 → 𝑖 2 , ℎ 𝐺 𝑖 4 , ℎ ( 𝐾 − 2 , 𝐾 − 1 , ∂ 𝑖
  { 𝑗 , 𝑘 } ) ] ,

(30a)

𝑄 𝑖 → 𝑗 2 , ℎ

1 𝑧 𝑖 → 𝑗 [ 𝐺 𝑖 3 , ℎ ( 𝐾 − 1 , 𝐾 − 1 , ∂ 𝑖
𝑗 )

• ∑ 𝑘 ∈ ∂ 𝑖
  𝑗 𝑄 𝑘 → 𝑖 2 , ℎ 𝐺 𝑖 4 , ℎ ( 𝐾 − 2 , 𝐾 − 2 , ∂ 𝑖
  { 𝑗 , 𝑘 } ) ] ,

(30b)

𝑄 𝑖 → 𝑗 3 , ℎ

1 𝑧 𝑖 → 𝑗 ⁢ 𝐺 𝑖 3 , ℎ ⁢ ( 𝐾 − 2 , 𝐾 − 1 , ∂ 𝑖
𝑗 ) ,

(30c)

𝑄 𝑖 → 𝑗 4 , ℎ

1 𝑧 𝑖 → 𝑗 ⁢ 𝐺 𝑖 4 , ℎ ⁢ ( 𝐾 − 2 , 𝐾 − 1 , ∂ 𝑖
𝑗 ) ,

(30d)

𝑄 𝑖 → 𝑗 5 , ℎ

1 𝑧 𝑖 → 𝑗 ⁢ ∑ 𝑘 ∈ ∂ 𝑖
𝑗 𝑄 𝑘 → 𝑖 2 , ℎ ⁢ 𝐺 𝑖 4 , ℎ ⁢ ( 𝐾 − 3 , 𝐾 − 2 , ∂ 𝑖
{ 𝑗 , 𝑘 } ) .

(30e)

Here the functions 𝐺 𝑖 3 , ℎ ⁢ ( 𝑚 , 𝑛 , 𝑉 ) and 𝐺 𝑖 4 , ℎ ⁢ ( 𝑚 , 𝑛 , 𝑉 ) are shorthand notations for the following two longer expressions:

𝐺 𝑖 3 , ℎ ⁢ ( 𝑥 , 𝑦 , 𝑉 )

∑ 𝑈 1 ⊂ 𝑉 | 𝑈 1 | ≤ 𝑥 ∑ 𝑈 2 ⊂ 𝑉
𝑈 1 | 𝑈 1 ∪ 𝑈 2 | ≥ 𝑦 ∏ 𝑘 ∈ 𝑈 1 [ ∑ 𝑡

ℎ + 1 𝐻 𝑄 𝑘 → 𝑖 1 , 𝑡 ] ⁢ ∏ 𝑙 ∈ 𝑈 2 [ 𝑄 𝑙 → 𝑖 5 , ℎ − 1 + 𝑄 𝑙 → 𝑖 4 , ℎ ]

× ∏ 𝑚 ∈ 𝑉
( 𝑈 1 ∪ 𝑈 2 ) [ 𝑄 𝑚 → 𝑖 0 + ∑ 𝑡

1 ℎ − 1 𝑄 𝑚 → 𝑖 3 , 𝑡 + ∑ 𝑡

1 ℎ − 2 𝑄 𝑚 → 𝑖 5 , 𝑡 ] ,

(31a)

𝐺 𝑖 4 , ℎ ⁢ ( 𝑥 , 𝑦 , 𝑉 )

∑ 𝑈 1 ∈ 𝑉 | 𝑈 1 | ≤ 𝑥 ∑ 𝑈 2 ∈ 𝑉
𝑈 1 | 𝑈 1 ∪ 𝑈 2 | ≥ 𝑦 ∏ 𝑘 ∈ 𝑈 1 [ 𝑄 𝑘 → 𝑖 2 , ℎ + 1 + 𝑄 𝑘 → 𝑖 5 , ℎ + ∑ 𝑡 ≥ ℎ + 2 𝑄 𝑘 → 𝑖 1 , 𝑡 ]

× ∏ 𝑙 ∈ 𝑈 2 [ 𝑄 𝑙 → 𝑖 5 , ℎ − 1 + 𝑄 𝑙 → 𝑖 4 , ℎ ]

× ∏ 𝑚 ∈ 𝑉
( 𝑈 1 ∪ 𝑈 2 ) [ 𝑄 𝑚 → 𝑖 0 + ∑ 𝑡

1 ℎ − 1 𝑄 𝑚 → 𝑖 3 , 𝑡 + ∑ 𝑡

1 ℎ − 2 𝑄 𝑚 → 𝑖 5 , 𝑡 ] ,

(31b)

where ∑ 𝑈 1 ⊂ 𝑉 | 𝑈 1 | ≤ 𝑥 means summation over all the subsets 𝑈 1 of the vertex set 𝑉 under the constraint of the cardinality of 𝑈 1 not exceeding the integer value 𝑥 , and ∑ 𝑈 2 ⊂ 𝑉
𝑈 1 | 𝑈 1 ∪ 𝑈 2 | ≥ 𝑦 means summation over all the subsets 𝑈 2 of the vertex set 𝑉
𝑈 1 under the constraint of the cardinality of 𝑈 1 ∪ 𝑈 2 being equal or larger than the integer value 𝑦 . It is easy to check that 𝑄 𝑖 → 𝑗 3 , 𝐻

0 .

The normalization constant 𝑧 𝑖 ⁢ 𝑗 in the above coarse-grained BP equations is fixed by the requirement that

( 1 + 𝑑 𝑗 ⁢ 𝐻 ) ⁢ 𝑄 𝑖 → 𝑗 0 + 2 ⁢ 𝑄 𝑖 → 𝑗 1 , 1 + ∑ ℎ

1 𝐻 − 1 ( 𝐻 − ℎ ) ⁢ 𝑑 𝑗 ⁢ 𝑄 𝑖 → 𝑗 3 , ℎ

+ ∑ ℎ

2 𝐻 [ ( ( ℎ − 2 ) ⁢ 𝑑 𝑗 + 2 ) ⁢ 𝑄 𝑖 → 𝑗 1 , ℎ + 𝑑 𝑗 ⁢ 𝑄 𝑖 → 𝑗 2 , ℎ ]

+ ∑ ℎ

1 𝐻 [ 𝑑 𝑗 ⁢ 𝑄 𝑖 → 𝑗 4 , ℎ + ( ( 𝐻 − ℎ + 1 ) ⁢ 𝑑 𝑗 − 1 ) ⁢ 𝑄 𝑖 → 𝑗 5 , ℎ ]

1 .

(32)

There are ( 5 ⁢ 𝐻 − 1 ) distinct coarse-grained cavity probabilities on each directed edge pointing from vertex 𝑖 to vertex 𝑗 : 𝑄 𝑖 → 𝑗 0 , 𝑄 𝑖 → 𝑗 𝑚 , 1 (for 𝑚

1 , 3 , 4 , 5 ), 𝑄 𝑖 → 𝑗 𝑚 , ℎ with 𝑚

1 , 2 , 3 , 4 , 5 and ℎ

2 , … , 𝐻 (except for 𝑚

3 and ℎ

𝐻 ). For a graph with 𝑁 vertices and 𝑀 undirected edges, we need to iterate these ( 5 ⁢ 𝐻 − 1 ) self-consistent equations on 2 ⁢ 𝑀 directed edges until they converge. The time complexity is then approximately of order 10 ⁢ 𝑟 ⁢ 𝐻 ⁢ 𝑀 with 𝑟 being the total number of BP iteration repeats. In our numerical simulation on the hCTGA algorithm, we simply set 𝑟 to the minimum value 𝑟

1 .

A common and straightforward way to obtain a fixed-point solution of these coarse-grained BP equations on a single graph instance is by iteration on all the edges of the graph. This works for low inverse temperature values. When the inverse temperature 𝛽 becomes large, it is often the case that the BP iteration fails to converge but instead becomes oscillatory. This non-convergence is often an indication of the emergence of spin glass phases Mezard-2009. To partially suppress oscillatory behavior, we introduce a damping factor 𝜂 to the BP message-passing equations so that the old value of a cavity probability still contributes a weight 𝜂 to the new value of this cavity probability. For example, in the case of the cavity probability 𝑄 𝑖 → 𝑗 0 , the modified version of Eq. (26) becomes

𝑄 𝑖 → 𝑗 0 ← 𝜂 ⁢ 𝑄 𝑖 → 𝑗 0 + ( 1 − 𝜂 ) ⁢ 𝑒 − 𝛽 𝑧 𝑖 → 𝑗 ⁢ ∏ 𝑘 ∈ ∂ 𝑖
𝑗 [ 𝑄 𝑘 → 𝑖 0 + 𝑄 𝑘 → 𝑖 1 , 1 + ∑ ℎ

2 𝐻 𝑄 𝑘 → 𝑖 1 , ℎ ] .

(33)

In the present paper we fix 𝜂

0.3 in all the numerical simulations (the results are not sensitive to the precise value of 𝜂 ).

5.5 Thermodynamic quantities

After reaching a fixed point of the coarse-grained BP equations, the free energy density 𝑓 is obtained by

𝑓

− 1 𝑁 ⁢ 𝛽 ⁢ ∑ 𝑖 𝑁 ln ⁡ 𝑧 𝑖 + 1 𝑁 ⁢ 𝛽 ⁢ ∑ ( 𝑖 , 𝑗 ) ∈ 𝐺 ln ⁡ 𝑧 𝑖 ⁢ 𝑗 ,

(34)

where the two normalization constants 𝑧 𝑖 and 𝑧 𝑖 ⁢ 𝑗 are computed through

𝑧 𝑖

𝑒 − 𝛽 ⁢ ∏ 𝑗 ∈ ∂ 𝑖 [ 𝑄 𝑗 → 𝑖 0 + 𝑄 𝑗 → 𝑖 1 , 1 + ∑ ℎ

2 𝐻 𝑄 𝑗 → 𝑖 1 , ℎ ] + 𝐺 𝑖 1 ⁢ ( 𝐾 − 1 , ∂ 𝑖 )

(35)

• ∑ 𝑗 ∈ ∂ 𝑖 𝑄 𝑗 → 𝑖 1 , 1 ⁢ 𝐺 𝑖 2 ⁢ ( 𝐾 − 2 , ∂ 𝑖
  𝑗 )

• ∑ ℎ

  2 𝐻 𝐺 𝑖 3 , ℎ ⁢ ( 𝐾 − 1 , 𝐾 , ∂ 𝑖 )

• ∑ ℎ

  2 𝐻 ∑ 𝑗 ∈ ∂ 𝑖 𝑄 𝑗 → 𝑖 2 , ℎ ⁢ 𝐺 𝑖 4 , ℎ ⁢ ( 𝐾 − 2 , 𝐾 − 1 , ∂ 𝑖
  𝑗 ) ,

𝑧 𝑖 ⁢ 𝑗

𝑄 𝑖 → 𝑗 0 ⁢ 𝑄 𝑗 → 𝑖 0 + 𝑄 𝑖 → 𝑗 1 , 1 ⁢ 𝑄 𝑗 → 𝑖 4 , 1 + 𝑄 𝑖 → 𝑗 4 , 1 ⁢ 𝑄 𝑗 → 𝑖 1 , 1 + ∑ ℎ

1 𝐻 [ 𝑄 𝑖 → 𝑗 1 , ℎ ⁢ 𝑄 𝑗 → 𝑖 0 + 𝑄 𝑖 → 𝑗 0 ⁢ 𝑄 𝑗 → 𝑖 1 , ℎ ]

(36)

• ∑ ℎ

  2 𝐻 [ 𝑄 𝑖 → 𝑗 4 , ℎ ⁢ 𝑄 𝑗 → 𝑖 2 , ℎ

• 𝑄 𝑖 → 𝑗 2 , ℎ ⁢ 𝑄 𝑗 → 𝑖 4 , ℎ ]

• ∑ ℎ

  2 𝐻 ∑ 𝑡

  1 ℎ − 1 [ 𝑄 𝑖 → 𝑗 3 , 𝑡 ⁢ 𝑄 𝑗 → 𝑖 1 , ℎ

• 𝑄 𝑖 → 𝑗 1 , ℎ ⁢ 𝑄 𝑗 → 𝑖 3 , 𝑡 ]

• ∑ ℎ

  1 𝐻 𝑄 𝑖 → 𝑗 5 , ℎ ⁢ 𝑄 𝑗 → 𝑖 5 , ℎ

• ∑ ℎ

  3 𝐻 ∑ 𝑡

  1 ℎ − 2 [ 𝑄 𝑖 → 𝑗 1 , ℎ ⁢ 𝑄 𝑗 → 𝑖 5 , 𝑡

• 𝑄 𝑖 → 𝑗 5 , 𝑡 ⁢ 𝑄 𝑗 → 𝑖 1 , ℎ ]

• ∑ ℎ

  1 𝐻 − 1 [ 𝑄 𝑖 → 𝑗 2 , ℎ

• 1 ⁢ 𝑄 𝑗 → 𝑖 5 , ℎ

• 𝑄 𝑖 → 𝑗 5 , ℎ ⁢ 𝑄 𝑗 → 𝑖 2 , ℎ

• 1 ] .

The marginal probability of vertex 𝑖 being a seed is then evaluated as

𝑞 𝑖 0

1 𝑧 𝑖 ⁢ 𝑒 − 𝛽 ⁢ ∏ 𝑗 ∈ ∂ 𝑖 [ 𝑄 𝑗 → 𝑖 0 + 𝑄 𝑗 → 𝑖 1 , 1 + ∑ ℎ

2 𝐻 𝑄 𝑗 → 𝑖 1 , ℎ ] ,

(37)

and the mean energy density 𝜌 is

𝜌

1 𝑁 ⁢ ∑ 𝑖

1 𝑁 𝑞 𝑖 0 .

(38)

The entropy density at a fixed value of 𝛽 is determined as 𝑠

𝛽 ⁢ ( 𝜌 − 𝑓 ) .

5.6 Replica-symmetric mean field equations for regular random graph ensembles

For the regular random graph ensemble with uniform vertex degree ( 𝑑 𝑖

𝐷 for all the vertices 𝑖 ), we make the additional assumption that all the cavity probability messages are independent of the specific edges, namely 𝑄 𝑖 → 𝑗 0

𝑄 0 , 𝑄 𝑖 → 𝑗 1 , ℎ

𝑄 1 , ℎ , and so on. The normalization constant 𝑧 𝑖 → 𝑗 will then be the same for all the edges ( 𝑖 , 𝑗 ) . The replica-symmetric mean field equations for the quantities 𝑄 0 , 𝑄 1 , ℎ , … can be easily written down from the general coarse-grained BP equations. For layer ℎ

0 and ℎ

1 , they are

𝑄 0

1 𝑧 𝑖 → 𝑗 ⁢ 𝑒 − 𝛽 ⁢ ( 𝑄 0 + 𝑄 1 , 1 + ∑ ℎ

2 𝐻 𝑄 1 , ℎ ) 𝐷 − 1 ,

(39a)

𝑄 1 , 1

1 𝑧 𝑖 → 𝑗 { ∑ 𝑛

0 𝐾 − 1 𝐶 𝐷 − 1 𝑛 ( ∑ ℎ

2 𝐻 𝑄 1 , ℎ ) 𝑛 ( 𝑄 0 + 𝑄 4 , 1 ) 𝐷 − 1 − 𝑛 + ( 𝐷 − 1 ) 𝑄 1 , 1 ×

∑ 𝑛

0 𝐾 − 2 𝐶 𝐷 − 2 𝑛 ( 𝑄 5 , 1 + 𝑄 2 , 2 + ∑ 𝑑

3 𝐻 𝑄 1 , ℎ ) 𝑛 ( 𝑄 0 + 𝑄 4 , 1 ) 𝐷 − 2 − 𝑛 } ,

(39b)

𝑄 3 , 1

1 𝑧 𝑖 → 𝑗 ⁢ ∑ 𝑛

0 𝐾 − 2 𝐶 𝐷 − 1 𝑛 ⁢ ( ∑ ℎ

2 𝐻 𝑄 1 , ℎ ) 𝑛 ⁢ ( 𝑄 0 + 𝑄 4 , 1 ) 𝐷 − 1 − 𝑛 ,

(39c)

𝑄 4 , 1

1 𝑧 𝑖 → 𝑗 ⁢ ∑ 𝑛

0 𝐾 − 2 𝐶 𝐷 − 1 𝑛 ⁢ ( 𝑄 5 , 1 + 𝑄 2 , 2 + ∑ ℎ

3 𝐻 𝑄 1 , ℎ ) 𝑛 ⁢ ( 𝑄 0 + 𝑄 4 , 1 ) 𝐷 − 1 − 𝑛 ,

(39d)

𝑄 5 , 1

1 𝑧 𝑖 → 𝑗 ( 𝐷 − 1 ) 𝑄 1 , 1 ×

∑ 𝑛

0 𝐾 − 3 𝐶 𝐷 − 2 𝑛 ⁢ ( 𝑄 5 , 1 + 𝑄 2 , 2 + ∑ ℎ

3 𝐻 𝑄 1 , ℎ ) 𝑛 ⁢ ( 𝑄 0 + 𝑄 4 , 1 ) 𝐷 − 2 − 𝑛 ,

(39e)

where 𝐶 𝐷 𝑛 ≡ 𝐷 ! 𝑛 ! ⁢ ( 𝐷 − 𝑛 ) ! is the binomial coefficient. For layer ℎ

2 , … , 𝐻 , the self-consistent equations are

𝑄 1 , ℎ

1 𝑧 𝑖 → 𝑗 { ∑ 𝑛

0 𝐾 − 1 ∑ 𝑚

𝐾 − 𝑛 𝐷 − 1 − 𝑛 𝐶 𝐷 − 1 𝑛 𝐶 𝐷 − 1 − 𝑛 𝑚 ( ∑ 𝑡

ℎ + 1 𝐻 𝑄 1 , 𝑡 ) 𝑛 ( 𝑄 5 , ℎ − 1 + 𝑄 4 , ℎ ) 𝑚 ×

( 𝑄 0 + ∑ 𝑡

1 ℎ − 1 𝑄 3 , 𝑡 + ∑ 𝑡

1 ℎ − 2 𝑄 5 , 𝑡 ) 𝐷 − 1 − 𝑛 − 𝑚 + ( 𝐷 − 1 ) 𝑄 2 , ℎ ×

∑ 𝑛

0 𝐾 − 2 ∑ 𝑚

𝐾 − 1 − 𝑛 𝐷 − 2 − 𝑛 𝐶 𝐷 − 2 𝑛 𝐶 𝐷 − 2 − 𝑛 𝑚 ( 𝑄 2 , ℎ + 1 + ∑ 𝑡

ℎ + 2 𝐻 𝑄 1 , 𝑡 + 𝑄 5 , ℎ ) 𝑛 ×

( 𝑄 5 , ℎ − 1 + 𝑄 4 , ℎ ) 𝑚 ( 𝑄 0 + ∑ 𝑡

1 ℎ − 1 𝑄 3 , 𝑡 + ∑ 𝑡

1 ℎ − 2 𝑄 5 , 𝑡 ) 𝐷 − 2 − 𝑛 − 𝑚 } ,

(40a)

𝑄 2 , ℎ

1 𝑧 𝑖 → 𝑗 { ∑ 𝑛

0 𝐾 − 1 ∑ 𝑚

𝐾 − 1 − 𝑛 𝐷 − 1 − 𝑛 𝐶 𝐷 − 1 𝑛 𝐶 𝐷 − 1 − 𝑛 𝑚 ( ∑ 𝑡

ℎ + 1 𝐻 𝑄 1 , 𝑡 ) 𝑛 ( 𝑄 5 , ℎ − 1 + 𝑄 4 , ℎ ) 𝑚

× ( 𝑄 0 + ∑ 𝑡

1 ℎ − 1 𝑄 3 , 𝑡 + ∑ 𝑡

1 ℎ − 2 𝑄 5 , 𝑡 ) 𝐷 − 1 − 𝑛 − 𝑚 + ( 𝐷 − 1 ) 𝑄 2 , ℎ ×

∑ 𝑛

0 𝐾 − 2 ∑ 𝑚

𝐾 − 2 − 𝑛 𝐷 − 2 − 𝑛 𝐶 𝐷 − 2 𝑛 𝐶 𝐷 − 2 − 𝑛 𝑚 ( 𝑄 2 , ℎ + 1 + ∑ 𝑡

ℎ + 2 𝐻 𝑄 1 , 𝑡 + 𝑄 5 , ℎ ) 𝑛 ×

( 𝑄 5 , ℎ − 1 + 𝑄 4 , ℎ ) 𝑚 ( 𝑄 0 + ∑ 𝑡

1 ℎ − 1 𝑄 3 , 𝑡 + ∑ 𝑡

1 ℎ − 2 𝑄 5 , 𝑡 ) 𝐷 − 2 − 𝑛 − 𝑚 } ,

(40b)

𝑄 3 , ℎ

1 𝑧 𝑖 → 𝑗 ⁢ ∑ 𝑛

0 𝐾 − 2 ∑ 𝑚

𝐾 − 1 − 𝑛 𝐷 − 1 − 𝑛 𝐶 𝐷 − 1 𝑛 ⁢ 𝐶 𝐷 − 1 − 𝑛 𝑚 ⁢ ( ∑ 𝑡

ℎ + 1 𝐻 𝑄 1 , 𝑡 ) 𝑛 ⁢ ( 𝑄 5 , ℎ − 1 + 𝑄 4 , ℎ ) 𝑚

× ( 𝑄 0 + ∑ 𝑡

1 ℎ − 1 𝑄 3 , 𝑡 + ∑ 𝑡

1 ℎ − 2 𝑄 5 , 𝑡 ) 𝐷 − 1 − 𝑛 − 𝑚 ,

(40c)

𝑄 4 , ℎ

1 𝑧 𝑖 → 𝑗 ⁢ ∑ 𝑛

0 𝐾 − 2 ∑ 𝑚

𝐾 − 1 − 𝑛 𝐷 − 1 − 𝑛 𝐶 𝐷 − 1 𝑛 ⁢ 𝐶 𝐷 − 1 − 𝑛 𝑚 ⁢ ( 𝑄 2 , ℎ + 1 + ∑ 𝑡

ℎ + 2 𝐻 𝑄 1 , 𝑡 + 𝑄 5 , ℎ ) 𝑛

× ( 𝑄 5 , ℎ − 1 + 𝑄 4 , ℎ ) 𝑚 ⁢ ( 𝑄 0 + ∑ 𝑡

1 ℎ − 1 𝑄 3 , 𝑡 + ∑ 𝑡

1 ℎ − 2 𝑄 5 , 𝑡 ) 𝐷 − 1 − 𝑛 − 𝑚 ,

(40d)

𝑄 5 , ℎ

1 𝑧 𝑖 → 𝑗 ( 𝐷 − 1 ) 𝑄 2 , ℎ ∑ 𝑛

0 𝐾 − 3 ∑ 𝑚

𝐾 − 2 − 𝑛 𝐷 − 2 − 𝑛 𝐶 𝐷 − 2 𝑛 𝐶 𝐷 − 2 − 𝑛 𝑚 ×

( 𝑄 2 , ℎ + 1 + ∑ 𝑡

ℎ + 2 𝐻 𝑄 1 , 𝑡 + 𝑄 5 , ℎ ) 𝑛 ( 𝑄 5 , ℎ − 1 + 𝑄 4 , ℎ ) 𝑚 ×

( 𝑄 0 + ∑ 𝑡

1 ℎ − 1 𝑄 3 , 𝑡 + ∑ 𝑡

1 ℎ − 2 𝑄 5 , 𝑡 ) 𝐷 − 2 − 𝑛 − 𝑚 .

(40e)

The normalization constant 𝑧 𝑖 → 𝑗 is determined the condition

1

( 1 + 𝐷 ⁢ 𝐻 ) ⁢ 𝑄 0 + 2 ⁢ 𝑄 1 , 1 + ∑ ℎ

2 𝐻 [ ( ( ℎ − 2 ) ⁢ 𝐷 + 2 ) ⁢ 𝑄 1 , ℎ + 𝐷 ⁢ 𝑄 2 , ℎ ] +

(41)

∑ ℎ

1 𝐻 − 1 ( 𝐻 − ℎ ) ⁢ 𝐷 ⁢ 𝑄 3 , ℎ + ∑ ℎ

1 𝐻 [ 𝐷 ⁢ 𝑄 4 , ℎ + ( ( 𝐻 − ℎ + 1 ) ⁢ 𝐷 − 1 ) ⁢ 𝑄 5 , ℎ ] .

At any given value of inverse temperature 𝛽 , we can solve the coupled mean-field equations by the Newton-Raphson method or other numerical methods. At the fixed-point solution the thermodynamical quantities of interest can then be easily computed as follows. The average energy density 𝜌 (which is also the probability of a vertex belonging to the attack set) is

𝜌

1 𝑧 𝑖 ⁢ 𝑒 − 𝛽 ⁢ ( 𝑄 0 + 𝑄 1 , 1 + ∑ ℎ

2 𝐻 𝑄 1 , ℎ ) 𝐷 ,

(42)

where the normalization constant 𝑧 𝑖 is

𝑧 𝑖

𝑒 − 𝛽 ⁢ ( 𝑄 0 + 𝑄 1 , 1 + ∑ ℎ

2 𝐻 𝑄 1 , ℎ ) 𝐷 + ∑ 𝑛

0 𝐾 − 1 𝐶 𝐷 𝑛 ⁢ ( ∑ ℎ

2 𝐻 𝑄 1 , ℎ ) 𝑛 ⁢ ( 𝑄 0 + 𝑄 4 , 1 ) 𝐷 − 𝑛

(43)

• 𝐷 ⁢ 𝑄 1 , 1 ⁢ ∑ 𝑛

  0 𝐾 − 2 𝐶 𝐷 − 1 𝑛 ⁢ ( 𝑄 5 , 1

• 𝑄 2 , 2

• ∑ ℎ

  3 𝐻 𝑄 1 , ℎ ) 𝑛 ⁢ ( 𝑄 0

• 𝑄 4 , 1 ) 𝐷 − 1 − 𝑛

• ∑ ℎ

  2 𝐻 ∑ 𝑛

  0 𝐾 − 1 ∑ 𝑚

  𝐾 − 𝑛 𝐷 − 𝑛 𝐶 𝐷 𝑛 𝐶 𝐷 − 𝑛 𝑚 ( ∑ 𝑡

  ℎ

• 1 𝐻 𝑄 1 , 𝑡 ) 𝑛 ( 𝑄 5 , ℎ − 1

• 𝑄 4 , ℎ ) 𝑚 ×

( 𝑄 0 + ∑ 𝑡

1 ℎ − 1 𝑄 3 , 𝑡 + ∑ 𝑡

1 ℎ − 2 𝑄 5 , 𝑡 ) 𝐷 − 𝑛 − 𝑚 + 𝐷 ∑ ℎ

2 𝐻 𝑄 2 , ℎ ×

∑ 𝑛

0 𝐾 − 2 ∑ 𝑚

𝐾 − 1 − 𝑛 𝐷 − 1 − 𝑛 𝐶 𝐷 − 1 𝑛 ⁢ 𝐶 𝐷 − 1 − 𝑛 𝑚 ⁢ ( 𝑄 2 , ℎ + 1 + ∑ 𝑡

ℎ + 2 𝐻 𝑄 1 , 𝑡 + 𝑄 5 , ℎ ) 𝑛

× ( 𝑄 5 , ℎ − 1 + 𝑄 4 , ℎ ) 𝑚 ⁢ ( 𝑄 0 + ∑ 𝑡

1 ℎ − 1 𝑄 3 , 𝑡 + ∑ 𝑡

1 ℎ − 2 𝑄 5 , 𝑡 ) 𝐷 − 1 − 𝑛 − 𝑚 .

The free energy density 𝑓 is computed as

𝑓

− 1 𝛽 ⁢ ln ⁡ 𝑧 𝑖 + 𝐷 2 ⁢ 𝛽 ⁢ ln ⁡ 𝑧 𝑖 ⁢ 𝑗 ,

(44)

where the other normalization constant 𝑧 𝑖 ⁢ 𝑗 is

𝑧 𝑖 ⁢ 𝑗

𝑄 0 ⁢ 𝑄 0 + 2 ⁢ 𝑄 0 ⁢ 𝑄 1 , 1 + 2 ⁢ 𝑄 1 , 1 ⁢ 𝑄 4 , 1 + 2 ⁢ 𝑄 0 ⁢ ∑ ℎ

2 𝐻 𝑄 1 , ℎ + 2 ⁢ ∑ ℎ

2 𝐻 𝑄 2 , ℎ ⁢ 𝑄 4 , ℎ

(45)

• 2 ⁢ ∑ ℎ

  2 𝐻 ∑ 𝑡

  1 ℎ − 1 𝑄 1 , ℎ ⁢ 𝑄 3 , 𝑡

• 2 ⁢ ∑ ℎ

  3 𝐻 ∑ 𝑡

  1 ℎ − 2 𝑄 1 , ℎ ⁢ 𝑄 5 , 𝑡

• 2 ⁢ ∑ ℎ

  1 𝐻 − 1 𝑄 2 , ℎ

• 1 ⁢ 𝑄 5 , ℎ

• ∑ ℎ

  1 𝐻 𝑄 5 , ℎ ⁢ 𝑄 5 , ℎ .

The entropy density is 𝑠

𝛽 ⁢ ( 𝜌 − 𝑓 ) .

6Acknowledgments

This work was supported by the National Natural Science Foundation of China (Grant Nos. 11975295, 12047503, and 12247104), the Chinese Academy of Sciences (Grant Nos. QYZDJ-SSW-SYS018, and XDPD15), and National Innovation Institute of Defense Technology Grant No. 22TQ0904ZT01025. Numerical simulations were carried out at the Tianwen cluster of ITP-CAS.

7Data availability statement

The Python code used to generate the datasets of the provided examples is available from the first author, Jianwen Zhou (zhoujianwen@itp.ac.cn), on reasonable request.

8Conflict of interest statement

We declared that we have no conflicts of interest in this work.

References \bibcommenthead (1) ↑ M. Pollak, I. Riess, Application of percolation theory to 2d-3d Heisenberg ferromagnets.Physica Status Solidi (B) 69(1), K15–K18 (1975).10.1002/pssb.2220690138.URL https://onlinelibrary.wiley.com/doi/abs/10.1002/pssb.2220690138 (2) ↑ J. Chalupa, P.L. Leath, G.R. Reich, Bootstrap percolation on a Bethe lattice.Journal of Physics C: Solid State Physics 12(1), L31–L35 (1979).10.1088/0022-3719/12/1/008.URL http://dx.doi.org/10.1088/0022-3719/12/1/008 (3) ↑ M. Granovetter, Threshold models of collective behavior.American Journal of Sociology 83(6), 1420–1443 (1978).10.1086/226707.URL https://www.journals.uchicago.edu/doi/abs/10.1086/226707 (4) ↑ S.B. Seidman, Network structure and minimum degree.Social Networks 5(3), 269–287 (1983).10.1016/0378-8733(83)90028-x.URL https://www.sciencedirect.com/science/article/abs/pii/037887338390028X?via%3Dihub (5) ↑ Y.X. Kong, G.Y. Shi, R.J. Wu, Y.C. Zhang, K-core: Theories and applications.Physics Reports 832, 1–32 (2019).10.1016/j.physrep.2019.10.004.URL https://www.sciencedirect.com/science/article/pii/S037015731930328X (6) ↑ G.H. Fredrickson, H.C. Andersen, Kinetic Ising model of the glass transition.Physical Review Letters 53(13), 1244–1247 (1984).10.1103/PhysRevLett.53.1244.URL https://link.aps.org/doi/10.1103/PhysRevLett.53.1244 (7) ↑ M. Sellitto, G. Biroli, C. Toninelli, Facilitated spin models on Bethe lattice: Bootstrap percolation, mode-coupling transition and glassy dynamics.Europhysics Letters 69(4), 496 (2005).10.1209/epl/i2004-10372-5.URL https://dx.doi.org/10.1209/epl/i2004-10372-5 (8) ↑ T. Rizzo, Fate of the hybrid transition of bootstrap percolation in physical dimension.Physical Review Letters 122(10), 108301 (2019).10.1103/PhysRevLett.122.108301.URL https://link.aps.org/doi/10.1103/PhysRevLett.122.108301 (9) ↑ T. Rizzo, T. Voigtmann, Solvable models of supercooled liquids in three dimensions.Physical Review Letters 124(19), 195,501 (2020).10.1103/PhysRevLett.124.195501.URL https://link.aps.org/doi/10.1103/PhysRevLett.124.195501 (10) ↑ G. Perrupato, T. Rizzo, Exact dynamical equations for kinetically-constrained-models.e-print arXiv:2212.05132 (2022).10.48550/arXiv.2212.05132.URL https://ui.adsabs.harvard.edu/abs/2022arXiv221205132P (11) ↑ M. Altaf-Ul-Amine, K. Nishikata, T. Korna, T. Miyasato, Y. Shinbo, M. Arifuzzaman, C. Wada, M. Maeda, T. Oshima, H. Mori, S. Kanaya, Prediction of protein functions based on K-cores of protein-protein interaction networks and amino acid sequences.Genome Informatics 14, 498–499 (2003).10.11234/gi1990.14.498.URL https://www.jstage.jst.go.jp/article/gi1990/14/0/14_0_498/_article (12) ↑ S. Wuchty, E. Almaas, Peeling the yeast protein network.PROTEOMICS 5(2), 444–449 (2005).10.1002/pmic.200400962.URL https://analyticalsciencejournals.onlinelibrary.wiley.com/doi/abs/10.1002/pmic.200400962 (13) ↑ F. Arese Lucini, G. Del Ferraro, M. Sigman, H.A. Makse, How the brain transitions from conscious to subliminal perception.Neuroscience 411, 280–290 (2019).10.1016/j.neuroscience.2019.03.047.URL https://www.sciencedirect.com/science/article/pii/S0306452219302052 (14) ↑ W.C. Stanford, P.J. Mucha, E. Dayan, A robust core architecture of functional brain networks supports topological resilience and cognitive performance in middle- and old-aged adults.Proceedings of the National Academy of Sciences 119(44), e2203682,119 (2022).10.1073/pnas.2203682119.URL https://www.pnas.org/doi/abs/10.1073/pnas.2203682119 (15) ↑ J. García-Algarra, J.M. Pastor, J.M. Iriondo, J. Galeano, Ranking of critical species to preserve the functionality of mutualistic networks using the K-core decomposition.PeerJ 5, e3321 (2017).10.7717/peerj.3321.URL https://doi.org/10.7717/peerj.3321 (16) ↑ M. Kitsak, L.K. Gallos, S. Havlin, F. Liljeros, L. Muchnik, H.E. Stanley, H.A. Makse, Identification of influential spreaders in complex networks.Nature Physics 6(11), 888–893 (2010).10.1038/nphys1746.URL https://doi.org/10.1038/nphys1746 (17) ↑ S.N. Dorogovtsev, A.V. Goltsev, J.F.F. Mendes, K-core organization of complex networks.Physical Review Letters 96(4), 040601 (2006).10.1103/PhysRevLett.96.040601.URL https://link.aps.org/doi/10.1103/PhysRevLett.96.040601 (18) ↑ S.N. Dorogovtsev, A.V. Goltsev, J.F.F. Mendes, K-core architecture and K-core percolation on complex networks.Physica D: Nonlinear Phenomena 224(1), 7–19 (2006).10.1016/j.physd.2006.09.027.URL https://www.sciencedirect.com/science/article/pii/S0167278906003617 (19) ↑ N. Azimi-Tafreshi, J. Gómez-Gardeñes, S.N. Dorogovtsev, K-core percolation on multiplex networks.Physical Review E 90(3), 032,816 (2014).10.1103/PhysRevE.90.032816.URL https://link.aps.org/doi/10.1103/PhysRevE.90.032816 (20) ↑ G. J. Baxter, S. N. Dorogovtsev, K.-E. Lee, J. F. F. Mendes, A. V. Goltsev, Critical dynamics of the K-core pruning process.Physical Review X 5(3), 031017 (2015).10.1103/PhysRevX.5.031017.URL https://journals.aps.org/prx/abstract/10.1103/PhysRevX.5.031017 (21) ↑ R.J. Wu, Y.X. Kong, Z. Di, Y.C. Zhang, G.Y. Shi, Analytical solution to the K-core pruning process.Physica A 608, 128260 (2022).10.1016/j.physa.2022.128260.URL https://www.sciencedirect.com/science/article/pii/S0378437122008184 (22) ↑ J.H. Zhao, H.J. Zhou, Y.Y. Liu, Inducing effect on the percolation transition in complex networks.Nature Commun. 4, 2412 (2013).doi: 10.1038/ncomms3412 (23) ↑ J.H. Zhao, Generalized K-core pruning process on directed networks.Journal of Statistical Mechanics: Theory and Experiment 2017, 063407 (2017).10.1088/1742-5468/aa71e0.URL https://iopscience.iop.org/article/10.1088/1742-5468/aa71e0 (24) ↑ S.N. Wang, L. Cheng, H.J. Zhou, Vulnerability and resilience of social engagement: Equilibrium theory.Europhys. Lett. 132, 60006 (2020).https://doi.org/10.1209/0295-5075/132/60006. (25) ↑ A. Guggiola, G. Semerjian, Minimal contagious sets in random regular graphs.Journal of Statistical Physics 158(2), 300–358 (2015).10.1007/s10955-014-1136-2.URL https://doi.org/10.1007/s10955-014-1136-2 (26) ↑ C. Schmidt, H.D. Pfister, L. Zdeborová, Minimal sets to destroy the K-core in random networks.Phys Rev E 99(2-1), 022,310 (2019).10.1103/PhysRevE.99.022310.URL https://www.ncbi.nlm.nih.gov/pubmed/30934241 (27) ↑ H.J. Zhou, Cycle-tree guided attack of random K-core: Spin glass model and efficient message-passing algorithm.Science China Physics, Mechanics & Astronomy 65(3), 230,511 (2022).10.1007/s11433-021-1845-6.URL https://link.springer.com/article/10.1007/s11433-021-1845-6 (28) ↑ R. Ma, Y. Hu, J.H. Zhao, Random node reinforcement and k-core structure of complex networks.Chaos Solitons & Fractals 173, 113706 (2023).10.1016/j.chaos.2023.113706 (29) ↑ R.M. Karp, Reducibility among Combinatorial Problems, in Complexity of Computer Computations (Springer US, Boston, MA, 1972), pp. 85–103.10.1007/978-1-4684-2001-2_9.URL https://doi.org/10.1007/978-1-4684-2001-2_9 (30) ↑ F.V. Fomin, S. Gaspers, A.V. Pyatkin, I. Razgon, On the minimum feedback vertex set problem: Exact and enumeration algorithms.Algorithmica 52, 293–307 (2008).10.1007/s00453-007-9152-0 (31) ↑ S. Bau, N.C. Wormald, S. Zhou, Decycling numbers of random regular graphs.Random Structures & Algorithms 21(3-4), 397–413 (2002).10.1002/rsa.10069.URL https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.10069 (32) ↑ H.J. Zhou, Spin glass approach to the feedback vertex set problem.The European Physical Journal B 86(11), 455 (2013).10.1140/epjb/e2013-40690-1.URL https://doi.org/10.1140/epjb/e2013-40690-1 (33) ↑ H.J. Zhou, A spin glass approach to the directed feedback vertex set problem.Journal of Statistical Mechanics: Theory and Experiment 2016(7), 073303 (2016).10.1088/1742-5468/2016/07/073303.URL http://dx.doi.org/10.1088/1742-5468/2016/07/073303 (34) ↑ A. Braunstein, L. Dall’Asta, G. Semerjian, L. Zdeborová, Network dismantling.Proceedings of the National Academy of Sciences 113(44), 12368–12373 (2016).10.1073/pnas.1605083113.URL https://dx.doi.org/10.1073/pnas.1605083113 (35) ↑ L. Zdeborová, P. Zhang, H.J. Zhou, Fast and simple decycling and dismantling of networks.Scientific Reports 6(1), 37954 (2016).10.1038/srep37954.URL https://doi.org/10.1038/srep37954 (36) ↑ S. Pei, X. Teng, J. Shaman, F. Morone, H.A. Makse, Efficient collective influence maximization in cascading processes with first-order transitions.Scientific Reports 7(1), 45240 (2017).10.1038/srep45240.URL https://doi.org/10.1038/srep45240 (37) ↑ F. Altarelli, A. Braunstein, L. Dall’Asta, R. Zecchina, Optimizing spread dynamics on graphs by message passing.Journal of Statistical Mechanics: Theory and Experiment 2013(09), P09011 (2013).10.1088/1742-5468/2013/09/p09011.URL http://dx.doi.org/10.1088/1742-5468/2013/09/P09011 (38) ↑ F. Altarelli, A. Braunstein, L. Dall’Asta, R. Zecchina, Large deviations of cascade processes on graphs.Physical Review E 87(6), 062115 (2013).10.1103/physreve.87.062115.URL https://dx.doi.org/10.1103/physreve.87.062115 (39) ↑ D. Reichman, New bounds for contagious sets.Discrete Mathematics 312(10), 1812–1814 (2012).10.1016/j.disc.2012.01.016.URL https://www.sciencedirect.com/science/article/pii/S0012365X12000301 (40) ↑ A. Coja-Oghlan, U. Feige, M. Krivelevich, D. Reichman, Contagious Sets in Expanders, in Proceedings of the 2015 Annual ACM-SIAM Symposium on Discrete Algorithms (Society for Industrial and Applied Mathematics, 2014), pp. 1953–1987.10.1137/1.9781611973730.131.URL https://doi.org/10.1137/1.9781611973730.131 (41) ↑ P.A. Dreyer, F.S. Roberts, Irreversible K-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion.Discrete Applied Mathematics 157(7), 1615–1627 (2009).10.1016/j.dam.2008.09.012.URL https://www.sciencedirect.com/science/article/pii/S0166218X08004393 (42) ↑ F. Zhang, Y. Zhang, L. Qin, W. Zhang, X. Lin, Finding critical users for social network engagement: The collapsed k-core problem.Proceedings of the AAAI Conference on Artificial Intelligence 31(1), 245–251 (2017).10.1609/aaai.v31i1.10482.URL https://ojs.aaai.org/index.php/AAAI/article/view/10482 (43) ↑ J.H. Zhao, H.J. Zhou, Optimal disruption of complex networks.e-print arXiv:1605.09257 (2016).10.48550/arXiv.1605.09257.URL https://arxiv.org/abs/1605.09257 (44) ↑ M. Mézard, A. Montanari, Information, Physics, and Computation (Oxford University Press, 2009).10.1093/acprof:oso/9780198570837.001.0001.URL https://academic.oup.com/book/6337 (45) ↑ H. Zhou, Spin Glass and Message Passing (Science Press, Beijing, 2015) (46) ↑ Y. Habibulla, H.J. Zhou, Minimum connected dominating set and backbone of a random graph.e-print arXiv:2310.15980 (2023).10.48550/arXiv.2310.15980. (47) ↑ Y.Z. Xu, H.J. Zhou, Optimal segmentation of directed graph and the minimum number of feedback arcs.Journal of Statistical Physics 169(1), 187–202 (2017).10.1007/s10955-017-1860-5.URL https://link.springer.com/article/10.1007/s10955-017-1860-5 (48) ↑ B. Zhou, Y. Lv, J. Wang, J. Zhang, Q. Xuan, COREATTACK: Breaking Up the Core Structure of Graphs.arXiv e-prints (2021).10.48550/arXiv.2111.15276.URL https://ui.adsabs.harvard.edu/abs/2021arXiv211115276Z (49) ↑ X.J. Wang, J. Jiang, U. Pereira-Obilinovic, Bifurcation in space: Emergence of function modularity in the neocortex.e-print bioRxiv:2023.06.04.543639 (2023).10.1101/2023.06.04.543639.URL https://www.biorxiv.org/content/10.1101/2023.06.04.543639v1.full.pdf yuD3OozU2wAAAABJRU5ErkJggg==" alt="[LOGO]"> Generated by L A T E xml Instructions for reporting errors

We are continuing to improve HTML versions of papers, and your feedback helps enhance accessibility and mobile support. To report errors in the HTML that will help us improve conversion and rendering, choose any of the methods listed below:

Click the "Report Issue" button. Open a report feedback form via keyboard, use "Ctrl + ?". Make a text selection and click the "Report Issue for Selection" button near your cursor. You can use Alt+Y to toggle on and Alt+Shift+Y to toggle off accessible reporting links at each section.

Our team has already identified the following issues. We appreciate your time reviewing and reporting rendering errors we may not have found yet. Your efforts will help us improve the HTML versions for all readers, because disability should not be a barrier to accessing research. Thank you for your continued support in championing open access for all.

Have a free development cycle? Help support accessibility at arXiv! Our collaborators at LaTeXML maintain a list of packages that need conversion, and welcome developer contributions.

Report Issue Report Issue for Selection