PLOD Generator (Scale-Free Graph)

Generates scale-free graphs using the Power Law Out Degree (PLOD) algorithm.

Defined in: <boost/graph/plod_generator.hpp>

Synopsis

template <typename RandomGenerator, typename Graph>
class plod_iterator;

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

The PLOD algorithm [57] generates a scale-free graph from three parameters, n, alpha, and beta, by allocating degree "credits" to each vertex drawn from a power-law distribution. It then creates edges between vertices, deducting a credit from each involved vertex (undirected case) or the source vertex (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. Increasing beta increases the average degree. Increasing alpha steepens the drop-off (the web graph has alpha ~ 2.72).

plod_iterator selects between out_directed_plod_iterator and undirected_plod_iterator at compile time based on the directed_category of Graph.

Parameters

Direction Parameter Description

Direction	Parameter	Description
IN	`RandomGenerator& gen`	A random number generator.
IN	`std::size_t n`	Number of vertices in the generated graph.
IN	`double alpha`	Power-law exponent controlling the steepness of the degree distribution.
IN	`double beta`	Scaling factor controlling the y-intercept (average degree).
IN	`bool allow_self_loops`	When `true`, self-loops are permitted. Default: `false`.

RandomGenerator& gen

A random number generator.

std::size_t n

Number of vertices in the generated graph.

double alpha

Power-law exponent controlling the steepness of the degree distribution.

double beta

Scaling factor controlling the y-intercept (average degree).

bool allow_self_loops

When true, self-loops are permitted. Default: false.

Example

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

int main() {
    using namespace boost;
    using Graph = adjacency_list<>;
    using PLODGen = plod_iterator<minstd_rand, Graph>;

    minstd_rand gen(42);

    double alpha = 2.5;
    double beta = 10;
    Graph g(PLODGen(gen, 8, alpha, beta), PLODGen(), 8);

    std::cout << num_vertices(g) << " vertices, " << num_edges(g) << " edges\n";
    for (auto e : make_iterator_range(edges(g))) {
        std::cout << "  " << source(e, g) << " -> " << target(e, g) << "\n";
    }
}

8 vertices, 2 edges
  0 -> 0
  2 -> 3

Variants

The header provides two underlying iterator classes that plod_iterator dispatches to at compile time.

`out_directed_plod_iterator`

template <typename RandomGenerator>
class out_directed_plod_iterator;

out_directed_plod_iterator();
out_directed_plod_iterator(RandomGenerator& gen, std::size_t n, double alpha, double beta, bool allow_self_loops);

Generates only out-edges for directed graphs. The allow_self_loops parameter has no default value in this variant.

`undirected_plod_iterator`

template <typename RandomGenerator>
class undirected_plod_iterator;

undirected_plod_iterator();
undirected_plod_iterator(RandomGenerator& gen, std::size_t n, double alpha, double beta, bool allow_self_loops = false);

Generates undirected edges by pairing vertices with remaining degree credits. Each edge consumes one credit from both endpoints. Vertices with zero credits are assigned a minimum degree of 1; vertices with degree greater than or equal to n are capped at n - 1.

Edit this Page