Discovering the graph topology itself it is a very challenging task.

In fact for the Internet, no one has a precise map of the Internet.

You may think somewhere in the world that there is a place that stores the map of

the Internet. Actually, there is no such map.

If we're talking about the AS, autonomous system relation graph, many links are

missing. These business or physical links are not

reported or recorded. There also whats called Internet exchange

points. For example, thousands of these just in

Europe. As pairing shortcuts, they decide that

instead of going through some bigger autonomous system, they will form a short

cut themselves, say between two smaller and medium-sized autonomous systems and

often these are not reported. So, it's widely reported that it could be

more than half of the links actually missing and therefore we are not even

close to having precise view of the AS graph.

But what about the router level graph with physical links that we are focusing on

today? Often, the topology is estimated or

inferred based on some measurements. These are limited measurements called say

traceroutes. But it is also widely reported that because of the protocol

details, traceroutes often lead to bias the sampling.

In other words, in a huge network, , with many nodes and many links, a lot of links

are not properly recorded by this measurement methodology.

And in fact, near the edge of the network, for example, near your, corporation, near

on a campus, or near your home, High-rise buildings as opposed to in the

backbone of the network. There's often no scalable measurement

platforms. So at the router level, the graph is also

not known for sure. There are many missing links.

But let's assume again incorrectly, that we can measure the degrees accurately and

see what we can say. So let's skip the important fact that

robustness is more than just about a graph,

And skip the fact that these graphs, we do not yet have a good view.

And just go straight to say, suppose we believe that we can measure the degrees

and that's all that matters. The topology is all that matters.

Let's see what we can say. Alright.

So what is the degree distribution we observe for router level graphs?

Well, we can tabulate these degrees into a histogram.

And we can, therefore construct the probability distribution.

Let's say probability that a node's degree x is assuming a certain specific value

small x. And often, people look at the tail distribution, which is the

probability that the node degree x is bigger than or equal to a specific value

small x. It turns out that,

If you look at the either AS or router level, although the router level graph is

as well focusing right now. The tail distribution roughly follows x to

the power of minus alpha with sum constant k in front of it.

This alpha here is a constant parameter that describes that the decay of the tail

distribution and this approximate symbol basically says that for sufficiently large