For using the igraph C library
void igraph_version(const char **version_string, int *major, int *minor, int *subminor);
Arguments:
| Pointer to a string pointer. If not null, it is set to the igraph version string, e.g. "0.9.11" or "0.10.0". This string must not be modified or deallocated. |
| If not a null pointer, then it is set to the major igraph version. E.g. for version "0.9.11" this is 0. |
| If not a null pointer, then it is set to the minor igraph version. E.g. for version "0.9.11" this is 11. |
| If not a null pointer, then it is set to the subminor igraph version. E.g. for version "0.9.11" this is 11. |
Example 32.1. Fileexamples/simple/igraph_version.c
#include <igraph.h>#include <string.h>intmain(void) { char tmp[100];const char *string; int major, minor, subminor;igraph_version(&string, &major, &minor, &subminor);snprintf(tmp,sizeof(tmp), "%i.%i.%i", major, minor, subminor);if (strncmp(string, tmp,strlen(tmp))) {return 1; }return 0;}
igraph_error_t igraph_running_mean(const igraph_vector_t *data, igraph_vector_t *res, igraph_integer_t binwidth);
The running mean is defined by the mean of thepreviousbinwidth values.
Arguments:
| The vector containing the data. |
| The vector containing the result. This should be initialized before calling this function and will be resized. |
| Integer giving the width of the bin for the running mean calculation. |
Returns:
Error code. |
Time complexity: O(n),n is the length ofthe data vector.
igraph_error_t igraph_random_sample(igraph_vector_int_t *res, igraph_integer_t l, igraph_integer_t h, igraph_integer_t length);
This function generates an increasing sequence of random integernumbers from a given interval. The algorithm is taken literallyfrom (Vitter 1987). This method can be used for generating numbers from avery large interval. It is primarily created for randomlyselecting some edges from the sometimes huge set of possible edgesin a large graph.
Reference:
J. S. Vitter. An efficient algorithm for sequential random sampling.ACM Transactions on Mathematical Software, 13(1):58--67, 1987.https://doi.org/10.1145/23002.23003
Arguments:
| Pointer to an initialized vector. This will hold the result. It will be resized to the proper size. |
| The lower limit of the generation interval (inclusive). This must be less than or equal to the upper limit, and it must be integral. |
| The upper limit of the generation interval (inclusive). This must be greater than or equal to the lower limit, and it must be integral. |
| The number of random integers to generate. |
Returns:
The error code |
Time complexity: according to (Vitter 1987), the expectedrunning time is O(length).
Example 32.2. Fileexamples/simple/igraph_random_sample.c
#include <igraph.h>intmain(void) { igraph_vector_int_t V;igraph_vector_int_init(&V, 0);igraph_random_sample(&V, 0, 100, 5);igraph_vector_int_print(&V);igraph_vector_int_destroy(&V);}
igraph_error_t igraph_sample_sphere_surface(igraph_integer_t dim, igraph_integer_t n, igraph_real_t radius, igraph_bool_t positive, igraph_matrix_t *res);
The center of the sphere is at the origin.
Arguments:
| The dimension of the random vectors. |
| The number of vectors to sample. |
| Radius of the sphere, it must be positive. |
| Whether to restrict sampling to the positive orthant. |
| Pointer to an initialized matrix, the result is stored here, each column will be a sampled vector. The matrix is resized, as needed. |
Returns:
Error code. |
Time complexity: O(n*dim*g), where g is the time complexity ofgenerating a standard normal random number.
See also:
|
igraph_error_t igraph_sample_sphere_volume(igraph_integer_t dim, igraph_integer_t n, igraph_real_t radius, igraph_bool_t positive, igraph_matrix_t *res);
The center of the sphere is at the origin.
Arguments:
| The dimension of the random vectors. |
| The number of vectors to sample. |
| Radius of the sphere, it must be positive. |
| Whether to restrict sampling to the positive orthant. |
| Pointer to an initialized matrix, the result is stored here, each column will be a sampled vector. The matrix is resized, as needed. |
Returns:
Error code. |
Time complexity: O(n*dim*g), where g is the time complexity ofgenerating a standard normal random number.
See also:
|
igraph_error_t igraph_sample_dirichlet(igraph_integer_t n, const igraph_vector_t *alpha, igraph_matrix_t *res);
Arguments:
| The number of vectors to sample. |
| The parameters of the Dirichlet distribution. They must be positive. The length of this vector gives the dimension of the generated samples. |
| Pointer to an initialized matrix, the result is stored here, one sample in each column. It will be resized, as needed. |
Returns:
Error code. |
Time complexity: O(n * dim * g), where dim is the dimension of thesample vectors, set by the length of alpha, and g is the timecomplexity of sampling from a Gamma distribution.
See also:
|
igraph_error_t igraph_convex_hull_2d( const igraph_matrix_t *data, igraph_vector_int_t *resverts, igraph_matrix_t *rescoords);
The convex hull is determined by the Graham scan algorithm.See the following reference for details:
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and CliffordStein. Introduction to Algorithms, Second Edition. MIT Press andMcGraw-Hill, 2001. ISBN 0262032937. Pages 949-955 of section 33.3:Finding the convex hull.
Arguments:
| vector containing the coordinates. The length of the vector must be even, since it contains X-Y coordinate pairs. |
| the vector containing the result, e.g. the vector of vertex indices used as the corners of the convex hull. Supply |
| the matrix containing the coordinates of the selected corner vertices. Supply |
Returns:
Error code: |
Time complexity: O(n log(n)) where n is the number of vertices.
typedef struct igraph_plfit_result_t { igraph_bool_t continuous; igraph_real_t alpha; igraph_real_t xmin; igraph_real_t L; igraph_real_t D; const igraph_vector_t* data;} igraph_plfit_result_t;This data structure contains the result ofigraph_power_law_fit(),which tries to fit a power-law distribution to a vector of numbers. Thestructure contains the following members:
Values:
| Whether the fitted power-law distribution was continuous or discrete. |
| The exponent of the fitted power-law distribution. |
| The minimum value from which the power-law distribution was fitted. In other words, only the values larger than |
| The log-likelihood of the fitted parameters; in other words, the probability of observing the input vector given the parameters. |
| The test statistic of a Kolmogorov-Smirnov test that compares the fitted distribution with the input vector. Smaller scores denote better fit. |
| The p-value of the Kolmogorov-Smirnov test; |
| The vector containing the original input data. May not be valid any more if the caller already destroyed the vector. |
igraph_error_t igraph_power_law_fit( const igraph_vector_t* data, igraph_plfit_result_t* result, igraph_real_t xmin, igraph_bool_t force_continuous);
This function fits a power-law distribution to a vector containing samplesfrom a distribution (that is assumed to follow a power-law of course). Ina power-law distribution, it is generally assumed that P(X=x) isproportional to x-alpha, where x is a positive number and alphais greater than 1. In many real-world cases, the power-law behaviour kicksin only above a threshold valuexmin. The goal of this functions is todeterminealpha ifxmin is given, or to determinexmin and thecorresponding value ofalpha.
The function uses the maximum likelihood principle to determinealphafor a givenxmin; in other words, the function will return thealphavalue for which the probability of drawing the given sample is the highest.Whenxmin is not given in advance, the algorithm will attempt to findthe optimalxmin value for which the p-value of a Kolmogorov-Smirnovtest between the fitted distribution and the original sample is the largest.The function uses the method of Clauset, Shalizi and Newman to calculate theparameters of the fitted distribution. See the following reference fordetails:
Aaron Clauset, Cosma R. Shalizi and Mark E.J. Newman: Power-lawdistributions in empirical data. SIAM Review 51(4):661-703, 2009.https://doi.org/10.1137/070710111
Arguments:
| vector containing the samples for which a power-law distribution is to be fitted. Note that you have to provide thesamples, not the probability density function or the cumulative distribution function. For example, if you wish to fit a power-law to the degrees of a graph, you can use the output of |
| the result of the fitting algorithm. See |
| the minimum value in the sample vector where the power-law behaviour is expected to kick in. Samples smaller than |
| assume that the samples in the |
Returns:
Error code: |
Time complexity: in the continuous case, O(n log(n)) ifxmin is given.In the discrete case, the time complexity is dominated by the complexity ofthe underlying L-BFGS algorithm that is used to optimize alpha. Ifxminis not given, the time complexity is multiplied by the number of uniquesamples in the input vector (although it should be faster in practice).
Example 32.3. Fileexamples/simple/igraph_power_law_fit.c
#include <igraph.h>intmain(void) { igraph_t g;igraph_vector_t degree;igraph_plfit_result_t model;/* Seed random number generator to ensure reproducibility. */igraph_rng_seed(igraph_rng_default(), 42);/* Generate a BA network; degree distribution is supposed to be a power-law * if the graph is large enough */igraph_barabasi_game( &g, 10000,/*power=*/ 1,/*m=*/ 2,/* outseq= */ 0,/* outpref= */ 0,/*A=*/ 1, IGRAPH_UNDIRECTED, IGRAPH_BARABASI_BAG,/*start_from=*/ 0 );/* Get the vertex degrees. We use igraph_strength() because it stores its * result in an igraph_vector_t */igraph_vector_init(°ree, 0);igraph_strength(&g, °ree,igraph_vss_all(), IGRAPH_ALL, IGRAPH_NO_LOOPS, 0);/* Fit a power-law to the degrees */igraph_power_law_fit( °ree, &model,/* xmin = */ -1,/* force_continuous = */ 0 );/* If you also need a p-value: *//* igraph_plfit_result_calculate_p_value(&model, &p, 0.001); */printf("alpha = %.5f\n", model.alpha);printf("xmin = %.5f\n", model.xmin);printf("log-likelihood = %.5f\n", model.L);igraph_vector_destroy(°ree);igraph_destroy(&g);return 0;}
igraph_error_t igraph_plfit_result_calculate_p_value( const igraph_plfit_result_t* model, igraph_real_t* result, igraph_real_t precision);
The p-value is calculated by resampling the input data many times in a waythat the part below the fittedx_min threshold is resampled from theinput data itself, while the part above the fittedx_min threshold isdrawn from the fitted power-law function. A Kolmogorov-Smirnov test is thenperformed for each resampled dataset and its test statistic is compared with theobserved test statistic from the original dataset. The fraction of resampleddatasets that have ahigher test statistic is the returned p-value.
Note that the precision of the returned p-value depends on the number ofresampling attempts. The number of resampling trials is determined by0.25 divided by the square of the required precision. For instance, a requiredprecision of 0.01 means that 2500 samples will be drawn.
If igraph is compiled with OpenMP support, this function will use parallelOpenMP threads for the resampling. Each OpenMP thread gets its own instanceof a random number generator. However, since the scheduling of OpenMP threadsis outside our control, we cannot guarantee how many resampling instances thethreads are asked to execute, thus it may happen that the random numbergenerators are used differently between runs. If you want to obtainreproducible results, seed igraph's master RNG appropriately, and force thenumber of OpenMP threads to 1 early in your program, either by callingomp_set_num_threads(1) or by setting the value of theOMP_NUM_THREADSenvironment variable to 1.
Arguments:
| The fitted power-law model from the |
| The calculated p-value is returned here |
| The desired precision of the p-value. Higher values correspond to longer calculation time. |
Returns:
Error code. |
int igraph_cmp_epsilon(double a, double b, double eps);
Determines whether two double-precision floats are "almost equal"to each other with a given level of tolerance on the relative error.
The function supports infinities and NaN values. NaN values are considerednot equal to any other value (even another NaN), but the ordering isarbitrary; in other words, we only guarantee that comparing a NaN withany other value will not return zero. Positive infinity is considered tobe greater than any finite value with any tolerance. Negative infinity isconsidered to be smaller than any finite value with any tolerance.Positive infinity is considered to be equal to another positive infinitywith any tolerance. Negative infinity is considered to be equal to anothernegative infinity with any tolerance.
Arguments:
| The first float. |
| The second float. |
| The level of tolerance on the relative error. The relative error is defined as |
Returns:
Zero if the two floats are nearly equal to each other within the given level of tolerance, positive number if the first float is larger, negative number if the second float is larger. |
igraph_bool_t igraph_almost_equals(double a, double b, double eps);
Determines whether two double-precision floats are "almost equal"to each other with a given level of tolerance on the relative error.
Arguments:
| The first float. |
| The second float. |
| The level of tolerance on the relative error. The relative error is defined as |
Returns:
True if the two floats are nearly equal to each other within the given level of tolerance, false otherwise. |
igraph_bool_t igraph_complex_almost_equals(igraph_complex_t a, igraph_complex_t b, igraph_real_t eps);
Determines whether two complex numbers are "almost equal"to each other with a given level of tolerance on the relative error.
Arguments:
| The first complex number. |
| The second complex number. |
| The level of tolerance on the relative error. The relative error is defined as |
Returns:
True if the two complex numbers are nearly equal to each other within the given level of tolerance, false otherwise. |
igraph_error_t igraph_convex_hull( const igraph_matrix_t *data, igraph_vector_int_t *resverts, igraph_matrix_t *rescoords);
The convex hull is determined by the Graham scan algorithm.See the following reference for details:
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and CliffordStein. Introduction to Algorithms, Second Edition. MIT Press andMcGraw-Hill, 2001. ISBN 0262032937. Pages 949-955 of section 33.3:Finding the convex hull.
Arguments:
| vector containing the coordinates. The length of the vector must be even, since it contains X-Y coordinate pairs. |
| the vector containing the result, e.g. the vector of vertex indices used as the corners of the convex hull. Supply |
| the matrix containing the coordinates of the selected corner vertices. Supply |
Returns:
Error code: |
Time complexity: O(n log(n)) where n is the number of vertices.
| ← Chapter 31. Advanced igraph programming | Chapter 33. Glossary → |