Finally, we'll learn about another model for generating realistic complex networks. The story begins with Albert Laszlo Barabasi, one of the world's leading network scientists. Barabasi observed that many real-world complex networks have degree distributions that are decaying power laws of the form P of k goes as k to the minus Gamma, where the constant Gamma is the exponent of the power law. Because a power law remains a power-law after a re-scaling operation, K becoming k over k naught for any scaling factor k naught had agreed distribution that is a power law, is also said to be scale-free. Together with his then PhD student, Reka Albert, and post-doc Hawoong Jeong, Barabasi started looking for more examples of real-world networks that have scale-free degree distributions. By writing a BAD that would crawl web-pages by following URLs that they contain, Barabasi and his group mapped out over 3 billion documents on the World Wide Web as a complex network and found a power law for its degree distribution. Barabasi and his group made this discovery in the year 2000. An interesting question to ask might be, why didn't anyone discover it earlier? After all, the World Wide Web was created in 1990. It's been growing in scale and importance ever since. One possible reason for this might be that researchers plotting the degree distribution used a linear-linear scale. In this graph, three decaying curves are plotted on the linear-linear scale, and it's rather difficult to tell that they do not all have the same functional form. Only when we plot these curves on the semi-log scale on the right. In, on the log-log scale on the left, we can see that they're different. First, the black curve becomes a straight line when plotted on a semi-log scale, telling us that it's an exponential decay. On this scale, the red and blue curves decay slower and it exponential decay. Second, when we plot the three curves on a log-log scale, the red and the blue curves become straight lines. This tells us that both of them have the functional form log y equals negative k log x plus C, which is what we would expect if they were power-law is of the form y equals a times x to the power of minus k. The black curve, which we've established to be an exponential decay now curves downwards on the log-log scale. The moral of the story is, in order to establish the functional form of decaying curves, do not plot them on the linear-linear scale. Instead plot them first in the semi-log scale to see which ones might be decay exponentially and then in the log-log scale to see which others might be decaying power laws. Barabasi went further to compare road networks with air traffic networks. In a road network, nodes are intersections between roads, whereas links are non-branching road segments. In an air traffic network, nodes are airports and links are the flights that connect pairs of airports. For the United States, Barabasi found that the road network has a degree distribution that resembles a Poisson distribution. Which means the road network shares many statistical similarities with a random network. Most nodes have the same number of links and there are no highly connected nodes. But for the air traffic network, Barabasi found that the degree distribution is scale-free because the smaller airports are connected first to small hubs, which in turn connect to a larger airport hubs. So far, we've seen how scale-free networks have been discovered in engineered systems like roads and air travel. Looking at biochemical networks in archaea, bacteria, and eukaryotes, we find that the degree distribution is power law and has the same exponent of 2.2. In fact, let's also dive into some social data. For example, the IMDB Network, International Movie Database, and construct a network of 212,250 actors where a link between two actors means that they've acted together in at least one movie. From this database, we can see from the example that Tom Cruise co-star in three movies with Nicole Kidman. These three movies were Days of Thunder 1990, Far and Away in 1992, and Eyes Wide Shut 1999. The tail of the degree distribution of this network is convincingly a power-law with exponent 2.3. To explain why so many real-world complex networks have a scale-free degree distribution, Albert and Barabasi looked for mechanistic explanations. Drawing inspiration from the World Wide Web and the co starring network, Albert and Barabasi assumed that these scale-free networks did not come into existence as is, but had to grow from a small seed networks through the addition of new nodes. Barabasi assumed that when a new node is added to the growing network, m new links connect this new node to existing nodes. But where will these m new links connect? In the Erdos-Renyi model and the Watts-Strogatz model, new nodes connect to existing nodes randomly. But in the Albert Barabasi model, new nodes prefer to link to highly connected links. Albert and Barabasi called this mechanism preferential attachment, such that the probability of a new node connecting to an existing node is proportional to its degree. After growing the network by preferential attachment for a long time, the degree distribution obtained is a power-law with exponent 3. Using the simple preferential attachment mechanism that we've just described, the degree distribution will always be a power-law with exponent 3. To obtain other exponent's, other authors have devised modified preferential attachment schemes. In the following video, you'll hear Michael Leaves talk about power-law degree distribution in real-world networks before introducing the Barabasi Albert preferential attachment model.
