C. Abbe and . Sandon, Community Detection in General Stochastic Block models: Fundamental Limits and Efficient Algorithms for Recovery, 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp.1503-00609
DOI : 10.1109/FOCS.2015.47

N. Ailon, Y. Chen, and H. Xu, Breaking the small cluster barrier of graph clustering, Journal of Machine Learning Research, 2014.

E. Airoldi, D. Blei, S. Fienberg, and E. Xing, Mixed membership stochastic blockmodels, J. Machine Learning Research, vol.9, pp.1981-2014, 2008.

N. Alon, Spectral techniques in graph algorithms, LATIN'98: theoretical informatics (Campinas, Lecture Notes in Comput. Sci, pp.206-215, 1380.

N. Alon and N. Kahale, A Spectral Technique for Coloring Random 3-Colorable Graphs, SIAM Journal on Computing, vol.26, issue.6, pp.1733-1748, 1997.
DOI : 10.1137/S0097539794270248

N. Alon and A. Naor, Approximating the Cut-Norm via Grothendieck's Inequality, SIAM Journal on Computing, vol.35, issue.4, pp.787-803, 2006.
DOI : 10.1137/S0097539704441629

B. Ames and S. Vavasis, Nuclear norm minimization for the planted clique and biclique problems, Mathematical Programming, vol.170, issue.1, pp.69-89, 2011.
DOI : 10.1007/s10107-011-0459-x

A. Amini, A. Chen, P. Bickel, and E. Levina, Pseudo-likelihood methods for community detection in large sparse networks, The Annals of Statistics, vol.41, issue.4, pp.2097-2122, 2013.
DOI : 10.1214/13-AOS1138SUPP

A. Amini and E. Levina, On semidefinite relaxations of the block model, 2014.

P. Bickel and A. Chen, A nonparametric view of network models and Newman???Girvan and other modularities, Proc. Natl. Acad. Sci. USA, pp.21068-21073, 2009.
DOI : 10.1073/pnas.0907096106

P. Bickel, D. Choi, X. Chang, and H. Zhang, Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels, The Annals of Statistics, vol.41, issue.4, pp.1922-1943, 2013.
DOI : 10.1214/13-AOS1124

B. Bollobas, Random graphs, Second edition, Cambridge Studies in Advanced Mathematics, vol.73, 2001.

B. Bollobas, S. Janson, and O. Riordan, The phase transition in inhomogeneous random graphs, Random Structures and Algorithms, pp.31-34, 2007.

R. Boppana, Eigenvalues and graph bisection: An average-case analysis, 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), pp.280-285, 1987.
DOI : 10.1109/SFCS.1987.22

C. Bordenave and A. Guionnet, Localization and delocalization of eigenvectors for heavy-tailed random matrices, Probability Theory and Related Fields, vol.206, issue.1, pp.885-953, 2013.
DOI : 10.1007/s00440-012-0473-9

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

C. Bordenave, M. Lelarge, and L. Massoulié, Non-backtracking Spectrum of Random Graphs: Community Detection and Non-regular Ramanujan Graphs, 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp.1501-06087
DOI : 10.1109/FOCS.2015.86

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

M. Braverman, K. Makarychev, Y. Makarychev, and A. Naor, The Grothendieck constant is strictly smaller than Krivine's bound, IEEE 52nd Annual Symposium on Foundations of Computer ScienceFOCS 2011, pp.453-462, 2011.

T. N. Bui, S. Chaudhuri, F. T. Leighton, and M. Sipser, Graph bisection algorithms with good average case behavior, Combinatorica, vol.36, issue.2, pp.7-171, 1987.
DOI : 10.1007/BF02579448

T. Cai and X. Li, Robust and computationally feasible community detection in the presence of arbitrary outlier vertices, 2014.

A. Celisse, J. Daudin, and L. Pierre, Consistency of maximum-likelihood and variational estimators in the stochastic block model, Electronic Journal of Statistics, vol.6, issue.0, pp.1847-1899, 2012.
DOI : 10.1214/12-EJS729

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

