P. Holland, K. Laskey, and S. Leinhardt, Stochastic blockmodels: First steps, Social Networks, vol.5, pp.109-137, 1983.

Y. Wang and G. Wong, Stochastic Blockmodels for Directed Graphs, Journal of the American Statistical Association, vol.82, issue.397, pp.8-19, 1987.

V. Luxburg and U. , A tutorial on spectral clustering, Statistics and computing, vol.17, issue.4, pp.395-416, 2007.

P. Bickel and A. Chen, A nonparametric view of network models and Newman-Girvan and other modularities, PNAS, vol.106, pp.21068-21073, 2009.

A. Coja-oghlan, M. E. Vilenchik, and D. , A Spectral Approach to Analyzing Belief Propagation for 3-Coloring, Combinatorics, Probability and Computing, vol.18, pp.881-912, 2009.

A. Coja-oghlan, Graph partitioning via adaptive spectral techniques, Combinatorics, Probability and Computing, vol.19, issue.02, pp.227-284, 2010.

F. Mcsherry, Spectral partitioning of random graphs, Proceedings. 42nd IEEE Symposium on, pp.529-537, 2001.

R. Nadakuditi and M. Newman, Graph spectra and the detectability of community structure in networks, Phys. Rev. Lett, vol.108, p.188701, 2012.

A. Decelle, F. Krzakala, C. Moore, and L. Zdeborova, Phase transition in the detection of modules in sparse networks, Physical Review Letters, vol.107, p.65701, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00625321

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, p.66106, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00661643

E. Mossel, J. Neeman, and A. Sly, Stochastic Block Models and Reconstruction, 2012.

P. Zhang, F. Krzakala, J. Reichardt, and L. Zdeborová, Comparative study for inference of hidden classes in stochastic block models, Journal of Statistical Mechanics: Theory and Experiment, vol.2012, issue.12, p.12021, 2012.

B. Mckay, The expected eigenvalue distribution of a large regular graph, Linear Algebra and its Applications, vol.40, pp.203-216, 1981.

S. Sasha, Random matrices, nonbacktracking walks, and orthogonal polynomials, Journal of Mathematical Physics, p.48, 2007.

J. Friedman, A proof of Alon's second eigenvalue conjecture and related problems, Memoirs of the American Mathematical Society, issue.910, 2008.

K. -. Hashimoto, Zeta functions of finite graphs and representations of p-adic groups. Automorphic forms and geometry of arithmetic varieties, pp.211-280, 1989.

N. Alon, I. Benjamini, L. E. Sasha, and S. , Non-backtracking random walks mix faster, Communications in Contemporary Mathematics, vol.9, issue.4, pp.585-603, 2007.

Y. Watanabe and K. Fukumizu, Graph zeta function in the Bethe free energy and loopy belief propagation, 2010.

P. O. Vontobel, Connecting the Bethe entropy and the edge zeta function of a cycle code, IEEE International Symposium on Information Theory Proceedings (ISIT), pp.704-708, 2010.

P. Ren, R. C. Wilson, and E. R. Hancock, Graph characterization via Ihara coefficients, IEEE Transactions on Neural Networks, vol.22, issue.2, pp.233-245, 2011.

E. Wigner, On the distribution of the roots of certain symmetric matrices, Ann. Math, vol.67, issue.2, pp.325-327, 1958.

M. Krivelevich and B. Sudakov, The largest eigenvalue of sparse random graphs, Combinatorics, Probability and Computing, vol.12, issue.01, pp.61-72, 2003.

B. Bollobas, J. Svante, and R. Oliver, The phase transition in inhomogeneous random graphs, Random Structures & Algorithms, vol.31, pp.3-122, 2007.

H. Kesten and B. Stigum, Additional limit theorems for indecomposable multidimensional Galton-Watson processes, Ann. Math. Statist, vol.37, pp.1463-1481, 1966.

E. Mossel and Y. Peres, Information flow on trees, The Annals of Applied Probability, vol.13, pp.817-844, 2003.

H. Bass, The Ihara-Selberg zeta function of a tree lattice, International Journal of Mathematics, vol.3, issue.06, pp.717-797, 1992.

O. Angel, J. Friedman, and S. Hoory, The non-backtracking spectrum of the universal cover of a graph, 2007.

T. Richardson and R. Urbanke, Modern coding theory, 2008.
DOI : 10.1017/cbo9780511791338

L. Adamic and N. Glance, The political blogosphere and the 2004 US Election: Divided They Blog, Proc 3rd Intl Workshop on Link Discovery, 2005.
DOI : 10.1145/1134271.1134277

W. Zachary, An information flow model for conflict and fission in small groups, Journal of Anthropological Research, vol.33, pp.4520-473, 1977.

M. Newman, Finding community structure in networks using the eigenvectors of matrices, Physical review E, vol.74, issue.3, p.36104, 2006.

M. Girvan and M. E. Newman, Community structure in social and biological networks, Proceedings of the National Academy of Sciences, vol.99, issue.12, pp.7821-7826, 2002.

D. Lusseau, K. Schneider, O. Boisseau, P. Haase, E. Slooten et al., The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations, Behavioral Ecology and Sociobiology, vol.54, issue.4, pp.396-405, 2003.

, A matlab demo file can be

B. Ball, B. Karrer, and M. Newman, Efficient and principled method for detecting communities in networks, Physical Review E, vol.84, issue.3, p.36103, 2011.

A. Chen, A. Amini, P. Bickel, and E. Levina, Fitting community models to large sparse networks, 2012.

P. Gopalan, D. Mimno, S. Gerrish, M. Freedman, and D. Blei, Scalable inference of overlapping communities, Advances in Neural Information Processing Systems, vol.25, pp.2258-2266, 2012.