6.4. Degree

Figure 6.1: PMF of degree in the Facebook dataset and in the WS model.

If the WS graph is a good model for the Facebook network, it should have the same average degree across nodes, and ideally the same variance in degree.

This function returns a list of degrees in a graph, one for each node:

def degrees(G):
    return [G.degree(u) for u in G]

The mean degree in model is $44$, which is close to the mean degree in the dataset, $43.7$.

However, the standard deviation of degree in the model is $1.5$, which is not close to the standard deviation in the dataset, $52.4$. Oops.

What’s the problem? To get a better view, we have to look at the distribution of degrees, not just the mean and standard deviation.

We will represent the distribution of degrees with a Pmf object, which is defined in the thinkstats2 module. Pmf stands for “probability mass function”.

Briefly, a Pmf maps from values to their probabilities. A Pmf of degrees is a mapping from each possible degree, d, to the fraction of nodes with degree d.

As an example, we construct a graph with nodes $1$, $2$, and $3$ connected to a central node, $0$:

G = nx.Graph()
G.add_edge(1, 0)
G.add_edge(2, 0)
G.add_edge(3, 0)
nx.draw(G)

Here’s the list of degrees in this graph:

>>> degrees(G)
[3, 1, 1, 1]

Node $0$ has degree $3$, the others have degree $1$. Now we can make a Pmf that represents this degree distribution:

>>> from thinkstats2 import Pmf
>>> Pmf(degrees(G))
Pmf({1: 0.75, 3: 0.25})

The result is a Pmf object that maps from each degree to a fraction or probability. In this example, $75$ of the nodes have degree $1$ and $25$ have degree $3$.

Now we can make a Pmf that contains node degrees from the dataset, and compute the mean and standard deviation:

>>> from thinkstats2 import Pmf
>>> pmf_fb = Pmf(degrees(fb))
>>> pmf_fb.Mean(), pmf_fb.Std()
(43.691, 52.414)

And the same for the WS model:

>>> pmf_ws = Pmf(degrees(ws))
>>> pmf_ws.mean(), pmf_ws.std()
(44.000, 1.465)

We can use the thinkplot module to plot the results:

thinkplot.Pdf(pmf_fb, label='Facebook')
thinkplot.Pdf(pmf_ws, label='WS graph')

Figure 6.1 shows the two distributions. They are very different.

In the WS model, most users have about $44$ friends; the minimum is $38$ and the maximum is $50$. That’s not much variation. In the dataset, there are many users with only $1$ or $2$ friends, but one has more than $1000$!

Distributions like this, with many small values and a few very large values, are called heavy-tailed.

You have attempted 1 of 1 activities on this page