Description
The Barabási-Albert (BA) model is an algorithm which generates a scale-free network by incorporating growth and preferential attachment. Starting with an initial network of a few nodes, a new node is added at each time step. Older nodes with a higher degree have a higher probability of attracting edges from new nodes. The probability of attachment is given by
The initial number of nodes in the network must be greater than two and each of these nodes must have at least one connection. The final structure of the network does not depend on the initial number of nodes in the network. The degree distribution of the generated network is a power law with a scaling coefficient of -3. The figure on the left shows the network and the figure on the right gives the probability distribution on a log-log scale.
Pros & Cons
It is the simplest algorithm to generate a scale-free network. However, it is an undirected model and cannot be used to generate a directed network. Also, it should not be used to generate small networks as a larger number of time steps is required before the preferential attachment of new nodes to highly interconnected older nodes produces a scale-free structure.
Applications
It can be applied to generate any undirected network, such as the collaboration network among scientists, the movie actor network, and other social networks where the connections between the nodes are undirected.
Implementation Details
The inputs for the algorithm are the number of time steps, the number of initial nodes, and the number initial edges for a new node. The algorithm starts with the initial number of nodes that are fully connected. At each timestep, a new node is generated with the initial number of edges. The probability of attaching to an existing node is calculated by dividing the degree of an existing node by the total number of edges. If this probability is greater than zero and greater than the random number obtained from a random number generator then an edge is attached between the two nodes. This step is repeated in each time step.
Usage Hints
To obtain a proper scale-free network the number of time steps must be large, at least 1000. So using a timestep of around 1000, initial number of nodes 2 and number of edges 1 in the input a simple scale-free network can be obtained.
Acknowledgements
The JAVA version of the algorithm has been modeled by Shashikant Penumurthy of the IVC team and integrated by Vivek S. Thakres. The FORTRAN version has been implemented by Santo Fortunato and integrated by Santo Fortunato and Weixia (Bonnie) Huang. Documentation was compiled by Soma Sanyal.
References
Barabási, A.-L. & Albert, R. (1999). Emergence of scaling in random networks.
Science. 286:509-512.
Barabási, A.-L. & Albert, R. (2002). Statistical mechanics of complex networks.
Reviews of Modern Physics. 74:47-97.
