igraph 参考手册

用于使用 igraph C 库

搜索手册

第 9 章 图生成器

图生成器用于创建图。

几乎所有创建图对象的函数都在这里记录。例外情况是 igraph_induced_subgraph() 及其类似函数,它们基于另一个图创建图。

1. 确定性图生成器

1.1. igraph_create — 创建具有指定边的图。
1.2. igraph_small — 用于创建小图的简写,将边作为参数给出。
1.3. igraph_adjacency — 从邻接矩阵创建图。
1.4. igraph_weighted_adjacency — 从加权邻接矩阵创建图。
1.5. igraph_sparse_adjacency — 从稀疏邻接矩阵创建图。
1.6. igraph_sparse_weighted_adjacency — 从加权稀疏邻接矩阵创建图。
1.7. igraph_adjlist — 从邻接列表创建图。
1.8. igraph_star — 创建一个 星形 图,每个顶点仅连接到中心。
1.9. igraph_wheel — 创建一个 图,它是星形图和环图的并集。
1.10. igraph_hypercube — n 维超立方体图。
1.11. igraph_square_lattice — 任意维度的正方形格子。
1.12. igraph_triangular_lattice — 具有给定形状的三角形格子。
1.13. igraph_hexagonal_lattice — 具有给定形状的六边形格子。
1.14. igraph_ring — 创建一个 图或 路径 图。
1.15. igraph_kary_tree — 创建一个 k 叉树,其中几乎所有顶点都有 k 个子节点。
1.16. igraph_symmetric_tree — 创建一个对称树,在每个级别上具有指定的分支数。
1.17. igraph_regular_tree — 创建一个正则树。
1.18. igraph_tree_from_parent_vector — 从编码每个顶点的父节点的向量构造树或森林。
1.19. igraph_full — 创建一个完全图(完整图)。
1.20. igraph_full_citation — 创建一个完整的引用图(完整的有向无环图)。
1.21. igraph_full_multipartite — 创建一个完整的多部图。
1.22. igraph_turan — 创建一个图兰图。
1.23. igraph_realize_degree_sequence — 生成具有给定度序列的图。
1.24. igraph_realize_bipartite_degree_sequence — 生成具有给定二部度序列的二部图。
1.25. igraph_famous — 通过简单地提供其名称来创建一个著名的图。
1.26. igraph_lcf — 从 LCF 符号创建图。
1.27. igraph_lcf_vector — 从 LCF 符号创建图。
1.28. igraph_from_prufer — 从 Prüfer 序列生成树。
1.29. igraph_atlas — 从 图谱 创建一个小图。
1.30. igraph_de_bruijn — 生成一个德布鲁因图。
1.31. igraph_kautz — 生成一个 Kautz 图。
1.32. igraph_circulant — 创建一个循环图。
1.33. igraph_generalized_petersen — 创建一个广义 Petersen 图。
1.34. igraph_extended_chordal_ring — 创建一个扩展弦环。

1.1. igraph_create — 创建具有指定边的图。

igraph_error_t igraph_create(igraph_t *graph, const igraph_vector_int_t *edges,
                  igraph_integer_t n, igraph_bool_t directed);

参数: 

:

一个未初始化的图对象。

:

要添加的边,前两个元素是第一条边,依此类推。

n:

图中的顶点数,如果小于或等于 edges 向量中的最高顶点 ID,则会自动增加。因此,在这里给出 0 是安全的。

有向:

布尔值,是否创建有向图。如果是,则第一条边从 edges 中的第一个顶点 ID 指向第二个顶点 ID,依此类推。

返回值: 

错误代码: IGRAPH_EINVEVECTOR:无效的边向量(顶点数为奇数)。IGRAPH_EINVVID:无效(负)顶点 ID。

时间复杂度:O(|V|+|E|),|V| 是顶点数,|E| 是图中边的数量。

示例 9.1.  文件 examples/simple/igraph_create.c

#include <igraph.h>

int main(void) {

    igraph_t g;
    igraph_vector_int_t v1, v2;

    /* simple use */
    igraph_vector_int_init(&v1, 8);
    VECTOR(v1)[0] = 0;
    VECTOR(v1)[1] = 1;
    VECTOR(v1)[2] = 1;
    VECTOR(v1)[3] = 2;
    VECTOR(v1)[4] = 2;
    VECTOR(v1)[5] = 3;
    VECTOR(v1)[6] = 2;
    VECTOR(v1)[7] = 2;
    igraph_create(&g, &v1, 0, 0);
    if (igraph_vcount(&g) != 4) {
        return 1;
    }
    igraph_vector_int_init(&v2, 0);
    igraph_get_edgelist(&g, &v2, 0);
    igraph_vector_int_sort(&v1);
    igraph_vector_int_sort(&v2);
    if (!igraph_vector_int_all_e(&v1, &v2)) {
        return 2;
    }
    igraph_destroy(&g);

    /* higher number of vertices */
    igraph_create(&g, &v1, 10, 0);
    if (igraph_vcount(&g) != 10) {
        return 1;
    }
    igraph_get_edgelist(&g, &v2, 0);
    igraph_vector_int_sort(&v1);
    igraph_vector_int_sort(&v2);
    if (!igraph_vector_int_all_e(&v1, &v2)) {
        return 3;
    }
    igraph_destroy(&g);
    igraph_vector_int_destroy(&v1);
    igraph_vector_int_destroy(&v2);

    return 0;
}


1.2. igraph_small — 用于创建小图的简写,将边作为参数给出。

igraph_error_t igraph_small(igraph_t *graph, igraph_integer_t n, igraph_bool_t directed,
                            int first, ...);

当需要创建相对较小的图时,此函数非常方便。无需将边作为向量给出,而是简单地将它们作为参数给出,并且在最后一个有意义的边参数之后需要给出 -1

此函数旨在与作为文字整数输入的顶点 ID 一起使用。如果使用变量而不是文字,请确保它是 int 类型,因为这是此函数为所有可变参数假定的类型。使用不同的整数类型是未定义的行为,并且可能导致特定于平台的问题。

参数: 

:

指向未初始化的图对象的指针。结果将存储在此处。

n:

图中的顶点数;一个非负整数。

有向:

布尔常量;给出图是否应该是有向的。支持的值是

IGRAPH_DIRECTED

要创建的图将是 有向的。

IGRAPH_UNDIRECTED

要创建的图将是 无向的。

...:

给出图的边的附加参数,并且必须int 类型。不要忘记在最后一个(有意义的)参数之后提供一个附加的 -1first 参数的存在是出于技术原因,并且代表第一个可变参数。

返回值: 

错误代码。

时间复杂度:O(|V|+|E|),要创建的图中的顶点数加上边的数量。

示例 9.2.  文件 examples/simple/igraph_small.c

#include <igraph.h>

int main(void) {

    igraph_t g;

    igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 1, 2, 2, 3, 3, 4, 6, 1, -1);
    igraph_write_graph_edgelist(&g, stdout);
    igraph_destroy(&g);

    return 0;
}


1.3. igraph_adjacency — 从邻接矩阵创建图。

igraph_error_t igraph_adjacency(
    igraph_t *graph, const igraph_matrix_t *adjmatrix, igraph_adjacency_t mode,
    igraph_loops_t loops
);

保留矩阵中顶点的顺序,即对应于第一行/列的顶点将是 ID 为 0 的顶点,下一行是顶点 1,依此类推。

参数: 

:

指向未初始化的图对象的指针。

adjmatrix:

邻接矩阵。它的解释方式取决于 mode 参数。

模式:

用于指定给定矩阵如何被解释为邻接矩阵的常量。可能的值(A(i,j) 是邻接矩阵 adjmatrix 中第 i 行和第 j 列的元素)

IGRAPH_ADJ_DIRECTED

该图将是有向的,并且一个元素给出了两个顶点之间的边数。

IGRAPH_ADJ_UNDIRECTED

该图将是无向的,并且一个元素给出了两个顶点之间的边数。如果输入矩阵不是对称的,则会引发错误。

IGRAPH_ADJ_MAX

将创建一个无向图,顶点 i 和 j 之间的边数为 max(A(i,j), A(j,i))。

IGRAPH_ADJ_MIN

将创建一个无向图,顶点 i 和 j 之间有 min(A(i,j), A(j,i)) 条边。

IGRAPH_ADJ_PLUS

将创建一个无向图,顶点 i 和 j 之间有 A(i,j)+A(j,i) 条边。

IGRAPH_ADJ_UPPER

将创建一个无向图。只有右上三角形(包括对角线)用于边的数量。

IGRAPH_ADJ_LOWER

将创建一个无向图。只有左下三角形(包括对角线)用于边的数量。

循环:

用于指定在创建环边时应如何处理矩阵的对角线的常量。

IGRAPH_NO_LOOPS

忽略输入矩阵的对角线,并且不创建环。

IGRAPH_LOOPS_ONCE

将对角线条目视为入射到相应顶点上的环边的数量。

IGRAPH_LOOPS_TWICE

将对角线条目视为入射到相应顶点上的环边的数量的 两倍。对角线上的奇数将返回错误代码。

返回值: 

错误代码,IGRAPH_NONSQUARE:非正方形矩阵。IGRAPH_EINVAL:在邻接矩阵中找到负条目,或者在使用 IGRAPH_LOOPS_TWICE 的情况下在对角线上找到奇数。

时间复杂度:O(|V||V|),|V| 是图中的顶点数。

示例 9.3.  文件 examples/simple/igraph_adjacency.c

#include <igraph.h>

int main(void) {

    return 0;
}


1.4. igraph_weighted_adjacency — 从加权邻接矩阵创建图。

igraph_error_t igraph_weighted_adjacency(
    igraph_t *graph, const igraph_matrix_t *adjmatrix, igraph_adjacency_t mode,
    igraph_vector_t *weights, igraph_loops_t loops
);

保留矩阵中顶点的顺序,即对应于第一行/列的顶点将是 ID 为 0 的顶点,下一行是顶点 1,依此类推。

参数: 

:

指向未初始化的图对象的指针。

adjmatrix:

加权邻接矩阵。它的解释方式取决于 mode 参数。共同的特征是,权重为零的边被认为是不存在的(但是,允许负权重)。

模式:

用于指定给定矩阵如何被解释为邻接矩阵的常量。可能的值(A(i,j) 是邻接矩阵 adjmatrix 中第 i 行和第 j 列的元素)

IGRAPH_ADJ_DIRECTED

该图将是有向的,并且一个元素给出了两个顶点之间的边的权重。

IGRAPH_ADJ_UNDIRECTED

这与 IGRAPH_ADJ_MAX 相同,为了方便起见。

IGRAPH_ADJ_MAX

将创建一个无向图,顶点 i 和 j 之间的边的权重为 max(A(i,j), A(j,i))。

IGRAPH_ADJ_MIN

将创建一个无向图,顶点 i 和 j 之间的边权重为 min(A(i,j), A(j,i))。

IGRAPH_ADJ_PLUS

将创建一个无向图,顶点 i 和 j 之间的边权重为 A(i,j)+A(j,i)。

IGRAPH_ADJ_UPPER

将创建一个无向图,只有右上三角形(包括对角线)用于边权重。

IGRAPH_ADJ_LOWER

将创建一个无向图,只有左下三角形(包括对角线)用于边权重。

weights:

指向已初始化向量的指针,权重将存储在此处。

循环:

用于指定在创建环边时应如何处理矩阵的对角线的常量。

IGRAPH_NO_LOOPS

忽略输入矩阵的对角线,并且不创建环。

IGRAPH_LOOPS_ONCE

将对角线条目视为入射到相应顶点上的环边的权重。

IGRAPH_LOOPS_TWICE

将对角线条目视为入射到相应顶点上的环边的权重的 两倍

返回值: 

错误代码,IGRAPH_NONSQUARE:非正方形矩阵。

时间复杂度:O(|V||V|),|V| 是图中的顶点数。

示例 9.4.  文件 examples/simple/igraph_weighted_adjacency.c

#include <igraph.h>
#include <stdarg.h>

int main(void) {
    igraph_matrix_t mat;
    igraph_t g;
    int m[4][4] = { { 0, 1, 2, 0 }, { 2, 0, 0, 1 }, { 0, 0, 1, 0 }, { 0, 1, 0, 0 } };
    igraph_vector_t weights;
    igraph_vector_int_t el;
    igraph_integer_t i, j, n;
    igraph_vector_int_init(&el, 0);
    igraph_vector_init(&weights, 0);

    igraph_matrix_init(&mat, 4, 4);
    for (i = 0; i < 4; i++) for (j = 0; j < 4; j++) {
        MATRIX(mat, i, j) = m[i][j];
    }

    igraph_weighted_adjacency(&g, &mat, IGRAPH_ADJ_DIRECTED, &weights, IGRAPH_LOOPS_ONCE);

    igraph_get_edgelist(&g, &el, 0);
    n = igraph_ecount(&g);

    for (i = 0, j = 0; i < n; i++, j += 2) {
        printf("%" IGRAPH_PRId " --> %" IGRAPH_PRId ": %g\n",
               VECTOR(el)[j], VECTOR(el)[j + 1], VECTOR(weights)[i]);
    }

    igraph_matrix_destroy(&mat);
    igraph_vector_destroy(&weights);
    igraph_vector_int_destroy(&el);
    igraph_destroy(&g);

}


1.5. igraph_sparse_adjacency — 从稀疏邻接矩阵创建图。

igraph_error_t igraph_sparse_adjacency(igraph_t *graph, igraph_sparsemat_t *adjmatrix,
        igraph_adjacency_t mode, igraph_loops_t loops);

这具有与 igraph_adjacency() 相同的功能,但使用列压缩邻接矩阵。时间复杂度:O(|E|),其中 |E| 是图中的边数。

1.6. igraph_sparse_weighted_adjacency — 从加权稀疏邻接矩阵创建图。

igraph_error_t igraph_sparse_weighted_adjacency(
    igraph_t *graph, igraph_sparsemat_t *adjmatrix, igraph_adjacency_t mode,
    igraph_vector_t *weights, igraph_loops_t loops
);

这具有与 igraph_weighted_adjacency() 相同的功能,但使用列压缩邻接矩阵。时间复杂度:O(|E|),其中 |E| 是图中的边数。

1.7. igraph_adjlist — 从邻接列表创建图。

igraph_error_t igraph_adjlist(igraph_t *graph, const igraph_adjlist_t *adjlist,
                   igraph_neimode_t mode, igraph_bool_t duplicate);

邻接列表是一个向量列表,包含所有顶点的邻居。对于涉及对图结构进行许多更改的操作,建议您通过 igraph_adjlist_init() 将图转换为邻接列表,执行修改(对于邻接列表来说,这些修改的成本很低),然后通过此函数重新创建 igraph 图。

参数: 

:

指向未初始化的图对象的指针。

adjlist:

邻接列表。

模式:

是否创建有向图。IGRAPH_ALL 表示无向图,IGRAPH_OUT 表示来自外邻接列表的有向图(即,每个列表包含相应顶点的后继节点),IGRAPH_IN 表示来自内邻接列表的有向图

duplicate:

布尔常量。对于无向图,这指定每条边是否包含两次,在两个相邻顶点的向量中。如果这是 false,则假定每条边仅包含一次。对于有向图,此参数将被忽略。

返回值: 

错误代码。

另请参阅: 

igraph_adjlist_init() 用于相反的操作。

时间复杂度:O(|V|+|E|)。

1.8. igraph_star — 创建一个 星形 图,每个顶点仅连接到中心。

igraph_error_t igraph_star(igraph_t *graph, igraph_integer_t n, igraph_star_mode_t mode,
                igraph_integer_t center);

参数: 

:

指向未初始化的图对象的指针,这将是结果。

n:

整数常量,图中顶点的数量。

模式:

常量,给出要创建的星形图的类型。可能的值

IGRAPH_STAR_OUT

有向星形图,边从中心指向 其他顶点。

IGRAPH_STAR_IN

有向星形图,边从其他顶点指向 中心。

IGRAPH_STAR_MUTUAL

具有互边的有向星形图。

IGRAPH_STAR_UNDIRECTED

创建一个无向星形图。

center:

将作为图的中心的顶点的 ID。

返回值: 

错误代码

IGRAPH_EINVVID

无效的顶点数。

IGRAPH_EINVAL

无效的中心顶点。

IGRAPH_EINVMODE

无效的 mode 参数。

时间复杂度:O(|V|),图中顶点的数量。

另请参阅: 

示例 9.5.  文件 examples/simple/igraph_star.c

#include <igraph.h>
#include <stdio.h>

int main(void) {
    igraph_t graph;

    /* Create an undirected 6-star, with the 0th node as the centre. */
    igraph_star(&graph, 7, IGRAPH_STAR_UNDIRECTED, 0);

    /* Output the edge list of the graph. */
    igraph_write_graph_edgelist(&graph, stdout);

    /* Destroy the graph when we are done using it. */
    igraph_destroy(&graph);

    return 0;
}


1.9. igraph_wheel — 创建一个 图,它是星形图和环图的并集。

igraph_error_t igraph_wheel(igraph_t *graph, igraph_integer_t n, igraph_wheel_mode_t mode,
                igraph_integer_t center);

一个 n 个顶点的轮图可以被认为是一个具有 n - 1 个辐条的轮子。环图部分构成轮辋,而星形图部分添加辐条。

请注意,具有两个和三个顶点的轮图是非简单的:具有两个顶点的轮图包含一个自环,而具有三个顶点的轮图包含平行边(分别是 1 环和 2 环)。

参数: 

:

指向未初始化的图对象的指针,这将是结果。

n:

整数常量,图中顶点的数量。

模式:

常量,给出要创建的星形图的类型。可能的值

IGRAPH_WHEEL_OUT

有向轮图,边从中心指向 其他顶点。

IGRAPH_WHEEL_IN

有向轮图,边从其他顶点指向 中心。

IGRAPH_WHEEL_MUTUAL

具有互边的有向轮图。

IGRAPH_WHEEL_UNDIRECTED

创建一个无向轮图。

center:

将作为图的中心的顶点的 ID。

返回值: 

错误代码

IGRAPH_EINVVID

无效的顶点数。

