Albert Barabasi Topology of Evolving Networks: Local Events and Universality 2000
Contents
Citation
Albert R., Barabasi A. Topology of Evolving Networks: Local Events and Universality. Physical Review Letters. 2000.
Online version
Summary
This paper comes from the field of statistical physics and proposes a continuum model for the evolution of dynamic complex networks. The model is primarily based on the observation that the networks grow by 3 main local events such as (i) addition of new nodes, (ii) addition of new links and (iii) rewiring some of the existing links. The paper shows that depending on the frequency of these two processes (e.g. addition or rewiring) different networks can emerge with the connectivity distribution either following a power law or exponential kind of distribution.
In the second part of the paper, the proposed algorithm is extended to a continuum theory which predicts these two regimes (e.g. exponential and power law) as well as the scaling function and the exponents, in good agreement with numerical results.
Brief description of the method
The model the authors propose for generating networks have three probability parameters (p, q, and (1-p-q)) whose sum is equal to 1. As initial input, m0 isolated nodes are given. With probabilities p, q, and 1-p-q, the following events happen: (i) addition of m new nodes, (ii) rewiring of m existing links, and (iii) addition of a new node with m links to existing nodes in the network. When nodes create links to the new nodes, they follow preferential attachment giving a higher probability to the nodes that already have higher number of connections.
Since the number of links a node receives changes over time and since the choice of new or rewired links depends on the current number of links potential destination nodes have, the growth/evolution process for the networks is a continuous process; and the probability of a node to receive new links changes over time depending previous actions. Therefore, the authors model these preference parameters as continous processes and mathematically prove that the connectivity distribution, the main result provided by the continuum theory, has a generalized power-law form.
However, in the limit q -> 1 the growth of the network is suppressed. Because there are too many/too frequent rewirings on the network and the evolution/change in the network occurs with an almost constant number of nodes. This case corresponds to the exponential regime.
Datasets
To validate the accuracy of their model (i.e. to illustrate the predictive power of the obtained results about the real networks' topology), authors use collaboration graph among movie actors IMDB_dataset.
Results
In IMDB_dataset, the collaboration graph of movie actors is modelled. Since once two actors play in a movie, they remain as co-actors although they do not have any future collaboration (similar to co-authorship and citation networks), rewiring is not possible. Therefore, q=0 in this case. Since links are never eliminated, the network grows by addition/deletion of each nodes. Their results show that that 93.7% of new links connect existing nodes (actors), and only 6.3% of links come from newly added actors.
