Watts-Strogatz network model. More...

#include <watts_strogatz.h>

Inheritance diagram for pagmo::topology::watts_strogatz:

Public Member Functions
	watts_strogatz (int=10, const double &=0.05, int=0)
	Constructor from K, beta and size. More...

base_ptr	clone () const
	Clone method. More...

std::string	get_name () const
	Get name of the topology. More...

Public Member Functions inherited from pagmo::topology::base
	base ()
	Default constructor. More...

	base (const base &)
	Copy constructor. More...

base &	operator= (const base &)
	Assignment operator. More...

virtual	~base ()
	Trivial destructor. More...

vertices_size_type	get_number_of_vertices () const
	Get number of vertices. More...

edges_size_type	get_number_of_edges () const
	Get number of edges. More...

void	push_back ()
	Push back vertex. More...

double	get_average_shortest_path_length () const
	Calculate average path length. More...

double	get_clustering_coefficient () const
	Calculate clustering coefficient.

std::vector< double >	get_degree_distribution () const
	Constructs the Degree Distribution.

bool	are_adjacent (const vertices_size_type &, const vertices_size_type &) const
	Return true if two vertices are adjacent. More...

bool	are_inv_adjacent (const vertices_size_type &, const vertices_size_type &) const
	Return true if two vertices are inversely adjacent. More...

std::vector< vertices_size_type >	get_v_adjacent_vertices (const vertices_size_type &) const
	Return vector of adjacent vertices. More...

std::vector< vertices_size_type >	get_v_inv_adjacent_vertices (const vertices_size_type &) const
	Return vector of inversely adjacent vertices. More...

edges_size_type	get_num_adjacent_vertices (const vertices_size_type &) const
	Return the number of adjacent vertices. More...

edges_size_type	get_num_inv_adjacent_vertices (const vertices_size_type &) const
	Return the number of inversely adjacent vertices. More...

void	set_weight (double)
	Sets the migration probability. More...

void	set_weight (const vertices_size_type &, double)
	Sets the migration probability. More...

void	set_weight (const vertices_size_type &, const vertices_size_type &, double)
	Sets the migration probability. More...

double	get_weight (const vertices_size_type &, const vertices_size_type &) const
	Get the migration probability. More...

std::string	human_readable_terse () const
	Return terse human readable representation. More...

std::string	human_readable () const
	Return complete human readable representation. More...

Protected Member Functions
void	connect (const vertices_size_type &)
	Establish connections between islands during a push_back() operation. More...

Protected Member Functions inherited from pagmo::topology::base
void	add_vertex ()
	Add a vertex. More...

std::pair< a_iterator, a_iterator >	get_adjacent_vertices (const vertices_size_type &) const
	Return iterator range to adjacent vertices. More...

std::pair< ia_iterator, ia_iterator >	get_inv_adjacent_vertices (const vertices_size_type &) const
	Return iterator range to inversely adjacent vertices. More...

void	add_edge (const vertices_size_type &, const vertices_size_type &)
	Add an edge. More...

void	remove_edge (const vertices_size_type &, const vertices_size_type &)
	Remove an edge. More...

void	remove_all_edges ()
	Remove all edges. More...

std::pair< v_iterator, v_iterator >	get_vertices () const
	Return iterator range to vertices. More...

virtual std::string	human_readable_extra () const
	Return extra information for human readable representation. More...

Friends
class	boost::serialization::access

Additional Inherited Members
Public Types inherited from pagmo::topology::base
typedef graph_type::vertices_size_type	vertices_size_type
	Vertices size type.

typedef graph_type::edges_size_type	edges_size_type
	Edges size type.

Protected Types inherited from pagmo::topology::base
typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::bidirectionalS, boost::no_property, edge_properties, boost::no_property, boost::listS >	graph_type

typedef boost::graph_traits< graph_type >::vertex_iterator	v_iterator
	Iterator over the vertices.

typedef boost::graph_traits< graph_type >::edge_iterator	e_iterator
	Iterator over the edges.

typedef boost::graph_traits< graph_type >::adjacency_iterator	a_iterator
	Iterator over adjacent vertices.

typedef graph_type::inv_adjacency_iterator	ia_iterator
	Iterator over inversely adjacent vertices.

typedef boost::graph_traits< graph_type >::vertex_descriptor	v_descriptor
	Vertex descriptor.

typedef boost::graph_traits< graph_type >::edge_descriptor	e_descriptor
	Edge descriptor.

Detailed Description

Watts-Strogatz network model.

Example of Watts-Strogatz model with N = 20, K = 4 and beta = 0.1.

The Watts-Strogatz model is a ring lattice network in which forward edges are rewired with random probability. Such a network has small-world properties, including short average path lengths and high clustering.

In this implementation the graph grows dynamically by rewiring all the connections each time an island is added. Note that up to the the first K + 1 insertions, the topology will be fully connected. Afterwards, the topology will be a proper Watts-Strogatz model.

Since the addition of a single element to the topology implies the rewiring of the whole topology, for archipelago objects of large size it is advisable to build the topology outside the archipelago specifying the number of islands it will contain, and use archipelago::set_topology() to apply it to an existing (and possibly unconnected) archipelago.

See also: http://en.wikipedia.org/wiki/Watts_and_Strogatz_model

Author: Francesco Biscani (blues.nosp@m.carn.nosp@m.i@gma.nosp@m.il.c.nosp@m.om)

Definition at line 57 of file watts_strogatz.h.

Constructor & Destructor Documentation

pagmo::topology::watts_strogatz::watts_strogatz	(	int	k = `10`,
		const double &	beta = `0.05`,
		int	n = `0`
	)

Constructor from K, beta and size.

Build a Watts-Strogatz network model with K = k, rewiring probability beta and size n. Will fail if k is less than 2 or odd or if the beta parameter is outside the [0,1] range.

Parameters

[in]	k	K parameter of the model.
[in]	beta	probability of rewiring.
[in]	n	size (i.e., number of vertices) of the topology.

Definition at line 50 of file watts_strogatz.cpp.

Member Function Documentation

base_ptr pagmo::topology::watts_strogatz::clone ( ) const

virtual

Clone method.

Provided that the derived topology implements properly the copy constructor, virtually all implementations of this method will look like this:

return base_ptr(new derived_topology(*this));

Returns: topology::base_ptr to a copy of this.

Implements pagmo::topology::base.

Definition at line 74 of file watts_strogatz.cpp.

void pagmo::topology::watts_strogatz::connect ( const vertices_size_type & idx )

protectedvirtual

Establish connections between islands during a push_back() operation.

This method will be called by push_back() after a vertex has been added to the graph. The purpose of this method is to connect the newly-added vertex to other vertices according to the properties of the topology.

Parameters

[in] idx index of the newly-added vertex.

Implements pagmo::topology::base.

Definition at line 137 of file watts_strogatz.cpp.

std::string pagmo::topology::watts_strogatz::get_name ( ) const

virtual

Get name of the topology.

Default implementation will return the class' mangled C++ name.