stag.random Namespace Reference

Functions
graph.Graph	sbm (int n, int k, float p, float q, bool exact=False)
	Generate a graph from the symmetric stochastic block model.
graph.Graph	general_sbm (List[int] cluster_sizes, np.ndarray probabilities, bool exact=False)
	Generate a graph from the general stochastic block model.
def	general_sbm_edgelist (str filename, List[int] cluster_sizes, np.ndarray probabilities, bool exact=False)
	Generate a graph from the general stochastic block model and save the resulting graph as an edgelist file.
graph.Graph	erdos_renyi (int n, float p, bool exact=False)
	Generate a graph from the Erdos-Renyi model.
List[int]	sbm_gt_labels (int n, int k)
	Construct a vector with the ground truth labels for a graph drawn from the symmetric stochastic block model.
List[int]	general_sbm_gt_labels (List[int] cluster_sizes)
	Construct a vector with the ground truth labels for a graph drawn from the general stochastic block model.

Function Documentation

sbm()

graph.Graph stag.random.sbm	(	int	n,
		int	k,
		float	p,
		float	q,
		bool	exact = False
	)

Generate a graph from the symmetric stochastic block model.

Every cluster has the same number of vertices. 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})\) and the exact method has running time \(O(n^2)\) where \(\mathrm{nnz}\) is the number of non-zeros in the generated graph's adjacency matrix.

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 an edge inside a cluster.
q	the probability of including an edge between two clusters.
exact	(optional) whether to use the exact probability distribution or an approximation.

Returns

the randomly generated stag.graph.Graph

general_sbm()

graph.Graph stag.random.general_sbm	(	List[int]	cluster_sizes,
		np.ndarray	probabilities,
		bool	exact = False
	)

Generate a graph from the general stochastic block model.

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

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

import numpy as np
import stag.graph
import stag.random
 
cluster_sizes = [100, 20, 10]
prob_mat = np.asarray([[0.4, 0.1, 0.1],
                       [0.1, 0.7, 0],
                       [0.1, 0, 1]])
my_graph = stag.random.general_sbm(cluster_sizes, prob_mat)
print(my_graph.adjacency())

Parameters

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

Returns

the randomly generated graph

general_sbm_edgelist()

def stag.random.general_sbm_edgelist	(	str	filename,
		List[int]	cluster_sizes,
		np.ndarray	probabilities,
		bool	exact = False
	)

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 list 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.

erdos_renyi()

graph.Graph stag.random.erdos_renyi	(	int	n,
		float	p,
		bool	exact = False
	)

Generate a graph from the Erdos-Renyi model.

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 sampled 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.

Returns

the randomly generated stag.graph.Graph

sbm_gt_labels()

List[int] stag.random.sbm_gt_labels	(	int	n,
		int	k
	)

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

Example

import stag.graph
import stag.random
 
n = 6
k = 3
myGraph = stag.random.sbm(n, k, 0.8, 0.1)
 
gt_labels = stag.random.sbm_gt_labels(n, k)
 
# gt_labels is the list [0, 0, 1, 1, 2, 2].

Parameters

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

Returns

a list of integers containing the ground truth labels for the vertices in the graph.

general_sbm_gt_labels()

List[int] stag.random.general_sbm_gt_labels

(

List[int]

cluster_sizes

)

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

Example

import stag.graph
import stag.random
 
cluster_sizes = [4, 2]
gt_labels = stag.random.general_sbm_gt_labels(cluster_sizes)
 
# gt_labels is the list [0, 0, 0, 0, 1, 1]

Parameters

cluster_sizes

a list 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.