Class KleinbergSmallWorldGenerator<V,​E>

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

    public class KleinbergSmallWorldGenerator<V,​E>
    extends Lattice2DGenerator<V,​E>
    Graph generator that produces a random graph with small world properties. The underlying model is an mxn (optionally toroidal) lattice. Each node u has four local connections, one to each of its neighbors, and in addition 1+ long range connections to some node v where v is chosen randomly according to probability proportional to d^-alpha where d is the lattice distance between u and v and alpha is the clustering exponent.
    See Also:
    "Navigation in a small world J. Kleinberg, Nature 406(2000), 845."
    • Constructor Summary

      Constructors 
      Constructor Description
      KleinbergSmallWorldGenerator​(com.google.common.base.Supplier<? extends Graph<V,​E>> graphFactory, com.google.common.base.Supplier<V> vertexFactory, com.google.common.base.Supplier<E> edgeFactory, int latticeSize, double clusteringExponent)
      Creates an instance with the specified parameters, whose underlying lattice is (a) of size latticeSize x latticeSize, and (b) toroidal.
      KleinbergSmallWorldGenerator​(com.google.common.base.Supplier<? extends Graph<V,​E>> graphFactory, com.google.common.base.Supplier<V> vertexFactory, com.google.common.base.Supplier<E> edgeFactory, int row_count, int col_count, double clusteringExponent)
      Creates an instance with the specified parameters, whose underlying lattice is toroidal.
      KleinbergSmallWorldGenerator​(com.google.common.base.Supplier<? extends Graph<V,​E>> graphFactory, com.google.common.base.Supplier<V> vertexFactory, com.google.common.base.Supplier<E> edgeFactory, int row_count, int col_count, double clusteringExponent, boolean isToroidal)
      Creates an instance with the specified parameters.
    • Field Detail

      • clustering_exponent

        private double clustering_exponent
      • random

        private java.util.Random random
      • num_connections

        private int num_connections
    • Constructor Detail

      • KleinbergSmallWorldGenerator

        public KleinbergSmallWorldGenerator​(com.google.common.base.Supplier<? extends Graph<V,​E>> graphFactory,
                                            com.google.common.base.Supplier<V> vertexFactory,
                                            com.google.common.base.Supplier<E> edgeFactory,
                                            int latticeSize,
                                            double clusteringExponent)
        Creates an instance with the specified parameters, whose underlying lattice is (a) of size latticeSize x latticeSize, and (b) toroidal.
        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
        latticeSize - the number of rows and columns of the underlying lattice
        clusteringExponent - the clustering exponent
      • KleinbergSmallWorldGenerator

        public KleinbergSmallWorldGenerator​(com.google.common.base.Supplier<? extends Graph<V,​E>> graphFactory,
                                            com.google.common.base.Supplier<V> vertexFactory,
                                            com.google.common.base.Supplier<E> edgeFactory,
                                            int row_count,
                                            int col_count,
                                            double clusteringExponent)
        Creates an instance with the specified parameters, whose underlying lattice is toroidal.
        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
        row_count - number of rows of the underlying lattice
        col_count - number of columns of the underlying lattice
        clusteringExponent - the clustering exponent
      • KleinbergSmallWorldGenerator

        public KleinbergSmallWorldGenerator​(com.google.common.base.Supplier<? extends Graph<V,​E>> graphFactory,
                                            com.google.common.base.Supplier<V> vertexFactory,
                                            com.google.common.base.Supplier<E> edgeFactory,
                                            int row_count,
                                            int col_count,
                                            double clusteringExponent,
                                            boolean isToroidal)
        Creates an instance with the specified parameters.
        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
        row_count - number of rows of the underlying lattice
        col_count - number of columns of the underlying lattice
        clusteringExponent - the clustering exponent
        isToroidal - whether the underlying lattice is toroidal
    • Method Detail

      • initialize

        private void initialize()
      • setRandom

        public void setRandom​(java.util.Random random)
        Sets the Random instance used by this instance. Useful for unit testing.
        Parameters:
        random - the Random instance for this class to use
      • setRandomSeed

        public void setRandomSeed​(long seed)
        Sets the seed of the internal random number generator. May be used to provide repeatable experiments.
        Parameters:
        seed - the random seed that this class's random number generator is to use
      • setConnectionCount

        public void setConnectionCount​(int num_connections)
        Sets the number of new 'small-world' connections (outgoing edges) to be added to each vertex.
        Parameters:
        num_connections - the number of outgoing small-world edges to add to each vertex
      • getConnectionCount

        public int getConnectionCount()
        Returns:
        the number of new 'small-world' connections that will originate at each vertex
      • get

        public Graph<V,​E> get()
        Generates a random small world network according to the parameters given
        Specified by:
        get in interface com.google.common.base.Supplier<V>
        Specified by:
        get in interface java.util.function.Supplier<V>
        Overrides:
        get in class Lattice2DGenerator<V,​E>
        Returns:
        a random small world graph