D. Chafa¨?chafa¨?, O. Guédon, G. Lecué, and A. Pajor, Interactions between compressed sensing random matrices and high dimensional geometry, Panoramas et Synthèses [Panoramas and Syntheses], 37. Société Mathématique de France

K. Chaudhuri, F. Chung, and A. Tsiatas, Spectral clustering of graphs with general degrees in the extended planted partition model, Conference Proceedings, pp.35-36, 2012.

Y. Chen, A. Jalali, S. Sanghavi, and H. Xu, Clustering partially observed graphs via convex optimization, Journal of Machine Learning Research, 2014.

Y. Chen and J. Xu, Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices, 2014.

P. Chin, A. Rao, and V. Vu, Stochastic block model and community detection in the sparse graphs: a spectral algorithm with optimal rate of recovery, 2015.

A. Coja-oghlan, Graph Partitioning via Adaptive Spectral Techniques, Combinatorics, Probability and Computing, vol.51, issue.02, pp.227-284, 2010.
DOI : 10.1137/S0097539794270248

C. Davis and W. M. Kahan, The Rotation of Eigenvectors by a Perturbation. III, SIAM Journal on Numerical Analysis, vol.7, issue.1, pp.1-46, 1970.
DOI : 10.1137/0707001

A. Decelle, F. Krzakala, C. Moore, and L. Zdeborova, Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications, Physical Review E, vol.84, issue.6, p.66106, 2012.
DOI : 10.1103/PhysRevE.84.066106

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

M. E. Dyer and A. M. Frieze, The solution of some random NP-hard problems in polynomial expected time, Journal of Algorithms, vol.10, issue.4, pp.451-489, 1989.
DOI : 10.1016/0196-6774(89)90001-1

U. Feige and E. Ofek, Spectral techniques applied to sparse random graphs, Random Structures and Algorithms, vol.25, issue.2, pp.251-275, 2005.
DOI : 10.1002/rsa.20089

J. Friedman, J. Kahn, and E. Szemeredi, On the second eigenvalue of random regular graphs, Proceedings of the twenty-first annual ACM symposium on Theory of computing , STOC '89, pp.587-598, 1989.
DOI : 10.1145/73007.73063

C. Gao, Z. Ma, A. Zhang, and H. Zhou, Achieving optimal misclassification proportion in stochastic block model, pp.1505-03772

M. Goemans and D. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM, vol.42, issue.6, pp.1115-1145, 1995.
DOI : 10.1145/227683.227684

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

A. Grothendieck, Résumé de la théorie métrique des produits tensoriels topologiques, Bol. Soc. Mat. São Paulo, vol.8, pp.1-79, 1953.

O. Guédon and R. Vershynin, Community detection in sparse networks via Grothendieck's inequality ArXiv, pp.1411-4686

A. Jalali, Y. Chen, S. Sanghavi, and H. Xu, Clustering partially observed graphs via convex optimization, ICML, 2011.

A. Joseph and B. Yu, Impact of regularization on spectral clustering, 2014.

L. Hagen and A. Kahng, New spectral methods for ratio cut partitioning and clustering, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol.11, issue.9, pp.1074-1085, 1992.
DOI : 10.1109/43.159993

P. W. Holland, K. B. Laskey, and S. Leinhardt, Stochastic blockmodels: First steps, Social Networks, vol.5, issue.2, pp.109-137, 1983.
DOI : 10.1016/0378-8733(83)90021-7

S. Khot and A. Naor, Grothendieck-Type Inequalities in Combinatorial Optimization, Communications on Pure and Applied Mathematics, vol.16, issue.3, pp.992-1035, 2012.
DOI : 10.1002/cpa.21398

M. Ledoux and M. Talagrand, Probability in Banach spaces. Isoperimetry and processes, Reprint of the 1991 edition, Classics in Mathematics, 2011.

J. Lei and A. Rinaldo, Consistency of spectral clustering in sparse stochastic block models Arxiv: 1312, 2013.

M. Lelarge, L. Massoulié, and J. Xu, Reconstruction in the labeled stochastic block model, Arxiv: 1502.03365, Preliminary version in Proceedings of the Information Theory Workshop, 2013.

