H. Zhou, Spin glass approach to the feedback vertex set problem, The European Physical Journal B, vol.12, issue.11, p.455, 2013.
DOI : 10.1140/epjb/e2013-40690-1

F. Altarelli, A. Braunstein, L. Dallasta, and R. Zecchina, Optimizing spread dynamics on graphs by message passing, Journal of Statistical Mechanics: Theory and Experiment, vol.2013, issue.09, pp.2013-09011, 2013.
DOI : 10.1088/1742-5468/2013/09/P09011

URL : http://arxiv.org/abs/1203.1426

A. Guggiola and G. Semerjian, Minimal Contagious Sets in Random Regular Graphs, Journal of Statistical Physics, vol.86, issue.11, pp.300-358, 2015.
DOI : 10.1007/s10955-014-1136-2

URL : https://hal.archives-ouvertes.fr/hal-01061756

F. Morone and H. A. Makse, Influence maximization in complex networks through optimal percolation, Nature, vol.78, issue.7563, pp.65-68, 2015.
DOI : 10.1038/nature14604

S. Mugisha and H. Zhou, Identifying optimal targets of network attack by belief propagation. arXiv preprint, 2016.

A. Braunstein, L. Dall-'asta, G. Semerjian, and L. Zdeborová, Network dismantling, Proceedings of the National Academy of Sciences, vol.113, issue.44, 2016.
DOI : 10.1073/pnas.1605083113

URL : http://www.ncbi.nlm.nih.gov/pmc/articles/PMC5098660

S. Qin, Y. Zeng, and H. Zhou, Spin glass phase transitions in the random feedback vertex set problem, 2016.

P. Clusella, P. Grassberger, F. J. Pérez-reche, and A. Politi, Immunization and Targeted Destruction of Networks using Explosive Percolation, Physical Review Letters, vol.117, issue.20, 2016.
DOI : 10.1103/PhysRevLett.117.208301

R. M. Karp, Reducibility among combinatorial problems, Complexity of computer computations, pp.85-103
DOI : 10.1007/978-3-540-68279-0_8

S. Janson and A. Thomason, Dismantling Sparse Random Graphs, Combinatorics, Probability and Computing, vol.5, issue.02, pp.259-264, 2008.
DOI : 10.1002/jgt.3190180305

M. Richardson and P. Domingos, Mining knowledgesharing sites for viral marketing, Proceedings of 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp.61-70, 2002.
DOI : 10.1145/775047.775057

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.7697

D. Kempe, J. Kleinberg, and E. Tardos, Maximizing the spread of influence through a social network, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining , KDD '03, pp.105-147, 2015.
DOI : 10.1145/956750.956769

K. Jung, W. Heo, and W. Chen, IRIE: Scalable and Robust Influence Maximization in Social Networks, 2012 IEEE 12th International Conference on Data Mining, pp.918-923, 2012.
DOI : 10.1109/ICDM.2012.79

URL : http://arxiv.org/abs/1111.4795

C. Borgs, M. Brautbar, J. Chayes, and B. Lucier, Maximizing Social Influence in Nearly Optimal Time, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.946-957, 2014.
DOI : 10.1137/1.9781611973402.70

URL : http://arxiv.org/abs/1212.0884

R. Albert, H. Jeong, and A. Barabási, Error and attack tolerance of complex networks, Nature, vol.1696, issue.6794, pp.378-382, 2000.
DOI : 10.1038/35019019

R. Cohen, K. Erez, D. , and S. Havlin, Breakdown of the internet under intentional attack. Physical review letters, p.3682, 2001.

S. Bau, N. C. Wormald, and S. Zhou, Decycling numbers of random regular graphs, Random Structures and Algorithms, vol.85, issue.3-4, pp.3-4397, 2002.
DOI : 10.1002/rsa.10069

K. Goh, B. Kahng, D. K. Subelj, and M. Bajec, Universal behavior of load distribution in scale-free networks Robust network community detection using balanced propagation, Phys. Rev. Lett. Eur. Phys. J. B, vol.87, issue.81, pp.278701353-362, 2001.

D. Bu, Y. Zhao, L. Cai, H. Xue, X. Zhu et al., Topological structure analysis of the protein-protein interaction network in budding yeast, Nucleic Acids Research, vol.31, issue.9, pp.2443-2450, 2003.
DOI : 10.1093/nar/gkg340

D. J. Watts and S. H. Strogatz, Collective dynamics of 'small-world' netowrks, Nature, vol.393, issue.6684, pp.440-442, 1998.
DOI : 10.1038/30918

J. Leskovec, J. Kleinberg, and C. Faloutsos, Graphs over time, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining , KDD '05, pp.177-187, 2005.
DOI : 10.1145/1081870.1081893

J. Leskovec, J. Kleinberg, and C. Faloutsos, Graph evolution, ACM Transactions on Knowledge Discovery from Data, vol.1, issue.1, 2007.
DOI : 10.1145/1217299.1217301

M. Ripeanu, I. Foster, and A. Iamnitchi, Mapping the gnutella network: Properties of large-scale peer-to-peer systems and implications for system design, IEEE Internet Comput, vol.6, pp.50-57, 2002.

E. Cho, S. A. Myers, and J. Leskovec, Friendship and mobility, Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD '11, pp.1082-1090, 2011.
DOI : 10.1145/2020408.2020579

J. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahoney, Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters, Internet Mathematics, vol.6, issue.1, pp.29-123, 2009.
DOI : 10.1080/15427951.2009.10129177

P. Zhang, Nonbacktracking operator for the Ising model and its applications in systems with multiple states, Physical Review E, vol.91, issue.4, p.42120, 2015.
DOI : 10.1103/PhysRevE.91.042120

S. Pei, X. Teng, J. Shaman, F. Morone, and H. A. Makse, Collective influence maximization in threshold models of information cascading with first-order transitions. arXiv preprint, 2016.

F. Krzakala, C. Moore, E. Mossel, J. Neeman, A. Sly et al., Spectral redemption in clustering sparse networks, Proc. Natl. Acad. Sci. USA, pp.11020935-20940, 2013.
DOI : 10.1073/pnas.1312486110

URL : https://hal.archives-ouvertes.fr/cea-01223434

E. On and R. Networks, Each data point is the mean and standard deviation of ? (the fraction of deleted nodes) over 96 dismantling solutions obtained by CoreHD or CoreCI on 96 independent network instances of size N = 10 5 and mean degree c (ER and SF) or degree K (RR) The ball radius of CoreCI is fixed to = 4. The SF network instances are generated by the static method, TABLE II. Comparing the dismantling performance of CoreHD and CoreCI