IGRAPH_EINVAL

无效的中心顶点。

IGRAPH_EINVMODE

无效的 mode 参数。

时间复杂度:O(|V|),图中顶点的数量。

另请参阅: 

igraph_square_lattice()igraph_ring()igraph_star()igraph_kary_tree() 用于创建其他规则结构。

1.10. igraph_hypercube — n 维超立方体图。

igraph_error_t igraph_hypercube(igraph_t *graph,
                                igraph_integer_t n, igraph_bool_t directed);

警告

此函数是实验性的,其签名尚未被视为最终签名。我们保留更改函数签名的权利,而无需更改 igraph 的主要版本。使用它需要您自担风险。

超立方体图 Q_n 具有 2^n 个顶点和 2^(n-1) n 条边。当基于零的顶点 ID 的二进制表示形式恰好相差一位时,两个顶点连接。

参数: 

:

一个未初始化的图对象。

n:

超立方体图的维度。

有向:

图是否应该是有向的。边将从较低索引的顶点指向较高索引的顶点。

返回值: 

错误代码。

另请参阅: 

时间复杂度:O(2^n)

1.11. igraph_square_lattice — 任意维度的正方形格子。

igraph_error_t igraph_square_lattice(
    igraph_t *graph, const igraph_vector_int_t *dimvector, igraph_integer_t nei,
    igraph_bool_t directed, igraph_bool_t mutual, const igraph_vector_bool_t *periodic
);

创建给定大小的 d 维正方形格子。可以选择使格子周期性,并且可以在给定的图距离内连接邻居。

在零维情况下,返回单例图。

生成的图的顶点被排序,使得位置 (i_1, i_2, i_3, ..., i_d) 处的顶点在大小为 (n_1, n_2, ..., n_d) 的格子中的索引将为 i_1 + n_1 * i_2 + n_1 * n_2 * i_3 + ...

参数: 

:

一个未初始化的图对象。

dimvector:

向量,给出格子在每个维度上的大小。格子的维度将与此向量的长度相同。

nei:

整数值,给出将在其中连接两个顶点的距离(步数)。

有向:

布尔值,是否创建有向图。如果 mutualcircular 参数未设置为 true,则边将从较低索引的顶点指向较高索引的顶点。

mutual:

布尔值,如果图是有向的,则这给出是否将所有连接创建为互连。

periodic:

布尔向量,定义生成的格子是否沿每个维度都是周期性的。此向量的长度必须与 dimvector 的长度匹配。此参数也可以是 NULL,这意味着格子将不是周期性的。

返回值: 

错误代码:IGRAPH_EINVAL:无效(负)维度向量或维度向量的长度与周期性向量之间不匹配。

另请参阅: 

igraph_hypercube() 用于创建超立方体图;igraph_ring() 用于创建环图或路径图;igraph_triangular_lattice()igraph_hexagonal_lattice() 用于创建其他类型的格子;igraph_regular_tree() 用于创建 Bethe 格子。

时间复杂度:如果 nei 小于 2,则为 O(|V|+|E|)(就我记忆所及),|V| 和 |E| 是生成的图中顶点和边的数量。否则为 O(|V|*d^k+|E|),d 是图的平均度数,k 是 nei 参数。

1.12. igraph_triangular_lattice — 具有给定形状的三角形格子。

igraph_error_t igraph_triangular_lattice(
        igraph_t *graph, const igraph_vector_int_t *dims,
        igraph_bool_t directed, igraph_bool_t mutual);

警告

此函数是实验性的,其签名尚未被视为最终签名。我们保留更改函数签名的权利,而无需更改 igraph 的主要版本。使用它需要您自担风险。

创建一个三角形格子,其顶点的形式为 (i, j),对于非负整数 i 和 j,(i, j) 通常与 (i + 1, j)、(i, j + 1) 和 (i - 1, j + 1) 连接。该函数构造了由 igraph_hexagonal_lattice() 构造的图的平面对偶图。特别是,在构造的图中的顶点与由 igraph_hexagonal_lattice() 构造的图中长度为 6 的环之间存在一一对应关系,参数 dims 相同。

生成的图的顶点按字典顺序排序,第二个坐标更重要,例如,(i, j) < (i + 1, j) 和 (i + 1, j) < (i, j + 1)

参数: 

:

一个未初始化的图对象。

dims:

整数向量,定义格子的形状。如果 dims 的长度为 1,则生成的格子具有三角形形状,其中三角形的每一侧包含 dims[0] 个顶点。如果 dims 的长度为 2,则生成的格子具有“准矩形”形状,其中边分别包含 dims[0]dims[1] 个顶点。如果 dims 的长度为 3,则生成的格子具有六边形形状,其中六边形的边分别包含 dims[0]dims[1]dims[2] 个顶点。所有维度都必须是非负的。

有向:

布尔值,是否创建有向图。如果 mutual 参数未设置为 true,则边将从较低索引的顶点指向较高索引的顶点。

mutual:

布尔值,如果图是有向的,则这给出是否将所有连接创建为互连。

返回值: 

错误代码:IGRAPH_EINVALdims 的大小必须为 1、2 或 3,且所有分量至少为 1。

另请参阅: 

igraph_hexagonal_lattice()igraph_square_lattice() 用于创建其他类型的格子;igraph_regular_tree() 用于创建 Bethe 格子。

时间复杂度:O(|V|),其中 |V| 是生成的图中顶点的数量。

1.13. igraph_hexagonal_lattice — 具有给定形状的六边形格子。

igraph_error_t igraph_hexagonal_lattice(
        igraph_t *graph, const igraph_vector_int_t *dims,
        igraph_bool_t directed, igraph_bool_t mutual);

警告

此函数是实验性的,其签名尚未被视为最终签名。我们保留更改函数签名的权利,而无需更改 igraph 的主要版本。使用它需要您自担风险。

创建一个六边形格子,其顶点的形式为 (i, j),对于非负整数 i 和 j,(i, j) 通常与 (i + 1, j) 连接,如果 i 是奇数,则还与 (i - 1, j + 1) 连接。该函数构造了由 igraph_triangular_lattice() 构造的图的平面对偶图。特别是,在构造的图中长度为 6 的环与由 igraph_triangular_lattice() 函数构造的图中具有相同 dims 参数的顶点之间存在一一对应关系。

生成的图的顶点按字典顺序排序,第二个坐标更重要,例如,(i, j) < (i + 1, j) 和 (i + 1, j) < (i, j + 1)

参数: 

:

一个未初始化的图对象。

dims:

整数向量,定义格子的形状。如果 dims 的长度为 1,则生成的格子具有三角形形状,其中三角形的每一侧包含 dims[0] 个顶点。如果 dims 的长度为 2,则生成的格子具有“准矩形”形状,其中边分别包含 dims[0]dims[1] 个顶点。如果 dims 的长度为 3,则生成的格子具有六边形形状,其中六边形的边分别包含 dims[0]dims[1]dims[2] 个顶点。所有坐标都必须是非负的。

有向:

布尔值,是否创建有向图。如果 mutual 参数未设置为 true,则边将从较低索引的顶点指向较高索引的顶点。

mutual:

布尔值,如果图是有向的,则这给出是否将所有连接创建为互连。

返回值: 

错误代码:IGRAPH_EINVALdims 的大小必须为 1、2 或 3,且所有分量至少为 1。

另请参阅: 

igraph_triangular_lattice()igraph_square_lattice() 用于创建其他类型的格子;;igraph_regular_tree() 用于创建 Bethe 格子。

时间复杂度:O(|V|),其中 |V| 是生成的图中顶点的数量。

1.14. igraph_ring — 创建一个 图或 路径 图。

igraph_error_t igraph_ring(igraph_t *graph, igraph_integer_t n, igraph_bool_t directed,
                igraph_bool_t mutual, igraph_bool_t circular);

具有 n 个顶点的环通常在图论中被称为环图,通常用 C_n 表示。从环图 C_n 中删除一条边会导致路径图 P_n。此函数可以生成两者。

n 为 1 或 2 时,结果可能不是一个简单图:单环包含一个自环,而无向或互连的有向两环包含平行边。

参数: 

:

指向未初始化的图对象的指针。

n:

图中顶点的数量。

有向:

是否创建有向图。所有边都将沿环或路径的同一方向定向。

mutual:

是否在有向图中创建互边。对于无向图,它将被忽略。

circular:

是否创建闭环(环)或开路(路径)。

返回值: 

错误代码:IGRAPH_EINVAL:无效的顶点数。

时间复杂度:O(|V|),图中顶点的数量。

另请参阅: 

igraph_square_lattice() 用于生成更一般的(周期性或非周期性)格子。

示例 9.6.  文件 examples/simple/igraph_ring.c

#include <igraph.h>
#include <stdio.h>

int main(void) {
    igraph_t graph;

    /* Create a directed path graph on 10 vertices. */
    igraph_ring(&graph, 10, IGRAPH_DIRECTED, /* mutual= */ 0, /* circular= */ 0);

    /* Output the edge list of the graph. */
    printf("10-path graph:\n");
    igraph_write_graph_edgelist(&graph, stdout);

    /* Destroy the graph. */
    igraph_destroy(&graph);

    /* Create a 4-cycle graph. */
    igraph_ring(&graph, 4, IGRAPH_UNDIRECTED, /* mutual= */ 0, /* circular= */ 1);

    /* Output the edge list of the graph. */
    printf("\n4-cycle graph:\n");
    igraph_write_graph_edgelist(&graph, stdout);

    /* Destroy the graph. */
    igraph_destroy(&graph);

    return 0;
}


1.15. igraph_kary_tree — 创建一个 k 叉树,其中几乎所有顶点都有 k 个子节点。

igraph_error_t igraph_kary_tree(igraph_t *graph, igraph_integer_t n, igraph_integer_t children,
                igraph_tree_mode_t type);

要获得具有 l 层的完全对称树,其中每个顶点都恰好有 children 个后代,请使用 n = (children^(l+1) - 1) / (children - 1)。这样的树通常被称为 k 叉树,其中 k 指的是子节点的数量。

请注意,对于 n=0,将返回空图,igraph_is_tree() 不认为它是树。

参数: 

:

指向未初始化的图对象的指针。

n:

整数,图中的顶点数。

children:

整数,树中一个顶点的子节点数。

type:

常量,指示是否创建有向树,如果是,则指示其方向。可能的值

IGRAPH_TREE_OUT

有向树,边从父节点指向子节点。

IGRAPH_TREE_IN

有向树,边从子节点指向父节点。

IGRAPH_TREE_UNDIRECTED

无向树。

返回值: 

错误代码:IGRAPH_EINVAL:无效的顶点数。IGRAPH_INVMODE:无效的模式参数。

时间复杂度:O(|V|+|E|),顶点数加上图中的边数。

另请参阅: 

创建其他规则结构的函数:igraph_regular_tree()igraph_symmetric_tree()igraph_star();创建任意树的函数:igraph_from_prufer()igraph_tree_from_parent_vector();均匀随机抽样树的函数:igraph_tree_game();以及使用 IGRAPH_REALIZE_DEGSEQ_SMALLESTigraph_realize_degree_sequence(),用于创建具有给定度的树。

示例 9.7. 文件 examples/simple/igraph_kary_tree.c

#include <igraph.h>

int main(void) {
    igraph_t graph;
    igraph_bool_t res;

    /* Create a directed binary tree on 15 nodes,
       with edges pointing towards the root. */
    igraph_kary_tree(&graph, 15, 2, IGRAPH_TREE_IN);

    igraph_is_tree(&graph, &res, NULL, IGRAPH_IN);
    printf("Is it an in-tree? %s\n", res ? "Yes" : "No");

    igraph_is_tree(&graph, &res, NULL, IGRAPH_OUT);
    printf("Is it an out-tree? %s\n", res ? "Yes" : "No");

    igraph_destroy(&graph);

    return 0;
}


1.16. igraph_symmetric_tree — 创建一个对称树,其中在每一层具有指定数量的分支。

igraph_error_t igraph_symmetric_tree(igraph_t *graph, const igraph_vector_int_t *branches,
                igraph_tree_mode_t type);

此函数创建一个树,其中距根节点距离为 d 的所有顶点都有 branching_counts[d] 个子节点。

参数: 

:

指向未初始化的图对象的指针。

branches:

详细说明每一层分支数的向量。

type:

常量,指示是否创建有向树,如果是,则指示其方向。可能的值

IGRAPH_TREE_OUT

有向树,边从父节点指向子节点。

IGRAPH_TREE_IN

有向树,边从子节点指向父节点。

IGRAPH_TREE_UNDIRECTED

无向树。

返回值: 

错误代码:IGRAPH_INVMODE:无效的模式参数。IGRAPH_EINVAL:无效的子节点数。

时间复杂度:O(|V|+|E|),顶点数加上图中的边数。

另请参阅: 

创建其他规则树结构的函数:igraph_kary_tree()igraph_regular_tree()igraph_star();创建任意树的函数:igraph_from_prufer();均匀随机抽样树的函数:igraph_tree_game()

示例 9.8. 文件 examples/simple/igraph_symmetric_tree.c

#include <igraph.h>

int main(void) {

    igraph_t graph;
    igraph_bool_t res;
    igraph_vector_int_t v;
    igraph_vector_int_init_int(&v, 3, 3, 4, 5);

    /* Create a directed symmetric tree with 2 levels -
       3 children in first and 4 children in second level,
       5 children in third level
       with edges pointing towards the root. */
    igraph_symmetric_tree(&graph, &v, IGRAPH_TREE_IN);

    igraph_is_tree(&graph, &res, NULL, IGRAPH_IN);
    printf("Is it an in-tree? %s\n", res ? "Yes" : "No");

    igraph_is_tree(&graph, &res, NULL, IGRAPH_OUT);
    printf("Is it an out-tree? %s\n", res ? "Yes" : "No");

    igraph_destroy(&graph);
    igraph_vector_int_destroy(&v);

    return 0;
}


1.17. igraph_regular_tree — 创建一个规则树。

igraph_error_t igraph_regular_tree(igraph_t *graph, igraph_integer_t h, igraph_integer_t k, igraph_tree_mode_t type);

规则树的所有顶点(除了叶节点)都具有相同的总度数 k。这与 k 叉树(igraph_kary_tree())不同,在 k 叉树中,所有顶点都具有相同数量的子节点,因此根节点的度数比其他内部顶点小 1。规则树也称为 Bethe 格子。

参数: 

:

指向未初始化的图对象的指针。

h:

树的高度,即根节点和叶节点之间的距离。

k:

规则树的度数。

type:

常量,指示是否创建有向树,如果是,则指示其方向。可能的值

IGRAPH_TREE_OUT

有向树,边从父节点指向子节点。

IGRAPH_TREE_IN

有向树,边从子节点指向父节点。

IGRAPH_TREE_UNDIRECTED

无向树。

返回值: 

错误代码。

时间复杂度:O(|V|+|E|),顶点数加上图中的边数。

另请参阅: 

创建 k 叉树的函数:igraph_kary_tree(),其中每个顶点都具有相同数量的子节点,即出度,而不是相同的总度数。在每一层使用不同子节点数的函数:igraph_symmetric_tree()

示例 9.9. 文件 examples/simple/igraph_regular_tree.c

#include <igraph.h>

int main(void) {
    igraph_t tree;
    igraph_vector_t eccentricity;
    igraph_bool_t is_tree;

    /* Create a Bethe lattice with 5 levels, i.e. height 4. */
    igraph_regular_tree(&tree, 4, 3, IGRAPH_TREE_UNDIRECTED);

    /* Bethe lattices are trees. */
    igraph_is_tree(&tree, &is_tree, NULL, IGRAPH_ALL);
    printf("Is it a tree? %s\n", is_tree ? "Yes." : "No.");

    /* Compute and print eccentricities. The root is the most central. */
    igraph_vector_init(&eccentricity, 0);
    igraph_eccentricity(&tree, &eccentricity, igraph_vss_all(), IGRAPH_ALL);
    printf("Vertex eccentricities:\n");
    igraph_vector_print(&eccentricity);
    igraph_vector_destroy(&eccentricity);

    /* Clean up. */
    igraph_destroy(&tree);

    return 0;
}


1.18. igraph_tree_from_parent_vector — 从编码每个顶点的父节点的向量构造树或森林。

igraph_error_t igraph_tree_from_parent_vector(
        igraph_t *graph,
        const igraph_vector_int_t *parents,
        igraph_tree_mode_t type);

警告

此函数是实验性的,其签名尚未被视为最终签名。我们保留更改函数签名的权利,而无需更改 igraph 的主要版本。使用它需要您自担风险。

可以使用 parents 向量方便地表示有根树和森林,其中顶点 v 的父节点的 ID 存储在 parents[v] 中。此函数用于从父向量表示构造 igraph 图。结果保证是森林或树。如果发现 parents 向量编码了一个循环或自环,则会引发错误。

一些 igraph 函数会生成这样的向量,例如图遍历函数(igraph_bfs()igraph_dfs())、构造最短路径树的最短路径函数,以及一些其他专用函数,如 igraph_dominator_tree()igraph_cohesive_blocks()。没有父节点的顶点(即根节点)在 parents 向量中获得一个负数条目。

使用 igraph_bfs()igraph_dfs() 将森林转换为父向量表示。对于树,即具有单个根节点的森林,使用 igraph_bfs_simple() 更方便。

参数: 

:

指向未初始化的图对象的指针。

parents:

父向量。parents[v]v 的父顶点的 ID。parents[v] < 0 表示 v 没有父节点。

type:

常量,指示是否创建有向树,如果是,则指示其方向。可能的值

IGRAPH_TREE_OUT

有向树,边从父节点指向子节点。

IGRAPH_TREE_IN

有向树,边从子节点指向父节点。

IGRAPH_TREE_UNDIRECTED 无向树。

返回值: 

错误代码。

另请参阅: 

反向转换的函数:igraph_bfs()igraph_bfs_simple();从 Prüfer 序列创建树的函数:igraph_from_prufer();检查图是否为树或森林的函数:igraph_is_tree()igraph_is_forest()

时间复杂度:O(n),其中 n 是 parents 的长度。

