Package com.jgalgo.gen

Class BarabasiAlbertGraphGenerator<V,​E>

  • Type Parameters:
    V - the vertices type
    E - the edges type
    All Implemented Interfaces:
    GraphGenerator<V,​E>
    public class BarabasiAlbertGraphGenerator<V,​E>
extends Object
implements GraphGenerator<V,​E>
    Generates a Barabási–Albert graph.

    A Barabási–Albert graph is a random graph with a power law degree distribution, which is a good model for many real networks. The graph begins with an initial clique of size initCliqueSize, and then adds vertices one by one, each with k edges that are attached to existing vertices. The probability that a new vertex is connected to vertex \(v\) is proportional to the degree of \(v\) divided by the sum of degrees of all vertices in the graph.

    By default the initial clique size is \(20\) and the number of edges added each time step (denoted k) is \(10\). The generated graph(s) may be directed or undirected, and by default it is undirected. Self edges are never created.

    For deterministic behavior, set the seed of the generator using setSeed(long).

    Based on 'Emergence of scaling in random networks' by Albert-László Barabási and Réka Albert.

    Author:
    Barak Ugav

    • Method Detail

      • newInstance

        public static <V,​E> BarabasiAlbertGraphGenerator<V,​E> newInstance()
        Creates a new Barabási–Albert graph generator.
        Type Parameters:
        V - the vertices type
        E - the edges type
        Returns:
        a new Barabási–Albert graph generator

      • setVertices

        public void setVertices​(Collection<V> vertices)
        Set the vertices of the generated graph(s).

        If the generator is used to generate multiple graphs, the same vertices set is used for all of them.

        Parameters:
        vertices - the vertices set

      • setVertices

        public void setVertices​(int verticesNum,
                        Supplier<V> vertexSupplier)
        Set the vertices set of the generated graph(s) from a supplier.

        The supplier will be called exactly verticesNum times, and the same set of vertices created will be used for multiple graphs if GraphGenerator.generate() is called multiple times.

        Parameters:
        verticesNum - the number of vertices
        vertexSupplier - the supplier of vertices

      • setEdges

        public void setEdges​(Supplier<E> edgeSupplier)
        Set the edge supplier of the generated graph(s).

        The supplier will be called for any edge created, for any graph generated. This behavior is different from setVertices(int, Supplier), where the supplier is used to generate a set of vertices which is reused for any generated graph.

        Parameters:
        edgeSupplier - the edge supplier

      • setEdges

        public void setEdges​(BiFunction<V,​V,​E> edgeBuilder)
        Set the edge builder function of the generated graph(s).

        The function will be called for any edge created, for any graph generated. This behavior is different from setVertices(int, Supplier), where the supplier is used to generate a set of vertices which is reused for any generated graph.

        Parameters:
        edgeBuilder - the edge builder function

      • setInitialCliqueSize

        public void setInitialCliqueSize​(int initCliqueSize)
        Set the initial clique size of the generated graph(s).

        The initial clique is a complete graph of size initCliqueSize. After the initial clique is created, the generator adds vertices one by one, each with k edges that are attached to existing vertices. The probability that a new vertex is connected to vertex \(v\) is proportional to the degree of \(v\) divided by the sum of degrees of all vertices in the graph.

        By default, the initial clique size is \(20\). The initial clique size must not be greater than the number of vertices provided by setVertices(java.util.Collection<V>)

        Parameters:
        initCliqueSize - the initial clique size

      • setEdgesToAddPerStep

        public void setEdgesToAddPerStep​(int k)
        Set the number of edges added each time step (k) when generated graph(s).

        The initial clique is a complete graph of size setInitialCliqueSize(int). After the initial clique is created, the generator adds vertices one by one, each with k edges that are attached to existing vertices. The probability that a new vertex is connected to vertex \(v\) is proportional to the degree of \(v\) divided by the sum of degrees of all vertices in the graph.

        By default, the number of edges added per time step is \(10\). The number of edges per time step must not be greater than the initial clique size provided by setInitialCliqueSize(int).

        Parameters:
        k - the number of edges added to each vertex added to the graph after the initial clique

      • setDirected

        public void setDirected​(boolean directed)
        Determine if the generated graph(s) is directed or undirected.

        By default, the generated graph(s) is undirected.

        Parameters:
        directed - true if the generated graph(s) will be directed, false if undirected

      • setSeed

        public void setSeed​(long seed)
        Set the seed of the random number generator used to generate the graph(s).

        By default, a random seed is used. For deterministic behavior, set the seed of the generator.

        Parameters:
        seed - the seed of the random number generator

      • generateIntoBuilder

        public GraphBuilder<V,​E> generateIntoBuilder()
        Description copied from interface: GraphGenerator
        Generates a graph into a builder.

        This is the a more flexible way to generate a graph. The builder can be used to generate a mutable or immutable graph, or to add additional vertices or edges on top of the generated ones.

        Specified by:
        generateIntoBuilder in interface GraphGenerator<V,​E>
        Returns:
        a new graph builder populated by the generator with the generator parameters