Scale-free networks

The Twitter degree histograms are a characteristic of power-law degree distributions. Unlike the normally distributed, randomly generated graph, the Twitter histograms show that a few vertices are connected to a large majority of the edges.

Note

The term "scale-free network" was coined by researchers at the University of Notre Dame in 1999 to describe the structure they observed on the World Wide Web.

In the graphs that model human interactions, we'll often observe a power law of connectedness. This is also called the Zipf scale and it indicates the so-called "law of preferential attachment", where a popular vertex is more likely to develop additional connections. Social media sites are prime examples of this sort of a process, where new users tend to follow already popular users.

In Chapter 2, Inference, we identified the exponential distribution by looking for a straight line when the data was plotted on log-linear axes. We can most easily determine a power-law relationship...