random.h File Reference

Description

Methods for generating graphs from random graph models.

Functions
Graph	stag::sbm (StagInt n, StagInt k, StagReal p, StagReal q, bool exact)
Graph	stag::sbm (StagInt n, StagInt k, StagReal p, StagReal q)
Graph	stag::general_sbm (std::vector< StagInt > &cluster_sizes, DenseMat &probabilities, bool exact)
Graph	stag::general_sbm (std::vector< StagInt > &cluster_sizes, DenseMat &probabilities)
void	stag::general_sbm_edgelist (std::string &filename, std::vector< StagInt > &cluster_sizes, DenseMat &probabilities, bool exact)
void	stag::general_sbm_edgelist (std::string &filename, std::vector< StagInt > &cluster_sizes, DenseMat &probabilities)
Graph	stag::erdos_renyi (StagInt n, StagReal p, bool exact)
Graph	stag::erdos_renyi (StagInt n, StagReal p)
std::vector< StagInt >	stag::sbm_gt_labels (StagInt n, StagInt k)
std::vector< StagInt >	stag::general_sbm_gt_labels (std::vector< StagInt > &cluster_sizes)

Function Documentation

sbm() [1/2]

Graph stag::sbm	(	StagInt	n,
		StagInt	k,
		StagReal	p,
		StagReal	q,
		bool	exact
	)

Generate a graph from the symmetric stochastic block model.

Generates a graph with \(n\) vertices, divided into \(k\) evenly-sized clusters. For each pair of vertices \(u\) and \(v\), the probability of including the edge \(\{u, v\}\) in the graph is

• \(p\) if \(u\) and \(v\) are in the same cluster, and
• \(q\) otherwise.

For large enough values of \(n\), this method samples from an approximate stochastic block model by default which significantly speeds up the execution time. To sample exactly from the stochastic block model, pass the optional 'exact' parameter to the method.

The approximate sampling method has running time \(O(k^2 + \mathrm{nnz})\) where \(\mathrm{nnz}\) is the number of non-zeros in the generated graph's adjacency matrix, and the exact method has running time \(O(n^2)\).

Parameters

n	the number of vertices in the graph
k	the number of clusters; vertices are split evenly between clusters
p	the probability of including each edge inside a cluster
q	the probability of including each edge between two clusters
exact	(optional) whether to use the exact probability distribution. Default: false.

Returns

the randomly generated graph

sbm() [2/2]

Graph stag::sbm	(	StagInt	n,
		StagInt	k,
		StagReal	p,
		StagReal	q
	)

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

general_sbm() [1/2]

Graph stag::general_sbm	(	std::vector< StagInt > &	cluster_sizes,
		DenseMat &	probabilities,
		bool	exact
	)

Generate a graph from the general stochastic block model.

The cluster_sizes vector specifies the number of vertices in each generated cluster. Let \(k\) be the length of the cluster_sizes vector.

Then, probabilities should be a \(k \times k\) matrix which specifies the edge probability between every pair of vertices. That is, for each pair of vertices \(u\) and \(v\), the probability of including the edge \(\{u, v\}\) in the graph is \(P(u, v)\), where \(P\) is the probabilities matrix.

The approximate sampling method has running time \(O(k^2 + \mathrm{nnz})\) where \(\mathrm{nnz}\) is the number of non-zeros in the generated graph's adjacency matrix, and the exact method has running time \(O(n^2)\).

Example

#include <stag/graph.h>
#include <stag/random.h>
 
int main() {
  std::vector<StagInt> cluster_sizes = {100, 20, 10};
  DenseMat prob_mat {{0.4, 0.1, 0.1}, {0.1, 0.7, 0}, {0.1, 0, 1}};
  stag::Graph myGraph = stag::general_sbm(cluster_sizes, prob_mat);
  std::cout << *myGraph.adjacency() << std::endl;
  return 0;
}

Parameters

