Emergence of Scaling in Random Networks
The research paper "Emergence of Scaling in Random Networks", led by researchers Albert-Laszlo Barabasi and Reka Albert of the University of Notre-Dame's Physics Department, focused on finding a suitable and accurate model for random networks, including the internet and social networks. In doing so, they challenged existing models by incorporating two new facets, previously ignored in network models using complex topology, namely exponential growth and preferential attachment. These were believed to be necessary for the emergence of scale-free random networks, a proposition that was later mathematically proven by the researchers. Furthermore, this research also discovered that the growth and preferential attachment in these models of random networks is independent of time, implying networks are characterized as Self-organizing.
The primary goal of the study was to answer the question of how to model random networks and to identify the key characteristics thereof. Modeling random networks is essential for better understanding the large systems around us, including biological, economic, and social systems, as well as the World Wide Web itself. In order to implement a better model, the researchers considered previously taken approaches to analyze their shortcomings. Pairing this newfound knowledge of gaps and holes with more accessible data, they were able to identify two new governing rules — the growth of networks over time and preferential treatment in edge selections between vertices (similar to the widely observed "rich get richer" phenomenon). In the end, the research found that common among the various systems observed were scale-free distributions and power-law-obeying patterns (where P(k) ~ k and P(k) is the −γ, γ ∈ [2.1, 4] probability of a vertex having k edges).
The paper showed that random networks organize themselves through growth and preferential attachment, thereby forming scale-free power-law distributions. Barabasi and Albert demonstrated that using the popular Erdos and Renyi theory is neither applicable nor accurate, as it neglects two key characteristics of real random networks (the aforementioned preferential attachment and expansion). However, there may be an even better representation of these complex, random networks, employing characteristics the authors themselves did not include, meaning this is not a definitive solution. Though this paper isn't conclusive, it has helped foster a greater understanding of models and their workings. Additionally, the paper assumed linear preferential attachment. At the same time, other cases are explained away as not leading to scaling; there is more work that can be done to address these cases. Suppose preferential attachment (PA) is modeled by Π(k); then, linear PA is modeled by Π(k) ~ k, while nonlinear, exponential PA is modeled by Π(k) ~ k , and more generic α, α ≠ 1 forms of PA are given by Π(k) ~ m(k), where m may follow a damped oscillation pattern, for instance.
Furthermore, the authors believe these findings may be applied to an even more vast array of networks, including those for which there is still very little data available. The broad applicability is another important consideration; these models can be used to enhance humanity's understanding of genetic, biological, socioeconomic, and a host of other types of networks. In summary, random networks like the World Wide Web are self-organizing and follow scale-free power-law distributions subject to constraints of growth and PA. These are widely applicable to a variety of models, ranging from genetics and heredity to airports and connections therein.