1.19. igraph_full — 创建一个满图(完全图)。

igraph_error_t igraph_full(igraph_t *graph, igraph_integer_t n, igraph_bool_t directed,
                igraph_bool_t loops);

在满图中,存在每个可能的边:每个顶点都连接到每个其他顶点。igraph 将图论中完全图的通常概念推广到具有自环的图以及有向图。

参数: 

:

指向未初始化的图对象的指针。

n:

整数,图中的顶点数。

有向:

是否创建有向图。

循环:

是否包含自环。

返回值: 

错误代码:IGRAPH_EINVAL:无效的顶点数。

时间复杂度:O(|V|^2) = O(|E|),其中 |V| 是顶点数,|E| 是边数。

另请参阅: 

创建其他规则结构的函数:igraph_square_lattice()igraph_star()igraph_kary_tree()

示例 9.10. 文件 examples/simple/igraph_full.c

#include <igraph.h>
#include <stdio.h>

int main(void) {
    igraph_t graph;
    igraph_integer_t n_vertices = 10;

    /* Create an undirected complete graph. */
    /* Use IGRAPH_UNDIRECTED and IGRAPH_NO_LOOPS instead of 1/TRUE and 0/FALSE for better readability. */
    igraph_full(&graph, n_vertices, IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS);
    printf("The undirected complete graph on %" IGRAPH_PRId " vertices has %" IGRAPH_PRId " edges.\n",
          igraph_vcount(&graph), igraph_ecount(&graph));

    /* Remember to destroy the object at the end. */
    igraph_destroy(&graph);

    /* Create a directed complete graph. */
    igraph_full(&graph, n_vertices, IGRAPH_DIRECTED, IGRAPH_NO_LOOPS);
    printf("The directed complete graph on %" IGRAPH_PRId " vertices has %" IGRAPH_PRId " edges.\n",
          igraph_vcount(&graph), igraph_ecount(&graph));

    igraph_destroy(&graph);

    /* Create an undirected complete graph with self-loops. */
    igraph_full(&graph, n_vertices, IGRAPH_UNDIRECTED, IGRAPH_LOOPS);
    printf("The undirected complete graph on %" IGRAPH_PRId " vertices with self-loops has %" IGRAPH_PRId " edges.\n",
          igraph_vcount(&graph), igraph_ecount(&graph));

    igraph_destroy(&graph);

    /* Create a directed graph with self-loops. */
    igraph_full(&graph, n_vertices, IGRAPH_DIRECTED, IGRAPH_LOOPS);
    printf("The directed complete graph on %" IGRAPH_PRId " vertices with self-loops has %" IGRAPH_PRId " edges.\n",
          igraph_vcount(&graph), igraph_ecount(&graph));

    igraph_destroy(&graph);

    return 0;

}


1.20. igraph_full_citation — 创建一个完全引用图(完全有向无环图)。

igraph_error_t igraph_full_citation(igraph_t *graph, igraph_integer_t n,
                         igraph_bool_t directed);

这是一个有向图,当且仅当 j<i 时才存在每个 i->j 边。如果 directed 参数为 false,则创建一个无向图,它只是一个完全图。

参数: 

:

指向未初始化的图对象的指针,结果将存储在此处。

n:

顶点数。

有向:

是否创建有向图。如果为 false,则创建一个无向图。

返回值: 

错误代码。

另请参阅: 

时间复杂度:O(|V|^2) = O(|E|),其中 |V| 是顶点数,|E| 是边数。

1.21. igraph_full_multipartite — 创建一个完全多部图。

igraph_error_t igraph_full_multipartite(igraph_t *graph,
                          igraph_vector_int_t *types,
                          const igraph_vector_int_t *n,
                          igraph_bool_t directed,
                          igraph_neimode_t mode);

多部图包含两种或多种类型的顶点,并且只有不同类型的两个顶点之间才可能存在连接。此函数创建一个完全多部图。

参数: 

:

指向未初始化的图对象的指针,图将在此处创建。

types:

指向整数向量的指针。如果不为 null 指针,则将在此处存储每个顶点的类型。

n:

指向整数向量的指针,每种类型的顶点数。

有向:

布尔值,是否创建有向图。

模式:

一个常量,用于给出有向图的连接类型。如果 IGRAPH_OUT,则边从低索引顶点指向高索引顶点;如果 IGRAPH_IN,则实现相反的方向;IGRAPH_ALL,则将创建互边。

返回值: 

错误代码。

时间复杂度:O(|V|+|E|),顶点数和边数的线性关系。

另请参阅: 

完全二部图的函数:igraph_full_bipartite();Turán 图的函数:igraph_turan()

1.22. igraph_turan — 创建一个 Turán 图。

igraph_error_t igraph_turan(igraph_t *graph,
                            igraph_vector_int_t *types,
                            igraph_integer_t n,
                            igraph_integer_t r);

Turán 图是完全多部图,其分区的大小尽可能接近相等。

具有 n 个顶点和 r 个分区的 Turán 图是 n 个顶点上最密集的图,它不包含大小为 r+1 的团。

此函数生成无向图。当顶点数为零时,将返回空图。如果分区数大于顶点数,则返回完全图。

参数: 

:

指向 igraph_t 对象的指针,图将在此处创建。

types:

指向整数向量的指针。如果不为 null 指针,则将在此处存储每个顶点的类型(分区索引)。

n:

整数,图中的顶点数。

r:

整数,图的分区数,必须为正数。

返回值: 

错误代码。

时间复杂度:O(|V|+|E|),顶点数和边数的线性关系。

另请参阅: 

完全多部图的函数:igraph_full_multipartite()

1.23. igraph_realize_degree_sequence — 生成具有给定度序列的图。

igraph_error_t igraph_realize_degree_sequence(
        igraph_t *graph,
        const igraph_vector_int_t *outdeg, const igraph_vector_int_t *indeg,
        igraph_edge_type_sw_t allowed_edge_types,
        igraph_realize_degseq_t method);

此函数生成一个实现给定度序列的无向图,或一个实现给定出度和入度序列对的有向图。

使用 Havel-Hakimi 算法(无向情况)或类似的 Kleitman-Wang 算法(有向情况)构造简单无向图。这些算法的工作原理是选择一个任意顶点,并将其所有残桩连接到其他最高度数的顶点。在有向情况下,根据字典顺序确定“最高”(入度,出度)度数对。重复此步骤,直到所有度数都已连接完毕。

使用类似的算法生成无环多重图:选择一个任意顶点,并将其与单个连接连接到剩余度数最高的顶点。如果也允许自环,则使用相同的算法,但如果在此过程结束时仍然存在一个非零顶点,则通过向其添加自环来完成该图。因此,结果将最多包含一个具有自环的顶点。

method 参数控制选择要连接的顶点的顺序。在无向情况下,IGRAPH_REALIZE_DEGSEQ_SMALLEST 会生成一个连通图(如果存在)。这使得此方法适合于构造具有给定度序列的树。

参考

V. Havel: Poznámka o existenci konečných grafů (关于有限图的存在的说明), Časopis pro pěstování matematiky 80, 477-480 (1955). http://eudml.org/doc/19050

S. L. Hakimi: On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph, Journal of the SIAM 10, 3 (1962). https://www.jstor.org/stable/2098770

D. J. Kleitman and D. L. Wang: Algorithms for Constructing Graphs and Digraphs with Given Valences and Factors, Discrete Mathematics 6, 1 (1973). https://doi.org/10.1016/0012-365X%2873%2990037-X P. L. Erdős, I. Miklós, Z. Toroczkai: A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs, The Electronic Journal of Combinatorics 17.1 (2010). http://eudml.org/doc/227072

Sz. Horvát and C. D. Modes: Connectedness matters: construction and exact random sampling of connected networks (2021). https://doi.org/10.1088/2632-072X/abced5

参数: 

:

指向未初始化的图对象的指针。

outdeg:

无向图的度序列(如果 indeg 为 NULL),或有向图的出度序列(如果给定 indeg)。

indeg:

有向图的入度序列。传递 NULL 以生成无向图。

allowed_edge_types:

图中允许的边类型。对于有向图,目前仅实现了 IGRAPH_SIMPLE_SW。对于无向图,以下值为有效值

IGRAPH_SIMPLE_SW

简单图(即不允许自环或多重边)。

IGRAPH_LOOPS_SW

允许单个自环,但不允许多重边;目前尚未实现。

IGRAPH_MULTI_SW

允许多重边,但不允许自环。

IGRAPH_LOOPS_SW | IGRAPH_MULTI_SW

允许自环和多重边。

method:

生成图的方法。可能的值

IGRAPH_REALIZE_DEGSEQ_SMALLEST

