1
$\begingroup$

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?

(Curious about this in light of recent NSA revelations)

$\endgroup$
2
  • $\begingroup$ I highly doubt it. $\endgroup$ – George V. Williams Jul 17 '13 at 22:51
  • $\begingroup$ 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. $\endgroup$ – mbrenig Jul 17 '13 at 22:54
3
$\begingroup$

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.

Once you have suitable parameters, generate some of these networks and use that to estimate the proportion of people that are distance 1, 2, or 3. (We could similarly estimate any other statistic.)


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.

$\endgroup$
2
  • $\begingroup$ I'm new here and can't up vote. But If I could I would. Will research tonight. $\endgroup$ – mbrenig Jul 17 '13 at 23:14
  • $\begingroup$ @mbrenig Welcome to Math.SE. If this answer is satisfactory, you can accept it, no matter how much rep you have, by clicking the checkmark to the left. $\endgroup$ – Code-Guru Jul 19 '13 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.