Class 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 java.lang.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 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:
        java.lang.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:
        java.lang.IllegalArgumentException - in case of invalid parameters
      • BarabasiAlbertGraphGenerator

        public BarabasiAlbertGraphGenerator​(int m0,
                                            int m,
                                            int n,
                                            java.util.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:
        java.lang.IllegalArgumentException - in case of invalid parameters
    • Method Detail

      • generateGraph

        public void generateGraph​(Graph<V,​E> target,
                                  java.util.Map<java.lang.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