J. Leskovec, K. Lang, A. Dasgupta, and M. Mahoney, Statistical properties of community structure in large social and information networks, Proceeding of the 17th international conference on World Wide Web , WWW '08, pp.695-704, 2008.
DOI : 10.1145/1367497.1367591

E. Levina, C. Le, and R. Vershynin, Sparse random graphs: regularization and concentration of the Laplacian, pp.1502-03049

C. Le and R. Vershynin, Concentration and regularization of random graphs, Random Structures & Algorithms, vol.27, issue.2013, pp.1506-00669
DOI : 10.1002/rsa.20713

J. Lindenstrauss and A. Pelczy´nskipelczy´nski, Absolutely summing operators in Lp-spaces and their applications, Studia Math, vol.29, pp.275-326, 1968.

L. Lovász and A. Schrijver, Cones of Matrices and Set-Functions and 0???1 Optimization, SIAM Journal on Optimization, vol.1, issue.2, pp.166-190, 1991.
DOI : 10.1137/0801013

F. Mcsherry, Spectral partitioning of random graphs, Proceedings 2001 IEEE International Conference on Cluster Computing, pp.529-537, 2001.
DOI : 10.1109/SFCS.2001.959929

L. Massoulié, Community detection thresholds and the weak Ramanujan property, Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC '14, 2013.
DOI : 10.1145/2591796.2591857

A. Montanari and S. Sen, Semidefinite programs on sparse random graphs, pp.1504-05910

E. Mossel, J. Neeman, and A. Sly, Belief propagation, robust reconstruction and optimal recovery of block models, The Annals of Applied Probability, vol.26, issue.4, 2013.
DOI : 10.1214/15-AAP1145

E. Mossel, J. Neeman, and A. Sly, Stochastic Block Models and Reconstruction, Probability Theory and Related Fields, 2014.

E. Mossel, J. Neeman, and A. Sly, A proof of the block model threshold conjecture, pp.1311-4115, 2014.

E. Mossel, J. Neeman, and A. Sly, Consistency Thresholds for the Planted Bisection Model, pp.1407-1591, 2014.

R. Nadakuditi and M. Newman, Graph Spectra and the Detectability of Community Structure in Networks, Physical Review Letters, vol.108, issue.18, p.188701, 2012.
DOI : 10.1103/PhysRevLett.108.188701

Y. Nesterov, Semidefinite relaxation and nonconvex quadratic optimization, Optimization Methods and Software, vol.160, issue.1-3, pp.141-160, 1998.
DOI : 10.1080/10556789808805690

M. Newman, Modularity and community structure in networks, Proc. Natl. Acad. Sci. USA 103, pp.8577-8582, 2006.
DOI : 10.1073/pnas.0601602103

K. Nowicki and T. Snijders, Estimation and Prediction for Stochastic Blockstructures, Journal of the American Statistical Association, vol.96, issue.455, pp.1077-1087, 2001.
DOI : 10.1198/016214501753208735

S. Oymak and B. Hassibi, Finding dense clusters via low rank + sparse decomposition, CoRR, 2011.

G. Pisier, Grothendieck???s Theorem, past and present, Bulletin of the American Mathematical Society, vol.49, issue.2, pp.237-323, 2012.
DOI : 10.1090/S0273-0979-2011-01348-9

T. Qin and K. Rohe, Regularized spectral clustering under the degree-corrected stochastic blockmodel, pp.1309-4111

K. Rohe, S. Chatterjee, and B. Yu, Spectral clustering and the high-dimensional stochastic blockmodel, The Annals of Statistics, vol.39, issue.4, pp.1878-1915, 2011.
DOI : 10.1214/11-AOS887

T. Snijders and K. Nowicki, Estimation and prediction for stochastic block-structures for graphs with latent block structure, Journal of Classification14, pp.75-100, 1997.

S. Strogatz, Exploring complex networks, Nature, vol.84, issue.6825, pp.268-276, 2001.
DOI : 10.1038/35065725

V. Vu, Singular vectors under random perturbation, Random Structures & Algorithms, vol.20, issue.4, pp.526-538, 2011.
DOI : 10.1002/rsa.20367

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