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
Breaking the small cluster barrier of graph clustering, Journal of Machine Learning Research, 2014. ,
Mixed membership stochastic blockmodels, J. Machine Learning Research, vol.9, pp.1981-2014, 2008. ,
Spectral techniques in graph algorithms, LATIN'98: theoretical informatics (Campinas, Lecture Notes in Comput. Sci, pp.206-215, 1380. ,
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
Approximating the Cut-Norm via Grothendieck's Inequality, SIAM Journal on Computing, vol.35, issue.4, pp.787-803, 2006. ,
DOI : 10.1137/S0097539704441629
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
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
On semidefinite relaxations of the block model, 2014. ,
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
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
Random graphs, Second edition, Cambridge Studies in Advanced Mathematics, vol.73, 2001. ,
The phase transition in inhomogeneous random graphs, Random Structures and Algorithms, pp.31-34, 2007. ,
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
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
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
The Grothendieck constant is strictly smaller than Krivine's bound, IEEE 52nd Annual Symposium on Foundations of Computer ScienceFOCS 2011, pp.453-462, 2011. ,
Graph bisection algorithms with good average case behavior, Combinatorica, vol.36, issue.2, pp.7-171, 1987. ,
DOI : 10.1007/BF02579448
Robust and computationally feasible community detection in the presence of arbitrary outlier vertices, 2014. ,
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
Interactions between compressed sensing random matrices and high dimensional geometry, Panoramas et Synthèses [Panoramas and Syntheses], 37. Société Mathématique de France ,
Spectral clustering of graphs with general degrees in the extended planted partition model, Conference Proceedings, pp.35-36, 2012. ,
Clustering partially observed graphs via convex optimization, Journal of Machine Learning Research, 2014. ,
Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices, 2014. ,
Stochastic block model and community detection in the sparse graphs: a spectral algorithm with optimal rate of recovery, 2015. ,
Graph Partitioning via Adaptive Spectral Techniques, Combinatorics, Probability and Computing, vol.51, issue.02, pp.227-284, 2010. ,
DOI : 10.1137/S0097539794270248
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
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
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
Spectral techniques applied to sparse random graphs, Random Structures and Algorithms, vol.25, issue.2, pp.251-275, 2005. ,
DOI : 10.1002/rsa.20089
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
Achieving optimal misclassification proportion in stochastic block model, pp.1505-03772 ,
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
Résumé de la théorie métrique des produits tensoriels topologiques, Bol. Soc. Mat. São Paulo, vol.8, pp.1-79, 1953. ,
Community detection in sparse networks via Grothendieck's inequality ArXiv, pp.1411-4686 ,
Clustering partially observed graphs via convex optimization, ICML, 2011. ,
Impact of regularization on spectral clustering, 2014. ,
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
Stochastic blockmodels: First steps, Social Networks, vol.5, issue.2, pp.109-137, 1983. ,
DOI : 10.1016/0378-8733(83)90021-7
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
Probability in Banach spaces. Isoperimetry and processes, Reprint of the 1991 edition, Classics in Mathematics, 2011. ,
Consistency of spectral clustering in sparse stochastic block models Arxiv: 1312, 2013. ,
Reconstruction in the labeled stochastic block model, Arxiv: 1502.03365, Preliminary version in Proceedings of the Information Theory Workshop, 2013. ,
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
Sparse random graphs: regularization and concentration of the Laplacian, pp.1502-03049 ,
Concentration and regularization of random graphs, Random Structures & Algorithms, vol.27, issue.2013, pp.1506-00669 ,
DOI : 10.1002/rsa.20713
Absolutely summing operators in Lp-spaces and their applications, Studia Math, vol.29, pp.275-326, 1968. ,
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
Spectral partitioning of random graphs, Proceedings 2001 IEEE International Conference on Cluster Computing, pp.529-537, 2001. ,
DOI : 10.1109/SFCS.2001.959929
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
Semidefinite programs on sparse random graphs, pp.1504-05910 ,
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
Stochastic Block Models and Reconstruction, Probability Theory and Related Fields, 2014. ,
A proof of the block model threshold conjecture, pp.1311-4115, 2014. ,
Consistency Thresholds for the Planted Bisection Model, pp.1407-1591, 2014. ,
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
Semidefinite relaxation and nonconvex quadratic optimization, Optimization Methods and Software, vol.160, issue.1-3, pp.141-160, 1998. ,
DOI : 10.1080/10556789808805690
Modularity and community structure in networks, Proc. Natl. Acad. Sci. USA 103, pp.8577-8582, 2006. ,
DOI : 10.1073/pnas.0601602103
Estimation and Prediction for Stochastic Blockstructures, Journal of the American Statistical Association, vol.96, issue.455, pp.1077-1087, 2001. ,
DOI : 10.1198/016214501753208735
Finding dense clusters via low rank + sparse decomposition, CoRR, 2011. ,
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
Regularized spectral clustering under the degree-corrected stochastic blockmodel, pp.1309-4111 ,
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
Estimation and prediction for stochastic block-structures for graphs with latent block structure, Journal of Classification14, pp.75-100, 1997. ,
Exploring complex networks, Nature, vol.84, issue.6825, pp.268-276, 2001. ,
DOI : 10.1038/35065725
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