Minimal Contagious Sets in Random Regular Graphs

详细信息    查看全文

• 作者：Alberto Guggiola (1)
  Guilhem Semerjian (1)
  
  1. LPTENS ; Unit茅 Mixte de Recherche (UMR 8549) du CNRS et de l鈥橢NS ; associ茅e 脿 l鈥橴PMC Univ Paris 06 ; 24 Rue Lhomond ; 75231 ; Paris Cedex 05 ; France
  
• 关键词：Bootstrap percolation ; Optimization problems ; Cavity method ; Random graphs
• 刊名：Journal of Statistical Physics
• 出版年：2015
• 出版时间：January 2015
• 年：2015
• 卷：158
• 期：2
• 页码：300-358
• 全文大小：1,110 KB
• 参考文献：1. Achlioptas, D., Coja-Oghlan, A.: Algorithmic barriers from phase transitions. In: IEEE 49th Annual IEEE Symposium on Foundations of Computer Science, 2008. FOCS鈥?8, pp. 793鈥?02. IEEE (2008)
  2. Achlioptas, D., D鈥橲ouza, R.M., Spencer, J.: Explosive percolation in random networks. Science 323(5920), 1453鈥?455 (2009) CrossRef
  3. Achlioptas, D., Ricci-Tersenghi, F.: On the solution-space geometry of random constraint satisfaction problems. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (2006)
  4. Ackerman, E., Ben-Zwi, O., Wolfovitz, G.: Combinatorial model and bounds for target set selection. Theor. Comput. Sci. 411(44鈥?6), 4017鈥?022 (2010) CrossRef
  5. Aizenman, M., Lebowitz, J.L.: Metastability effects in bootstrap percolation. J. Phys. A 21(19), 3801 (1988) CrossRef
  6. Altarelli, F., Braunstein, A., Dall鈥橝sta, L., Lage-Castellanos, A., Zecchina, R.: Bayesian inference of epidemics on networks via belief propagation. Phys. Rev. Lett. 112, 118701 (2014) CrossRef
  7. Altarelli, F., Braunstein, A., Dall鈥橝sta, L., Wakeling, R.: Containing epidemic outbreaks by message-passing techniques. Phys. Rev. X 4, 021024 (2014)
  8. Altarelli, F., Braunstein, A., Dall鈥橝sta, L., Zecchina, R.: Large deviations of cascade processes on graphs. Phys. Rev. E 87, 062115 (2013) CrossRef
  9. Altarelli, F., Braunstein, A., Dall鈥橝sta, L., Zecchina, R.: Optimizing spread dynamics on graphs by message passing. J. Stat. Mech. 2013(09), P09011 (2013) CrossRef
  10. Altarelli, F., Braunstein, A., Dall鈥橝sta, L., Zecchina, R.: Private communication (2014)
  11. Balogh, J., Bollob谩s, B., Duminil-Copin, H., Morris, R.: The sharp threshold for bootstrap percolation in all dimensions. Trans. Am. Math. Soc. 364(5), 2667鈥?701 (2012) CrossRef
  12. Balogh, J., Pittel, B.G.: Bootstrap percolation on the random regular graph. Random Struct. Algorithms 30(1鈥?), 257鈥?86 (2007) CrossRef
  13. Bapst, V., Coja-Oghlan, A., Hetterich, S., Rassmann, F., Vilenchik, D.: The Condensation Phase Transition in Random Graph Coloring. arXiv:1404.5513 (2014)
  14. Barbier, J., Krzakala, F., Zdeborova, L., Zhang, P.: The hard-core model on random graphs revisited. J. Phys. Conf. Ser. 473(1), 012021 (2013) CrossRef
  15. Barrat, A., Barthelemy, M., Vespignani, A.: Dynamical Processes on Complex Networks. Cambridge University Press, Cambridge (2008) CrossRef
  16. Battaglia, D., Kol谩艡, M., Zecchina, R.: Minimizing energy below the glass thresholds. Phys. Rev. E 70, 036107 (2004) CrossRef
  17. Bau, S., Wormald, N.C., Zhou, S.: Decycling numbers of random regular graphs. Random Struct. Algorithms 21(3鈥?), 397鈥?13 (2002) CrossRef
  18. Bayati, M., Gamarnik, D., Tetali, P.: Combinatorial approach to the interpolation method and scaling limits in sparse random graphs. Ann. Probab. 41(6), 4080鈥?115 (2013) CrossRef
  19. Beineke, L.W., Vandell, R.C.: Decycling graphs. J. Graph Theory 25(1), 59鈥?7 (1997) CrossRef
  20. Benevides, F., Przykucki, M.: Maximum Percolation Time in Two-Dimensional Bootstrap Percolation. arXiv (2013)
  21. Biroli, G., M茅zard, M.: Lattice glass models. Phys. Rev. Lett. 88, 025501 (2001) CrossRef
  22. Biskup, M., Schonmann, R.: Metastable behavior for bootstrap percolation on regular trees. J. Stat. Phys. 136(4), 667鈥?76 (2009) CrossRef
  23. Boccaletti, S., Latora, V., Moreno, Y., Chavez, M., Hwang, D.-U.: Complex networks: structure and dynamics. Phys. Rep. 424(4), 175鈥?08 (2006) CrossRef
  24. Bohman, T., Frieze, A., Wormald, N.C.: Avoidance of a giant component in half the edge set of a random graph. Random Struct. Algorithms 25(4), 432鈥?49 (2004) CrossRef
  25. Bohman, T., Picollelli, M.: Sir epidemics on random graphs with a fixed degree sequence. Random Struct. Algorithms 41(2), 179鈥?14 (2012) CrossRef
  26. Bordenave, C., Lelarge, M., Salez, J.: Matchings on infinite graphs. Probab. Theory Relat. Fields 157(1鈥?), 183鈥?08 (2013) CrossRef
  27. Chalupa, J., Leath, P.L., Reich, G.R.: Bootstrap percolation on a bethe lattice. J. Phys. C Solid State Phys. 12(1), L31 (1979) CrossRef
  28. Chen, N.: On the approximability of influence in social networks. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 鈥?8, pp. 1029鈥?037 (2008)
  29. Coja-Oghlan, A.: On belief propagation guided decimation for random k-sat. In: Proceedings of 22nd SODA, p. 957 (2011)
  30. Coja-Oghlan, A.: The Asymptotic \(k\) -sat Threshold. arXiv:1310.2728 (2013)
  31. Coja-Oghlan, A., Feige, U., Krivelevich, M., Reichman, D.: Contagious Sets in Expanders. 2465" class="a-plus-plus">arXiv:1306.2465 (2013)
  32. Daud茅, H., Mora, T., M茅zard, M., Zecchina, R.: Pairs of sat assignments and clustering in random boolean formulae. Theor. Comput. Sci. 393, 260鈥?79 (2008) CrossRef
  33. Ding, J., Sly, A., Sun, N.: Maximum independent sets on random regular graphs. arXiv:1310.4787 (2013)
  34. Dorogovtsev, S.N., Mendes, J.F.F.: Evolution of networks. Adv. Phys. 51(4), 1079鈥?187 (2002) CrossRef
  35. Dreyer Jr, P.A., Roberts, F.S.: Irreversible \(k\) -threshold processes: graph-theoretical threshold models of the spread of disease and of opinion. Discrete Appl. Math. 157(7), 1615鈥?627 (2009) CrossRef
  36. Franz, S., Leone, M.: Replica bounds for optimization problems and diluted spin systems. J. Stat. Phys. 111(3鈥?), 535鈥?64 (2003) CrossRef
  37. Franz, S., Leone, M., Toninelli, F.L.: Replica bounds for diluted non-poissonian spin systems. J. Phys. A Math. Gen. 36, 10967鈥?0985 (2003) CrossRef
  38. Frieze, A., Luczak, T.: On the independence and chromatic numbers of random regular graphs. J. Comb. Theory Ser B 54(1), 123鈥?32 (1992) CrossRef
  39. Granovetter, M.: Threshold models of collective behavior. Am. J. Sociol. 83, 1420鈥?443 (1978) CrossRef
  40. Guerra, F.: Broken replica symmetry bounds in the mean field spin glass model. Commun. Math. Phys. 233(1), 1鈥?2 (2003) CrossRef
  41. Haxell, P., Pikhurko, O., Thomason, A.: Maximum acyclic and fragmented sets in regular graphs. J. Graph Theory 57(2), 149鈥?56 (2008) CrossRef
  42. Hethcote, H.W.: The mathematics of infectious diseases. SIAM Rev. 42, 599 (2000) CrossRef
  43. Holroyd, A.E.: Sharp metastability threshold for two-dimensional bootstrap percolation. Probab. Theory Relat. Fields 125(2), 195鈥?24 (2003) CrossRef
  44. Janson, S., Luczak, M., Windridge, P.: Law of large numbers for the sir epidemic on a random graph with given degrees. arXiv:1308.5493 (2013)
  45. Janson, S., Luczak, T., Turova, T., Vallier, T.: Bootstrap percolation on the random graph \(g_{n, p}\) . Ann. Appl. Probab. 22(5), 1989鈥?047 (2012) CrossRef
  46. Karrer, B., Newman, M.E.J.: Message passing approach for general epidemic models. Phys. Rev. E 82, 016101 (2010) CrossRef
  47. Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through a social network. In: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 鈥?3, pp. 137鈥?46 (2003)
  48. Krzakala, F., Montanari, A., Ricci-Tersenghi, F., Semerjian, G., Zdeborov谩, L.: Gibbs states and the set of solutions of random constraint satisfaction problems. Proc. Natl. Acad. Sci. 104(25), 10318鈥?0323 (2007) CrossRef
  49. Kschischang, F., Frey, B., Loeliger, H.: Factor graphs and the sum-product algorithm. IEEE Trans. Inf. Theory 47(2), 498 (2001) CrossRef
  50. Lelarge, M.: Diffusion and cascading behavior in random networks. Games Econ. Behav. 75(2), 752鈥?75 (2012) CrossRef
  51. Lokhov, A.Y., M茅zard, M., Ohta, H., Zdeborova, L.: Inferring the Origin of an Epidemic with Dynamic Message-Passing Algorithm. arXiv:1303.5315 (2013)
  52. M茅zard, M., Montanari, A.: Reconstruction on trees and spin glass transition. J. Stat. Phys. 124(6), 1317鈥?350 (2006) CrossRef
  53. M茅zard, M., Montanari, A.: Information, Physics and Computation. Oxford University Press, Oxford (2009) CrossRef
  54. M茅zard, M., Parisi, G.: The Bethe lattice spin glass revisited. Eur. Phys. J. B. 20, 217 (2001) CrossRef
  55. M茅zard, M., Parisi, G.: The cavity method at zero temperature. J. Stat. Phys. 111(1鈥?), 1 (2003) CrossRef
  56. M茅zard, M., Zecchina, R.: Random \(k\) -satisfiability problem: from an analytic solution to an efficient algorithm. Phys. Rev. E 66(5), 056126 (2002) CrossRef
  57. Molloy, M.: The freezing threshold for k-colourings of a random graph. In: Proceedings of the 44th Symposium on Theory of Computing, p. 921. ACM (2012)
  58. Monasson, R.: Structural glass transition and the entropy of the metastable states. Phys. Rev. Lett. 75, 2847鈥?850 (1995) CrossRef
  59. Montanari, A., Parisi, G., Ricci-Tersenghi, F.: Instability of one-step replica-symmetry-broken phase in satisfiability problems. J. Phys. A 37(6), 2073 (2004) CrossRef
  60. Montanari, A., Ricci-Tersenghi, F.: On the nature of the low-temperature phase in discontinuous mean-field spin glasses. Eur. Phys. J. B. 33(3), 339鈥?46 (2003) CrossRef
  61. Montanari, A., Ricci-Tersenghi, F., Semerjian, G.: Clusters of solutions and replica symmetry breaking in random \(k\) -satisfiability. J. Stat. Mech. 2008(04), P04004 (2008) CrossRef
  62. Morris, R.: Minimal percolating sets in bootstrap percolation. Electron. J. Comb. 16(1), R2 (2009)
  63. Newman, M.: The structure and function of complex networks. SIAM Rev. 45(2), 167鈥?56 (2003) 2480" target="_blank" title="It opens in new window">CrossRef
  64. Panchenko, D.: The Sherrington鈥揔irkpatrick Model. Springer, New york (2013)
  65. Panchenko, D., Talagrand, M.: Bounds for diluted mean-fields spin glass models. Probab. Theory Relat. Fields 130(3), 319鈥?36 (2004) CrossRef
  66. Pinto, P.C., Thiran, P., Vetterli, M.: Locating the source of diffusion in large-scale networks. Phys. Rev. Lett. 109, 068702 (2012) CrossRef
  67. Reichman, D.: New bounds for contagious sets. Discrete Math. 312(10), 1812鈥?814 (2012) CrossRef
  68. Ricci-Tersenghi, F., Semerjian, G.: On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms. J. Stat. Mech. 2009(09), P09001 (2009) CrossRef
  69. Riordan, O., Warnke, L.: Achlioptas process phase transitions are continuous. Ann. Appl. Probab. 22(4), 1450鈥?464 (2012) CrossRef
  70. Rivoire, O., Biroli, G., Martin, O., M茅zard, M.: Glass models on Bethe lattices. Eur. Phys. J. B. 37, 55 (2004) CrossRef
  71. Qin, S.-M., Zhou, H.-J.: Solving the Undirected Feedback Vertex Set Problem by Local Search. arXiv:1405.0446 (2014)
  72. Shah, D., Zaman, T.: Rumors in a network: who鈥檚 the culprit? IEEE Trans. Inf. Theory 57(8), 5163鈥?181 (2011) CrossRef
  73. Shrestha, M., Moore, C.: Message-passing approach for threshold models of behavior in networks. Phys. Rev. E 89, 022805 (2014) CrossRef
  74. Talagrand, M.: The parisi formula. Ann. Math. 163, 221 (2006) CrossRef
  75. Zdeborov谩, L., M茅zard, M.: The number of matchings in random graphs. J. Stat. Mech. 2006(05), P05003 (2006) CrossRef
  76. Zhou, H.-J.: Spin glass approach to the feedback vertex set problem. Eur. Phys. J. B. 86(11), 1鈥? (2013) CrossRef
  
