Class BarabasiAlbertGenerator<V,​E>

  • All Implemented Interfaces:
    com.google.common.base.Supplier<Graph<V,​E>>, EvolvingGraphGenerator<V,​E>, GraphGenerator<V,​E>, java.util.function.Supplier<Graph<V,​E>>

    public class BarabasiAlbertGenerator<V,​E>
    extends java.lang.Object
    implements EvolvingGraphGenerator<V,​E>

    Simple evolving scale-free random graph generator. At each time step, a new vertex is created and is connected to existing vertices according to the principle of "preferential attachment", whereby vertices with higher degree have a higher probability of being selected for attachment.

    At a given timestep, the probability p of creating an edge between an existing vertex v and the newly added vertex is

     p = (degree(v) + 1) / (|E| + |V|);
     

    where |E| and |V| are, respectively, the number of edges and vertices currently in the network (counting neither the new vertex nor the other edges that are being attached to it).

    Note that the formula specified in the original paper (cited below) was

     p = degree(v) / |E|
     

    However, this would have meant that the probability of attachment for any existing isolated vertex would be 0. This version uses Lagrangian smoothing to give each existing vertex a positive attachment probability.

    The graph created may be either directed or undirected (controlled by a constructor parameter); the default is undirected. If the graph is specified to be directed, then the edges added will be directed from the newly added vertex u to the existing vertex v, with probability proportional to the indegree of v (number of edges directed towards v). If the graph is specified to be undirected, then the (undirected) edges added will connect u to v, with probability proportional to the degree of v.

    The parallel constructor parameter specifies whether parallel edges may be created.

    See Also:
    "A.-L. Barabasi and R. Albert, Emergence of scaling in random networks, Science 286, 1999."
    • Constructor Summary

      Constructors 
      Constructor Description
      BarabasiAlbertGenerator​(com.google.common.base.Supplier<Graph<V,​E>> graphFactory, com.google.common.base.Supplier<V> vertexFactory, com.google.common.base.Supplier<E> edgeFactory, int init_vertices, int numEdgesToAttach, int seed, java.util.Set<V> seedVertices)
      Constructs a new instance of the generator.
      BarabasiAlbertGenerator​(com.google.common.base.Supplier<Graph<V,​E>> graphFactory, com.google.common.base.Supplier<V> vertexFactory, com.google.common.base.Supplier<E> edgeFactory, int init_vertices, int numEdgesToAttach, java.util.Set<V> seedVertices)
      Constructs a new instance of the generator, whose output will be an undirected graph, and which will use the current time as a seed for the random number generation.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private void createRandomEdge​(java.util.Collection<V> preexistingNodes, V newVertex, java.util.Set<Pair<V>> added_pairs, WeightedChoice<V> weightedProbabilities)  
      private java.util.Set<Pair<V>> createRandomEdges​(java.util.Collection<V> preexistingNodes, V newVertex, int numEdges)  
      private void evolveGraph()  
      void evolveGraph​(int numTimeSteps)
      Instructs the algorithm to evolve the graph N steps.
      Graph<V,​E> get()  
      private void initialize​(java.util.Set<V> seedVertices)  
      int numIterations()
      Retrieves the total number of steps elapsed.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • mGraph

        private Graph<V,​E> mGraph
      • mNumEdgesToAttachPerStep

        private int mNumEdgesToAttachPerStep
      • mElapsedTimeSteps

        private int mElapsedTimeSteps
      • mRandom

        private java.util.Random mRandom
      • vertex_index

        protected java.util.List<V> vertex_index
      • init_vertices

        protected int init_vertices
      • index_vertex

        protected java.util.Map<V,​java.lang.Integer> index_vertex
      • graphFactory

        protected com.google.common.base.Supplier<Graph<V,​E>> graphFactory
      • vertexFactory

        protected com.google.common.base.Supplier<V> vertexFactory
      • edgeFactory

        protected com.google.common.base.Supplier<E> edgeFactory
    • Constructor Detail

      • BarabasiAlbertGenerator

        public BarabasiAlbertGenerator​(com.google.common.base.Supplier<Graph<V,​E>> graphFactory,
                                       com.google.common.base.Supplier<V> vertexFactory,
                                       com.google.common.base.Supplier<E> edgeFactory,
                                       int init_vertices,
                                       int numEdgesToAttach,
                                       int seed,
                                       java.util.Set<V> seedVertices)
        Constructs a new instance of the generator.
        Parameters:
        graphFactory - factory for graphs of the appropriate type
        vertexFactory - factory for vertices of the appropriate type
        edgeFactory - factory for edges of the appropriate type
        init_vertices - number of unconnected 'seed' vertices that the graph should start with
        numEdgesToAttach - the number of edges that should be attached from the new vertex to pre-existing vertices at each time step
        seed - random number seed
        seedVertices - storage for the seed vertices that this graph creates
      • BarabasiAlbertGenerator

        public BarabasiAlbertGenerator​(com.google.common.base.Supplier<Graph<V,​E>> graphFactory,
                                       com.google.common.base.Supplier<V> vertexFactory,
                                       com.google.common.base.Supplier<E> edgeFactory,
                                       int init_vertices,
                                       int numEdgesToAttach,
                                       java.util.Set<V> seedVertices)
        Constructs a new instance of the generator, whose output will be an undirected graph, and which will use the current time as a seed for the random number generation.
        Parameters:
        graphFactory - factory for graphs of the appropriate type
        vertexFactory - factory for vertices of the appropriate type
        edgeFactory - factory for edges of the appropriate type
        init_vertices - number of vertices that the graph should start with
        numEdgesToAttach - the number of edges that should be attached from the new vertex to pre-existing vertices at each time step
        seedVertices - storage for the seed vertices that this graph creates
    • Method Detail

      • initialize

        private void initialize​(java.util.Set<V> seedVertices)
      • evolveGraph

        public void evolveGraph​(int numTimeSteps)
        Description copied from interface: EvolvingGraphGenerator
        Instructs the algorithm to evolve the graph N steps.
        Specified by:
        evolveGraph in interface EvolvingGraphGenerator<V,​E>
        Parameters:
        numTimeSteps - number of steps to iterate from the current state
      • evolveGraph

        private void evolveGraph()
      • createRandomEdges

        private java.util.Set<Pair<V>> createRandomEdges​(java.util.Collection<V> preexistingNodes,
                                                         V newVertex,
                                                         int numEdges)
      • createRandomEdge

        private void createRandomEdge​(java.util.Collection<V> preexistingNodes,
                                      V newVertex,
                                      java.util.Set<Pair<V>> added_pairs,
                                      WeightedChoice<V> weightedProbabilities)
      • get

        public Graph<V,​E> get()
        Specified by:
        get in interface com.google.common.base.Supplier<V>
        Specified by:
        get in interface java.util.function.Supplier<V>