cluster_sizes	a vector of length \(k\) with the number of vertices in each cluster.
probabilities	a \(k \times k\) matrix with the inter-cluster probabilities.
exact	(optional) whether to use the exact probability distribution. Default: false.

Returns

the randomly generated graph

general_sbm() [2/2]

Graph stag::general_sbm	(	std::vector< StagInt > &	cluster_sizes,
		DenseMat &	probabilities
	)

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

general_sbm_edgelist() [1/2]

void stag::general_sbm_edgelist	(	std::string &	filename,
		std::vector< StagInt > &	cluster_sizes,
		DenseMat &	probabilities,
		bool	exact
	)

Generate a graph from the general stochastic block model and save the resulting graph as an edgelist file.

This method uses only constant memory since the graph can be streamed to disk while it is being generated.

Parameters

filename	the edgelist file to save the graph to
cluster_sizes	a vector of length \(k\) with the number of vertices in each cluster.
probabilities	a \(k \times k\) matrix with the inter-cluster probabilities.
exact	(optional) whether to use the exact probability distribution. Default: false.

general_sbm_edgelist() [2/2]

void stag::general_sbm_edgelist	(	std::string &	filename,
		std::vector< StagInt > &	cluster_sizes,
		DenseMat &	probabilities
	)

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

erdos_renyi() [1/2]

Graph stag::erdos_renyi	(	StagInt	n,
		StagReal	p,
		bool	exact
	)

Generate a graph from the Erdos-Renyi model.

Generates a graph with \(n\) vertices. For each pair of vertices \(u\) and \(v\), the edge \(\{u, v\}\) is included in the graph with probability \(p\).

For large values of n, this method will use an approximate version of the random model with running time \(O(\mathrm{nnz})\) where \(\mathrm{nnz}\) is the number of edges in the generated graph.

If the 'exact' parameter is true, then the true Erdos-Renyi distribution will be used, with running time \(O(n^2)\).

Parameters

n	the number of vertices in the graph
p	the probability of including each edge
exact	(optional) whether to sample from the exact model. Default: false.

Returns

the randomly generated graph

erdos_renyi() [2/2]

Graph stag::erdos_renyi	(	StagInt	n,
		StagReal	p
	)

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

sbm_gt_labels()

std::vector< StagInt > stag::sbm_gt_labels	(	StagInt	n,
		StagInt	k
	)

Construct a vector with the ground truth labels for a graph drawn from the symmetric stochastic block model.

Example

#include <stag/graph.h>
#include <stag/random.h>
 
int main() {
  stag_int n = 6;
  stag_int k = 3;
  stag::Graph myGraph = stag::sbm(n, k, 0.8, 0.1);
 
  std::vector<stag_int> gt_labels = stag::sbm_gt_labels(n, k);
 
  // gt_labels is the vector {0, 0, 1, 1, 2, 2}.
 
  return 0;
}

Parameters

n	the number of vertices in the graph
k	the number of clusters

Returns

a vector containing the ground truth labels for the vertices in the graph.

general_sbm_gt_labels()

std::vector< StagInt > stag::general_sbm_gt_labels

(

std::vector< StagInt > &

cluster_sizes

)

Construct a vector with the ground truth labels for a graph drawn from the general stochastic block model.

Example

#include <stag/graph.h>
#include <stag/random.h>
 
int main() {
  std::vector<stag_int> cluster_sizes = {4, 2};
  DenseMat prob_mat {{0.4, 0.1}, {0.1, 0.7}};
  stag::Graph myGraph = stag::general_sbm(cluster_sizes, prob_mat);
 
  std::vector<stag_int> gt_labels = stag::general_sbm_gt_labels(cluster_sizes);
 
  // gt_labels is the vector {0, 0, 0, 0, 1, 1}.
 
  return 0;
}

Parameters

cluster_sizes

a vector of length \(k\) with the number of vertices in each cluster.

Returns

a vector containing the ground truth labels for the vertices in the graph.