# Given average network diameter, how many nodes are three hops away.

The University of Milan found in 2011 that everyone on the Internet was, on average, 4.74 steps away from anyone else.. is that information sufficient to answer this question:

What proportion of people on the internet are, 1, 2 or 3 steps away from the average person?

With simplifying assumptions - could you make a guess?

• I highly doubt it. – George V. Williams Jul 17 '13 at 22:51
• I agree it's almost certainly not sufficient. At one extreme I could split all people in to two groups and construct two very connected graphs, then connect them by a narrow single person bridge and shuffle the hyper connected graph sizes to get the 4.74 step average. Obviously the internet doesn't look like that, so I'd like to know more about how you model a question like this. – mbrenig Jul 17 '13 at 22:54

First, we'd need an estimate of the number of people on the internet, $N$ say. With an estimate of $N$, we can model the network in a variety of ways. If you want a realistic model, it's probably much easier to estimate these numbers experimentally.
The next step is to find a model you like; e.g. take some model with desirable properties (e.g. some scale-free model) that has some parameter (such as the probability $p$ of an edge occurring). Use the model to generate $N$-vertex graphs, and estimate the distance between two random nodes. If the average distance is less than 4.74, increase $p$, and if it's greater than 4.74, decrease $p$. Eventually you'll obtain a model that gives you both the correct number of nodes and a reasonable approximation of the average distance.
The above outlines how it could be done in principle. In practice, it'll take considerable effort, since $N$ is quite large. The answer will also vary greatly on the choice of model; a modified Barabási–Albert model might be suitable. (What an edge is in this network wasn't defined in the question; so that's an important factor.) There's probably a zillion papers presenting various models for different levels of the internet.