org.jgrapht.generate

Class BarabasiAlbertGraphGenerator<V,E>

java.lang.Object

org.jgrapht.generate.BarabasiAlbertGraphGenerator<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

GraphGenerator<V,E,V>

public class BarabasiAlbertGraphGenerator<V,E>
extends Object
implements GraphGenerator<V,E,V>

Barabási-Albert growth and preferential attachment graph generator.

The generator is described in the paper: A.-L. Barabási and R. Albert. Emergence of scaling in random networks. Science, 286:509-512, 1999.

The generator starts with a complete graph of $m_0$ nodes and grows the network by adding $n - m_0$ additional nodes. The additional nodes are added one by one and each of them is connected to $m$ previously added nodes, where the probability of connecting to a node is proportional to its degree.

Note that the Barabàsi-Albert model is designed for undirected networks. Nevertheless, this generator also works with directed networks where the probabilities are proportional to the sum of incoming and outgoing degrees. For a more general discussion see the paper: M. E. J. Newman. The Structure and Function of Complex Networks. SIAM Rev., 45(2):167--256, 2003.

For a version that generates trees/forests see BarabasiAlbertForestGenerator.

Author:

Dimitrios Michail

Constructor Summary

Constructors

Constructor and Description
BarabasiAlbertGraphGenerator(int m0, int m, int n) Constructor
BarabasiAlbertGraphGenerator(int m0, int m, int n, long seed) Constructor
BarabasiAlbertGraphGenerator(int m0, int m, int n, Random rng) Constructor

Method Summary

Modifier and Type	Method and Description
void	generateGraph(Graph<V,E> target, Map<String,V> resultMap) Generates an instance.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface org.jgrapht.generate.GraphGenerator

generateGraph

Constructor Detail

BarabasiAlbertGraphGenerator

public BarabasiAlbertGraphGenerator(int m0,
                                    int m,
                                    int n)

Constructor

Parameters:

m0 - number of initial nodes

m - number of edges of each new node added during the network growth

n - final number of nodes

Throws:

IllegalArgumentException - in case of invalid parameters

BarabasiAlbertGraphGenerator

public BarabasiAlbertGraphGenerator(int m0,
                                    int m,
                                    int n,
                                    long seed)

Constructor

Parameters:

m0 - number of initial nodes

m - number of edges of each new node added during the network growth

n - final number of nodes

seed - seed for the random number generator

Throws:

IllegalArgumentException - in case of invalid parameters

BarabasiAlbertGraphGenerator

public BarabasiAlbertGraphGenerator(int m0,
                                    int m,
                                    int n,
                                    Random rng)

Constructor

Parameters:

m0 - number of initial nodes

m - number of edges of each new node added during the network growth

n - final number of nodes

rng - the random number generator to use

Throws:

IllegalArgumentException - in case of invalid parameters

Method Detail

generateGraph

public void generateGraph(Graph<V,E> target,
                          Map<String,V> resultMap)

Generates an instance.

Specified by:

generateGraph in interface GraphGenerator<V,E,V>

Parameters:

target - the target graph

resultMap - not used by this generator, can be null