• 刊物类别：Physics and Astronomy
• 刊物主题：Physics
  Statistical Physics
  Mathematical and Computational Physics
  Physical Chemistry
  Quantum Physics
  
• 出版者：Springer Netherlands
• ISSN：1572-9613

文摘

The bootstrap percolation (or threshold model) is a dynamic process modelling the propagation of an epidemic on a graph, where inactive vertices become active if their number of active neighbours reach some threshold. We study an optimization problem related to it, namely the determination of the minimal number of active sites in an initial configuration that leads to the activation of the whole graph under this dynamics, with and without a constraint on the time needed for the complete activation. This problem encompasses in special cases many extremal characteristics of graphs like their independence, decycling or domination number, and can also be seen as a packing problem of repulsive particles. We use the cavity method (including the effects of replica symmetry breaking), an heuristic technique of statistical mechanics many predictions of which have been confirmed rigorously in the recent years. We have obtained in this way several quantitative conjectures on the size of minimal contagious sets in large random regular graphs, the most striking being that 5-regular random graph with a threshold of activation of 3 (resp. 6-regular with threshold 4) have contagious sets containing a fraction \(1/6\) (resp. \(1/4\) ) of the total number of vertices. Equivalently these numbers are the minimal fraction of vertices that have to be removed from a 5-regular (resp. 6-regular) random graph to destroy its 3-core. We also investigated Survey Propagation like algorithmic procedures for solving this optimization problem on single instances of random regular graphs.