Barabàsi-Albert preferential attachement graph generator
Scale-free graph generator using the preferential attachment rule as defined in the Barabási-Albert model.
This is a very simple graph generator that generates a graph using the preferential attachment rule defined in the Barabási-Albert model: nodes are generated one by one, and each time attached by one or more edges other nodes. The other nodes are chosen using a biased random selection giving more chance to a node if it has a high degree.
The more this generator is iterated, the more nodes are generated. It can
therefore generate graphs of any size. One node is generated at each call to
nextEvents(). At each node added at least one new edge is added. The number
of edges added at each step is given by the
by default the generator creates a number of edges per new node chosen randomly
between 1 and
getMaxLinksPerStep(). To have exactly this number of edges at
each new node, use
Above are four graphs generated using the Barabàsi-Albert model with four distinct values for the maximum number of links per step, one, two, three and six. Central nodes are highlighted (see the betweenness centrality algorithm).
For each new step, the algorithm act in O(n) with n the number of nodes if 1 max edge per new node is created, else the complexity is O(nm) if m max edge per new node is created.
Here is an example of use:
- Emergence of scaling in random networks,
- Albert-László Barabási & Réka Albert
- Science 286: 509–512.
- October 1999,