girgs Namespace Reference

Functions
GIRGS_API std::vector< double >	generateWeights (int n, double ple, int weightSeed, bool parallel=true)
	The weights are sampled according to a power law distribution between [1, n) More...
GIRGS_API std::vector< std::vector< double > >	generatePositions (int n, int dimension, int positionSeed, bool parallel=true)
	Samples d dimensional coordinates for n points on a torus \([0,1)^d\). More...
GIRGS_API double	scaleWeights (std::vector< double > &weights, double desiredAvgDegree, int dimension, double alpha)
	Scales all weights so that the expected average degree equals desiredAvgDegree. Implemented as binary search over an estimation function. More...
GIRGS_API std::vector< std::pair< int, int > >	generateEdges (const std::vector< double > &weights, const std::vector< std::vector< double >> &positions, double alpha, int samplingSeed)
	Samples edges according to weights and positions. An edge between node u and v is formed with probability \( \left(\frac{w_u w_v / W}{|| x_u - x_v ||^d}\right)^\alpha \) or 1.0 if the term exceeds 1.0. More...
GIRGS_API void	saveDot (const std::vector< double > &weights, const std::vector< std::vector< double >> &positions, const std::vector< std::pair< int, int >> &graph, const std::string &file)
	Saves the graph in .dot format (graphviz). The weight is saved as a label and the coordinates as a position attribute for each Node. More...

Function Documentation

generateEdges()

GIRGS_API std::vector<std::pair<int,int> > girgs::generateEdges	(	const std::vector< double > &	weights,
		const std::vector< std::vector< double >> &	positions,
		double	alpha,
		int	samplingSeed
	)

Samples edges according to weights and positions. An edge between node u and v is formed with probability \( \left(\frac{w_u w_v / W}{|| x_u - x_v ||^d}\right)^\alpha \) or 1.0 if the term exceeds 1.0.

Parameters

weights	Power law distributed weights.
positions	Positions on a torus. All inner vectors should have the same length indicating the dimension of the torus.
alpha	Edge probability parameter.
samplingSeed	Seed to sample the edges.

Returns

An edge list with zero based indices.

generatePositions()

GIRGS_API std::vector<std::vector<double> > girgs::generatePositions	(	int	n,
		int	dimension,
		int	positionSeed,
		bool	parallel = true
	)

Samples d dimensional coordinates for n points on a torus \([0,1)^d\).

Parameters

n	Size of the graph.
dimension	Dimension of the geometry.
positionSeed	Seed to sample the positions.

Returns

The positions on a torus. All inner vectors have the same length.

generateWeights()

GIRGS_API std::vector<double> girgs::generateWeights	(	int	n,
		double	ple,
		int	weightSeed,
		bool	parallel = true
	)

The weights are sampled according to a power law distribution between [1, n)

Parameters

n	The size of the graph. Should match with size of positions.
ple	The power law exponent to sample the new weights. Should be 2.0 to 3.0.
weightSeed	A seed for weight sampling. Should not be equal to the position seed.

Returns

The weights according to the desired distribution.

saveDot()

GIRGS_API void girgs::saveDot	(	const std::vector< double > &	weights,
		const std::vector< std::vector< double >> &	positions,
		const std::vector< std::pair< int, int >> &	graph,
		const std::string &	file
	)

Saves the graph in .dot format (graphviz). The weight is saved as a label and the coordinates as a position attribute for each Node.

Parameters

weights	Power law distributed weights.
positions	The positions on a torus.
graph	An edge list with zero based indices.
file	The name of the output file.

scaleWeights()

GIRGS_API double girgs::scaleWeights	(	std::vector< double > &	weights,
		double	desiredAvgDegree,
		int	dimension,
		double	alpha
	)

Scales all weights so that the expected average degree equals desiredAvgDegree. Implemented as binary search over an estimation function.

Bug:

For \(\alpha > 10\) we use the estimation for threshold graphs due to numerical difficulties. This leads to slightly higher degrees than desired. Also I experienced inaccurate results for \(9 \leq \alpha < 10\).

Parameters

weights	The weights to be modified.
desiredAvgDegree	The desired average degree.
dimension	Dimension of the underlying geometry. Should equal the dimensionality of the positions.
alpha	Parameter of the algorithm. Should be the same as for the generation process.

Returns

The scaling s applied to all weights. The constant c hidden in the theta of the edge probabilities is \(s^\alpha\) for \(\alpha < \infty\) and \(s^{1/d}\) in the threshold case.