• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Mini-course:"Statistical Network Analysis" Professor Olga Klopp

On May 30 – June 08 professor of The University Paris West (France) Olga Klopp read the mini-course "Statistical Network Analysis"

"Statistical Network Analysis"

The study of networks is an old problem considered almost independently in different fields: social science, computer science, statistical physics, biology. Recently   there was a considerable interest in statistics for statistical network analysis which is motivated by a number of applications. The goal of this course is to give an introduction to this topic and an overview of some recent results in this area.

Content 

➔    Introduction. The Erdös-Renyi model. The Stochastic Block Model (SBM).

➔    Analysis of the  Stochastic Block Model: estimation of labels, estimation of parameters. Extensions of the SBM.

➔    Spectral Clustering.

➔    Exact recovery in the general SBM.

➔   Graphons and non-parametric estimation. Graphex.

➔   Graph limit theory. Cut distance.

➔   Random geometric graph on a high-dimensional sphere.

➔   Uniform and preferential attachment trees.

References

1.                 E. Abbe and C. Sandon. Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms. In Proceedings of the 56-th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, 2015.

2.                 C. Borgs, J.T. Chayes, H. Cohn, and S. Ganguly. Consistent nonparametric estimation for heavy-tailed sparse graphs. ArXiv e-prints, August 2015.

3.                 S. Bubeck, J. Ding, R. Eldan, and M. Z. Rácz. Testing for high-dimensional geometry in random graphs. Random Structures & Algorithms, 49(3):503–532, 2016.

4.                 S. Bubeck, E. Mossel, and M. Z. Rácz. On the influence of the seed graph in the preferential attachment model. IEEE Transactions on Network Science and Engineering, 2(1):30–39, 2015.

5.                 U Feige and E Ofek. Spectral techniques applied to sparse random graphs. Random Struct. Algorithms, 27(2):251–275, 2005.

6.                 Olga Klopp, Alexandre B. Tsybakov, and Nicolas Verzelen. Oracle inequalities for network models and sparse graphon estimation. Ann. Statist., 45(1):316–354, 2017.

7.                 Olga Klopp, Alexandre B. Tsybakov and Nicolas Verzelen. Optimal graphon estimation in cut distance  ArXiv e-prints, March 2017.

8.                 Jing Lei and Alessandro Rinaldo. Consistency of spectral clustering in stochastic block models. Ann. Statist., 43(1):215–237, 2015.

9.                 László Lovász. Large networks and graph limits, volume 60 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2012.

10.             Miklós Z. Rácz with Sébastien Bubeck. Basic models and questions in statistical network analysis.  ArXiv e-prints, September 2016.

11.             Dan-Cristian Tomozei and Laurent Massoulie. Distributed User Profiling via Spectral Methods. In Sigmetrics 2010, volume 38, pages 383–384. ACM Sigmetrics, 2010.

12.             Victor Veitch and Daniel M. Roy. The Class of Random Graphs Arising from Exchangeable Random Measures.  ArXiv e-prints, December 2015.

13.             Van Vu. A simple svd algorithm for finding hidden partitions. ArXiv 1404.3918, April 2014.