Boost Graph Library: Power Law Out Degree (PLOD) Generator

`plod_iterator`

    template<typename RandomGenerator, typename Graph>
    class plod_iterator
    {
    public:
      typedef std::input_iterator_tag iterator_category;
      typedef std::pair<vertices_size_type, vertices_size_type> value_type;
      typedef const value_type& reference;
      typedef const value_type* pointer;
      typedef void difference_type;

      plod_iterator();
      plod_iterator(RandomGenerator& gen, vertices_size_type n,
                    double alpha, double beta, bool allow_self_loops = false);
      // Iterator operations
      reference operator*() const;
      pointer operator->() const;
      plod_iterator& operator++();
      plod_iterator operator++(int);
      bool operator==(const plod_iterator& other) const;
      bool operator!=(const plod_iterator& other) const;
    };

This class template implements a generator for scale-free graphs using the Power Law Out Degree (PLOD) algorithm [63], suitable for initializing an `adjacency_list` or other graph structure with iterator-based initialization. A scale-free graph typically has a very skewed degree distribution, where few vertices have a very high degree and a large number of vertices have a very small degree. Many naturally evolving networks, such as the World Wide Web, are scale-free graphs, making these graphs a good model for certain networking problems.

The Power Law Out Degree (PLOD) algorithm generates a scale-free graph from three parameters, n, alpha, and beta, by allocating a certain number of degree "credits" to each vertex, drawn from a power-law distribution. It then creates edges between vertices, deducting a credit from each involved vertex (in the undirected case) or the source vertex (in the directed case). The number of credits assigned to a vertex is: beta*x-alpha, where x is a random value between 0 and n-1. The value of beta controls the y-intercept of the curve, so that increasing beta increases the average degree of vertices. The value of alpha controls how steeply the curve drops off, with larger values indicating a steeper curve. The web graph, for instance, has alpha ~ 2.72.

### Where Defined

`boost/graph/plod_generator.hpp`

### Constructors

    plod_iterator();

> Constructs a past-the-end iterator.

    plod_iterator(RandomGenerator& gen, vertices_size_type n,
                  double alpha, double beta, bool allow_self_loops = false);

> Constructs a PLOD generator iterator that creates a graph with `n` vertices. Probabilities are drawn from the random number generator `gen`. Self-loops are permitted only when `allow_self_loops` is `true`.

### Example

    #include <boost/graph/adjacency_list.hpp>
    #include <boost/graph/plod_generator.hpp>
    #include <boost/random/linear_congruential.hpp>

    typedef boost::adjacency_list<> Graph;
    typedef boost::plod_iterator<boost::minstd_rand, Graph> SFGen;

    int main()
    {
      boost::minstd_rand gen;
      // Create graph with 100 nodes
      Graph g(SFGen(gen, 100, 2.5, 1000), SFGen(), 100);
      return 0;
    }

Copyright © 2005 | Doug Gregor, Indiana University ( ) Andrew Lumsdaine, Indiana University ( )