用于使用 igraph C 库
图生成器用于创建图。
几乎所有创建图对象的函数都在这里记录。例外情况是 igraph_induced_subgraph()
及其类似函数,它们基于另一个图创建图。
igraph_create
— 创建具有指定边的图。igraph_small
— 用于创建小图的简写,将边作为参数给出。igraph_adjacency
— 从邻接矩阵创建图。igraph_weighted_adjacency
— 从加权邻接矩阵创建图。igraph_sparse_adjacency
— 从稀疏邻接矩阵创建图。igraph_sparse_weighted_adjacency
— 从加权稀疏邻接矩阵创建图。igraph_adjlist
— 从邻接列表创建图。igraph_star
— 创建一个 星形 图,每个顶点仅连接到中心。igraph_wheel
— 创建一个 轮 图,它是星形图和环图的并集。igraph_hypercube
— n 维超立方体图。igraph_square_lattice
— 任意维度的正方形格子。igraph_triangular_lattice
— 具有给定形状的三角形格子。igraph_hexagonal_lattice
— 具有给定形状的六边形格子。igraph_ring
— 创建一个 环 图或 路径 图。igraph_kary_tree
— 创建一个 k 叉树,其中几乎所有顶点都有 k 个子节点。igraph_symmetric_tree
— 创建一个对称树,在每个级别上具有指定的分支数。igraph_regular_tree
— 创建一个正则树。igraph_tree_from_parent_vector
— 从编码每个顶点的父节点的向量构造树或森林。igraph_full
— 创建一个完全图(完整图)。igraph_full_citation
— 创建一个完整的引用图(完整的有向无环图)。igraph_full_multipartite
— 创建一个完整的多部图。igraph_turan
— 创建一个图兰图。igraph_realize_degree_sequence
— 生成具有给定度序列的图。igraph_realize_bipartite_degree_sequence
— 生成具有给定二部度序列的二部图。igraph_famous
— 通过简单地提供其名称来创建一个著名的图。igraph_lcf
— 从 LCF 符号创建图。igraph_lcf_vector
— 从 LCF 符号创建图。igraph_from_prufer
— 从 Prüfer 序列生成树。igraph_atlas
— 从 “图谱” 创建一个小图。igraph_de_bruijn
— 生成一个德布鲁因图。igraph_kautz
— 生成一个 Kautz 图。igraph_circulant
— 创建一个循环图。igraph_generalized_petersen
— 创建一个广义 Petersen 图。igraph_extended_chordal_ring
— 创建一个扩展弦环。
igraph_error_t igraph_create(igraph_t *graph, const igraph_vector_int_t *edges, igraph_integer_t n, igraph_bool_t directed);
参数:
|
一个未初始化的图对象。 |
|
要添加的边,前两个元素是第一条边,依此类推。 |
|
图中的顶点数,如果小于或等于 |
|
布尔值,是否创建有向图。如果是,则第一条边从 |
返回值:
错误代码: |
时间复杂度: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; }
igraph_error_t igraph_small(igraph_t *graph, igraph_integer_t n, igraph_bool_t directed, int first, ...);
当需要创建相对较小的图时,此函数非常方便。无需将边作为向量给出,而是简单地将它们作为参数给出,并且在最后一个有意义的边参数之后需要给出 -1
。
此函数旨在与作为文字整数输入的顶点 ID 一起使用。如果使用变量而不是文字,请确保它是 int 类型,因为这是此函数为所有可变参数假定的类型。使用不同的整数类型是未定义的行为,并且可能导致特定于平台的问题。
参数:
|
指向未初始化的图对象的指针。结果将存储在此处。 |
||||
|
图中的顶点数;一个非负整数。 |
||||
|
布尔常量;给出图是否应该是有向的。支持的值是
|
||||
|
给出图的边的附加参数,并且必须是 int 类型。不要忘记在最后一个(有意义的)参数之后提供一个附加的 |
返回值:
错误代码。 |
时间复杂度: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; }
igraph_error_t igraph_adjacency( igraph_t *graph, const igraph_matrix_t *adjmatrix, igraph_adjacency_t mode, igraph_loops_t loops );
保留矩阵中顶点的顺序,即对应于第一行/列的顶点将是 ID 为 0 的顶点,下一行是顶点 1,依此类推。
参数:
|
指向未初始化的图对象的指针。 |
||||||||||||||
|
邻接矩阵。它的解释方式取决于 |
||||||||||||||
|
用于指定给定矩阵如何被解释为邻接矩阵的常量。可能的值(A(i,j) 是邻接矩阵
|
||||||||||||||
|
用于指定在创建环边时应如何处理矩阵的对角线的常量。
|
返回值:
错误代码, |
时间复杂度:O(|V||V|),|V| 是图中的顶点数。
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,依此类推。
参数:
|
指向未初始化的图对象的指针。 |
||||||||||||||
|
加权邻接矩阵。它的解释方式取决于 |
||||||||||||||
|
用于指定给定矩阵如何被解释为邻接矩阵的常量。可能的值(A(i,j) 是邻接矩阵
|
||||||||||||||
|
指向已初始化向量的指针,权重将存储在此处。 |
||||||||||||||
|
用于指定在创建环边时应如何处理矩阵的对角线的常量。
|
返回值:
错误代码, |
时间复杂度: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); }
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| 是图中的边数。
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| 是图中的边数。
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 图。
参数:
|
指向未初始化的图对象的指针。 |
|
邻接列表。 |
|
是否创建有向图。 |
|
布尔常量。对于无向图,这指定每条边是否包含两次,在两个相邻顶点的向量中。如果这是 |
返回值:
错误代码。 |
另请参阅:
|
时间复杂度:O(|V|+|E|)。
igraph_error_t igraph_star(igraph_t *graph, igraph_integer_t n, igraph_star_mode_t mode, igraph_integer_t center);
参数:
|
指向未初始化的图对象的指针,这将是结果。 |
||||||||
|
整数常量,图中顶点的数量。 |
||||||||
|
常量,给出要创建的星形图的类型。可能的值
|
||||||||
|
将作为图的中心的顶点的 ID。 |
返回值:
错误代码
|
时间复杂度: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; }
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 环)。
参数:
|
指向未初始化的图对象的指针,这将是结果。 |
||||||||
|
整数常量,图中顶点的数量。 |
||||||||
|
常量,给出要创建的星形图的类型。可能的值
|
||||||||
|
将作为图的中心的顶点的 ID。 |
返回值:
错误代码
|
时间复杂度:O(|V|),图中顶点的数量。
另请参阅:
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 的二进制表示形式恰好相差一位时,两个顶点连接。
参数:
|
一个未初始化的图对象。 |
|
超立方体图的维度。 |
|
图是否应该是有向的。边将从较低索引的顶点指向较高索引的顶点。 |
返回值:
错误代码。 |
另请参阅:
时间复杂度:O(2^n)
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 + ...
。
参数:
|
一个未初始化的图对象。 |
|
向量,给出格子在每个维度上的大小。格子的维度将与此向量的长度相同。 |
|
整数值,给出将在其中连接两个顶点的距离(步数)。 |
|
布尔值,是否创建有向图。如果 |
|
布尔值,如果图是有向的,则这给出是否将所有连接创建为互连。 |
|
布尔向量,定义生成的格子是否沿每个维度都是周期性的。此向量的长度必须与 |
返回值:
错误代码: |
另请参阅:
|
时间复杂度:如果 nei
小于 2,则为 O(|V|+|E|)(就我记忆所及),|V| 和 |E| 是生成的图中顶点和边的数量。否则为 O(|V|*d^k+|E|),d 是图的平均度数,k 是 nei
参数。
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)
参数:
|
一个未初始化的图对象。 |
|
整数向量,定义格子的形状。如果 |
|
布尔值,是否创建有向图。如果 |
|
布尔值,如果图是有向的,则这给出是否将所有连接创建为互连。 |
返回值:
错误代码: |
另请参阅:
|
时间复杂度:O(|V|),其中 |V| 是生成的图中顶点的数量。
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)
参数:
|
一个未初始化的图对象。 |
|
整数向量,定义格子的形状。如果 |
|
布尔值,是否创建有向图。如果 |
|
布尔值,如果图是有向的,则这给出是否将所有连接创建为互连。 |
返回值:
错误代码: |
另请参阅:
|
时间复杂度:O(|V|),其中 |V| 是生成的图中顶点的数量。
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 时,结果可能不是一个简单图:单环包含一个自环,而无向或互连的有向两环包含平行边。
参数:
|
指向未初始化的图对象的指针。 |
|
图中顶点的数量。 |
|
是否创建有向图。所有边都将沿环或路径的同一方向定向。 |
|
是否在有向图中创建互边。对于无向图,它将被忽略。 |
|
是否创建闭环(环)或开路(路径)。 |
返回值:
错误代码: |
时间复杂度:O(|V|),图中顶点的数量。
另请参阅:
|
示例 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; }
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()
不认为它是树。
参数:
|
指向未初始化的图对象的指针。 |
||||||
|
整数,图中的顶点数。 |
||||||
|
整数,树中一个顶点的子节点数。 |
||||||
|
常量,指示是否创建有向树,如果是,则指示其方向。可能的值
|
返回值:
错误代码: |
时间复杂度:O(|V|+|E|),顶点数加上图中的边数。
另请参阅:
创建其他规则结构的函数: |
示例 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; }
igraph_error_t igraph_symmetric_tree(igraph_t *graph, const igraph_vector_int_t *branches, igraph_tree_mode_t type);
此函数创建一个树,其中距根节点距离为 d
的所有顶点都有 branching_counts
[d] 个子节点。
参数:
|
指向未初始化的图对象的指针。 |
||||||
|
详细说明每一层分支数的向量。 |
||||||
|
常量,指示是否创建有向树,如果是,则指示其方向。可能的值
|
返回值:
错误代码: |
时间复杂度:O(|V|+|E|),顶点数加上图中的边数。
另请参阅:
创建其他规则树结构的函数: |
示例 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; }
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 格子。
参数:
|
指向未初始化的图对象的指针。 |
||||||
|
树的高度,即根节点和叶节点之间的距离。 |
||||||
|
规则树的度数。 |
||||||
|
常量,指示是否创建有向树,如果是,则指示其方向。可能的值
|
返回值:
错误代码。 |
时间复杂度:O(|V|+|E|),顶点数加上图中的边数。
另请参阅:
创建 k 叉树的函数: |
示例 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; }
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()
更方便。
参数:
|
指向未初始化的图对象的指针。 |
||||||
|
父向量。 |
||||||
|
常量,指示是否创建有向树,如果是,则指示其方向。可能的值
|
返回值:
错误代码。 |
另请参阅:
反向转换的函数: |
时间复杂度:O(n),其中 n 是 parents
的长度。
igraph_error_t igraph_full(igraph_t *graph, igraph_integer_t n, igraph_bool_t directed, igraph_bool_t loops);
在满图中,存在每个可能的边:每个顶点都连接到每个其他顶点。igraph 将图论中完全图的通常概念推广到具有自环的图以及有向图。
参数:
|
指向未初始化的图对象的指针。 |
|
整数,图中的顶点数。 |
|
是否创建有向图。 |
|
是否包含自环。 |
返回值:
错误代码: |
时间复杂度:O(|V|^2) = O(|E|),其中 |V| 是顶点数,|E| 是边数。
另请参阅:
创建其他规则结构的函数: |
示例 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; }
igraph_error_t igraph_full_citation(igraph_t *graph, igraph_integer_t n, igraph_bool_t directed);
这是一个有向图,当且仅当 j<i
时才存在每个 i->j
边。如果 directed
参数为 false,则创建一个无向图,它只是一个完全图。
参数:
|
指向未初始化的图对象的指针,结果将存储在此处。 |
|
顶点数。 |
|
是否创建有向图。如果为 false,则创建一个无向图。 |
返回值:
错误代码。 |
另请参阅:
时间复杂度:O(|V|^2) = O(|E|),其中 |V| 是顶点数,|E| 是边数。
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);
多部图包含两种或多种类型的顶点,并且只有不同类型的两个顶点之间才可能存在连接。此函数创建一个完全多部图。
参数:
|
指向未初始化的图对象的指针,图将在此处创建。 |
|
指向整数向量的指针。如果不为 null 指针,则将在此处存储每个顶点的类型。 |
|
指向整数向量的指针,每种类型的顶点数。 |
|
布尔值,是否创建有向图。 |
|
一个常量,用于给出有向图的连接类型。如果 |
返回值:
错误代码。 |
时间复杂度:O(|V|+|E|),顶点数和边数的线性关系。
另请参阅:
完全二部图的函数: |
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 对象的指针,图将在此处创建。 |
|
指向整数向量的指针。如果不为 null 指针,则将在此处存储每个顶点的类型(分区索引)。 |
|
整数,图中的顶点数。 |
|
整数,图的分区数,必须为正数。 |
返回值:
错误代码。 |
时间复杂度:O(|V|+|E|),顶点数和边数的线性关系。
另请参阅:
完全多部图的函数: |
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
参数:
|
指向未初始化的图对象的指针。 |
||||||||
|
无向图的度序列(如果 |
||||||||
|
有向图的入度序列。传递 |
||||||||
|
图中允许的边类型。对于有向图,目前仅实现了
|
||||||||
|
生成图的方法。可能的值
|
返回值:
错误代码
|
另请参阅:
测试图形性而不生成图的函数: |
示例 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(°ree, nodes); igraph_degree(&g1, °ree, 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, °ree, 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, °ree, 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(°ree); return 0; }
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
。
参数:
|
指向未初始化的图对象的指针。 |
||||||
|
第一个分区的度数序列。 |
||||||
|
第二个分区的度数序列。 |
||||||
|
图中允许的边类型。
|
||||||
|
控制选择顶点进行连接的顺序。可能的值
|
返回值:
错误代码。 |
另请参阅:
测试二分性而不生成图的函数: |
igraph_error_t igraph_famous(igraph_t *graph, const char *name);
图的名称可以简单地作为字符串提供。请注意,此函数创建不带任何参数的图,对于带有参数的图,有单独的函数,例如,用于创建完全图的函数:igraph_full()
。
支持以下图
|
公牛图,5 个顶点,5 条边,如果正确绘制,则类似于公牛的头部。 |
|
这是最小的无三角形图,它既是 4 色又是 4 正则的。根据 Grunbaum 猜想,对于每个 m>1 和 n>2,都存在一个具有 n 个顶点的 m 正则、m 色图。Chvatal 图是 m=4 和 n=12 的一个示例。它有 24 条边。 |
|
一个非哈密顿立方对称图,具有 28 个顶点和 42 条边。 |
|
立方体的柏拉图图。具有 8 个顶点和 12 条边的凸规则多面体。 |
|
一个具有 4 个顶点和 5 条边的图,如果正确绘制,则类似于示意性钻石。 |
|
另一个具有 20 个顶点和 30 条边的柏拉图立体。 |
|
具有最少顶点数 20 和 40 条边的半对称图。半对称图是正则的、边传递的而不是顶点传递的。 |
|
这是一个嵌入到克莱因瓶中的图可以用六种颜色着色,它是克莱因瓶上 Heawood 猜想的必要性的一个反例。它有 12 个顶点和 18 条边。 |
|
Frucht 图是最小的立方图,其自同构群仅由恒等元素组成。它有 12 个顶点和 18 条边。 |
|
Grötzsch 图是一个无三角形图,具有 11 个顶点、20 条边和色数 4。它以德国数学家 Herbert Grötzsch 的名字命名,它的存在证明了在 Grötzsch 定理中平面性的假设是必要的,即每个无三角形平面图都是 3 可着色的。 |
|
Heawood 图是一个具有 14 个顶点和 21 条边的无向图。该图是立方的,并且该图中的所有循环都有六条或更多边。每个较小的立方图都有较短的循环,因此该图是 6 笼,即周长为 6 的最小立方图。 |
|
Herschel 图是最小的非哈密顿多面体图。它是 11 个节点上的唯一此类图,并且有 18 条边。 |
|
房屋图是一个 5 顶点、6 边图,如果正确绘制,则为房屋的示意图,基本上是正方形顶部的三角形。 |
|
与带有正方形 X 的房屋图相同。5 个顶点和 8 条边。 |
|
一个具有 12 个顶点和 30 条边的柏拉图立体。 |
|
一个具有 10 个顶点和 18 条边的社交网络。Krackhardt, D. Assessing the Political Landscape: Structure, Cognition, and Power in Organizations. Admin. Sci. Quart. 35, 342-369, 1990. |
|
该图是一个 4 弧传递立方图,具有 30 个顶点和 45 条边。 |
|
McGee 图是唯一的 3 正则 7 笼图,具有 24 个顶点和 36 条边。 |
|
Meredith 图是一个具有 70 个节点和 140 条边的四次图,它是每个 4 正则 4 连通图都是哈密顿图的猜想的反例。 |
|
一个具有 16 个顶点和 27 条边的连通图,不包含完美匹配。图中的匹配是一组成对的非相邻边;也就是说,没有两条边共享一个公共顶点。完美匹配是一个覆盖图中所有顶点的匹配。 |
|
一个图,其连通分量是 9 个图,这些图作为图中顶点诱导的子图的存在使其成为非线图。它有 50 个顶点和 72 条边。 |
|
具有 6 个顶点和 12 条边的柏拉图立体。 |
|
一个具有 10 个顶点和 15 条边的 3 正则图。它是最小的次哈密顿图,也就是说,它是非哈密顿图,但从中移除任何单个顶点都会使其成为哈密顿图。 |
|
唯一的 (4,5) 笼图,即周长为 5 的 4 正则图。它有 19 个顶点和 38 条边。 |
|
一个最小的非平凡图,其自同构群是循环的。它有 9 个顶点和 15 条边。 |
|
具有 4 个顶点和 6 条边的柏拉图立体。 |
|
最小的次可追溯图,具有 34 个顶点和 52 条边。次可追溯图不包含哈密顿路径,但从中移除任何单个顶点后,剩余部分始终包含哈密顿路径。包含哈密顿路径的图称为可追溯的。 |
|
Tait 的哈密顿图猜想指出,每个 3 连通 3 正则平面图都是哈密顿图。此图是一个反例。它有 46 个顶点和 69 条边。 |
|
返回一个 12 顶点、无三角形图,其色数为 3,并且是唯一 3 可着色的。 |
|
一个具有 25 个顶点和 31 条边的恒等图。恒等图具有单个图自同构,即平凡的自同构。 |
|
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)。 |
参数:
|
指向未初始化的图对象的指针。 |
|
字符常量,要创建的图的名称,不区分大小写。 |
返回值:
错误代码,如果不存在给定名称的图,则为 |
另请参阅:
用于创建图结构的其他函数: |
时间复杂度:O(|V|+|E|),顶点数加上图中的边数。
igraph_error_t igraph_lcf(igraph_t *graph, igraph_integer_t n, ...);
LCF 是 Lederberg-Coxeter-Frucht 的缩写,它是 3 正则哈密顿图的简洁表示法。它由三个参数组成:图中顶点的数量、给出添加到循环骨架的附加边的移位列表,以及另一个整数,给出应执行移位的次数。有关详细信息,请参见 https://mathworld.net.cn/LCFNotation.html。
参数:
|
指向未初始化的图对象的指针。 |
|
整数,图中的顶点数。 |
|
移位和移位的重复次数,再加上一个额外的 0 来标记参数的结尾。 |
返回值:
错误代码。 |
另请参阅:
请参阅 |
时间复杂度: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; }
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()
。
参数:
|
指向未初始化的图对象的指针。 |
|
给出顶点数的整数常量。 |
|
给出移位的向量。 |
|
给出移位重复次数的整数常量。 |
返回值:
错误代码。 |
另请参阅:
时间复杂度:O(|V|+|E|),顶点数加上边数的线性关系。
igraph_error_t igraph_from_prufer(igraph_t *graph, const igraph_vector_int_t *prufer);
Prüfer 序列是与标记树关联的唯一整数序列。具有 n
个顶点的树可以用 n-2
个整数的序列表示,每个整数介于 0
和 n-1
之间(包括在内)。此函数使用的算法基于 Paulius Micikevičius, Saverio Caminiti, Narsingh Deo: Linear-time Algorithms for Encoding Trees as Sequences of Node Labels
参数:
|
指向未初始化的图对象的指针。 |
|
Prüfer 序列 |
返回值:
错误代码
|
另请参阅:
时间复杂度:O(|V|),其中 |V| 是树中的顶点数。
igraph_error_t igraph_atlas(igraph_t *graph, igraph_integer_t number);
图集包含 0 到 7 个顶点之间的所有简单无向未标记图。图的编号作为参数给出。这些图按以下顺序排列
按顶点数量递增排序;
对于固定数量的顶点,按边数量递增排序;
对于固定数量的顶点和边,按度数序列的词典顺序递增排序,例如 111223 < 112222;
对于固定的度序列,按自同构数递增排序。
数据来自 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; }
igraph_error_t igraph_de_bruijn(igraph_t *graph, igraph_integer_t m, igraph_integer_t n);
德布鲁因图表示字符串之间的关系。使用 m
个字母的字母表,并考虑长度为 n
的字符串。一个顶点对应于每个可能的字符串,并且如果 v
的字符串可以通过删除其第一个字母并在其后附加一个字母来转换为 w
的字符串,则从顶点 v
到顶点 w
存在一条有向边。
请注意,该图将具有 m
的 n
次方个顶点,甚至更多的边,因此您可能不想为 m
和 n
提供太大的数字。
德布鲁因图有一些有趣的属性,请参阅其他来源,例如维基百科了解详细信息。
参数:
|
指向未初始化的图对象的指针,结果将存储在此处。 |
|
整数,字母表中的字母数。 |
|
整数,字符串的长度。 |
返回值:
错误代码。 |
另请参阅:
时间复杂度:O(|V|+|E|),顶点数加上边数。
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 中编写了此函数的第一个版本,谢谢。
参数:
|
指向未初始化的图对象的指针,结果将存储在此处。 |
|
整数, |
|
整数, |
返回值:
错误代码。 |
另请参阅:
时间复杂度:O(|V|* [(m+1)/m]^n +|E|),实际上更像是 O(|V|+|E|)。 |V| 是顶点数,|E| 是边数,m
和 n
是相应的参数。
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)
。
该函数可以生成有向图或无向图。它不会生成多重边或自环。
参数:
|
指向未初始化的图对象的指针,结果将存储在此处。 |
|
整数,循环图中的顶点数。 |
|
整数向量,循环图中的偏移量列表。 |
|
布尔值,是否创建有向图。 |
返回值:
错误代码。 |
另请参阅:
时间复杂度:O(|V| |shifts|),图中顶点的数量乘以偏移量的数量。
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
参数:
|
指向未初始化的图对象的指针,结果将存储在此处。 |
|
整数, |
|
整数, |
返回值:
错误代码。 |
另请参阅:
对于原始彼得森图,请参见 |
时间复杂度:O(|V|),图中顶点的数量。
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)]
步,其中 p
是 L
的长度。换句话说,顶点 i
将连接到顶点 (i + L[(i mod p)]) mod nodes
。如果以这种方式定义了多条边,这将输出一个非简单图。可以使用 igraph_simplify()
简化结果。
另请参阅 Kotsis, G: 用于并行处理系统的互连拓扑,PARS Mitteilungen 11, 1-6, 1993。igraph 扩展弦环与论文中的弦环不相同。在 igraph 中,矩阵指定要添加哪些边。在论文中,指定了一个条件,该条件应同时在两个端点和反向端点之间成立。
参数:
|
指向未初始化的图对象的指针,结果将存储在此处。 |
|
整数常量,图中的顶点数。它必须至少为 3。 |
|
指定额外边的矩阵。列数应能整除总顶点数。允许元素为负数。 |
|
图是否应该是有向图。 |
返回值:
错误代码。 |
另请参阅:
时间复杂度:O(|V|+|E|),顶点数加上边数。
igraph_grg_game
— 生成一个几何随机图。igraph_barabasi_game
— 生成一个基于 Barabási-Albert 模型的图。igraph_erdos_renyi_game_gnm
— 生成一个具有固定边数的随机 (Erdős-Rényi) 图。igraph_erdos_renyi_game_gnp
— 生成一个具有固定边概率的随机 (Erdős-Rényi) 图。igraph_watts_strogatz_game
— Watts-Strogatz 小世界模型。igraph_rewire_edges
— 以恒定概率重新连接图的边。igraph_rewire_directed_edges
— 重新连接有向边的选定端点。igraph_degree_sequence_game
— 生成一个具有给定度序列的随机图。igraph_k_regular_game
— 生成一个每个顶点都具有相同度的随机图。igraph_static_fitness_game
— 边概率与节点适应度得分成比例的非增长随机图。igraph_static_power_law_game
— 生成一个具有预期幂律度分布的非增长随机图。igraph_chung_lu_game
— 从 Chung-Lu 模型中采样图。igraph_forest_fire_game
— 根据“森林火灾游戏”生成网络。igraph_rewire
— 随机重新连接图,同时保留其度序列。igraph_growing_random_game
— 生成一个增长的随机图。igraph_callaway_traits_game
— 模拟具有顶点类型的增长网络。igraph_establishment_game
— 生成一个具有简单增长模型和顶点类型的图。igraph_preference_game
— 生成一个具有顶点类型和连接偏好的图。igraph_asymmetric_preference_game
— 生成一个具有不对称顶点类型和连接偏好的图。igraph_recent_degree_game
— 基于节点最近获得的入射边数的随机图生成器。igraph_barabasi_aging_game
— 优先连接,顶点老化。igraph_recent_degree_aging_game
— 基于最近获得的边数的优先连接,顶点老化。igraph_lastcit_game
— 模拟引文网络,基于自上次引文以来经过的时间。igraph_cited_type_game
— 模拟基于顶点类型的引文。igraph_citing_cited_type_game
— 模拟基于顶点类型的引文网络。igraph_sbm_game
— 从随机块模型中采样。igraph_hsbm_game
— 分层随机块模型。igraph_hsbm_list_game
— 分层随机块模型,更通用的版本。igraph_dot_product_game
— 生成一个随机点积图。igraph_tree_game
— 生成一个具有给定节点数的随机树。igraph_correlated_game
— 生成一个与现有图相关的随机图。igraph_correlated_pair_game
— 生成成对相关的随机图。igraph_simple_interconnected_islands_game
— 生成一个由几个互连的岛屿组成的随机图,每个岛屿都是一个随机图。游戏是随机图生成器,即每次调用它们时都会生成不同的图。 igraph 包括许多此类生成器。一些实现受现实世界机制(例如优先连接)启发的随机图构造过程,而另一些旨在生成具有某些使用属性的图(例如,固定边数、固定度数等)。
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。
参数:
|
指向未初始化的图对象的指针。 |
|
图中顶点的数量。 |
|
顶点将在其内连接的半径。 |
|
布尔常量。如果为 true,则将使用周期性边界条件,即假定顶点位于环面上而不是正方形上。 |
|
初始化的向量或 |
|
初始化的向量或 |
返回值:
错误代码。 |
时间复杂度: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; }
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
参数控制),而 power
和 A
由参数给出。常数吸引力 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
参数:
|
一个未初始化的图对象。 |
||||||
|
图中顶点的数量。 |
||||||
|
优先连接的幂。在经典优先连接模型中, |
||||||
|
为每个顶点生成的出边数。仅当 |
||||||
|
给出顶点的(出)度。如果这是常数,则可以是指向 |
||||||
|
布尔值,如果为 true,则不仅顶点的入度会增加其引用概率,而且出度也会增加其引用概率。即,引用概率由顶点的总度确定。如果生成的图是无向图,则忽略并假定为 true。 |
||||||
|
顶点的常数吸引力。当 |
||||||
|
布尔值,是否生成有向图。当设置为 |
||||||
|
用于生成网络的算法。可能的值
|
||||||
|
可以是 |
返回值:
错误代码: |
时间复杂度: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; }
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
条边的图。
参数:
|
指向未初始化的图对象的指针。 |
|
图中顶点的数量。 |
|
图中的边数。 |
|
是否生成有向图。 |
|
是否生成自环。 |
返回值:
错误代码: |
时间复杂度:O(|V|+|E|),顶点数加上图中的边数。
另请参阅:
使用 |
示例 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; }
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
。
参数:
|
指向未初始化的图对象的指针。 |
|
图中顶点的数量。 |
|
图中存在边的概率。 |
|
是否生成有向图。 |
|
是否生成自环。 |
返回值:
错误代码: |
时间复杂度:O(|V|+|E|),顶点数加上图中的边数。
另请参阅:
使用 |
示例 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; }
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
参数:
|
要初始化的图。 |
|
格的维度。 |
|
格在每个维度上的大小。 |
|
每个顶点的邻域大小。这与 |
|
重新连接概率。一个介于零和一之间的实数(包括零和一)。 |
|
是否生成循环边。 |
|
是否允许在生成的图中出现多重边。 |
返回值:
错误代码。 |
另请参阅:
如果需要更大的灵活性,例如不同类型的格,则可以使用 |
时间复杂度:O(|V|*d^o+|E|),|V| 和 |E| 是顶点数和边数,d 是平均度数,o 是 nei
参数。
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()
。
参数:
|
输入图,这将重新连接,它可以是有向图或无向图。 |
|
重新连接概率,一个介于零和一之间的常数(包括零和一)。 |
|
布尔值,是否允许在新图中出现循环边。 |
|
布尔值,是否允许在新图中出现多重边。 |
返回值:
错误代码。 |
另请参阅:
对于重新连接, |
时间复杂度:O(|V|+|E|)。
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()
。
此函数可以在两个顶点之间生成多重边。
参数:
|
输入图,这将重新连接,它可以是有向图或无向图。如果它是无向图,或者 |
||||||
|
重新连接概率,一个介于零和一之间的常数(包括零和一)。 |
||||||
|
布尔值,是否允许在新图中出现循环边。 |
||||||
|
要重新连接的有向边的端点。对于无向图,将忽略此参数。可能的值
|
返回值:
错误代码。 |
另请参阅:
时间复杂度:O(|E|)。
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。
参数:
|
指向未初始化的图对象的指针。 |
||||||||||
|
无向图的度序列(如果 |
||||||||||
|
它可以是零长度向量或 |
||||||||||
|
生成图的方法。可能的值
|
返回值:
错误代码: |
时间复杂度:O(|V|+|E|),对于 IGRAPH_DEGSEQ_CONFIGURATION
和 IGRAPH_DEGSEQ_EDGE_SWITCHING_SIMPLE
,顶点数加上边数。其他模式的时间复杂度未知。
另请参阅:
|
示例 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; }
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_CONFIGURATION
或 IGRAPH_DEGSEQ_FAST_SIMPLE
方法和适当构建的度序列。因此,它不均匀采样:虽然它可以生成具有给定顶点数的所有 k 正则图,但它不会以相同的概率生成每个图。
参数:
|
指向未初始化的图对象的指针。 |
|
生成的图中的节点数。 |
|
无向图中每个顶点的度,或有向图中每个顶点的出度和入度。 |
|
生成的图是否为有向图。 |
|
是否允许在生成的图中出现多重边。 |
返回值:
错误代码: |
时间复杂度:如果 multiple
为 true,则为 O(|V|+|E|),否则未知。
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);
此游戏生成有向或无向随机图,其中顶点 i
和 j
之间的边的概率取决于所涉及的两个顶点的适应度分数。对于无向图,每个顶点都有一个适应度分数。对于有向图,每个顶点都有一个出适应度和一个入适应度,并且从 i
到 j
的边的概率取决于顶点 i
的出适应度和顶点 j
的入适应度。
生成过程如下。我们从 N
个断开连接的节点开始(其中 N
由适应度向量的长度给出)。然后,我们随机选择两个顶点 i
和 j
,概率与它们的适应度成正比。(当生成的图是有向图时,根据出适应度选择 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.
参数:
|
指向未初始化的图对象的指针。 |
|
包含每个顶点的适应度的数值向量。对于有向图,这指定了每个顶点的出适应度。 |
|
如果 |
|
生成的图中的边数。 |
|
是否允许在生成的图中存在环边。 |
|
是否允许在生成的图中出现多重边。 |
返回值:
错误代码: |
另请参阅:
时间复杂度:O(|V| + |E| log |E|)。
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
参数:
|
指向未初始化的图对象的指针。 |
|
生成的图中的节点数。 |
|
生成的图中的边数。 |
|
度分布的幂律指数。对于有向图,这指定了出度分布的指数。它必须大于或等于 2。如果在此处传递 |
|
如果为负数,则生成的图将是无向图。如果大于或等于 2,则此参数指定入度分布的指数。如果为非负数但小于 2,则会生成错误。 |
|
是否允许在生成的图中存在环边。 |
|
是否允许在生成的图中出现多重边。 |
|
是否使用 Cho 等人提出的有限尺寸校正。 |
返回值:
错误代码: |
时间复杂度:O(|V| + |E| log |E|)。
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 模型中,每对顶点 i
和 j
都以独立的概率 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_k
。 i
和 j
之间的连接概率为 p_ij = w^out_i w^in_j / S
。
此模型通常用于创建具有固定预期度序列的随机图。顶点 i
的预期度近似等于权重 w_i
。具体来说,如果图是有向图且允许自环,则预期出度和入度正是 w^out
和 w^in
。如果不允许自环,则预期出度和入度分别为 w^out (S - w^in) / S
和 w^in (S - w^out) / S
。如果图是无向图,则有和没有自环的预期度分别为 w (S + w) / S
和 w (S - w) / S
。
原始 Chung-Lu 模型的一个限制是,当某些权重很大时,p_ij
的公式会产生大于 1 的值。Chung 和 Lu 的原始论文排除了使用此类权重。当 p_ij > 1
时,此函数只会发出警告并在 i
和 j
之间创建连接。但是,在这种情况下,预期度将不再以上述方式与权重相关。因此,原始 Chung-Lu 模型无法产生某些(大的)预期度。
为了克服此限制,此函数实现了该模型的其他变体,并修改了顶点 i
和 j
之间的连接概率 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
参数:
|
指向未初始化的图对象的指针。 |
||||||
|
非负顶点权重(或出权重)的向量。在稀疏图中,这些值将近似等于预期(出)度。 |
||||||
|
非负入权重的向量,近似等于稀疏图中的预期入度。可以设置为 |
||||||
|
是否允许创建自环。由于顶点对是独立连接的,因此将此项设置为 false 等效于仅从现有带环 Chung-Lu 图中丢弃自环。 |
||||||
|
要从中采样的模型变体,具有顶点
|
返回值:
错误代码。 |
另请参阅:
|
时间复杂度:O(|E| + |V|),与边数呈线性关系。
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
,我们执行以下过程
我们生成两个随机数 x
和 y
,它们是几何分布的,均值分别为 p/(1-p)
和 rp(1-rp)
。(p
是 fw_prob
,r
是 bw_factor
。)新顶点从那些尚未被新顶点引用的顶点中引用 v
的 x
个传出邻居和 y
个传入邻居。如果可用的此类顶点少于 x
或 y
个,那么我们将引用所有这些顶点。
相同的过程应用于所有新引用的顶点。
另请参见:Jure Leskovec、Jon Kleinberg 和 Christos Faloutsos。随时间推移的图:稠密化定律、收缩直径和可能的解释。 KDD '05:第十一届 ACM SIGKDD 国际知识发现和数据挖掘会议的论文集,177-187, 2005。
但是请注意,已发表论文中的模型版本是不正确的,因为它无法生成作者声称的那种图。更正后的版本可从 https://www.cs.cmu.edu/~jure/pubs/powergrowth-tkdd.pdf 获取,我们的实现基于此版本。
参数:
|
指向未初始化的图对象的指针。 |
|
图中顶点的数量。 |
|
前向燃烧概率。 |
|
后向燃烧率。后向燃烧概率计算为 |
|
大使顶点数。 |
|
是否创建有向图。 |
返回值:
错误代码。 |
时间复杂度:待定。
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)
。
参数:
|
要重连的图对象。 |
||||
|
要执行的重连试验次数。 |
||||
|
要使用的重连算法。它可以是以下标志之一
|
返回值:
错误代码
|
时间复杂度:待定。
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);
此函数模拟一个增长的随机图。我们从一个顶点开始。在每个步骤中,都会添加一个新顶点,并且还会添加一些新边。众所周知,这些图与标准(非增长)随机图不同。
参数:
|
未初始化的图对象。 |
|
图中顶点的数量。 |
|
在时间步长中(即添加顶点后)要添加的边数。 |
|
布尔值,是否生成有向图。 |
|
布尔值,如果 |
返回值:
错误代码: |
时间复杂度:O(|V|+|E|),顶点数加上边数。
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
参数:
|
指向未初始化图的指针。 |
|
图中的节点数。 |
|
节点类型数。 |
|
每个时间步长中尝试的连接数。 |
|
给出顶点类型分布的向量。如果 |
|
给出顶点类型连接概率的矩阵。 |
|
是否生成有向图。 |
|
已初始化的向量或 |
返回值:
错误代码。 |
在 0.2 版本中添加。
时间复杂度:O(|V|*k*log(|V|)),|V| 是顶点数,k 是 edges_per_step
。
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
个顶点。这种连接实现的可能性取决于所涉及的顶点的类型。
参数:
|
指向未初始化图的指针。 |
|
图中顶点的数量。 |
|
顶点类型的数量。 |
|
每个时间步长中尝试的连接数。 |
|
给出顶点类型分布的向量。如果 |
|
给出不同顶点类型连接概率的矩阵。 |
|
是否生成有向图。 |
|
已初始化的向量或 |
返回值:
错误代码。 |
在 0.2 版本中添加。
时间复杂度:O(|V|*k*log(|V|)),|V| 是顶点数,k 是 k
参数。
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()
的非增长变体。生成给定数量的顶点。根据给定的类型概率将每个顶点分配给一个顶点类型。最后,评估每个顶点对,并以取决于所涉及的顶点的类型的概率在它们之间创建边。
换句话说,此函数根据块模型生成图。顶点被分成组(或块),并且两个顶点连接的可能性仅取决于它们的组。
参数:
|
指向未初始化图的指针。 |
|
图中顶点的数量。 |
|
顶点类型的数量。 |
|
给出顶点类型分布的向量。如果 |
|
布尔值。如果为 true,则具有给定顶点类型的顶点数是固定的,并且 |
|
给出不同顶点类型连接概率的矩阵。如果请求的图是无向图,则这应该是对称的。 |
|
将在其中存储各个生成的顶点类型的向量。如果 |
|
是否生成有向图。如果请求无向图,则仅考虑首选项矩阵的左下三角。 |
|
是否允许环边。 |
返回值:
错误代码。 |
在版本 0.3 中添加。
时间复杂度:O(|V|+|E|),顶点数加上图中的边数。
另请参阅:
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()
的不对称变体。生成给定数量的顶点。根据给定的联合类型概率,将每个顶点分配给“传出”和“传入”顶点类型。最后,评估每对顶点,并以取决于源顶点的“传出”类型和目标顶点的“传入”类型的概率在它们之间创建一条有向边。
参数:
|
指向未初始化图的指针。 |
|
图中顶点的数量。 |
|
顶点传出类型的数量。 |
|
顶点传入类型的数量。 |
|
大小为 |
|
首选项矩阵 |
|
node_type_out_vec |
|
node_type_in_vec |
|
是否允许环边。 |
返回值:
错误代码。 |
在版本 0.3 中添加。
时间复杂度:O(|V|+|E|),顶点数加上图中的边数。
另请参阅:
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);
参数:
|
指向未初始化的图对象的指针。 |
|
图中的顶点数,与时间步数相同。 |
|
指数是指节点获得新边的概率与它最近(在最近的 |
|
整数常量,用于计算最近边数量的时间窗口大小。 |
|
整数常量,如果 |
|
每个时间步要添加的边数。如果此参数是空指针或零长度向量,则忽略此参数。在这种情况下,将使用常量 |
|
布尔常量,如果为 true,则由顶点发起的边也计为最近的入射边。对于大多数应用来说,将其设置为 false 是合理的。 |
|
常量,表示最近未获得任何边的顶点的吸引力。 |
|
布尔常量,是否生成有向图。 |
返回值:
错误代码。 |
时间复杂度:O(|V|*log(|V|)+|E|),|V| 是顶点的数量,|E| 是图中的边数。
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。
参数:
|
指向未初始化的图对象的指针。 |
|
图中顶点的数量。 |
|
每个时间步要添加的边数。如果 |
|
每个时间步要添加的边数。如果它是 |
|
布尔常量,顶点发起的边是否影响获得新边的概率。 |
|
优先连接的指数,通常是一个小的正数,值为 1 表示经典的线性优先连接。 |
|
老化的指数,通常是一个负数。 |
|
整数常量,要使用的年龄箱的数量。 |
|
零度顶点的吸引力的与度相关的部分。 |
|
零年龄顶点的吸引力的与年龄相关的部分。此参数通常为零。 |
|
度的系数。 |
|
年龄的系数。 |
|
布尔常量,是否生成有向图。 |
返回值:
错误代码。 |
时间复杂度:O((|V|+|V|/aging_bins)*log(|V|)+|E|)。|V| 是顶点的数量,|E| 是边的数量。
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 是顶点的年龄。
参数:
|
指向未初始化的图对象的指针。 |
|
图中顶点的数量。 |
|
每个时间步要添加的边数。如果 |
|
向量,给出每个时间步要添加的边数。如果它是空指针或零长度向量,则忽略此参数,并使用 |
|
布尔常量,如果为 true,则顶点发起的边也会被计算在内。通常为 false。 |
|
优先连接的指数。 |
|
老化的指数,通常为负数:旧顶点获得边的概率较低。 |
|
整数常量,要使用的年龄箱的数量。 |
|
用于计算顶点的入射边数量的时间窗口。 |
|
零度顶点的吸引力的与度相关的部分。 |
|
布尔常量,是否创建有向图。 |
返回值:
错误代码。 |
时间复杂度:O((|V|+|V|/aging_bins)*log(|V|)+|E|)。|V| 是顶点的数量,|E| 是边的数量。
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()
以摆脱这些边。
参数:
|
指向未初始化的图对象的指针,结果将存储在此处。 |
|
网络中的顶点数量。 |
|
每个时间步要添加的边数。 |
|
要使用的年龄箱的数量。 |
|
指向长度为 |
|
布尔常量,是否创建有向网络。 |
返回值:
错误代码。 |
另请参阅:
时间复杂度:O(|V|*a+|E|*log|V|),|V| 是顶点的数量,|E| 是边的总数,a 是 agebins
参数。
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()
以删除多条边。
参数:
|
指向未初始化的图对象的指针。 |
|
网络中的顶点数量。 |
|
数值向量,给出顶点的类别,因此它应包含 |
|
向量中不同顶点类别的吸引力。它的长度应为 |
|
整数常量,每个时间步要添加的边数。 |
|
布尔常量,是否创建有向网络。 |
返回值:
错误代码。 |
另请参阅:
|
时间复杂度:O((|V|+|E|)log|V|),|V| 和 |E| 分别是顶点和边的数量。
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()
以删除多条边。
参数:
|
指向未初始化的图对象的指针。 |
|
网络中的顶点数量。 |
|
长度为 |
|
偏好矩阵,需要一个方阵,行数和列数都应该是 |
|
整数常量,每个时间步要添加的边数。 |
|
布尔常量,是否创建有向网络。 |
返回值:
错误代码。 |
时间复杂度:O((|V|+|E|)log|V|),|V| 和 |E| 分别是顶点和边的数量。
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
参数。
参数:
|
输出图。这应该是指向未初始化图的指针。 |
|
顶点数。 |
|
矩阵,给出伯努利率。这是一个 KxK 矩阵,其中 K 是组数。从组 i 和 j 中的顶点之间创建边的概率由元素 (i,j) 给出。 |
|
整数向量,给出每组中的顶点数量。 |
|
布尔值,是否创建有向图。如果此参数为 false,则 |
|
布尔值,是否创建自环。 |
返回值:
错误代码。 |
时间复杂度:O(|V|+|E|+K^2),其中 |V| 是顶点的数量,|E| 是边的数量,K 是组数。
另请参阅:
|
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 必须是整数。 |
|
每个集群中的顶点比例,在块内。总和必须为 1,并且对于 rho 的所有元素,rho * m 必须是整数。 |
|
一个方形对称数值矩阵,块内集群的伯努利率。它的大小必须与 |
|
不同块中顶点之间连接的伯努利率。 |
返回值:
错误代码。 |
另请参阅:
|
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);
该函数根据分层随机块模型生成一个随机图。
参数:
|
生成的图存储在此处。 |
|
图中顶点的数量。 |
|
块大小的整数向量。 |
|
rho 向量的列表( |
|
方形矩阵的列表( |
|
不同块中顶点之间连接的伯努利率。 |
返回值:
错误代码。 |
另请参阅:
|
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.
参数:
|
输出图存储在此处。 |
|
一个矩阵,其中每个潜在位置向量都是一列。潜在位置向量的点积应位于 [0,1] 区间内,否则会给出警告。对于负点积,不添加边;大于 1 的点积始终会添加边。 |
|
生成的图应该是有向的吗? |
返回值:
错误代码。 |
时间复杂度:O(n*n*m),其中 n 是顶点的数量,m 是潜在向量的长度。
另请参阅:
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()
不认为它是树。
参数:
|
指向未初始化的图对象的指针。 |
||||
|
树中的节点数量。 |
||||
|
是否创建有向树。边从根开始定向。 |
||||
|
用于生成树的算法。可能的值
|
返回值:
错误代码: |
另请参阅:
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);
通过扰动给定简单图的邻接矩阵并打乱其顶点来采样新图。
参数:
|
原始图,它必须是简单的。 |
|
新图将存储在此处。 |
|
单位区间 [0,1] 中的值,原始图和生成的图的邻接矩阵之间的目标 Pearson 相关性(邻接矩阵用作向量)。 |
|
两个顶点之间边的概率。它必须在开区间 (0,1) 中。通常是 |
|
要应用于生成的图的顶点的排列。它也可以是一个空指针,在这种情况下,顶点将不会被排列。 |
返回值:
错误代码 |
另请参阅:
|
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);
采样两个随机图,具有给定的相关性。
参数:
|
第一个图将存储在此处。 |
|
第二个图将存储在此处。 |
|
两个图中的顶点数量。 |
|
单位区间中的标量,原始图和生成的图的邻接矩阵之间的目标 Pearson 相关性(邻接矩阵用作向量)。 |
|
一个数值标量,两个顶点之间边的概率,它必须在开区间 (0,1) 中。 |
|
是否生成有向图。 |
|
要应用于第二个图的顶点的排列。它也可以是一个空指针,在这种情况下,顶点将不会被排列。 |
返回值:
错误代码 |
另请参阅:
|
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);
所有岛屿的大小都相同。在一个岛屿内,每条边都以相同的概率生成。然后为每对无序岛屿生成固定数量的附加边以连接它们。生成的图保证是简单的。
参数:
|
指向未初始化的图对象的指针。 |
|
图中的岛屿数量。 |
|
图中岛屿的大小。 |
|
在岛屿内创建每个可能的边的概率。 |
|
在两个岛屿之间创建的边数。它可能大于 |
返回值:
错误代码: |
时间复杂度:O(|V|+|E|),顶点数加上图中的边数。
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()
。
参数:
|
指向未初始化的图对象的指针。 |
||||
|
随机图的类型,可能的值
|
||||
|
图中顶点的数量。 |
||||
|
这是 G(n,p) 图的 p 参数和 G(n,m) 图的 m 参数。 |
||||
|
是否生成有向图。 |
||||
|
是否生成循环(自环)边。 |
返回值:
错误代码: |
时间复杂度:O(|V|+|E|),顶点数加上图中的边数。
另请参阅:
|
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()
。
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()
。
← 第 8 章 随机数 | 第 10 章 图上的模型 → |