Small World Generator (Watts-Strogatz)

Generates small-world graphs using the Watts-Strogatz model.

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

Synopsis

template <typename RandomGenerator, typename Graph>
class small_world_iterator;

small_world_iterator();
small_world_iterator(RandomGenerator& gen, vertices_size_type n, vertices_size_type k, double prob = 0.0, bool allow_self_loops = false);

A small-world graph starts as a ring lattice where each vertex is connected to its k nearest neighbors. Each edge is then randomly rewired to a different vertex with probability prob. The resulting graphs exhibit high clustering (vertices stay connected to nearby neighbors) combined with short average path lengths (from the rewired long-range edges).

The Watts-Strogatz model is inherently undirected. This iterator must be used with an undirected graph (e.g., adjacency_list<vecS, vecS, undirectedS>). Using it with a directed graph compiles silently but produces a broken graph where edges exist in only one direction, violating the degree guarantee of the model.

Parameters

Direction Parameter Description

Direction	Parameter	Description
IN	`RandomGenerator& gen`	A random number generator.
IN	`vertices_size_type n`	Number of vertices in the ring lattice.
IN	`vertices_size_type k`	Each vertex is connected to its `k` nearest neighbors (must be even).
IN	`double prob`	Probability that each edge is rewired. Default: `0.0`.
IN	`bool allow_self_loops`	When `true`, self-loops are permitted. Default: `false`.

RandomGenerator& gen

A random number generator.

vertices_size_type n

Number of vertices in the ring lattice.

vertices_size_type k

Each vertex is connected to its k nearest neighbors (must be even).

double prob

Probability that each edge is rewired. Default: 0.0.

bool allow_self_loops

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

Example

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/small_world_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<vecS, vecS, undirectedS>;
    using SWGen = small_world_iterator<minstd_rand, Graph>;

    minstd_rand gen(42);

    int k = 2;
    double rewire_prob = 0.1;
    Graph g(SWGen(gen, 6, k, rewire_prob), SWGen(), 6);

    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";
    }
}

6 vertices, 6 edges
  0 -- 1
  1 -- 3
  2 -- 3
  3 -- 4
  4 -- 5
  5 -- 0

Edit this Page