首先选择具有最小剩余度数的顶点。结果通常是具有高负度数同配性的图。在无向情况下,如果存在连通实现,则保证此方法生成一个连通图,而无论是否允许多重边(请参见 Horvát 和 Modes,2021,以及 http://szhorvat.net/pelican/hh-connected-graphs.html)。此方法可用于从其度数构造树。在有向情况下,它倾向于生成弱连通图,但不能保证。

IGRAPH_REALIZE_DEGSEQ_LARGEST

首先选择具有最大剩余度数的顶点。结果通常是具有高正度数同配性的图,并且通常是不连通的。

IGRAPH_REALIZE_DEGSEQ_INDEX

顶点按其索引顺序选择(即,它们在度数向量中的位置)。请注意,对度数向量进行排序并使用 INDEX 方法不等同于上面的 SMALLEST 方法,因为 SMALLEST 使用最小的剩余度数来选择顶点,而不是最小的初始度数。

返回值: 

错误代码

IGRAPH_UNIMPLEMENTED

请求的方法未实现。

IGRAPH_ENOMEM

没有足够的内存来执行操作。

IGRAPH_EINVAL

无效的方法参数,或无效的入度和/或出度向量。度数向量应为非负数,对于有向图,outdegindeg 的长度和总和应匹配。

另请参阅: 

测试图形性而不生成图的函数:igraph_is_graphical();从两个度数序列创建二分图的函数:igraph_realize_bipartite_degree_sequence();生成具有给定度数序列的随机图的函数:igraph_degree_sequence_game();生成每个顶点都具有相同度数的随机图的函数:igraph_k_regular_game();在保留其度数序列的同时随机重新连接图的边的函数:igraph_rewire()

示例 9.11. 文件 examples/simple/igraph_realize_degree_sequence.c

#include <igraph.h>
#include <stdio.h>

int main(void){
    igraph_t g1, g2, g3;
    igraph_integer_t nodes = 500, A = 0, power = 1, m = 1;
    igraph_real_t assortativity;

    igraph_rng_seed(igraph_rng_default(), 42);
    printf("Demonstration of difference in assortativities of graphs with the same degree sequence but different linkages:\n\nInitial graph based on the Barabasi-Albert model with %" IGRAPH_PRId " nodes.\n", nodes);

    /* Graph 1 generated by a randomized graph generator */
    igraph_barabasi_game(&g1, nodes, power, m, NULL, /* outpref */ 0, A, IGRAPH_UNDIRECTED, IGRAPH_BARABASI_PSUMTREE, /* start from */ NULL);

    igraph_vector_int_t degree;
    igraph_vector_int_init(&degree, nodes);
    igraph_degree(&g1, &degree, igraph_vss_all(), IGRAPH_ALL, IGRAPH_NO_LOOPS);

    /* Measuring assortativity of the first graph */
    igraph_assortativity_degree(&g1, &assortativity, IGRAPH_UNDIRECTED);
    printf("Assortativity of initial graph = %g\n\n", assortativity);
    igraph_destroy(&g1);

    /* Graph 2 (with the same degree sequence) generated by selecting vertices with the smallest degree first */
    igraph_realize_degree_sequence(&g2, &degree, NULL, IGRAPH_SIMPLE_SW, IGRAPH_REALIZE_DEGSEQ_SMALLEST);
    igraph_assortativity_degree(&g2, &assortativity, IGRAPH_UNDIRECTED);
    printf("Assortativity after choosing vertices with the smallest degrees first = %g\n\n", assortativity);
    igraph_destroy(&g2);

    /* Graph 3 (with the same degree sequence) generated by selecting vertices with the largest degree first */
    igraph_realize_degree_sequence(&g3, &degree, NULL, IGRAPH_SIMPLE_SW, IGRAPH_REALIZE_DEGSEQ_LARGEST);
    igraph_assortativity_degree(&g3, &assortativity, IGRAPH_UNDIRECTED);
    printf("Assortativity after choosing vertices with the largest degrees first = %g\n", assortativity);
    igraph_destroy(&g3);
    igraph_vector_int_destroy(&degree);

    return 0;
}


1.24. igraph_realize_bipartite_degree_sequence — 生成具有给定二度序列的二分图。

igraph_error_t igraph_realize_bipartite_degree_sequence(
    igraph_t *graph,
    const igraph_vector_int_t *degrees1, const igraph_vector_int_t *degrees2,
    const igraph_edge_type_sw_t allowed_edge_types, const igraph_realize_degseq_t method
);

警告

此函数是实验性的,其签名尚未被视为最终签名。我们保留更改函数签名的权利,而无需更改 igraph 的主要版本。使用它需要您自担风险。

此函数使用类似于 Havel-Hakimi 的构造算法生成具有给定二度序列的二分图。顶点连接的顺序由 method 参数控制。当使用 IGRAPH_REALIZE_DEGSEQ_SMALLEST 方法时,可以确保当且仅当给定的二度序列可能连通时,图才是连通的。

将对图的顶点进行排序,以便具有 degrees1 的顶点排在最前面,其次是 degrees2

参数: 

:

指向未初始化的图对象的指针。

degrees1:

第一个分区的度数序列。

degrees2:

第二个分区的度数序列。

allowed_edge_types:

图中允许的边类型。

IGRAPH_SIMPLE_SW

简单图(即不允许使用多重边)。

IGRAPH_MULTI_SW

允许多重边

method:

控制选择顶点进行连接的顺序。可能的值

IGRAPH_REALIZE_DEGSEQ_SMALLEST

首先从任一分区中选择具有最小剩余度数的顶点。结果通常是具有高负度数同配性的图。如果存在连通图,则保证此方法生成一个连通图。

IGRAPH_REALIZE_DEGSEQ_LARGEST

首先从任一分区中选择具有最大剩余度数的顶点。结果通常是具有高正度数同配性的图,并且通常是不连通的。

IGRAPH_REALIZE_DEGSEQ_INDEX

顶点按其索引顺序选择。

返回值: 

错误代码。

另请参阅: 

测试二分性而不生成图的函数:igraph_is_bigraphical()

1.25. igraph_famous — 通过简单地提供其名称来创建著名图。

igraph_error_t igraph_famous(igraph_t *graph, const char *name);

图的名称可以简单地作为字符串提供。请注意,此函数创建不带任何参数的图,对于带有参数的图,有单独的函数,例如,用于创建完全图的函数:igraph_full()

支持以下图

Bull

公牛图,5 个顶点,5 条边,如果正确绘制,则类似于公牛的头部。

Chvatal

这是最小的无三角形图,它既是 4 色又是 4 正则的。根据 Grunbaum 猜想,对于每个 m>1 和 n>2,都存在一个具有 n 个顶点的 m 正则、m 色图。Chvatal 图是 m=4 和 n=12 的一个示例。它有 24 条边。

Coxeter

一个非哈密顿立方对称图,具有 28 个顶点和 42 条边。

Cubical

立方体的柏拉图图。具有 8 个顶点和 12 条边的凸规则多面体。

Diamond

一个具有 4 个顶点和 5 条边的图,如果正确绘制,则类似于示意性钻石。

Dodecahedral, Dodecahedron

另一个具有 20 个顶点和 30 条边的柏拉图立体。

Folkman

具有最少顶点数 20 和 40 条边的半对称图。半对称图是正则的、边传递的而不是顶点传递的。

Franklin

这是一个嵌入到克莱因瓶中的图可以用六种颜色着色,它是克莱因瓶上 Heawood 猜想的必要性的一个反例。它有 12 个顶点和 18 条边。

Frucht

Frucht 图是最小的立方图,其自同构群仅由恒等元素组成。它有 12 个顶点和 18 条边。

Grotzsch, Groetzsch

Grötzsch 图是一个无三角形图,具有 11 个顶点、20 条边和色数 4。它以德国数学家 Herbert Grötzsch 的名字命名,它的存在证明了在 Grötzsch 定理中平面性的假设是必要的,即每个无三角形平面图都是 3 可着色的。

Heawood

Heawood 图是一个具有 14 个顶点和 21 条边的无向图。该图是立方的,并且该图中的所有循环都有六条或更多边。每个较小的立方图都有较短的循环,因此该图是 6 笼,即周长为 6 的最小立方图。

Herschel

Herschel 图是最小的非哈密顿多面体图。它是 11 个节点上的唯一此类图,并且有 18 条边。

House

房屋图是一个 5 顶点、6 边图,如果正确绘制,则为房屋的示意图,基本上是正方形顶部的三角形。

HouseX

与带有正方形 X 的房屋图相同。5 个顶点和 8 条边。

Icosahedral, Icosahedron

一个具有 12 个顶点和 30 条边的柏拉图立体。

Krackhardt_Kite

一个具有 10 个顶点和 18 条边的社交网络。Krackhardt, D. Assessing the Political Landscape: Structure, Cognition, and Power in Organizations. Admin. Sci. Quart. 35, 342-369, 1990.

Levi

该图是一个 4 弧传递立方图,具有 30 个顶点和 45 条边。

McGee

McGee 图是唯一的 3 正则 7 笼图,具有 24 个顶点和 36 条边。

Meredith

Meredith 图是一个具有 70 个节点和 140 条边的四次图,它是每个 4 正则 4 连通图都是哈密顿图的猜想的反例。

Noperfectmatching

一个具有 16 个顶点和 27 条边的连通图,不包含完美匹配。图中的匹配是一组成对的非相邻边;也就是说,没有两条边共享一个公共顶点。完美匹配是一个覆盖图中所有顶点的匹配。

Nonline

一个图,其连通分量是 9 个图,这些图作为图中顶点诱导的子图的存在使其成为非线图。它有 50 个顶点和 72 条边。

Octahedral, Octahedron

具有 6 个顶点和 12 条边的柏拉图立体。

Petersen

一个具有 10 个顶点和 15 条边的 3 正则图。它是最小的次哈密顿图,也就是说,它是非哈密顿图,但从中移除任何单个顶点都会使其成为哈密顿图。

Robertson

唯一的 (4,5) 笼图,即周长为 5 的 4 正则图。它有 19 个顶点和 38 条边。

Smallestcyclicgroup

一个最小的非平凡图,其自同构群是循环的。它有 9 个顶点和 15 条边。

Tetrahedral, Tetrahedron

具有 4 个顶点和 6 条边的柏拉图立体。

Thomassen

最小的次可追溯图,具有 34 个顶点和 52 条边。次可追溯图不包含哈密顿路径,但从中移除任何单个顶点后,剩余部分始终包含哈密顿路径。包含哈密顿路径的图称为可追溯的。

Tutte

Tait 的哈密顿图猜想指出,每个 3 连通 3 正则平面图都是哈密顿图。此图是一个反例。它有 46 个顶点和 69 条边。

Uniquely3colorable

返回一个 12 顶点、无三角形图,其色数为 3,并且是唯一 3 可着色的。

Walther

一个具有 25 个顶点和 31 条边的恒等图。恒等图具有单个图自同构,即平凡的自同构。

Zachary

20 世纪 70 年代美国大学中 34 名空手道俱乐部成员之间的友谊社交网络。请参见 W. W. Zachary, An information flow model for conflict and fission in small groups, Journal of Anthropological Research 33, 452-473 (1977)。

参数: 

:

指向未初始化的图对象的指针。

name:

字符常量,要创建的图的名称,不区分大小写。

返回值: 

错误代码,如果不存在给定名称的图,则为 IGRAPH_EINVAL

另请参阅: 

用于创建图结构的其他函数:igraph_ring()igraph_kary_tree()igraph_square_lattice()igraph_full()

时间复杂度:O(|V|+|E|),顶点数加上图中的边数。

1.26. igraph_lcf — 从 LCF 表示法创建图。

igraph_error_t igraph_lcf(igraph_t *graph, igraph_integer_t n, ...);

LCF 是 Lederberg-Coxeter-Frucht 的缩写,它是 3 正则哈密顿图的简洁表示法。它由三个参数组成:图中顶点的数量、给出添加到循环骨架的附加边的移位列表,以及另一个整数,给出应执行移位的次数。有关详细信息,请参见 https://mathworld.net.cn/LCFNotation.html

参数: 

:

指向未初始化的图对象的指针。

n:

整数,图中的顶点数。

...:

移位和移位的重复次数,再加上一个额外的 0 来标记参数的结尾。

返回值: 

错误代码。

另请参阅: 

请参阅 igraph_lcf_vector(),了解使用 igraph_vector_t 而不是可变长度参数列表的类似函数;请参阅 igraph_circulant(),了解创建循环图的信息。

时间复杂度:O(|V|+|E|),顶点数加上边数。

示例 9.12. 文件 examples/simple/igraph_lcf.c

#include <igraph.h>

int main(void) {

    igraph_t g, g2;
    igraph_bool_t iso;

    // Franklin graph
    igraph_lcf(&g, 12, 5, -5, 6, 0);
    igraph_famous(&g2, "franklin");

    igraph_isomorphic_vf2(&g, &g2,
                          /*vertex.color1=*/ 0, /*vertex.color2=*/ 0,
                          /*edge.color1=*/ 0, /*edge.color2=*/ 0,
                          &iso, 0, 0, 0, 0, 0);
    if (!iso) {
        printf("Failure: Franklin\n");
        return 1;
    }

    igraph_destroy(&g);
    igraph_destroy(&g2);

    // [3, -2]^4, n=8
    igraph_lcf(&g, 8, 3, -2, 4, 0);

    if (igraph_ecount(&g) != 16) {
        printf("Failure: [3, -2]^4, n=8\n");
        return 1;
    }

    igraph_destroy(&g);

    // [2, -2]^2, n=2
    igraph_lcf(&g, 2, 2, -2, 2, 0);

    if (igraph_ecount(&g) != 1) {
        printf("Failure: [2, -2]^2, n=2\n");
        return 1;
    }

    igraph_destroy(&g);

    // [2]^2, n=2
    igraph_lcf(&g, 2, 2, 2, 0);

    if (igraph_ecount(&g) != 1) {
        printf("Failure: [2]^2, n=2\n");
        return 1;
    }

    igraph_destroy(&g);

    // Regression test for bug #996
    igraph_lcf(&g, 0, 0);
    if (igraph_vcount(&g) != 0 || igraph_ecount(&g) != 0) {
        printf("Failure: regression test for #996\n");
        return 1;
    }

    igraph_destroy(&g);

    return 0;
}


1.27. igraph_lcf_vector — 从 LCF 表示法创建图。

igraph_error_t igraph_lcf_vector(igraph_t *graph, igraph_integer_t n,
                      const igraph_vector_int_t *shifts,
                      igraph_integer_t repeats);

此函数本质上与 igraph_lcf() 相同,只是给出参数的方式不同。有关详细信息,请参见 igraph_lcf()

参数: 

:

指向未初始化的图对象的指针。

n:

给出顶点数的整数常量。

shifts:

给出移位的向量。

repeats:

给出移位重复次数的整数常量。

返回值: 

错误代码。

另请参阅: 

时间复杂度:O(|V|+|E|),顶点数加上边数的线性关系。

1.28. igraph_from_prufer — 从 Prüfer 序列生成树。

igraph_error_t igraph_from_prufer(igraph_t *graph, const igraph_vector_int_t *prufer);

Prüfer 序列是与标记树关联的唯一整数序列。具有 n 个顶点的树可以用 n-2 个整数的序列表示,每个整数介于 0n-1 之间(包括在内)。此函数使用的算法基于 Paulius Micikevičius, Saverio Caminiti, Narsingh Deo: Linear-time Algorithms for Encoding Trees as Sequences of Node Labels

参数: 

:

指向未初始化的图对象的指针。

prufer:

Prüfer 序列

返回值: 

错误代码

IGRAPH_ENOMEM

没有足够的内存来执行操作。

IGRAPH_EINVAL

给出了无效的 Prüfer 序列

另请参阅: 

时间复杂度:O(|V|),其中 |V| 是树中的顶点数。

1.29. igraph_atlas — 从“图集”创建一个小图。

igraph_error_t igraph_atlas(igraph_t *graph, igraph_integer_t number);

图集包含 0 到 7 个顶点之间的所有简单无向未标记图。图的编号作为参数给出。这些图按以下顺序排列

  1. 按顶点数量递增排序;

  2. 对于固定数量的顶点,按边数量递增排序;

  3. 对于固定数量的顶点和边,按度数序列的词典顺序递增排序,例如 111223 < 112222;

  4. 对于固定的度序列,按自同构数递增排序。

数据来自 NetworkX 软件包,参见 https://networkx.cn/

参见 Ronald C. Read 和 Robin J. Wilson 合著的图谱,Oxford University Press,1998 年。

参数: 

:

指向未初始化的图对象的指针。

数字:

要生成的图的编号。必须介于 0 和 1252 之间(包括两者)。顶点数为 0-7 的图分别从编号 0、1、2、4、8、19、53 和 209 开始。

在 0.2 版本中添加。

时间复杂度:O(|V|+|E|),顶点数加上边数。

示例 9.13。 文件 examples/simple/igraph_atlas.c

#include <igraph.h>

int main(void) {

    igraph_t g;

    igraph_atlas(&g, 45);
    igraph_write_graph_edgelist(&g, stdout);
    printf("\n");
    igraph_destroy(&g);

    igraph_atlas(&g, 0);
    igraph_write_graph_edgelist(&g, stdout);
    printf("\n");
    igraph_destroy(&g);

    igraph_atlas(&g, 1252);
    igraph_write_graph_edgelist(&g, stdout);
    printf("\n");
    igraph_destroy(&g);

    return 0;
}


1.30. igraph_de_bruijn — 生成一个德布鲁因图。

igraph_error_t igraph_de_bruijn(igraph_t *graph, igraph_integer_t m, igraph_integer_t n);

德布鲁因图表示字符串之间的关系。使用 m 个字母的字母表,并考虑长度为 n 的字符串。一个顶点对应于每个可能的字符串,并且如果 v 的字符串可以通过删除其第一个字母并在其后附加一个字母来转换为 w 的字符串,则从顶点 v 到顶点 w 存在一条有向边。

请注意,该图将具有 mn 次方个顶点,甚至更多的边,因此您可能不想为 mn 提供太大的数字。

德布鲁因图有一些有趣的属性,请参阅其他来源,例如维基百科了解详细信息。

参数: 

:

指向未初始化的图对象的指针,结果将存储在此处。

m:

整数,字母表中的字母数。

n:

整数,字符串的长度。

返回值: 

错误代码。

另请参阅: 

时间复杂度:O(|V|+|E|),顶点数加上边数。

1.31. igraph_kautz — 生成一个考茨图。

igraph_error_t igraph_kautz(igraph_t *graph, igraph_integer_t m, igraph_integer_t n);

考茨图是一个标记图,顶点用长度为 n+1 的字符串标记,字符串的字母表有 m+1 个字母,并限制字符串中每两个连续的字母必须不同。如果可以通过删除第一个字母并在其后附加一个字母将 v 的字符串转换为 w 的字符串,则从顶点 v 到另一个顶点 w 存在一条有向边。对于字符串长度为 1,新字母不能等于旧字母,因此没有循环。

考茨图有一些有趣的属性,例如,请参阅维基百科了解详细信息。

Vincent Matossian 在 R 中编写了此函数的第一个版本,谢谢。

参数: 

:

指向未初始化的图对象的指针,结果将存储在此处。

m:

整数,m+1 是字母表中的字母数。

n:

整数,n+1 是字符串的长度。

返回值: 

错误代码。

另请参阅: 

时间复杂度:O(|V|* [(m+1)/m]^n +|E|),实际上更像是 O(|V|+|E|)。 |V| 是顶点数,|E| 是边数,mn 是相应的参数。

1.32. igraph_circulant — 创建一个循环图。

igraph_error_t igraph_circulant(igraph_t *graph, igraph_integer_t n, const igraph_vector_int_t *shifts, igraph_bool_t directed);

循环图 G(n, shifts)n 个顶点 v_0, ..., v_(n-1) 组成,使得对于偏移量列表 shifts 中的每个 s_i,对于所有 j,v_j 都连接到 v_((j + s_i) mod n)

该函数可以生成有向图或无向图。它不会生成多重边或自环。

参数: 

:

指向未初始化的图对象的指针,结果将存储在此处。

n:

整数,循环图中的顶点数。

shifts:

整数向量,循环图中的偏移量列表。

有向:

布尔值,是否创建有向图。

返回值: 

错误代码。

另请参阅: 

时间复杂度:O(|V| |shifts|),图中顶点的数量乘以偏移量的数量。

1.33. igraph_generalized_petersen — 创建一个广义彼得森图。

igraph_error_t igraph_generalized_petersen(igraph_t *graph, igraph_integer_t n, igraph_integer_t k);

广义彼得森图 G(n, k) 由形成“外”环形图的 n 个顶点 v_0, ..., v_n 和形成“内”循环图的 n 个附加顶点 u_0, ..., u_n 组成,其中 u_i 连接到 u_(i + k mod n)。此外,所有 v_i 都连接到 u_i

G(n, k)2n 个顶点和 3n 条边。彼得森图本身是 G(5, 2)

参考

M. E. Watkins, 关于泰特着色的一个定理及其在广义彼得森图中的应用,《组合理论杂志》6, 152-164 (1969)。 https://doi.org/10.1016%2FS0021-9800%2869%2980116-X

参数: 

:

指向未初始化的图对象的指针,结果将存储在此处。

n:

整数,n 是内部和外部环/循环图中的顶点数。它必须至少为 3。

k:

整数,k 是循环图的偏移量。它必须为正且小于 n/2

返回值: 

错误代码。

另请参阅: 

对于原始彼得森图,请参见 igraph_famous()

时间复杂度:O(|V|),图中顶点的数量。

1.34. igraph_extended_chordal_ring — 创建一个扩展的弦环。

igraph_error_t igraph_extended_chordal_ring(
    igraph_t *graph, igraph_integer_t nodes, const igraph_matrix_int_t *W,
    igraph_bool_t directed);

扩展的弦环是一个环形图,具有连接其顶点的附加弦。矩阵 W 的每一行 L 指定一组要插入的弦,方式如下:顶点 i 将连接到顶点,该顶点沿环超前 L[(i mod p)] 步,其中 pL 的长度。换句话说,顶点 i 将连接到顶点 (i + L[(i mod p)]) mod nodes。如果以这种方式定义了多条边,这将输出一个非简单图。可以使用 igraph_simplify() 简化结果。

另请参阅 Kotsis, G: 用于并行处理系统的互连拓扑,PARS Mitteilungen 11, 1-6, 1993。igraph 扩展弦环与论文中的弦环不相同。在 igraph 中,矩阵指定要添加哪些边。在论文中,指定了一个条件,该条件应同时在两个端点和反向端点之间成立。

参数: 

:

指向未初始化的图对象的指针,结果将存储在此处。

nodes:

整数常量,图中的顶点数。它必须至少为 3。

W:

指定额外边的矩阵。列数应能整除总顶点数。允许元素为负数。

有向:

图是否应该是有向图。

返回值: 

错误代码。

另请参阅: 

时间复杂度:O(|V|+|E|),顶点数加上边数。

2. 游戏:随机图生成器

2.1. igraph_grg_game — 生成一个几何随机图。
2.2. igraph_barabasi_game — 生成一个基于 Barabási-Albert 模型的图。
2.3. igraph_erdos_renyi_game_gnm — 生成一个具有固定边数的随机 (Erdős-Rényi) 图。
2.4. igraph_erdos_renyi_game_gnp — 生成一个具有固定边概率的随机 (Erdős-Rényi) 图。
2.5. igraph_watts_strogatz_game — Watts-Strogatz 小世界模型。
2.6. igraph_rewire_edges — 以恒定概率重新连接图的边。
2.7. igraph_rewire_directed_edges — 重新连接有向边的选定端点。
2.8. igraph_degree_sequence_game — 生成一个具有给定度序列的随机图。
2.9. igraph_k_regular_game — 生成一个每个顶点都具有相同度的随机图。
2.10. igraph_static_fitness_game — 边概率与节点适应度得分成比例的非增长随机图。
2.11. igraph_static_power_law_game — 生成一个具有预期幂律度分布的非增长随机图。
2.12. igraph_chung_lu_game — 从 Chung-Lu 模型中采样图。
2.13. igraph_forest_fire_game — 根据森林火灾游戏生成网络。
2.14. igraph_rewire — 随机重新连接图,同时保留其度序列。
2.15. igraph_growing_random_game — 生成一个增长的随机图。
2.16. igraph_callaway_traits_game — 模拟具有顶点类型的增长网络。
2.17. igraph_establishment_game — 生成一个具有简单增长模型和顶点类型的图。
2.18. igraph_preference_game — 生成一个具有顶点类型和连接偏好的图。
2.19. igraph_asymmetric_preference_game — 生成一个具有不对称顶点类型和连接偏好的图。
2.20. igraph_recent_degree_game — 基于节点最近获得的入射边数的随机图生成器。
2.21. igraph_barabasi_aging_game — 优先连接,顶点老化。
2.22. igraph_recent_degree_aging_game — 基于最近获得的边数的优先连接,顶点老化。
2.23. igraph_lastcit_game — 模拟引文网络,基于自上次引文以来经过的时间。
2.24. igraph_cited_type_game — 模拟基于顶点类型的引文。
2.25. igraph_citing_cited_type_game — 模拟基于顶点类型的引文网络。
2.26. igraph_sbm_game — 从随机块模型中采样。
2.27. igraph_hsbm_game — 分层随机块模型。
2.28. igraph_hsbm_list_game — 分层随机块模型,更通用的版本。
2.29. igraph_dot_product_game — 生成一个随机点积图。
2.30. igraph_tree_game — 生成一个具有给定节点数的随机树。
2.31. igraph_correlated_game — 生成一个与现有图相关的随机图。
2.32. igraph_correlated_pair_game — 生成成对相关的随机图。
2.33. igraph_simple_interconnected_islands_game — 生成一个由几个互连的岛屿组成的随机图,每个岛屿都是一个随机图。

游戏是随机图生成器,即每次调用它们时都会生成不同的图。 igraph 包括许多此类生成器。一些实现受现实世界机制(例如优先连接)启发的随机图构造过程,而另一些旨在生成具有某些使用属性的图(例如,固定边数、固定度数等)。

2.1. igraph_grg_game — 生成一个几何随机图。

igraph_error_t igraph_grg_game(igraph_t *graph, igraph_integer_t nodes,
                    igraph_real_t radius, igraph_bool_t torus,
                    igraph_vector_t *x, igraph_vector_t *y);

几何随机图的创建方法是在单位正方形上随机放置点(即顶点),然后连接所有欧几里得距离严格小于 radius 的点对。

原始代码由 Keith Briggs 贡献,谢谢 Keith。

参数: 

:

指向未初始化的图对象的指针。

nodes:

图中顶点的数量。

radius:

顶点将在其内连接的半径。

torus:

布尔常量。如果为 true,则将使用周期性边界条件,即假定顶点位于环面上而不是正方形上。

x:

初始化的向量或 NULL。如果不为 NULL,则点的 x 坐标将在此处返回。

y:

初始化的向量或 NULL。如果不为 NULL,则点的 y 坐标将在此处返回。

返回值: 

错误代码。

时间复杂度:TODO,小于 O(|V|^2+|E|)。

示例 9.14。 文件 examples/simple/igraph_grg_game.c

#include <igraph.h>
#include <math.h>

int main(void) {
    igraph_t graph;
    igraph_vector_t x, y;
    igraph_vector_t weights;
    igraph_eit_t eit;
    igraph_real_t avg_dist;

    /* Set random seed for reproducible results */

    igraph_rng_seed(igraph_rng_default(), 42);

    /* Create a random geometric graph and retrieve vertex coordinates */

    igraph_vector_init(&x, 0);
    igraph_vector_init(&y, 0);

    igraph_grg_game(&graph, 200, 0.1, /* torus */ 0, &x, &y);

    /* Compute edge weights as geometric distance */

    igraph_vector_init(&weights, igraph_ecount(&graph));
    igraph_eit_create(&graph, igraph_ess_all(IGRAPH_EDGEORDER_ID), &eit);
    for (; ! IGRAPH_EIT_END(eit); IGRAPH_EIT_NEXT(eit)) {
        igraph_integer_t e = IGRAPH_EIT_GET(eit);
        igraph_integer_t u = IGRAPH_FROM(&graph, e);
        igraph_integer_t v = IGRAPH_TO(&graph, e);

        VECTOR(weights)[e] = hypot(VECTOR(x)[u] - VECTOR(x)[v], VECTOR(y)[u] - VECTOR(y)[v]);
    }
    igraph_eit_destroy(&eit);

    /* Compute average path length */

    igraph_average_path_length_dijkstra(&graph, &avg_dist, NULL, &weights, IGRAPH_UNDIRECTED, /* unconn */ 1);

    printf("Average distance in the geometric graph: %g.\n", avg_dist);

    /* Destroy data structures when no longer needed */

    igraph_vector_destroy(&weights);
    igraph_destroy(&graph);
    igraph_vector_destroy(&x);
    igraph_vector_destroy(&y);

    return 0;
}


2.2. igraph_barabasi_game — 生成一个基于 Barabási-Albert 模型的图。

igraph_error_t igraph_barabasi_game(igraph_t *graph, igraph_integer_t n,
                         igraph_real_t power,
                         igraph_integer_t m,
                         const igraph_vector_int_t *outseq,
                         igraph_bool_t outpref,
                         igraph_real_t A,
                         igraph_bool_t directed,
                         igraph_barabasi_algorithm_t algo,
                         const igraph_t *start_from);

此函数实现优先连接过程的多个变体,包括 Barabási-Albert 和 Price 模型的线性变体和非线性变体。图构造从单个顶点开始,或从 start_from 参数给定的现有图开始。然后一次添加一个新顶点。每个新顶点连接到 m 个现有顶点,以与

d^power + A,

成比例的概率选择它们,其中 d 是现有顶点的入度或总度(由 outpref 参数控制),而 powerA 由参数给出。常数吸引力 A 用于确保入度为零的顶点也可以以非零概率连接到。

Barabási, A.-L. 和 Albert R. 1999。随机网络中尺度的出现,《科学》,286 509--512。 https://doi.org/10.1126/science.286.5439.509

de Solla Price, D. J. 1965。科学论文网络,《科学》,149 510--515。 https://doi.org/10.1126/science.149.3683.510

参数: 

:

一个未初始化的图对象。

n:

图中顶点的数量。

power:

优先连接的幂。在经典优先连接模型中,power=1。其他值允许从非线性优先连接模型中采样。当构造过程中不存在零度顶点时,即当起始图没有孤立顶点且 outpref 设置为 true 时,才允许使用负值。

m:

为每个顶点生成的出边数。仅当 outseqNULL 时使用。

outseq:

给出顶点的(出)度。如果这是常数,则可以是指向 NULL 的指针或空向量。在这种情况下,m 包含常数出度。根据定义,第一个顶点没有出边,因此忽略此向量中的第一个数字。

outpref:

布尔值,如果为 true,则不仅顶点的入度会增加其引用概率,而且出度也会增加其引用概率。即,引用概率由顶点的总度确定。如果生成的图是无向图,则忽略并假定为 true。

A:

顶点的常数吸引力。当 outpref 设置为 false 时,它应为正数,以确保也可以连接到零入度顶点。

有向:

布尔值,是否生成有向图。当设置为 false 时,假定 outpref 为 true

algo:

用于生成网络的算法。可能的值

IGRAPH_BARABASI_BAG

这是以前(0.6 版之前)igraph 中唯一实现的算法。它的工作方式是将顶点的 ID 放入一个包(实际上是多重集),次数与它们的(入)度数相同,再加上一次。然后,从包中抽取所需数量的引用顶点,并进行替换。此方法可能会生成多重边。它仅在 power=1 且 A=1 时有效。

IGRAPH_BARABASI_PSUMTREE

此算法使用部分前缀和树生成图。它不会生成多重边,并且适用于任何 power 和 A 值。

IGRAPH_BARABASI_PSUMTREE_MULTIPLE

此算法还使用部分前缀和树生成图。区别在于,现在允许使用多重边。此方法在 0.6 版之前以 igraph_nonlinear_barabasi_game 的名称实现。

start_from:

可以是 NULL 指针,也可以是图。在前一种情况下,起始配置是大小为 m 的团。在后一种情况下,该图是起始配置。该图必须是非空的,即它必须至少有一个顶点。如果此处提供了图,并且还提供了 outseq 参数,则 outseq 应仅包含不在 start_from 图中的顶点的信息。

返回值: 

错误代码:IGRAPH_EINVALnmAoutseq 参数无效。

时间复杂度:O(|V|+|E|),顶点数加上边数。

示例 9.15。 文件 examples/simple/igraph_barabasi_game.c

#include <igraph.h>

int main(void) {

    igraph_t g;
    igraph_vector_int_t v;
    igraph_vector_int_t v2, v3;

    igraph_barabasi_game(&g, 10, /*power=*/ 1, 2, 0, 0, /*A=*/ 1, 1,
                         IGRAPH_BARABASI_BAG, /*start_from=*/ 0);
    if (igraph_ecount(&g) != 18) {
        return 1;
    }
    if (igraph_vcount(&g) != 10) {
        return 2;
    }
    if (!igraph_is_directed(&g)) {
        return 3;
    }

    igraph_vector_int_init(&v, 0);
    igraph_get_edgelist(&g, &v, 0);
    for (igraph_integer_t i = 0; i < igraph_ecount(&g); i++) {
        if (VECTOR(v)[2 * i] <= VECTOR(v)[2 * i + 1]) {
            return 4;
        }
    }
    igraph_vector_int_destroy(&v);
    igraph_destroy(&g);

    /* out-degree sequence */
    igraph_vector_int_init_int(&v3, 10, 0, 1, 3, 3, 4, 5, 6, 7, 8, 9);

    igraph_barabasi_game(&g, 10, /*power=*/ 1, 0, &v3, 0, /*A=*/ 1, 1,
                         IGRAPH_BARABASI_BAG, /*start_from=*/ 0);
    if (igraph_ecount(&g) != igraph_vector_int_sum(&v3)) {
        return 5;
    }
    igraph_vector_int_init(&v2, 0);
    igraph_degree(&g, &v2, igraph_vss_all(), IGRAPH_OUT, 1);
    for (igraph_integer_t i = 0; i < igraph_vcount(&g); i++) {
        if (VECTOR(v3)[i] != VECTOR(v2)[i]) {
            igraph_vector_int_print(&v3);
            printf("\n");
            igraph_vector_int_print(&v2);
            return 6;
        }
    }
    igraph_vector_int_destroy(&v3);
    igraph_vector_int_destroy(&v2);
    igraph_destroy(&g);

    /* outpref, we cannot really test this quantitatively,
       would need to set random seed */
    igraph_barabasi_game(&g, 10, /*power=*/ 1, 2, 0, 1, /*A=*/ 1, 1,
                         IGRAPH_BARABASI_BAG, /*start_from=*/ 0);
    igraph_vector_int_init(&v, 0);
    igraph_get_edgelist(&g, &v, 0);
    for (igraph_integer_t i = 0; i < igraph_ecount(&g); i++) {
        if (VECTOR(v)[2 * i] <= VECTOR(v)[2 * i + 1]) {
            return 7;
        }
    }
    if (!igraph_is_directed(&g)) {
        return 8;
    }
    igraph_vector_int_destroy(&v);
    igraph_destroy(&g);

    return 0;
}


示例 9.16。 文件 examples/simple/igraph_barabasi_game2.c

#include <igraph.h>
#include <stdio.h>

int main(void) {

    igraph_t g;
    igraph_bool_t simple;

    igraph_barabasi_game(/* graph=    */ &g,
                                         /* n=        */ 100,
                                         /* power=    */ 1.0,
                                         /* m=        */ 2,
                                         /* outseq=   */ 0,
                                         /* outpref=  */ 0,
                                         /* A=        */ 1.0,
                                         /* directed= */ IGRAPH_DIRECTED,
                                         /* algo=     */ IGRAPH_BARABASI_PSUMTREE,
                                         /* start_from= */ 0);

    if (igraph_ecount(&g) != 197) {
        return 1;
    }
    if (igraph_vcount(&g) != 100) {
        return 2;
    }
    igraph_is_simple(&g, &simple);
    if (!simple) {
        return 3;
    }

    igraph_destroy(&g);

    /* ============================== */

    igraph_barabasi_game(/* graph=    */ &g,
                                         /* n=        */ 100,
                                         /* power=    */ 1.0,
                                         /* m=        */ 2,
                                         /* outseq=   */ 0,
                                         /* outpref=  */ 0,
                                         /* A=        */ 1.0,
                                         /* directed= */ IGRAPH_DIRECTED,
                                         /* algo=     */ IGRAPH_BARABASI_PSUMTREE_MULTIPLE,
                                         /* start_from= */ 0);

    if (igraph_ecount(&g) != 198) {
        return 4;
    }
    if (igraph_vcount(&g) != 100) {
        return 5;
    }
    igraph_is_simple(&g, &simple);
    if (simple) {
        return 6;
    }

    igraph_destroy(&g);

    /* ============================== */

    igraph_barabasi_game(/* graph=    */ &g,
                                         /* n=        */ 100,
                                         /* power=    */ 1.0,
                                         /* m=        */ 2,
                                         /* outseq=   */ 0,
                                         /* outpref=  */ 0,
                                         /* A=        */ 1.0,
                                         /* directed= */ IGRAPH_DIRECTED,
                                         /* algo=     */ IGRAPH_BARABASI_BAG,
                                         /* start_from= */ 0);

    if (igraph_ecount(&g) != 198) {
        return 7;
    }
    if (igraph_vcount(&g) != 100) {
        return 8;
    }
    igraph_is_simple(&g, &simple);
    if (simple) {
        return 9;
    }

    igraph_destroy(&g);

    return 0;
}


2.3. igraph_erdos_renyi_game_gnm — 生成一个具有固定边数的随机 (Erdős-Rényi) 图。

igraph_error_t igraph_erdos_renyi_game_gnm(
    igraph_t *graph, igraph_integer_t n, igraph_integer_t m,
    igraph_bool_t directed, igraph_bool_t loops
);

G(n, m) Erdős-Rényi 模型中,会随机统一生成一个具有 n 个顶点和 m 条边的图。

参数: 

:

指向未初始化的图对象的指针。

n:

图中顶点的数量。

m:

图中的边数。

有向:

是否生成有向图。

循环:

是否生成自环。

返回值: 

错误代码:IGRAPH_EINVALnm 参数无效。IGRAPH_ENOMEM:操作的内存不足。

时间复杂度:O(|V|+|E|),顶点数加上图中的边数。

另请参阅: 

使用 igraph_erdos_renyi_game_gnp() 从相关的 G(n, p) 模型中采样,该模型约束了预期边数;使用 igraph_degree_sequence_game() 约束度序列;对于此模型的二分图版本,使用 igraph_bipartite_game_gnm();对于其他常用的随机图模型,使用 igraph_barabasi_game()igraph_growing_random_game()

示例 9.17。 文件 examples/simple/igraph_erdos_renyi_game_gnm.c

#include <igraph.h>

int main(void) {
    igraph_t graph;
    igraph_vector_int_t component_sizes;

    igraph_rng_seed(igraph_rng_default(), 42); /* make program deterministic */

    /* Sample a graph from the Erdős-Rényi G(n,m) model */

    igraph_erdos_renyi_game_gnm(
        &graph, /* n= */ 100, /* m= */ 100,
        IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS
    );

    /* Compute the fraction of vertices contained within the largest connected component */

    igraph_vector_int_init(&component_sizes, 0);
    igraph_connected_components(&graph, NULL, &component_sizes, NULL, IGRAPH_STRONG);

    printf(
        "Fraction of vertices in giant component: %g\n",
        ((double) igraph_vector_int_max(&component_sizes)) / igraph_vcount(&graph)
    );

    /* Clean up data structures when no longer needed */

    igraph_vector_int_destroy(&component_sizes);
    igraph_destroy(&graph);

    return 0;
}


2.4. igraph_erdos_renyi_game_gnp — 生成一个具有固定边概率的随机 (Erdős-Rényi) 图。

igraph_error_t igraph_erdos_renyi_game_gnp(
    igraph_t *graph, igraph_integer_t n, igraph_real_t p,
    igraph_bool_t directed, igraph_bool_t loops
);

G(n, p) Erdős-Rényi 模型中,也称为 Gilbert 模型或伯努利随机图,生成一个具有 n 个顶点的图,使得每个可能的边都以概率 p 独立地包含在图中。这等效于对预期边数施加约束的最大熵随机图模型。设置 p = 1/2 会生成 n 个顶点上的所有图,且概率相同。

图的预期平均度数约为 p n;当需要大约 k 的平均度数时,设置 p = k/n。更准确地说,无自环(无向或有向)图中的预期平均度数为 p(n-1),有自环的无向图中的预期平均度数为 p(n+1),有自环的有向图中的预期平均度数为 p n

参数: 

:

指向未初始化的图对象的指针。

n:

图中顶点的数量。

p:

图中存在边的概率。

有向:

是否生成有向图。

循环:

是否生成自环。

返回值: 

错误代码:IGRAPH_EINVALnp 参数无效。IGRAPH_ENOMEM:操作的内存不足。

时间复杂度:O(|V|+|E|),顶点数加上图中的边数。

另请参阅: 

使用 igraph_erdos_renyi_game_gnm() 生成具有严格固定边数的随机图;使用 igraph_chung_lu_game()igraph_static_fitness_game() 生成具有固定预期度序列的随机图;对于此模型的二分图版本,使用 igraph_bipartite_game_gnm();对于其他常用的随机图模型,使用 igraph_barabasi_game()igraph_growing_random_game()

示例 9.18。 文件 examples/simple/igraph_erdos_renyi_game_gnp.c

#include <igraph.h>

int main(void) {
    igraph_t graph;
    igraph_vector_int_t component_sizes;

    igraph_rng_seed(igraph_rng_default(), 42); /* make program deterministic */

    /* Sample a graph from the Erdős-Rényi G(n,p) model */

    igraph_erdos_renyi_game_gnp(
        &graph, /* n= */ 100, /* p= */ 0.01,
        IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS
    );

    /* Compute the fraction of vertices contained within the largest connected component */

    igraph_vector_int_init(&component_sizes, 0);
    igraph_connected_components(&graph, NULL, &component_sizes, NULL, IGRAPH_STRONG);

    printf(
        "Fraction of vertices in giant component: %g\n",
        ((double) igraph_vector_int_max(&component_sizes)) / igraph_vcount(&graph)
    );

    /* Clean up data structures when no longer needed */

    igraph_vector_int_destroy(&component_sizes);
    igraph_destroy(&graph);

    return 0;
}


2.5. igraph_watts_strogatz_game — Watts-Strogatz 小世界模型。

igraph_error_t igraph_watts_strogatz_game(igraph_t *graph, igraph_integer_t dim,
                               igraph_integer_t size, igraph_integer_t nei,
                               igraph_real_t p, igraph_bool_t loops,
                               igraph_bool_t multiple);

此函数基于 Watts-Strogatz 模型的变体生成具有小世界属性的网络。该网络的获取方式是,首先创建一个周期性无向格,然后以概率 p 重新连接每条边的两个端点,同时避免创建多重边。

此过程与 Watts 和 Strogatz 的原始模型(参见参考资料)的不同之处在于,它重新连接边的两个端点。因此,在 p=1 的限制下,我们获得了 G(n,m) 随机图,其顶点和边的数量与原始格相同。相比之下,原始的 Watts-Strogatz 模型仅重新连接每条边的单个端点,因此即使对于 p=1,网络也不会完全随机。对于 p 的适当选择,两个模型都表现出同时具有短路径长度和高聚类性的属性。

参考

Duncan J Watts 和 Steven H Strogatz: 小世界网络的集体动力学,《自然》393, 440-442, 1998。 https://doi.org/10.1038/30918

参数: 

:

要初始化的图。

dim:

格的维度。

size:

格在每个维度上的大小。

nei:

每个顶点的邻域大小。这与 igraph_connect_neighborhood()order 参数相同。

p:

重新连接概率。一个介于零和一之间的实数(包括零和一)。

循环:

是否生成循环边。

multiple:

是否允许在生成的图中出现多重边。

返回值: 

错误代码。

另请参阅: 

如果需要更大的灵活性,例如不同类型的格,则可以使用 igraph_square_lattice()igraph_connect_neighborhood()igraph_rewire_edges()

时间复杂度:O(|V|*d^o+|E|),|V| 和 |E| 是顶点数和边数,d 是平均度数,o 是 nei 参数。

2.6. igraph_rewire_edges — 以恒定概率重新连接图的边。

igraph_error_t igraph_rewire_edges(igraph_t *graph, igraph_real_t prob,
                        igraph_bool_t loops, igraph_bool_t multiple);

此函数以恒定概率重新连接图的边。更准确地说,每条边的每个端点都以恒定概率 prob 重新连接到均匀随机选择的顶点。

请注意,此函数会修改输入 graph,如果要保留它,请调用 igraph_copy()

参数: 

:

输入图,这将重新连接,它可以是有向图或无向图。

prob:

重新连接概率,一个介于零和一之间的常数(包括零和一)。

循环:

布尔值,是否允许在新图中出现循环边。

multiple:

布尔值,是否允许在新图中出现多重边。

返回值: 

错误代码。

另请参阅: 

对于重新连接,igraph_watts_strogatz_game() 使用此函数。

时间复杂度:O(|V|+|E|)。

2.7. igraph_rewire_directed_edges — 重新连接有向边的选定端点。

igraph_error_t igraph_rewire_directed_edges(igraph_t *graph, igraph_real_t prob,
                                 igraph_bool_t loops, igraph_neimode_t mode);

此函数以恒定概率重新连接图中每个有向边的起点或终点。相应地,图的入度序列或出度序列将被保留。

请注意,此函数会修改输入 graph,如果要保留它,请调用 igraph_copy()

此函数可以在两个顶点之间生成多重边。

参数: 

:

输入图,这将重新连接,它可以是有向图或无向图。如果它是无向图,或者 mode 设置为 IGRAPH_ALL,则将调用 igraph_rewire_edges()

prob:

重新连接概率,一个介于零和一之间的常数(包括零和一)。

循环:

布尔值,是否允许在新图中出现循环边。

模式:

要重新连接的有向边的端点。对于无向图,将忽略此参数。可能的值

IGRAPH_OUT

重新连接每个有向边的终点

IGRAPH_IN

重新连接每个有向边的起点

IGRAPH_ALL

重新连接每条边的两个端点

返回值: 

错误代码。

另请参阅: 

时间复杂度:O(|E|)。

2.8. igraph_degree_sequence_game — 生成一个具有给定度序列的随机图。

igraph_error_t igraph_degree_sequence_game(
        igraph_t *graph,
        const igraph_vector_int_t *out_deg,
        const igraph_vector_int_t *in_deg,
        igraph_degseq_t method);

此函数生成具有指定度序列的随机图。有多种采样方法可用,这些方法尊重不同的约束(简单图或多重图、连通图等),并提供性能和无偏采样之间的不同权衡。有关具有固定度的图的采样技术的概述,请参见 Horvát 和 Modes (2021) 的第 2.1 节。

参考

Fabien Viger 和 Matthieu Latapy: 高效且简单地生成具有指定度序列的随机简单连通图,《复杂网络杂志》4, No. 1, pp. 15–37 (2015)。 https://doi.org/10.1093/comnet/cnv013

Szabolcs Horvát 和 Carl D Modes: 连接性很重要:连通网络的构造和精确随机采样,《物理学杂志:复杂性》2, No. 1, pp. 015008 (2021)。 https://doi.org/10.1088/2632-072x/abced5

参数: 

:

指向未初始化的图对象的指针。

out_deg:

无向图的度序列(如果 in_seqNULL 或长度为零),或者有向图的出度序列(如果 in_deq 的长度不为零)。

in_deg:

它可以是零长度向量或 NULL(如果生成无向图),或者入度序列。

method:

生成图的方法。可能的值

IGRAPH_DEGSEQ_CONFIGURATION

此方法实现了配置模型。对于无向图,它将所有顶点 ID 放入一个包中,使得顶点在包中的重数与其度相同。然后它从包中抽取对,直到包变空。此方法可能会生成环(自环)边和多重边。对于有向图,该算法基本相同,但入度和出度使用两个单独的包。生成无向图的概率与 (\prod_{i<j} A_{ij} ! \prod_i A_{ii} !!)^{-1} 成正比,其中 A 表示邻接矩阵,!! 表示双阶乘。这里假定 A 的对角线上有两倍的自环数。有向图的对应表达式为 (\prod_{i,j} A_{ij}!)^{-1}。因此,所有简单图(邻接矩阵中只有 0 和 1)的概率相同,而非简单图的概率取决于它们的边和自环重数。

IGRAPH_DEGSEQ_CONFIGURATION_SIMPLE

此方法与 IGRAPH_DEGSEQ_CONFIGURATION 相同,但如果生成的图不是简单图,它会拒绝它并重新开始生成。它以相同的概率生成所有简单图。

IGRAPH_DEGSEQ_FAST_HEUR_SIMPLE

此方法生成简单图。它类似于 IGRAPH_DEGSEQ_CONFIGURATION,但尝试避免多重边和环边,如果卡住则从头开始重新生成。它可以生成度序列的所有简单实现,但不保证均匀采样它们。此方法相对较快,如果提供的度序列是可图的,它最终会成功,但迭代次数没有上限。

IGRAPH_DEGSEQ_EDGE_SWITCHING_SIMPLE

这是一个基于度保持边交换的 MCMC 采样器。它生成简单的无向或有向图。它使用 igraph_realize_degree_sequence() 构建初始图,然后使用 igraph_rewire() 重新连接它。

IGRAPH_DEGSEQ_VL

此方法近似均匀地采样无向连通图。它是一种基于度保持边交换的蒙特卡罗方法。如果要生成无向连通图且不关心执行时间,则应优先选择此生成器。igraph 使用 Fabien Viger 的原始实现;有关算法,请参见 https://www-complexnetworks.lip6.fr/~latapy/FV/generation.html 和论文 https://arxiv.org/abs/cs/0502085

返回值: 

错误代码:IGRAPH_ENOMEM:没有足够的内存来执行操作。IGRAPH_EINVAL:无效的方法参数,或无效的入度和/或出度向量。度向量应为非负数,对于无向图,out_deg 的总和应为偶数;对于有向图,out_degin_deg 的长度和总和应匹配。

时间复杂度:O(|V|+|E|),对于 IGRAPH_DEGSEQ_CONFIGURATIONIGRAPH_DEGSEQ_EDGE_SWITCHING_SIMPLE,顶点数加上边数。其他模式的时间复杂度未知。

另请参阅: 

igraph_is_graphical() 确定是否存在具有特定度序列的图;igraph_erdos_renyi_game_gnm() 生成具有固定边数的图,没有任何度约束;igraph_chung_lu_game()igraph_static_fitness_game() 采样具有规定期望度序列(但实际度可变)的随机图;igraph_realize_degree_sequence()igraph_realize_bipartite_degree_sequence() 生成具有给定度的单个(非随机)图。

示例 9.19. 文件 examples/simple/igraph_degree_sequence_game.c

#include <igraph.h>

int main(void) {
    igraph_t g;
    igraph_vector_int_t outdeg, indeg;
    igraph_vector_int_t vec;
    igraph_bool_t is_simple;

    /* Set random seed for reproducibility */
    igraph_rng_seed(igraph_rng_default(), 42);

    igraph_vector_int_init_int(&outdeg, 10, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3);
    igraph_vector_int_init_int(&indeg, 10, 4, 4, 2, 2, 4, 4, 2, 2, 3, 3);
    igraph_vector_int_init(&vec, 0);

    /* checking the configuration model, undirected graphs */
    igraph_degree_sequence_game(&g, &outdeg, 0, IGRAPH_DEGSEQ_CONFIGURATION);
    if (igraph_is_directed(&g) || igraph_vcount(&g) != 10) {
        return 1;
    }
    if (igraph_degree(&g, &vec, igraph_vss_all(), IGRAPH_OUT, 1)) {
        return 2;
    }
    igraph_vector_int_print(&vec);
    igraph_destroy(&g);

    /* checking the Viger-Latapy method, undirected graphs */
    igraph_degree_sequence_game(&g, &outdeg, 0, IGRAPH_DEGSEQ_VL);
    if (igraph_is_directed(&g) || igraph_vcount(&g) != 10) {
        return 3;
    }
    if (igraph_is_simple(&g, &is_simple) || !is_simple) {
        return 4;
    }
    if (igraph_degree(&g, &vec, igraph_vss_all(), IGRAPH_OUT, 0)) {
        return 5;
    }
    igraph_vector_int_print(&vec);
    igraph_destroy(&g);

    /* checking the configuration model, directed graphs */
    igraph_degree_sequence_game(&g, &outdeg, &indeg, IGRAPH_DEGSEQ_CONFIGURATION);
    if (!igraph_is_directed(&g) || igraph_vcount(&g) != 10) {
        return 6;
    }
    if (igraph_degree(&g, &vec, igraph_vss_all(), IGRAPH_OUT, 1)) {
        return 7;
    }
    igraph_vector_int_print(&vec);
    if (igraph_degree(&g, &vec, igraph_vss_all(), IGRAPH_IN, 1)) {
        return 8;
    }
    igraph_vector_int_print(&vec);
    igraph_destroy(&g);

    /* checking the fast heuristic method, undirected graphs */
    igraph_degree_sequence_game(&g, &outdeg, 0, IGRAPH_DEGSEQ_FAST_HEUR_SIMPLE);
    if (igraph_is_directed(&g) || igraph_vcount(&g) != 10) {
        return 9;
    }
    if (igraph_is_simple(&g, &is_simple) || !is_simple) {
        return 10;
    }
    if (igraph_degree(&g, &vec, igraph_vss_all(), IGRAPH_OUT, 1)) {
        return 11;
    }
    igraph_vector_int_print(&vec);
    igraph_destroy(&g);

    /* checking the fast heuristic method, directed graphs */
    igraph_degree_sequence_game(&g, &outdeg, &indeg, IGRAPH_DEGSEQ_FAST_HEUR_SIMPLE);
    if (!igraph_is_directed(&g) || igraph_vcount(&g) != 10) {
        return 12;
    }
    if (igraph_is_simple(&g, &is_simple) || !is_simple) {
        return 13;
    }
    if (igraph_degree(&g, &vec, igraph_vss_all(), IGRAPH_OUT, 1)) {
        return 14;
    }
    igraph_vector_int_print(&vec);
    if (igraph_degree(&g, &vec, igraph_vss_all(), IGRAPH_IN, 1)) {
        return 15;
    }
    igraph_vector_int_print(&vec);
    igraph_destroy(&g);

    igraph_vector_int_destroy(&vec);
    igraph_vector_int_destroy(&outdeg);
    igraph_vector_int_destroy(&indeg);

    return 0;
}


2.9. igraph_k_regular_game — 生成每个顶点具有相同度的随机图。

igraph_error_t igraph_k_regular_game(igraph_t *graph,
                          igraph_integer_t no_of_nodes, igraph_integer_t k,
                          igraph_bool_t directed, igraph_bool_t multiple);

此游戏生成有向或无向随机图,其中顶点的度等于预定义的常数 k。对于无向图,k 和顶点数中至少有一个必须是偶数。

目前,此游戏仅使用 igraph_degree_sequence_game,并使用 IGRAPH_DEGSEQ_CONFIGURATIONIGRAPH_DEGSEQ_FAST_SIMPLE 方法和适当构建的度序列。因此,它不均匀采样:虽然它可以生成具有给定顶点数的所有 k 正则图,但它不会以相同的概率生成每个图。

参数: 

:

指向未初始化的图对象的指针。

no_of_nodes:

生成的图中的节点数。

k:

无向图中每个顶点的度,或有向图中每个顶点的出度和入度。

有向:

生成的图是否为有向图。

multiple:

是否允许在生成的图中出现多重边。

返回值: 

错误代码:IGRAPH_EINVAL:无效参数;例如,负节点数,或无向图的奇数节点数和奇数 k。IGRAPH_ENOMEM:操作没有足够的内存。

时间复杂度:如果 multiple 为 true,则为 O(|V|+|E|),否则未知。

2.10. igraph_static_fitness_game — 具有与节点适应度分数成比例的边概率的非增长随机图。

igraph_error_t igraph_static_fitness_game(igraph_t *graph, igraph_integer_t no_of_edges,
                               const igraph_vector_t *fitness_out, const igraph_vector_t *fitness_in,
                               igraph_bool_t loops, igraph_bool_t multiple);

此游戏生成有向或无向随机图,其中顶点 ij 之间的边的概率取决于所涉及的两个顶点的适应度分数。对于无向图,每个顶点都有一个适应度分数。对于有向图,每个顶点都有一个出适应度和一个入适应度,并且从 ij 的边的概率取决于顶点 i 的出适应度和顶点 j 的入适应度。

生成过程如下。我们从 N 个断开连接的节点开始(其中 N 由适应度向量的长度给出)。然后,我们随机选择两个顶点 ij,概率与它们的适应度成正比。(当生成的图是有向图时,根据出适应度选择 i,并根据入适应度选择 j)。如果顶点尚未连接(或者允许多重边),我们将它们连接起来;否则,我们选择一对新的顶点。重复此操作,直到创建了所需数量的链接。

每个顶点的期望度(虽然不是实际度)将与其适应度成正比。当允许自环和多重边时,这完全正确,否则近似正确。如果您需要生成具有精确度序列的图,请考虑 igraph_degree_sequence_game()igraph_realize_degree_sequence()

要生成具有给定预期度序列的随机无向图,请将 fitness_out(在有向情况下,fitness_out)设置为所需的预期度,并将 no_of_edges 设置为相应的边数,即无向情况下预期度总和的一半,以及有向情况下的出度或入度之和。

此模型类似于更广为人知的 Chung-Lu 模型,在 igraph 中实现为 igraph_chung_lu_game(),但具有严格固定的边数。

此模型通常用于生成静态无标度网络。为此,您必须从所需的幂律分布中绘制适应度分数。或者,您可以使用 igraph_static_power_law_game(),它会使用给定的指数为您生成适应度。

参考

Goh K-I, Kahng B, Kim D: Universal behaviour of load distribution in scale-free networks. Phys Rev Lett 87(27):278701, 2001 https://doi.org/10.1103/PhysRevLett.87.278701.

参数: 

:

指向未初始化的图对象的指针。

fitness_out:

包含每个顶点的适应度的数值向量。对于有向图,这指定了每个顶点的出适应度。

fitness_in:

如果 NULL,则生成的图将是无向图。如果不是 NULL,则此参数指定每个顶点的入适应度。

no_of_edges:

生成的图中的边数。

循环:

是否允许在生成的图中存在环边。

multiple:

是否允许在生成的图中出现多重边。

返回值: 

错误代码:IGRAPH_EINVAL:无效参数 IGRAPH_ENOMEM:操作没有足够的内存。

另请参阅: 

时间复杂度:O(|V| + |E| log |E|)。

2.11. igraph_static_power_law_game — 生成具有预期幂律度分布的非增长随机图。

igraph_error_t igraph_static_power_law_game(igraph_t *graph,
                                 igraph_integer_t no_of_nodes, igraph_integer_t no_of_edges,
                                 igraph_real_t exponent_out, igraph_real_t exponent_in,
                                 igraph_bool_t loops, igraph_bool_t multiple,
                                 igraph_bool_t finite_size_correction);

此游戏生成有向或无向随机图,其中顶点的度遵循具有规定指数的幂律分布。对于有向图,可以分别指定入度和出度分布的指数。

该游戏仅使用 igraph_static_fitness_game() 和适当构造的适应度向量。特别是,顶点 i 的适应度为 i^(-alpha),其中 alpha = 1/(gamma-1)gamma 是参数中给出的指数。

为了消除有向图中入度和出度之间的相关性,入适应度向量将在设置之后和调用 igraph_static_fitness_game() 之前被打乱。

请注意,对于游戏的原始公式中小于 3 的指数,可能会观察到明显的有限尺寸效应。此函数提供了一个参数,允许您通过假设顶点 i 的适应度为 (i+i0-1)^(-alpha) 来消除有限尺寸效应,其中 i0 是一个适当选择的常数,以确保最大度小于边数乘以平均度的平方根;有关更多详细信息,请参见 Chung 和 Lu 的论文以及 Cho 等人的论文。

参考

Goh K-I, Kahng B, Kim D: Universal behaviour of load distribution in scale-free networks. Phys Rev Lett 87(27):278701, 2001. https://doi.org/10.1103/PhysRevLett.87.278701

Chung F and Lu L: Connected components in a random graph with given degree sequences. Annals of Combinatorics 6, 125-145, 2002. https://doi.org/10.1007/PL00012580

Cho YS, Kim JS, Park J, Kahng B, Kim D: Percolation transitions in scale-free networks under the Achlioptas process. Phys Rev Lett 103:135702, 2009. https://doi.org/10.1103/PhysRevLett.103.135702

参数: 

:

指向未初始化的图对象的指针。

no_of_nodes:

生成的图中的节点数。

no_of_edges:

生成的图中的边数。

exponent_out:

度分布的幂律指数。对于有向图,这指定了出度分布的指数。它必须大于或等于 2。如果在此处传递 IGRAPH_INFINITY,您将获得 Erdős-Rényi 随机网络。

exponent_in:

如果为负数,则生成的图将是无向图。如果大于或等于 2,则此参数指定入度分布的指数。如果为非负数但小于 2,则会生成错误。

循环:

是否允许在生成的图中存在环边。

multiple:

是否允许在生成的图中出现多重边。

finite_size_correction:

是否使用 Cho 等人提出的有限尺寸校正。

返回值: 

错误代码:IGRAPH_EINVAL:无效参数 IGRAPH_ENOMEM:操作没有足够的内存。

时间复杂度:O(|V| + |E| log |E|)。

2.12. igraph_chung_lu_game — 从 Chung-Lu 模型中采样图。

igraph_error_t igraph_chung_lu_game(igraph_t *graph,
                                    const igraph_vector_t *out_weights,
                                    const igraph_vector_t *in_weights,
                                    igraph_bool_t loops,
                                    igraph_chung_lu_t variant);

警告

此函数是实验性的,其签名尚未被视为最终签名。我们保留更改函数签名的权利,而无需更改 igraph 的主要版本。使用它需要您自担风险。

Chung-Lu 模型对于生成具有固定预期度的随机图很有用。此函数实现了 Chung 和 Lu 的原始模型,以及一些具有有用属性的其他变体。

在原始 Chung-Lu 模型中,每对顶点 ij 都以独立的概率 p_ij = w_i w_j / S 连接,其中 w_i 是与顶点 i 关联的权重,S = sum_k w_k 是权重的总和。在有向变体中,顶点同时具有出权重 w^out 和入权重 w^in,且总和相等,S = sum_k w^out_k = sum_k w^in_kij 之间的连接概率为 p_ij = w^out_i w^in_j / S

此模型通常用于创建具有固定预期度序列的随机图。顶点 i 的预期度近似等于权重 w_i。具体来说,如果图是有向图且允许自环,则预期出度和入度正是 w^outw^in。如果不允许自环,则预期出度和入度分别为 w^out (S - w^in) / Sw^in (S - w^out) / S。如果图是无向图,则有和没有自环的预期度分别为 w (S + w) / Sw (S - w) / S

原始 Chung-Lu 模型的一个限制是,当某些权重很大时,p_ij 的公式会产生大于 1 的值。Chung 和 Lu 的原始论文排除了使用此类权重。当 p_ij > 1 时,此函数只会发出警告并在 ij 之间创建连接。但是,在这种情况下,预期度将不再以上述方式与权重相关。因此,原始 Chung-Lu 模型无法产生某些(大的)预期度。

为了克服此限制,此函数实现了该模型的其他变体,并修改了顶点 ij 之间的连接概率 p_ij 的表达式。令 q_ij = w_i w_j / S,或者在有向情况下令 q_ij = w^out_i w^in_j / S。所有模型变体在 q_ij 接近于零的稀疏图的限制中变得等效。在原始 Chung-Lu 模型中,可以通过将 variant 设置为 IGRAPH_CHUNG_LU_ORIGINAL 来选择,p_ij = min(q_ij, 1)IGRAPH_CHUNG_LU_MAXENT 变体,有时被称为广义随机图,使用 p_ij = q_ij / (1 + q_ij),并且等效于对预期度有限制的最大熵模型(即指数随机图模型);请参见 Park 和 Newman (2004),第 B 节,设置 exp(-Theta_ij) = w_i w_j / S。 Britton, Deijfen 和 Martin-Löf (2006) 也讨论了此模型。凭借作为度约束最大熵模型的优势,它以相同的概率生成具有相同度序列的图。可以使用 IGRAPH_CHUNG_LU_NR 请求第三个变体,并使用 p_ij = 1 - exp(-q_ij)。这是 Norros 和 Reittu (2006) 引入的多重图模型的底层简单图。有关这三个模型变体的讨论,请参见 Bollobás、Janson、Riordan (2007) 的第 16.4 节,以及 Van Der Hofstad (2013)。

参考

Chung F and Lu L: Connected components in a random graph with given degree sequences. Annals of Combinatorics 6, 125-145 (2002). https://doi.org/10.1007/PL00012580

Miller JC and Hagberg A: Efficient Generation of Networks with Given Expected Degrees (2011). https://doi.org/10.1007/978-3-642-21286-4_10

Park J and Newman MEJ: Statistical mechanics of networks. Physical Review E 70, 066117 (2004). https://doi.org/10.1103/PhysRevE.70.066117

Britton T, Deijfen M, Martin-Löf A: Generating Simple Random Graphs with Prescribed Degree Distribution. J Stat Phys 124, 1377–1397 (2006). https://doi.org/10.1007/s10955-006-9168-x

Norros I and Reittu H: On a conditionally Poissonian graph process. Advances in Applied Probability 38, 59–75 (2006). https://doi.org/10.1239/aap/1143936140

Bollobás B, Janson S, Riordan O: The phase transition in inhomogeneous random graphs. Random Struct Algorithms 31, 3–122 (2007). https://doi.org/10.1002/rsa.20168

Van Der Hofstad R: Critical behavior in inhomogeneous random graphs. Random Struct Algorithms 42, 480–508 (2013). https://doi.org/10.1002/rsa.20450

参数: 

:

指向未初始化的图对象的指针。

out_weights:

非负顶点权重(或出权重)的向量。在稀疏图中,这些值将近似等于预期(出)度。

in_weights:

非负入权重的向量,近似等于稀疏图中的预期入度。可以设置为 NULL,在这种情况下,会生成无向图。

循环:

是否允许创建自环。由于顶点对是独立连接的,因此将此项设置为 false 等效于仅从现有带环 Chung-Lu 图中丢弃自环。

variant:

要从中采样的模型变体,具有顶点 ij 之间的连接概率的不同定义。给定 q_ij = w_i w_j / S,以下公式可用

IGRAPH_CHUNG_LU_ORIGINAL

原始 Chung-Lu 模型,p_ij = min(q_ij, 1)

IGRAPH_CHUNG_LU_MAXENT

具有固定预期度的最大熵模型,p_ij = q_ij / (1 + q_ij)

IGRAPH_CHUNG_LU_NR

Norros 和 Reittu 的模型,p_ij = 1 - exp(-q_ij)

返回值: 

错误代码。

另请参阅: 

igraph_static_fitness_game() 实现了具有对边数有严格约束的类似模型;igraph_degree_sequence_game() 采样具有严格指定度的随机图;igraph_erdos_renyi_game_gnp() 创建在所有顶点对之间具有固定连接概率 p 的随机图。

时间复杂度:O(|E| + |V|),与边数呈线性关系。

2.13. igraph_forest_fire_game — 根据森林火灾游戏生成网络。

igraph_error_t igraph_forest_fire_game(igraph_t *graph, igraph_integer_t nodes,
                            igraph_real_t fw_prob, igraph_real_t bw_factor,
                            igraph_integer_t pambs, igraph_bool_t directed);

森林火灾模型旨在重现以下在真实网络中观察到的网络特征

  • 重尾入度和出度分布。

  • 社区结构。

  • 稠密化幂律。网络随时间推移而稠密化,遵循幂律规则。

  • 收缩直径。网络的直径随时间推移而减小。

网络以以下方式生成。一次添加一个顶点。此顶点连接到(引用)网络中已存在的 ambs 个顶点,这些顶点是均匀随机选择的。现在,对于每个引用的顶点 v,我们执行以下过程

  1. 我们生成两个随机数 xy,它们是几何分布的,均值分别为 p/(1-p)rp(1-rp)。(pfw_probrbw_factor。)新顶点从那些尚未被新顶点引用的顶点中引用 vx 个传出邻居和 y 个传入邻居。如果可用的此类顶点少于 xy 个,那么我们将引用所有这些顶点。

  2. 相同的过程应用于所有新引用的顶点。

另请参见:Jure Leskovec、Jon Kleinberg 和 Christos Faloutsos。随时间推移的图:稠密化定律、收缩直径和可能的解释。 KDD '05:第十一届 ACM SIGKDD 国际知识发现和数据挖掘会议的论文集,177-187, 2005。

但是请注意,已发表论文中的模型版本是不正确的,因为它无法生成作者声称的那种图。更正后的版本可从 https://www.cs.cmu.edu/~jure/pubs/powergrowth-tkdd.pdf 获取,我们的实现基于此版本。

参数: 

:

指向未初始化的图对象的指针。

nodes:

图中顶点的数量。

fw_prob:

前向燃烧概率。

bw_factor:

后向燃烧率。后向燃烧概率计算为 bw_factor * fw_prob

pambs:

大使顶点数。

有向:

是否创建有向图。

返回值: 

错误代码。

时间复杂度:待定。

2.14. igraph_rewire — 在保持度序列的同时随机重连图。

igraph_error_t igraph_rewire(igraph_t *graph, igraph_integer_t n, igraph_rewiring_t mode);

此函数基于原始图生成一个新图,方法是随机“重写”边,同时保持原始图的度序列。重连是“就地”完成的,因此不会分配新图。如果您想保持原始图完整,请事先使用 igraph_copy()。所有图属性都将丢失。

重连是通过度保持边交换进行的:统一随机选择两个任意边,即 (a, b)(c, d),然后如果这保留了 mode 指定的约束,则将它们替换为 (a, d)(b, c)

参数: 

:

要重连的图对象。

n:

要执行的重连试验次数。

模式:

要使用的重连算法。它可以是以下标志之一

IGRAPH_REWIRING_SIMPLE

此方法不会创建或销毁自环,也不会创建多重边。

IGRAPH_REWIRING_SIMPLE_LOOPS

此方法允许创建或销毁自环。自环是通过交换具有单个公共端点的边来创建的。

返回值: 

错误代码

IGRAPH_EINVMODE

无效的重连模式。

IGRAPH_ENOMEM

临时数据的内存不足。

时间复杂度:待定。

2.15. igraph_growing_random_game — 生成一个增长的随机图。

igraph_error_t igraph_growing_random_game(igraph_t *graph, igraph_integer_t n,
                               igraph_integer_t m, igraph_bool_t directed,
                               igraph_bool_t citation);

此函数模拟一个增长的随机图。我们从一个顶点开始。在每个步骤中,都会添加一个新顶点,并且还会添加一些新边。众所周知,这些图与标准(非增长)随机图不同。

参数: 

:

未初始化的图对象。

n:

图中顶点的数量。

m:

在时间步长中(即添加顶点后)要添加的边数。

有向:

布尔值,是否生成有向图。

citation:

布尔值,如果 true,则边始终源自最近添加的顶点,并连接到之前的顶点。

返回值: 

错误代码:IGRAPH_EINVAL:无效的 nm 参数。

时间复杂度:O(|V|+|E|),顶点数加上边数。

2.16. igraph_callaway_traits_game — 模拟具有顶点类型的增长网络。

igraph_error_t igraph_callaway_traits_game(igraph_t *graph, igraph_integer_t nodes,
                                igraph_integer_t types, igraph_integer_t edges_per_step,
                                const igraph_vector_t *type_dist,
                                const igraph_matrix_t *pref_matrix,
                                igraph_bool_t directed,
                                igraph_vector_int_t *node_type_vec);

不同类型的顶点更喜欢以给定的概率连接其他类型的顶点。

模拟过程如下:在每个离散时间步长中,都会向图中添加一个新顶点。此顶点的类型是基于 type_dist 生成的。然后从图中统一随机选择两个顶点。它们连接的可能性取决于这些顶点的类型,并从 pref_matrix 中获取。然后选择另外两个顶点,并且在每个时间步长中重复 edges_per_step 次。

参考

D. S. Callaway、J. E. Hopcroft、J. M. Kleinberg、M. E. J. Newman 和 S. H. Strogatz,随机增长的图真的是随机的吗? Phys. Rev. E 64, 041902 (2001)。 https://doi.org/10.1103/PhysRevE.64.041902

参数: 

:

指向未初始化图的指针。

nodes:

图中的节点数。

types:

节点类型数。

edges_per_step:

每个时间步长中尝试的连接数。

type_dist:

给出顶点类型分布的向量。如果 NULL,则假定分布是均匀的。

pref_matrix:

给出顶点类型连接概率的矩阵。

有向:

是否生成有向图。

node_type_vec:

已初始化的向量或 NULL。如果不是 NULL,则每个节点的类型将存储在此处。

返回值: 

错误代码。

在 0.2 版本中添加。

时间复杂度:O(|V|*k*log(|V|)),|V| 是顶点数,k 是 edges_per_step

2.17. igraph_establishment_game — 生成具有简单增长模型的顶点类型的图。

igraph_error_t igraph_establishment_game(igraph_t *graph, igraph_integer_t nodes,
                              igraph_integer_t types, igraph_integer_t k,
                              const igraph_vector_t *type_dist,
                              const igraph_matrix_t *pref_matrix,
                              igraph_bool_t directed,
                              igraph_vector_int_t *node_type_vec);

模拟过程如下:在每个时间步长添加一个顶点。此新顶点尝试连接到图中的 k 个顶点。这种连接实现的可能性取决于所涉及的顶点的类型。

参数: 

:

指向未初始化图的指针。

nodes:

图中顶点的数量。

types:

顶点类型的数量。

k:

每个时间步长中尝试的连接数。

type_dist:

给出顶点类型分布的向量。如果 NULL,则假定分布是均匀的。

pref_matrix:

给出不同顶点类型连接概率的矩阵。

有向:

是否生成有向图。

node_type_vec:

已初始化的向量或 NULL。如果不是 NULL,则每个节点的类型将存储在此处。

返回值: 

错误代码。

在 0.2 版本中添加。

时间复杂度:O(|V|*k*log(|V|)),|V| 是顶点数,k 是 k 参数。

2.18. igraph_preference_game — 生成具有顶点类型和连接首选项的图。

igraph_error_t igraph_preference_game(igraph_t *graph, igraph_integer_t nodes,
                           igraph_integer_t types,
                           const igraph_vector_t *type_dist,
                           igraph_bool_t fixed_sizes,
                           const igraph_matrix_t *pref_matrix,
                           igraph_vector_int_t *node_type_vec,
                           igraph_bool_t directed,
                           igraph_bool_t loops);

这实际上是 igraph_establishment_game() 的非增长变体。生成给定数量的顶点。根据给定的类型概率将每个顶点分配给一个顶点类型。最后,评估每个顶点对,并以取决于所涉及的顶点的类型的概率在它们之间创建边。

换句话说,此函数根据块模型生成图。顶点被分成组(或块),并且两个顶点连接的可能性仅取决于它们的组。

参数: 

:

指向未初始化图的指针。

nodes:

图中顶点的数量。

types:

顶点类型的数量。

type_dist:

给出顶点类型分布的向量。如果 NULL,则所有顶点类型将具有相等的概率。另请参见 fixed_sizes 参数。

fixed_sizes:

布尔值。如果为 true,则具有给定顶点类型的顶点数是固定的,并且 type_dist 参数给出了每个顶点类型的这些数字。如果为 true 且 type_distNULL,则该函数尝试使顶点组大小相同。如果不可能,则某些组将有一个额外的顶点。

pref_matrix:

给出不同顶点类型连接概率的矩阵。如果请求的图是无向图,则这应该是对称的。

node_type_vec:

将在其中存储各个生成的顶点类型的向量。如果 NULL,则不会保存顶点类型。

有向:

是否生成有向图。如果请求无向图,则仅考虑首选项矩阵的左下三角。

循环:

是否允许环边。

返回值: 

错误代码。

在版本 0.3 中添加。

时间复杂度:O(|V|+|E|),顶点数加上图中的边数。

另请参阅: 

2.19. igraph_asymmetric_preference_game — 生成具有不对称顶点类型和连接首选项的图。

igraph_error_t igraph_asymmetric_preference_game(igraph_t *graph, igraph_integer_t nodes,
                                      igraph_integer_t no_out_types,
                                      igraph_integer_t no_in_types,
                                      const igraph_matrix_t *type_dist_matrix,
                                      const igraph_matrix_t *pref_matrix,
                                      igraph_vector_int_t *node_type_out_vec,
                                      igraph_vector_int_t *node_type_in_vec,
                                      igraph_bool_t loops);

这是 igraph_preference_game() 的不对称变体。生成给定数量的顶点。根据给定的联合类型概率,将每个顶点分配给“传出”和“传入”顶点类型。最后,评估每对顶点,并以取决于源顶点的“传出”类型和目标顶点的“传入”类型的概率在它们之间创建一条有向边。

参数: 

:

指向未初始化图的指针。

nodes:

图中顶点的数量。

no_out_types:

顶点传出类型的数量。

no_in_types:

顶点传入类型的数量。

type_dist_matrix:

大小为 out_types * in_types 的矩阵,给出顶点类型的联合分布。如果 NULL,则传入和传出顶点类型是独立的且均匀分布的。

pref_matrix:

首选项矩阵

大小为 out_types * in_types 的矩阵,给出不同顶点类型的连接概率。:

node_type_out_vec

将在其中存储各个生成的“传出”顶点类型的向量。如果 NULL,则不会保存顶点类型。:

node_type_in_vec

循环:

是否允许环边。

返回值: 

错误代码。

在版本 0.3 中添加。

时间复杂度:O(|V|+|E|),顶点数加上图中的边数。

另请参阅: 

2.20. igraph_recent_degree_game — 基于节点最近获得的入射边数的随机图生成器。

igraph_error_t igraph_recent_degree_game(igraph_t *graph, igraph_integer_t nodes,
                              igraph_real_t power,
                              igraph_integer_t time_window,
                              igraph_integer_t m,
                              const igraph_vector_int_t *outseq,
                              igraph_bool_t outpref,
                              igraph_real_t zero_appeal,
                              igraph_bool_t directed);

参数: 

:

指向未初始化的图对象的指针。

nodes:

图中的顶点数,与时间步数相同。

power:

指数是指节点获得新边的概率与它最近(在最近的 window 个时间步内)获得的边的数量成正比,其比例为 power

time_window:

整数常量,用于计算最近边数量的时间窗口大小。

m:

整数常量,如果 outseq 参数为空指针或零长度向量,则每个时间步添加的边数。

outseq:

每个时间步要添加的边数。如果此参数是空指针或零长度向量,则忽略此参数。在这种情况下,将使用常量 m 参数。

outpref:

布尔常量,如果为 true,则由顶点发起的边也计为最近的入射边。对于大多数应用来说,将其设置为 false 是合理的。

zero_appeal:

常量,表示最近未获得任何边的顶点的吸引力。

有向:

布尔常量,是否生成有向图。

返回值: 

错误代码。

时间复杂度:O(|V|*log(|V|)+|E|),|V| 是顶点的数量,|E| 是图中的边数。

2.21. igraph_barabasi_aging_game — 带有顶点老化功能的优先连接模型。

igraph_error_t igraph_barabasi_aging_game(igraph_t *graph,
                               igraph_integer_t nodes,
                               igraph_integer_t m,
                               const igraph_vector_int_t *outseq,
                               igraph_bool_t outpref,
                               igraph_real_t pa_exp,
                               igraph_real_t aging_exp,
                               igraph_integer_t aging_bins,
                               igraph_real_t zero_deg_appeal,
                               igraph_real_t zero_age_appeal,
                               igraph_real_t deg_coef,
                               igraph_real_t age_coef,
                               igraph_bool_t directed);

此模型从一个顶点开始(如果 nodes > 0)。在每个步骤中,都会添加一个新节点,并将其连接到 m 个现有节点。选择要连接的现有节点的概率取决于它们的(入)度(k)和年龄(l)。与度相关的部分是 deg_coef * k^pa_exp + zero_deg_appeal,而与年龄相关的部分是 age_coef * l^aging_exp + zero_age_appeal,将它们相乘得到最终权重。

年龄 l 基于网络中的顶点数量和 aging_bins 参数:在每个 floor(nodes / aging_bins) + 1 时间步后,节点的年龄增加 1。

参数: 

:

指向未初始化的图对象的指针。

nodes:

图中顶点的数量。

m:

每个时间步要添加的边数。如果 outseq 是非零长度向量,则忽略此参数。

outseq:

每个时间步要添加的边数。如果它是 NULL 或零长度向量,则会被忽略,并使用 m 参数代替。

outpref:

布尔常量,顶点发起的边是否影响获得新边的概率。

pa_exp:

优先连接的指数,通常是一个小的正数,值为 1 表示经典的线性优先连接。

aging_exp:

老化的指数,通常是一个负数。

aging_bins:

整数常量,要使用的年龄箱的数量。

zero_deg_appeal:

零度顶点的吸引力的与度相关的部分。

zero_age_appeal:

零年龄顶点的吸引力的与年龄相关的部分。此参数通常为零。

deg_coef:

度的系数。

age_coef:

年龄的系数。

有向:

布尔常量,是否生成有向图。

返回值: 

错误代码。

时间复杂度:O((|V|+|V|/aging_bins)*log(|V|)+|E|)。|V| 是顶点的数量,|E| 是边的数量。

2.22. igraph_recent_degree_aging_game — 基于最近获得的边数和顶点老化的优先连接模型。

igraph_error_t igraph_recent_degree_aging_game(igraph_t *graph,
                                    igraph_integer_t nodes,
                                    igraph_integer_t m,
                                    const igraph_vector_int_t *outseq,
                                    igraph_bool_t outpref,
                                    igraph_real_t pa_exp,
                                    igraph_real_t aging_exp,
                                    igraph_integer_t aging_bins,
                                    igraph_integer_t time_window,
                                    igraph_real_t zero_appeal,
                                    igraph_bool_t directed);

此模型与 igraph_barabasi_aging_game() 非常相似,不同之处在于,计算的是最近 time_window 个时间步中获得的边数,而不是入射边的总数。

吸引力的与度相关的部分由 k 的 pa_exp 次方加上 zero_appeal 给出;与年龄相关的部分是 l 的 aging_exp 次方。k 是最近 time_window 个时间步中获得的边数,l 是顶点的年龄。

参数: 

:

指向未初始化的图对象的指针。

nodes:

图中顶点的数量。

m:

每个时间步要添加的边数。如果 outseq 参数不是空向量或零长度向量,则忽略此参数。

outseq:

向量,给出每个时间步要添加的边数。如果它是空指针或零长度向量,则忽略此参数,并使用 m 参数。

outpref:

布尔常量,如果为 true,则顶点发起的边也会被计算在内。通常为 false。

pa_exp:

优先连接的指数。

aging_exp:

老化的指数,通常为负数:旧顶点获得边的概率较低。

aging_bins:

整数常量,要使用的年龄箱的数量。

time_window:

用于计算顶点的入射边数量的时间窗口。

zero_appeal:

零度顶点的吸引力的与度相关的部分。

有向:

布尔常量,是否创建有向图。

返回值: 

错误代码。

时间复杂度:O((|V|+|V|/aging_bins)*log(|V|)+|E|)。|V| 是顶点的数量,|E| 是边的数量。

2.23. igraph_lastcit_game — 模拟引文网络,基于自上次引文以来经过的时间。

igraph_error_t igraph_lastcit_game(igraph_t *graph,
                        igraph_integer_t nodes, igraph_integer_t edges_per_node,
                        igraph_integer_t agebins,
                        const igraph_vector_t *preference,
                        igraph_bool_t directed);

这是一个非常特殊的随机图生成器,它模拟了一个演化图。在每个时间步中,都会向网络添加一个顶点,并且它引用许多其他顶点(由 edges_per_step 参数指定)。引用的顶点的选择基于它们上次被引用的时间。时间通过顶点的添加来衡量,并将其划分为 agebins 个箱。因此,如果当前时间步为 t 并且对给定 i 顶点的最后一次引用是在时间步 t0 中进行的,则计算 (t-t0) / binwidth,其中 binwidth 是 nodes/agebins + 1,在最后一个表达式中,“/”表示整数除法,因此省略小数部分。

preference 参数指定了引文滞后的偏好,即它的第一个元素包含最近引用的顶点的吸引力,依此类推。最后一个元素很特殊,它包含从未被引用的顶点的吸引力。此元素应大于零。

请注意,如果 edges_per_step 大于 1,则此函数会生成具有多条边的网络,请在结果上调用 igraph_simplify() 以摆脱这些边。

参数: 

:

指向未初始化的图对象的指针,结果将存储在此处。

nodes:

网络中的顶点数量。

edges_per_node:

每个时间步要添加的边数。

agebins:

要使用的年龄箱的数量。

preference:

指向长度为 agebins + 1 的已初始化向量的指针。它包含各种年龄箱的“吸引力”,最后一个元素是从未被引用的顶点的吸引力,并且它应该大于零。最好在此向量中包含所有正值。偏好不能为负。

有向:

布尔常量,是否创建有向网络。

返回值: 

错误代码。

另请参阅: 

时间复杂度:O(|V|*a+|E|*log|V|),|V| 是顶点的数量,|E| 是边的总数,a 是 agebins 参数。

2.24. igraph_cited_type_game — 模拟基于顶点类型的引文。

igraph_error_t igraph_cited_type_game(igraph_t *graph, igraph_integer_t nodes,
                           const igraph_vector_int_t *types,
                           const igraph_vector_t *pref,
                           igraph_integer_t edges_per_step,
                           igraph_bool_t directed);

基于某些顶点类别创建网络的函数。此函数创建一个引文网络:在每个步骤中,都会添加一个顶点和 edges_per_step 个引用边。具有不同类别的节点可能具有不同的被引用概率,如 pref 向量所示。

请注意,如果 edges_per_step 大于 1,则此函数可能会生成具有多条边的网络。您可能需要在结果上调用 igraph_simplify() 以删除多条边。

参数: 

:

指向未初始化的图对象的指针。

nodes:

网络中的顶点数量。

types:

数值向量,给出顶点的类别,因此它应包含 nodes 个非负整数。类型从零开始编号。

pref:

向量中不同顶点类别的吸引力。它的长度应为 types 中的最大元素加一(类型从零开始编号)。

edges_per_step:

整数常量,每个时间步要添加的边数。

有向:

布尔常量,是否创建有向网络。

返回值: 

错误代码。

另请参阅: 

igraph_citing_cited_type_game() 以获得更通用的模型。

时间复杂度:O((|V|+|E|)log|V|),|V| 和 |E| 分别是顶点和边的数量。

2.25. igraph_citing_cited_type_game — 模拟基于顶点类型的引文网络。

igraph_error_t igraph_citing_cited_type_game(igraph_t *graph, igraph_integer_t nodes,
                                  const igraph_vector_int_t *types,
                                  const igraph_matrix_t *pref,
                                  igraph_integer_t edges_per_step,
                                  igraph_bool_t directed);

此模型与 igraph_cited_type_game() 类似,但此处也考虑了引用顶点的类别。

此处模拟了一个演化的引文网络,在每个时间步中都会添加一个顶点及其 edges_per_step 个引用。给定顶点被新顶点引用的概率取决于引用顶点和被引用顶点的类别,并在 pref 矩阵中给出。引用顶点的类别对应于此矩阵的行,被引用顶点的类别对应于此矩阵的列。即,第 i 行和第 j 列中的元素给出了类别为 i 的顶点引用 j 顶点的概率。

请注意,如果 edges_per_step 大于 1,则此函数可能会生成具有多条边的网络。您可能需要在结果上调用 igraph_simplify() 以删除多条边。

参数: 

:

指向未初始化的图对象的指针。

nodes:

网络中的顶点数量。

types:

长度为 nodes 的数值向量,包含顶点的类别。类别从零开始编号。

pref:

偏好矩阵,需要一个方阵,行数和列数都应该是 types 中的最大元素加一(类型从零开始编号)。

edges_per_step:

整数常量,每个时间步要添加的边数。

有向:

布尔常量,是否创建有向网络。

返回值: 

错误代码。

时间复杂度:O((|V|+|E|)log|V|),|V| 和 |E| 分别是顶点和边的数量。

2.26. igraph_sbm_game — 从随机块模型中采样。

igraph_error_t igraph_sbm_game(igraph_t *graph, igraph_integer_t n,
                    const igraph_matrix_t *pref_matrix,
                    const igraph_vector_int_t *block_sizes,
                    igraph_bool_t directed, igraph_bool_t loops);

此函数通过(等效于)对每个可能的边进行伯努利试验,以伯努利率矩阵 pref_matrix 给出的概率,从随机块模型中采样图。请参阅 Faust, K., & Wasserman, S. (1992a). Blockmodels: Interpretation and evaluation. Social Networks, 14, 5-–61.

生成的图中顶点 ID 的顺序对应于 block_sizes 参数。

参数: 

:

输出图。这应该是指向未初始化图的指针。

n:

顶点数。

pref_matrix:

矩阵,给出伯努利率。这是一个 KxK 矩阵,其中 K 是组数。从组 i 和 j 中的顶点之间创建边的概率由元素 (i,j) 给出。

block_sizes:

整数向量,给出每组中的顶点数量。

有向:

布尔值,是否创建有向图。如果此参数为 false,则 pref_matrix 必须是对称的。

循环:

布尔值,是否创建自环。

返回值: 

错误代码。

时间复杂度:O(|V|+|E|+K^2),其中 |V| 是顶点的数量,|E| 是边的数量,K 是组数。

另请参阅: 

igraph_erdos_renyi_game_gnp() 以获得简单的伯努利图。

2.27. igraph_hsbm_game — 分层随机块模型。

igraph_error_t igraph_hsbm_game(igraph_t *graph, igraph_integer_t n,
                     igraph_integer_t m, const igraph_vector_t *rho,
                     const igraph_matrix_t *C, igraph_real_t p);

该函数根据分层随机块模型生成一个随机图。

参数: 

:

生成的图存储在此处。

n:

图中顶点的数量。

m:

每个块的顶点数量。n/m 必须是整数。

rho:

每个集群中的顶点比例,在块内。总和必须为 1,并且对于 rho 的所有元素,rho * m 必须是整数。

C:

一个方形对称数值矩阵,块内集群的伯努利率。它的大小必须与 rho 向量的大小匹配。

p:

不同块中顶点之间连接的伯努利率。

返回值: 

错误代码。

另请参阅: 

igraph_sbm_game() 以获得经典随机块模型,igraph_hsbm_list_game() 以获得更通用的版本。

2.28. igraph_hsbm_list_game — 分层随机块模型,更通用的版本。

igraph_error_t igraph_hsbm_list_game(igraph_t *graph, igraph_integer_t n,
                          const igraph_vector_int_t *mlist,
                          const igraph_vector_list_t *rholist,
                          const igraph_matrix_list_t *Clist,
                          igraph_real_t p);

该函数根据分层随机块模型生成一个随机图。

参数: 

:

生成的图存储在此处。

n:

图中顶点的数量。

mlist:

块大小的整数向量。

rholist:

rho 向量的列表(igraph_vector_t 对象),每个块一个。

Clist:

方形矩阵的列表(igraph_matrix_t 对象),每个块一个,指定块内连接的伯努利率。

p:

不同块中顶点之间连接的伯努利率。

返回值: 

错误代码。

另请参阅: 

igraph_sbm_game() 以获得经典随机块模型,igraph_hsbm_game() 以获得更简单的通用版本。

2.29. igraph_dot_product_game — 生成随机点积图。

igraph_error_t igraph_dot_product_game(igraph_t *graph, const igraph_matrix_t *vecs,
                            igraph_bool_t directed);

在此模型中,每个顶点都由一个潜在位置向量表示。两个顶点之间边的概率由其潜在位置向量的点积给出。

另请参阅 Christine Leigh Myers Nickel: Random dot product graphs, a model for social networks. Dissertation, Johns Hopkins University, Maryland, USA, 2006.

参数: 

:

输出图存储在此处。

vecs:

一个矩阵,其中每个潜在位置向量都是一列。潜在位置向量的点积应位于 [0,1] 区间内,否则会给出警告。对于负点积,不添加边;大于 1 的点积始终会添加边。

有向:

生成的图应该是有向的吗?

返回值: 

错误代码。

时间复杂度:O(n*n*m),其中 n 是顶点的数量,m 是潜在向量的长度。

另请参阅: 

2.30. igraph_tree_game — 生成具有给定节点数量的随机树。

igraph_error_t igraph_tree_game(igraph_t *graph, igraph_integer_t n, igraph_bool_t directed, igraph_random_tree_t method);

此函数从标记树的集合中均匀地采样,即它以相同的概率生成每个标记树。

请注意,对于 n=0,将返回空图,igraph_is_tree() 不认为它是树。

参数: 

:

指向未初始化的图对象的指针。

n:

树中的节点数量。

有向:

是否创建有向树。边从根开始定向。

method:

用于生成树的算法。可能的值

IGRAPH_RANDOM_TREE_PRUFER

此算法均匀地采样 Prüfer 序列,然后将其转换为树。目前不支持有向树。

IGRAPH_RANDOM_LERW

此算法有效地在完整图上执行循环擦除随机游走,以均匀地采样其生成树(Wilson 算法)。

返回值: 

错误代码:IGRAPH_ENOMEM:没有足够的内存来执行操作。IGRAPH_EINVAL:无效的树大小

另请参阅: 

2.31. igraph_correlated_game — 生成与现有图相关的随机图。

igraph_error_t igraph_correlated_game(const igraph_t *old_graph, igraph_t *new_graph,
                           igraph_real_t corr, igraph_real_t p,
                           const igraph_vector_int_t *permutation);

通过扰动给定简单图的邻接矩阵并打乱其顶点来采样新图。

参数: 

old_graph:

原始图,它必须是简单的。

new_graph:

新图将存储在此处。

corr:

单位区间 [0,1] 中的值,原始图和生成的图的邻接矩阵之间的目标 Pearson 相关性(邻接矩阵用作向量)。

p:

两个顶点之间边的概率。它必须在开区间 (0,1) 中。通常是 old_graph 的密度。

permutation:

要应用于生成的图的顶点的排列。它也可以是一个空指针,在这种情况下,顶点将不会被排列。

返回值: 

错误代码

另请参阅: 

igraph_correlated_pair_game() 用于一次生成一对相关的随机图。

2.32. igraph_correlated_pair_game — 生成相关随机图对。

igraph_error_t igraph_correlated_pair_game(igraph_t *graph1, igraph_t *graph2,
                                igraph_integer_t n, igraph_real_t corr, igraph_real_t p,
                                igraph_bool_t directed,
                                const igraph_vector_int_t *permutation);

采样两个随机图,具有给定的相关性。

参数: 

graph1:

第一个图将存储在此处。

graph2:

第二个图将存储在此处。

n:

两个图中的顶点数量。

corr:

单位区间中的标量,原始图和生成的图的邻接矩阵之间的目标 Pearson 相关性(邻接矩阵用作向量)。

p:

一个数值标量,两个顶点之间边的概率,它必须在开区间 (0,1) 中。

有向:

是否生成有向图。

permutation:

要应用于第二个图的顶点的排列。它也可以是一个空指针,在这种情况下,顶点将不会被排列。

返回值: 

错误代码

另请参阅: 

igraph_correlated_game() 用于生成与给定图相关的图对。

2.33. igraph_simple_interconnected_islands_game — 生成由几个相互连接的岛屿组成的随机图,每个岛屿都是一个随机图。

igraph_error_t igraph_simple_interconnected_islands_game(
        igraph_t *graph,
        igraph_integer_t islands_n,
        igraph_integer_t islands_size,
        igraph_real_t islands_pin,
        igraph_integer_t n_inter);

所有岛屿的大小都相同。在一个岛屿内,每条边都以相同的概率生成。然后为每对无序岛屿生成固定数量的附加边以连接它们。生成的图保证是简单的。

参数: 

:

指向未初始化的图对象的指针。

islands_n:

图中的岛屿数量。

islands_size:

图中岛屿的大小。

islands_pin:

在岛屿内创建每个可能的边的概率。

n_inter:

在两个岛屿之间创建的边数。它可能大于 islands_size 的平方,但在这种情况下,它被假定为 islands_size 的平方。

返回值: 

错误代码:IGRAPH_EINVAL:无效参数 IGRAPH_ENOMEM:操作没有足够的内存。

时间复杂度:O(|V|+|E|),顶点数加上图中的边数。

3. 已弃用的函数

3.1. igraph_erdos_renyi_game — 生成随机(Erdős-Rényi)图。

igraph_error_t igraph_erdos_renyi_game(igraph_t *graph, igraph_erdos_renyi_t type,
                            igraph_integer_t n, igraph_real_t p_or_m,
                            igraph_bool_t directed, igraph_bool_t loops);

此函数已弃用;请改用 igraph_erdos_renyi_game_gnm()igraph_erdos_renyi_game_gnp()

参数: 

:

指向未初始化的图对象的指针。

type:

随机图的类型,可能的值

IGRAPH_ERDOS_RENYI_GNM

G(n,m) 图,在具有 n 个顶点的图中均匀随机地选择 m 条边。

IGRAPH_ERDOS_RENYI_GNP

G(n,p) 图,每个可能的边都以概率 p 包含在图中。

n:

图中顶点的数量。

p_or_m:

这是 G(n,p) 图的 p 参数和 G(n,m) 图的 m 参数。

有向:

是否生成有向图。

循环:

是否生成循环(自环)边。

返回值: 

错误代码:IGRAPH_EINVAL:无效的 typenpm 参数。IGRAPH_ENOMEM:没有足够的内存用于操作。

时间复杂度:O(|V|+|E|),顶点数加上图中的边数。

另请参阅: 

3.2. igraph_lattice — 任意维度的正方形格子(已弃用)。

igraph_error_t igraph_lattice(igraph_t *graph, const igraph_vector_int_t *dimvector,
                   igraph_integer_t nei, igraph_bool_t directed, igraph_bool_t mutual,
                   igraph_bool_t circular);

警告

自 0.10.0 版本起已弃用。请不要在新代码中使用此函数;请改用 igraph_square_lattice()

3.3. igraph_tree — 创建一个 k 元树,其中几乎所有顶点都有 k 个孩子(已弃用的别名)。

igraph_error_t igraph_tree(igraph_t *graph, igraph_integer_t n, igraph_integer_t children,
                igraph_tree_mode_t type);

警告

自 0.10.0 版本起已弃用。请不要在新代码中使用此函数;请改用 igraph_kary_tree()