Category Archives: Random graphs
Guest post by Miklos Racz: Confidence sets for the root in uniform and preferential attachment trees
In the final post of this series (see here for the previous posts) we consider yet another point of view for understanding networks. In the previous posts we studied random graph models with community structure and also models with an … Continue reading
Posted in Probability theory, Random graphs
Comments Off on Guest post by Miklos Racz: Confidence sets for the root in uniform and preferential attachment trees
Guest post by Miklos Racz: Entropic central limit theorems and a proof of the fundamental limits of dimension estimation
In this post we give a proof of the fundamental limits of dimension estimation in random geometric graphs, based on the recent work of Bubeck and Ganguly. We refer the reader to the previous post for a detailed introduction; here … Continue reading
Posted in Probability theory, Random graphs
Comments Off on Guest post by Miklos Racz: Entropic central limit theorems and a proof of the fundamental limits of dimension estimation
Guest post by Miklos Racz: Estimating the dimension of a random geometric graph on a high-dimensional sphere
Following the previous post in which we studied community detection, in this post we study the fundamental limits of inferring geometric structure in networks. Many networks coming from physical considerations naturally have an underlying geometry, such as the network of … Continue reading
Posted in Probability theory, Random graphs
Comments Off on Guest post by Miklos Racz: Estimating the dimension of a random geometric graph on a high-dimensional sphere
Guest post by Miklos Racz: A primer on exact recovery in the general stochastic block model
Foreword: this will be a series of blog posts written by our Theory Group postdoc Miklos Racz. It is essentially the transcript of a mini-course that Miki gave at the University of Washington and at the XX Brazilian School of … Continue reading
Posted in Probability theory, Random graphs
Comments Off on Guest post by Miklos Racz: A primer on exact recovery in the general stochastic block model
Some pictures in geometric probability
As I discussed in a previous blog post, I have been recently interested in models of randomly growing networks. As a starting point I focused my attention on the preferential attachment rule and its variants, in part because its ubiquity … Continue reading
Posted in Probability theory, Random graphs
2 Comments
What’s the (hi)story of my network?
First an announcement: we have researcher and postdoc positions available in Theory Group at MSR, and I may have a position for an intern in the summer. If you are a talented young mathematician with interests in the kind of … Continue reading
Posted in Random graphs
3 Comments
On the influence of the seed graph in the preferential attachment model
The preferential attachment model, introduced in 1992 by Mahmoud and popularized in 1999 by Barabási and Albert, has attracted a lot of attention in the last decade. In its simplest form it describes the evolution of a random tree. Formally we denote by … Continue reading
Posted in Random graphs
9 Comments
Random-Approx 2013
Last week I attended the Random-Approx conference at Berkeley. I missed quite a few talks as I was also settling in my new office for the semester at the Simons Institute so I will just report on the three invited talks: Luca Trevisan gave a … Continue reading
Posted in Random graphs, Theoretical Computer Science
2 Comments
Guest post by Philippe Rigollet: Estimating structured graphs
Last wednesday, Sourav Chatterjee was speaking in the Mathematics Colloquium here at Princeton. While he is most famous for his contributions to probability, especially using Stein’s method, this talk was rather statistical. The problem was interesting and its solution simple enough that … Continue reading
Posted in Random graphs
Comments Off on Guest post by Philippe Rigollet: Estimating structured graphs
Proof of the lower bound
Our proof of the lower bound for the clique number of random geometric graphs (see Theorem 1 in the previous post) is a little bit contrived, but it might actually have some value. Our approach can be described as follows. … Continue reading
Posted in Random graphs
Comments Off on Proof of the lower bound