CIShell Manual : Barabási-Albert Scale-Free
This page last changed on Jan 12, 2011 by dapolley.
DescriptionThe 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 Pros & ConsIt 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. ApplicationsIt 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 DetailsThe 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 HintsTo 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. AcknowledgementsThe 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. ReferencesBarabási, A.-L. & Albert, R. (1999). Emergence of scaling in random networks. Barabási, A.-L. & Albert, R. (2002). Statistical mechanics of complex networks. LinksSee Also |
![]() |
Document generated by Confluence on May 31, 2011 16:37 |