Class DirectedScaleFreeGraphGenerator<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    GraphGenerator<V,​E,​V>

    public class DirectedScaleFreeGraphGenerator<V,​E>
    extends java.lang.Object
    implements GraphGenerator<V,​E,​V>
    A generator for directed scale-free graphs.

    This generator creates a directed scale-free graph according to a power law, as described in Bollobás et al. The paper can be cited as Béla Bollobás, Christian Borgs, Jennifer Chayes, and Oliver Riordan. "Directed scale-free graphs." Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2003.

    In This generator, the graph continues to grow one edge per step, according to the probabilities alpha, beta, and gamma (which sum up to 1).

    • alpha is the probability that the new edge is from a new vertex v to an existing vertex w, where w is chosen according to d_in + delta_in.
    • beta is the probability that the new edge is from an existing vertex v to an existing vertex w, where v and w are chosen independently, v according to d_out + delta_out, and w according to d_in + delta_in.
    • gamma is the probability that the new edge is from an existing vertex v to a new vertex w, where v is chosen according to d_out + delta_out.

    In their original paper, the graph continues to grow according to a certain power law until a certain number of edges is reached irrespective to the number of nodes.
    However, because the target number of edges is not known beforehand, in this implementation, we added another feature that enables the user to grow the curve according to that power law until the target number of edges or target number of nodes is reached.

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      private static class  DirectedScaleFreeGraphGenerator.Direction
      An enum to indicate the vertex selection using its inDegree or outDegree
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private boolean allowingMultipleEdges
      Control whether the generated graph may contain loops.
      private boolean allowingSelfLoops
      Control whether the generated graph many contain multiple (parallel) edges between the same two vertices
      private float alpha
      probability that the new edge is from a new vertex v to an existing vertex w, where w is chosen according to d_in + delta_in criterion.
      private float alphaPlusBeta
      The probability that the new edge is (from a new vertex v to an existing vertex w) plus the probability that the new edge is (from an existing vertex v to an existing vertex w), where v and w are chosen independently, v according to d_out + delta_out, and w according to d_in + delta_in criteria.
      private float deltaIn
      In-degree bias used for Alpha and Beta
      private float deltaOut
      Out-degree bias used for Beta and Gamma
      private int maxFailures
      Maximum number of consecutive failed attempts to add an edge.
      private java.util.Random rng  
      private int targetEdges
      Target total number of edges to reach.
      private int targetNodes
      Target total number of targetNodes to reach.
      This has lower priority than targetEdges.
    • Constructor Summary

      Constructors 
      Constructor Description
      DirectedScaleFreeGraphGenerator​(float alpha, float gamma, float deltaIn, float deltaOut, int targetEdges, int targetNodes)
      Constructs a Generator.
      DirectedScaleFreeGraphGenerator​(float alpha, float gamma, float deltaIn, float deltaOut, int targetEdges, int targetNodes, long seed)
      Constructs a Generator using a seed for the random number generator.
      DirectedScaleFreeGraphGenerator​(float alpha, float gamma, float deltaIn, float deltaOut, int targetEdges, int targetNodes, long seed, boolean allowingMultipleEdges, boolean allowingSelfLoops)
      Constructs a Generator using a seed for the random number generator and sets the two relaxation options allowingMultipleEdges and allowingSelfLoops.
      DirectedScaleFreeGraphGenerator​(float alpha, float gamma, float deltaIn, float deltaOut, int targetEdges, int targetNodes, java.util.Random rng)
      Construct a new generator using the provided random number generator.
      DirectedScaleFreeGraphGenerator​(float alpha, float gamma, float deltaIn, float deltaOut, int targetEdges, int targetNodes, java.util.Random rng, boolean allowingMultipleEdges, boolean allowingSelfLoops)
      Construct a new generator using the provided random number generator and sets the two relaxation options allowingMultipleEdges and allowingSelfLoops.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void generateGraph​(Graph<V,​E> target, java.util.Map<java.lang.String,​V> resultMap)
      Generates an instance of the Graph.
      int getMaxFailures()
      Returns the maximum allowed number of consecutive failed attempts to add an edge.
      boolean isAllowingMultipleEdges()
      Returns whether the generated graph may contain multiple (parallel) edges between the same two vertices.
      boolean isAllowingSelfLoops()
      Returns whether the generated graph may contain multiple (parallel) edges between the same two vertices
      private V pickAVertex​(Graph<V,​E> target, java.util.Set<V> allNewNodes, java.util.Set<E> allNewEdgesSet, DirectedScaleFreeGraphGenerator.Direction direction, float bias)
      Select a vertex from the currently available vertices, using the passed bias.
      void setAllowingMultipleEdges​(boolean allowingMultipleEdges)
      Sets whether the generated graph may contain multiple (parallel) edges between the same two vertices
      void setAllowingSelfLoops​(boolean allowingSelfLoops)
      Sets whether the generated graph may contain multiple (parallel) edges between the same two vertices
      void setMaxFailures​(int maxFailures)
      Sets the maximum allowed number of consecutive failed attempts to add an edge (must be non negative).
      • Methods inherited from class java.lang.Object

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

      • rng

        private final java.util.Random rng
      • alpha

        private final float alpha
        probability that the new edge is from a new vertex v to an existing vertex w, where w is chosen according to d_in + delta_in criterion.
      • alphaPlusBeta

        private final float alphaPlusBeta
        The probability that the new edge is (from a new vertex v to an existing vertex w) plus the probability that the new edge is (from an existing vertex v to an existing vertex w), where v and w are chosen independently, v according to d_out + delta_out, and w according to d_in + delta_in criteria. This equals 1 - gamma. Gamma refers to the probability that the new edge is from an existing vertex v to a new vertex w.
      • deltaIn

        private final float deltaIn
        In-degree bias used for Alpha and Beta
      • deltaOut

        private final float deltaOut
        Out-degree bias used for Beta and Gamma
      • targetEdges

        private final int targetEdges
        Target total number of edges to reach. It has a higher priority than targetNodes. Zero is a valid value.
        If negative number, the user does not care about the total number of edges and is interested only in the number of nodes, therefore, targetNodes will be considered instead. Otherwise, targetEdges will be considered and targetEdges will be ignored.
      • targetNodes

        private final int targetNodes
        Target total number of targetNodes to reach.
        This has lower priority than targetEdges. It will not be used unless targetEdges given is a negative number.
      • maxFailures

        private int maxFailures
        Maximum number of consecutive failed attempts to add an edge.
      • allowingMultipleEdges

        private boolean allowingMultipleEdges
        Control whether the generated graph may contain loops.
      • allowingSelfLoops

        private boolean allowingSelfLoops
        Control whether the generated graph many contain multiple (parallel) edges between the same two vertices
    • Constructor Detail

      • DirectedScaleFreeGraphGenerator

        public DirectedScaleFreeGraphGenerator​(float alpha,
                                               float gamma,
                                               float deltaIn,
                                               float deltaOut,
                                               int targetEdges,
                                               int targetNodes)
        Constructs a Generator.
        Parameters:
        alpha - The probability that the new edge is from a new vertex v to an existing vertex w, where w is chosen according to d_in + delta_in.
        gamma - The probability that the new edge is from an existing vertex v to a new vertex w, where v is chosen according to d_out + delta_out.
        deltaIn - The in-degree bias used for Alpha and Beta.
        deltaOut - The out-degree bias used for Beta and Gamma.
        targetEdges - Target total number of edges to reach. It has a higher priority than targetNodes. Zero is a valid value.
        If negative number, the user does not care about the total number of edges and is interested only in the number of nodes, therefore, targetNodes will be considered instead. Otherwise, targetEdges will be considered and targetEdges will be ignored.
        targetNodes - Target number of nodes to reach. Zero is a valid value.
        This parameter has lower priority than targetEdges and will be used only if targetEdges given is a negative number.
      • DirectedScaleFreeGraphGenerator

        public DirectedScaleFreeGraphGenerator​(float alpha,
                                               float gamma,
                                               float deltaIn,
                                               float deltaOut,
                                               int targetEdges,
                                               int targetNodes,
                                               long seed)
        Constructs a Generator using a seed for the random number generator.
        Parameters:
        alpha - The probability that the new edge is from a new vertex v to an existing vertex w, where w is chosen according to d_in + delta_in.
        gamma - The probability that the new edge is from an existing vertex v to a new vertex w, where v is chosen according to d_out + delta_out.
        deltaIn - The in-degree bias used for Alpha and Beta.
        deltaOut - The out-degree bias used for Beta and Gamma.
        targetEdges - Target total number of edges to reach. It has a higher priority than targetNodes. Zero is a valid value.
        If negative number, the user does not care about the total number of edges and is interested only in the number of nodes, therefore, targetNodes will be considered instead. Otherwise, targetEdges will be considered and targetEdges will be ignored.
        targetNodes - Target number of nodes to reach. Zero is a valid value.
        This parameter has lower priority than targetEdges and will be used only if targetEdges given is a negative number.
        seed - The seed to feed to the random number generator.
      • DirectedScaleFreeGraphGenerator

        public DirectedScaleFreeGraphGenerator​(float alpha,
                                               float gamma,
                                               float deltaIn,
                                               float deltaOut,
                                               int targetEdges,
                                               int targetNodes,
                                               long seed,
                                               boolean allowingMultipleEdges,
                                               boolean allowingSelfLoops)
        Constructs a Generator using a seed for the random number generator and sets the two relaxation options allowingMultipleEdges and allowingSelfLoops.
        Parameters:
        alpha - The probability that the new edge is from a new vertex v to an existing vertex w, where w is chosen according to d_in + delta_in.
        gamma - The probability that the new edge is from an existing vertex v to a new vertex w, where v is chosen according to d_out + delta_out.
        deltaIn - The in-degree bias used for Alpha and Beta.
        deltaOut - The out-degree bias used for Beta and Gamma.
        targetEdges - Target total number of edges to reach. It has a higher priority than targetNodes. Zero is a valid value.
        If negative number, the user does not care about the total number of edges and is interested only in the number of nodes, therefore, targetNodes will be considered instead. Otherwise, targetEdges will be considered and targetEdges will be ignored.
        targetNodes - Target number of nodes to reach. Zero is a valid value.
        This parameter has lower priority than targetEdges and will be used only if targetEdges given is a negative number.
        seed - The seed to feed to the random number generator.
        allowingMultipleEdges - whether the generator allows multiple parallel edges between the same two vertices (v, w).
        allowingSelfLoops - whether the generator allows self loops from the a vertex to itself.
      • DirectedScaleFreeGraphGenerator

        public DirectedScaleFreeGraphGenerator​(float alpha,
                                               float gamma,
                                               float deltaIn,
                                               float deltaOut,
                                               int targetEdges,
                                               int targetNodes,
                                               java.util.Random rng)
        Construct a new generator using the provided random number generator.
        Parameters:
        alpha - The probability that the new edge is from a new vertex v to an existing vertex w, where w is chosen according to d_in + delta_in.
        gamma - The probability that the new edge is from an existing vertex v to a new vertex w, where v is chosen according to d_out + delta_out.
        deltaIn - The in-degree bias used for Alpha and Beta.
        deltaOut - The out-degree bias used for Beta and Gamma.
        targetEdges - Target total number of edges to reach. It has a higher priority than targetNodes. Zero is a valid value.
        If negative number, the user does not care about the total number of edges and is interested only in the number of nodes, therefore, targetNodes will be considered instead. Otherwise, targetEdges will be considered and targetEdges will be ignored.
        targetNodes - Target number of nodes to reach. Zero is a valid value.
        This parameter has lower priority than targetEdges and will be used only if targetEdges given is a negative number.
        rng - The Random object to use.
      • DirectedScaleFreeGraphGenerator

        public DirectedScaleFreeGraphGenerator​(float alpha,
                                               float gamma,
                                               float deltaIn,
                                               float deltaOut,
                                               int targetEdges,
                                               int targetNodes,
                                               java.util.Random rng,
                                               boolean allowingMultipleEdges,
                                               boolean allowingSelfLoops)
        Construct a new generator using the provided random number generator and sets the two relaxation options allowingMultipleEdges and allowingSelfLoops.
        Parameters:
        alpha - The probability that the new edge is from a new vertex v to an existing vertex w, where w is chosen according to d_in + delta_in.
        gamma - The probability that the new edge is from an existing vertex v to a new vertex w, where v is chosen according to d_out + delta_out.
        deltaIn - The in-degree bias used for Alpha and Beta.
        deltaOut - The out-degree bias used for Beta and Gamma.
        targetEdges - Target total number of edges to reach. It has a higher priority than targetNodes. Zero is a valid value.
        If negative number, the user does not care about the total number of edges and is interested only in the number of nodes, therefore, targetNodes will be considered instead. Otherwise, targetEdges will be considered and targetEdges will be ignored.
        targetNodes - Target number of nodes to reach. Zero is a valid value.
        This parameter has lower priority than targetEdges and will be used only if targetEdges given is a negative number.
        rng - The Random object to use.
        allowingMultipleEdges - whether the generator allows multiple parallel edges between the same two vertices (v, w).
        allowingSelfLoops - whether the generator allows self loops from the a vertex to itself.
    • Method Detail

      • generateGraph

        public void generateGraph​(Graph<V,​E> target,
                                  java.util.Map<java.lang.String,​V> resultMap)
        Generates an instance of the Graph.
        Specified by:
        generateGraph in interface GraphGenerator<V,​E,​V>
        Parameters:
        target - the target graph
        resultMap - not used by this generator, can be null
        Throws:
        TooManyFailuresException - When the method fails maxFailures times to add a new edge to the growing graph.
        java.lang.IllegalArgumentException - When the graph does not support Multiple edges or self loop while the generator does.
      • getMaxFailures

        public int getMaxFailures()
        Returns the maximum allowed number of consecutive failed attempts to add an edge.
        Returns:
        maxFailure field.
      • setMaxFailures

        public void setMaxFailures​(int maxFailures)
        Sets the maximum allowed number of consecutive failed attempts to add an edge (must be non negative).
        Parameters:
        maxFailures - Maximum allowed (non negative) number of consecutive failed attempts to add an edge.
      • isAllowingMultipleEdges

        public boolean isAllowingMultipleEdges()
        Returns whether the generated graph may contain multiple (parallel) edges between the same two vertices.
        Returns:
        whether the generated graph may contain multiple (parallel) edges between the same two vertices
      • setAllowingMultipleEdges

        public void setAllowingMultipleEdges​(boolean allowingMultipleEdges)
        Sets whether the generated graph may contain multiple (parallel) edges between the same two vertices
        Parameters:
        allowingMultipleEdges - whether the generated graph may contain multiple (parallel) edges between the same two vertices
      • isAllowingSelfLoops

        public boolean isAllowingSelfLoops()
        Returns whether the generated graph may contain multiple (parallel) edges between the same two vertices
        Returns:
        whether the generated graph many contain multiple (parallel) edges between the same two vertices
      • setAllowingSelfLoops

        public void setAllowingSelfLoops​(boolean allowingSelfLoops)
        Sets whether the generated graph may contain multiple (parallel) edges between the same two vertices
        Parameters:
        allowingSelfLoops - whether the generated graph many contain multiple (parallel) edges between the same two vertices