igraph 参考手册

用于使用 igraph C 库

第 30 章二分图，即二模图

1. igraph 中的二分网络
2. 创建二模网络
3. 二分邻接矩阵
4. 投影二模图
5. 对二分图的其他操作
6. 已弃用的函数

1. igraph 中的二分网络

二分网络包含两种类型的顶点，并且连接仅可能发生在两种不同类型的顶点之间。有很多自然的例子，例如电影和演员作为顶点，一部电影与所有参与的演员连接等等。

igraph 没有直接支持二分网络，至少在 C 语言级别没有。换句话说，igraph_t 结构体不包含关于顶点类型的信息。用于二分网络的 C 函数通常具有一个额外的输入参数 graph，称为 types，这是一个布尔向量，给出顶点类型。

大多数创建二分网络的函数都能够创建这个额外的向量，你只需要提供一个初始化的布尔向量给它们。

2. 创建二模网络

2.1. igraph_create_bipartite — 创建一个二分图。
2.2. igraph_full_bipartite — 创建一个完整的二分图。
2.3. igraph_bipartite_game_gnm — 生成具有固定数量边的随机二分图。
2.4. igraph_bipartite_game_gnp — 生成具有固定连接概率的随机二分图。

2.1. `igraph_create_bipartite` — 创建一个二分图。

igraph_error_t igraph_create_bipartite(igraph_t *graph, const igraph_vector_bool_t *types,
                            const igraph_vector_int_t *edges,
                            igraph_bool_t directed);

这是一个简单的包装函数，用于创建一个二分图。它比 igraph_create() 做得更多，例如，它检查该图是否确实相对于给定的 types 向量是二分的。如果存在连接同一类型的两个顶点的边，则会报告错误。

参数：

`图`:	指向一个未初始化的图对象，结果在此处创建。
`types`:	布尔向量，给出顶点类型。该向量的长度定义了图中顶点的数量。
`边`:	向量，给出图的边。此向量中的最高顶点 ID 必须小于 `types` 向量的长度。
`有向`:	布尔值，是否创建有向图。

返回值：

错误代码。

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

示例 30.1. 文件 examples/simple/igraph_bipartite_create.c

#include <igraph.h>

int main(void) {

    igraph_integer_t edges2[] = {0, 1, 1, 2, 3, 4, 5, 6, 6, 5, 1, 4, 1, 6, 0, 3 };
    igraph_t g;
    igraph_vector_bool_t types;
    igraph_vector_int_t edges;
    igraph_integer_t i;

    igraph_vector_int_view(&edges, edges2, sizeof(edges2) / sizeof(edges2[0]));
    igraph_vector_bool_init(&types, igraph_vector_int_max(&edges) + 1);
    for (i = 0; i < igraph_vector_bool_size(&types); i++) {
        VECTOR(types)[i] = i % 2;
    }
    igraph_create_bipartite(&g, &types, &edges, /*directed=*/ 1);
    igraph_write_graph_edgelist(&g, stdout);
    igraph_vector_bool_destroy(&types);
    igraph_destroy(&g);


    return 0;
}

2.2. `igraph_full_bipartite` — 创建一个完整的二分图。

igraph_error_t igraph_full_bipartite(igraph_t *graph,
                          igraph_vector_bool_t *types,
                          igraph_integer_t n1, igraph_integer_t n2,
                          igraph_bool_t directed,
                          igraph_neimode_t mode);

igraph 没有直接支持二分网络，至少在 C 语言级别没有。换句话说，igraph_t 结构体不包含关于顶点类型的信息。用于二分网络的 C 函数通常具有一个额外的输入参数 graph，称为 types，这是一个布尔向量，给出顶点类型。

大多数创建二分网络的函数都能够创建这个额外的向量，你只需要提供一个初始化的布尔向量给它们。

参数：

`图`:	指向一个未初始化的图对象，图将在此处创建。
`types`:	指向一个布尔向量。如果不是空指针，则顶点类型将存储在此处。
`n1`:	整数，第一类顶点的数量。
`n2`:	整数，第二类顶点的数量。
`有向`:	布尔值，是否创建有向图。
`模式`:	一个常量，给出有向图的连接类型。如果 `IGRAPH_OUT`，则边从第一类顶点指向第二类顶点；如果 `IGRAPH_IN`，则实现相反的方向；如果 `IGRAPH_ALL`，则将创建互边。

返回值：

错误代码。

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

另请参阅：

igraph_full() 用于非二分完全图，igraph_full_multipartite() 用于完整的多分图。

2.3. `igraph_bipartite_game_gnm` — 生成具有固定数量边的随机二分图。

igraph_error_t igraph_bipartite_game_gnm(igraph_t *graph, igraph_vector_bool_t *types,
                              igraph_integer_t n1, igraph_integer_t n2,
                              igraph_integer_t m, igraph_bool_t directed,
                              igraph_neimode_t mode);

G(n1, n2, m) 模型均匀地抽样具有 n1 个底部顶点和 n2 个顶部顶点，以及精确的 m 条边的二分图。

参数：

`图`:	指向一个未初始化的 igraph 图，结果存储在此处。
`types`:	指向一个初始化的布尔向量，或者一个空指针。如果不是空指针，则顶点类型存储在此处。底部顶点首先出现，有 `n1` 个，然后是 `n2` 个顶部顶点。
`n1`:	底部顶点的数量。
`n2`:	顶部顶点的数量。
`m`:	边的数量。
`有向`:	布尔值，是否生成有向图。另请参见 `mode` 参数。
`模式`:	指定如何在有向图中定向边。如果它是 `IGRAPH_OUT`，则有向边从底部顶点指向顶部顶点。如果它是 `IGRAPH_IN`，则边从顶部顶点指向底部顶点。`IGRAPH_OUT` 和 `IGRAPH_IN` 不会生成互边。如果此参数是 `IGRAPH_ALL`，则每个边的方向都被独立考虑，并且可能会生成互边。此参数对于无向图将被忽略。

返回值：

错误代码。

另请参阅：

igraph_erdos_renyi_game_gnm() 用于单分图版本，igraph_bipartite_game_gnp() 用于 G(n1, n2, p) 模型。

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

2.4. `igraph_bipartite_game_gnp` — 生成具有固定连接概率的随机二分图。

igraph_error_t igraph_bipartite_game_gnp(igraph_t *graph, igraph_vector_bool_t *types,
                              igraph_integer_t n1, igraph_integer_t n2,
                              igraph_real_t p, igraph_bool_t directed,
                              igraph_neimode_t mode);

在 G(n1, n2, p) 模型中，n1 个底部顶点和 n2 个顶部顶点之间的每个可能的边都以概率 p 独立实现。

参数：

`图`:	指向一个未初始化的 igraph 图，结果存储在此处。
`types`:	指向一个初始化的布尔向量，或者一个空指针。如果不是 `NULL`，则顶点类型存储在此处。底部顶点首先出现，有 `n1` 个，然后是 `n2` 个顶部顶点。
`n1`:	底部顶点的数量。
`n2`:	顶部顶点的数量。
`p`:	连接概率。
`有向`:	布尔值，是否生成有向图。另请参见 `mode` 参数。
`模式`:	指定如何在有向图中定向边。如果它是 `IGRAPH_OUT`，则有向边从底部顶点指向顶部顶点。如果它是 `IGRAPH_IN`，则边从顶部顶点指向底部顶点。`IGRAPH_OUT` 和 `IGRAPH_IN` 不会生成互边。如果此参数是 `IGRAPH_ALL`，则每个边的方向都被独立考虑，并且可能会生成互边。此参数对于无向图将被忽略。

返回值：

错误代码。

另请参阅：

igraph_erdos_renyi_game_gnp() 用于单分图版本，igraph_bipartite_game_gnm() 用于 G(n1, n2, m) 模型。

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

3. 二分邻接矩阵

3.1. igraph_biadjacency — 从二分邻接矩阵创建一个二分图。
3.2. igraph_get_biadjacency — 将二分图转换为二分邻接矩阵。

3.1. `igraph_biadjacency` — 从二分邻接矩阵创建一个二分图。

igraph_error_t igraph_biadjacency(
    igraph_t *graph, igraph_vector_bool_t *types,
    const igraph_matrix_t *input, igraph_bool_t directed,
    igraph_neimode_t mode, igraph_bool_t multiple
);

二分（或二模）图包含两种类型的顶点，并且边总是连接不同类型的顶点。二分邻接矩阵是一个 n x m 矩阵，n 和 m 分别是两种类型顶点的数量。矩阵中的非零元素表示两个对应顶点之间的边。

请注意，此函数可以在两种模式下运行，具体取决于 multiple 参数。如果它是 false，则为二分邻接矩阵中的每个非零元素创建一个单边。如果 multiple 是 true，则矩阵元素向上舍入到最接近的非负整数，以获得在一对顶点之间创建的边的数量。

如果 multiple 是 false，则此函数不会创建多重边，但如果它是 true，则可能会创建一些。

参数：

`图`:	指向未初始化的图对象的指针。
`types`:	指向一个初始化的布尔向量，或者一个空指针。如果不是空指针，则顶点类型存储在此处。它会根据需要调整大小。
`input`:	充当此函数输入的二分邻接矩阵。
`有向`:	指定是创建无向图还是有向图。
`模式`:	指定有向图中边的方向。如果 `IGRAPH_OUT`，则边从第一类顶点（对应于行）指向第二类顶点（对应于列）；如果 `IGRAPH_IN`，则实现相反的方向；如果 `IGRAPH_ALL`，则将创建互边。
`multiple`:	如何解释矩阵元素。请参阅上面的详细信息。

返回值：

错误代码。

时间复杂度：O(n*m)，二分邻接矩阵的大小。

3.2. `igraph_get_biadjacency` — 将二分图转换为二分邻接矩阵。

igraph_error_t igraph_get_biadjacency(
    const igraph_t *graph, const igraph_vector_bool_t *types,
    igraph_matrix_t *res, igraph_vector_int_t *row_ids,
    igraph_vector_int_t *col_ids
);

在二分邻接矩阵 A 中，元素 A_ij 给出了第一分区的第 i 个顶点和第二分区的第 j 个顶点之间的边的数量。

如果图包含同一分区内的边，则此函数会发出警告。

参数：

`图`:	输入图，边的方向将被忽略。
`types`:	布尔向量，包含顶点类型。属于第一分区的顶点类型为 `false`，第二分区中的顶点类型为 `true`。
`res`:	指向一个初始化的矩阵，结果存储在此处。矩阵的元素给出了两个对应顶点之间的边的数量（与其方向无关）。行将对应于类型为 `false` 的顶点，列对应于类型为 `true` 的顶点。
`row_ids`:	指向一个初始化的向量或 `NULL`。如果不是空指针，则类型为 `false` 的顶点的 ID 存储在此处，其顺序与二分邻接矩阵的行相同。
`col_ids`:	指向一个初始化的向量或 `NULL`。如果不是空指针，则类型为 `true` 的顶点的 ID 存储在此处，其顺序与二分邻接矩阵的列相同。

返回值：

错误代码。

时间复杂度：O(|E|)，其中 |E| 是边的数量。

另请参阅：

igraph_biadjacency() 用于相反的操作。

4. 投影二模图

4.1. igraph_bipartite_projection_size — 计算二分投影中顶点和边的数量。
4.2. igraph_bipartite_projection — 创建二分（二模）网络的一个或两个投影。

4.1. `igraph_bipartite_projection_size` — 计算二分投影中顶点和边的数量。

igraph_error_t igraph_bipartite_projection_size(const igraph_t *graph,
                                     const igraph_vector_bool_t *types,
                                     igraph_integer_t *vcount1,
                                     igraph_integer_t *ecount1,
                                     igraph_integer_t *vcount2,
                                     igraph_integer_t *ecount2);

此函数计算二分网络的两个投影中顶点和边的数量。如果您有一个大的二分网络并且想要估计计算投影本身所需的内存量，这将非常有用。

参数：

`图`:	输入图。
`types`:	布尔向量，给出图的顶点类型。
`vcount1`:	指向一个 `igraph_integer_t`，第一个投影中的顶点数存储在此处。如果不需要，可以为 `NULL`。
`ecount1`:	指向一个 `igraph_integer_t`，第一个投影中的边数存储在此处。如果不需要，可以为 `NULL`。
`vcount2`:	指向一个 `igraph_integer_t`，第二个投影中的顶点数存储在此处。如果不需要，可以为 `NULL`。
`ecount2`:	指向一个 `igraph_integer_t`，第二个投影中的边数存储在此处。如果不需要，可以为 `NULL`。

返回值：

错误代码。

另请参阅：

igraph_bipartite_projection() 用于计算实际投影。

时间复杂度：O(|V|*d^2+|E|)，|V| 是顶点的数量，|E| 是边的数量，d 是图的平均（总）度数。

4.2. `igraph_bipartite_projection` — 创建二分（二模）网络的一个或两个投影。

igraph_error_t igraph_bipartite_projection(const igraph_t *graph,
                                const igraph_vector_bool_t *types,
                                igraph_t *proj1,
                                igraph_t *proj2,
                                igraph_vector_int_t *multiplicity1,
                                igraph_vector_int_t *multiplicity2,
                                igraph_integer_t probe1);

创建二分图的一个或两个投影。

如果一个图的顶点可以被划分为两个集合 V1 和 V2，使得连接仅在 V1 和 V2 之间运行，而不是在 V1 或 V2 内部，则该图被称为二分图。types 参数指定哪个顶点应被视为一个或另一个分区的成员。到 V1 的投影具有顶点集 V1，并且如果两个顶点在 V2 中至少有一个公共邻居，则它们是连接的。如果请求，公共邻居的数量将在 multiplicity1 中返回。

参数：

`图`:	二分输入图。边的方向被忽略。
`types`:	布尔向量，给出图的顶点类型。
`proj1`:	指向一个未初始化的图对象，第一个投影将在此处创建。如果它是一个空指针，则它将被忽略，另请参见 `probe1` 参数。
`proj2`:	指向一个未初始化的图对象，如果它不是一个空指针，则第二个投影将在此处创建。另请参见 `probe1` 参数。
`multiplicity1`:	指向一个向量，或者一个空指针。如果不是后者，则边的多重性将存储在此处。例如，如果在二分图中有一个 A-C-B 和一个 A-D-B 三元组（但没有更多 X，使得 A-X-B 也在图中），则投影中 A-B 边的多重性将为 2。
`multiplicity2`:	与 `multiplicity1` 相同，但适用于另一个投影。
`probe1`:	此参数可用于指定结果列表中投影的顺序。当它为非负数时，它被视为顶点 ID，并且包含此顶点的投影将是结果中的第一个。将此参数设置为非负值意味着 `proj1` 必须是非空指针。如果您不关心投影的顺序，请在此处传递 -1。

返回值：

错误代码。

另请参阅：

igraph_bipartite_projection_size() 用于计算投影中顶点和边的数量，而无需创建投影图本身。

时间复杂度：O(|V|*d^2+|E|)，|V| 是顶点的数量，|E| 是边的数量，d 是图的平均（总）度数。

5. 对二分图的其他操作

5.1. igraph_is_bipartite — 检查图是否为二分图。

5.1. `igraph_is_bipartite` — 检查图是否为二分图。

igraph_error_t igraph_is_bipartite(const igraph_t *graph,
                        igraph_bool_t *res,
                        igraph_vector_bool_t *types);

此函数检查图是否为二分图。它尝试找到一个映射，给出顶点可能划分为两类的结果，使得同一类的两个顶点不会被边连接。

存在这样的映射等价于图中没有奇数长度的环路。具有自环边的图不能是二分图。

请注意，映射不一定是唯一的，例如，如果图至少有两个组件，则可以独立映射单独组件中的顶点。

参数：

`图`:	输入图。
`res`:	指向一个布尔值，结果存储在此处。
`types`:	指向一个初始化的布尔向量，或者一个空指针。如果不是空指针并且找到了映射，则它将存储在此处。如果不是空指针，但未找到映射，则此向量的内容无效。

返回值：

错误代码。

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

6. 已弃用的函数

6.1. igraph_bipartite_game — 生成一个二分随机图（类似于 Erdős-Rényi）。
6.2. igraph_incidence — 从二分邻接矩阵创建一个二分图（已弃用的别名）。
6.3. igraph_get_incidence — 将二分图转换为二分邻接矩阵（已弃用的别名）。

6.1. `igraph_bipartite_game` — 生成一个二分随机图（类似于 Erdős-Rényi）。

igraph_error_t igraph_bipartite_game(igraph_t *graph, igraph_vector_bool_t *types,
                          igraph_erdos_renyi_t type,
                          igraph_integer_t n1, igraph_integer_t n2,
                          igraph_real_t p, igraph_integer_t m,
                          igraph_bool_t directed, igraph_neimode_t mode);

此函数已弃用；请改用 igraph_bipartite_game_gnm() 或 igraph_bipartite_game_gnp()。

参数：

图:

指向一个未初始化的 igraph 图，结果存储在此处。

types:

指向一个初始化的布尔向量，或者一个空指针。如果不是空指针，则顶点类型存储在此处。底部顶点首先出现，有 n1 个，然后是 n2 个顶部顶点。

type:

随机图的类型，可能的值

`IGRAPH_ERDOS_RENYI_GNM`	G(n,m) 图，m 条边在具有 n 个顶点的图中均匀随机选择。
`IGRAPH_ERDOS_RENYI_GNP`	G(n,p) 图，每个可能的边都以概率 p 包含在图中。

n1:

底部顶点的数量。

n2:

顶部顶点的数量。

p:

G(n,p) 图的连接概率。对于 G(n,m) 图将被忽略。

m:

G(n,m) 图的边数。对于 G(n,p) 图将被忽略。

有向:

布尔值，是否生成有向图。另请参见 mode 参数。

模式:

指定如何在有向图中定向边。如果它是 IGRAPH_OUT，则有向边从底部顶点指向顶部顶点。如果它是 IGRAPH_IN，则边从顶部顶点指向底部顶点。IGRAPH_OUT 和 IGRAPH_IN 不会生成互边。如果此参数是 IGRAPH_ALL，则每个边的方向都被独立考虑，并且可能会生成互边。此参数对于无向图将被忽略。

返回值：

错误代码。

另请参阅：

igraph_bipartite_game_gnm(), igraph_bipartite_game_gnp().

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

6.2. `igraph_incidence` — 从二分邻接矩阵创建一个二分图（已弃用的别名）。

igraph_error_t igraph_incidence(
    igraph_t *graph, igraph_vector_bool_t *types,
    const igraph_matrix_t *incidence, igraph_bool_t directed,
    igraph_neimode_t mode, igraph_bool_t multiple
);

警告

自 0.10.5 版本起已弃用。请不要在新代码中使用此函数；请改用 igraph_biadjacency()。

6.3. `igraph_get_incidence` — 将二分图转换为二分邻接矩阵（已弃用的别名）。

igraph_error_t igraph_get_incidence(const igraph_t *graph,
                         const igraph_vector_bool_t *types,
                         igraph_matrix_t *res,
                         igraph_vector_int_t *row_ids,
                         igraph_vector_int_t *col_ids);

警告

自 0.10.5 版本起已弃用。请不要在新代码中使用此函数；请改用 igraph_get_biadjacency()。

igraph 参考手册

第 30 章 二分图，即二模图

1. igraph 中的二分网络

2. 创建二模网络

2.1. igraph_create_bipartite — 创建一个二分图。

2.2. igraph_full_bipartite — 创建一个完整的二分图。

2.3. igraph_bipartite_game_gnm — 生成具有固定数量边的随机二分图。

2.4. igraph_bipartite_game_gnp — 生成具有固定连接概率的随机二分图。

3. 二分邻接矩阵

3.1. igraph_biadjacency — 从二分邻接矩阵创建一个二分图。

3.2. igraph_get_biadjacency — 将二分图转换为二分邻接矩阵。

4. 投影二模图

4.1. igraph_bipartite_projection_size — 计算二分投影中顶点和边的数量。

4.2. igraph_bipartite_projection — 创建二分（二模）网络的一个或两个投影。

5. 对二分图的其他操作

5.1. igraph_is_bipartite — 检查图是否为二分图。

6. 已弃用的函数

6.1. igraph_bipartite_game — 生成一个二分随机图（类似于 Erdős-Rényi）。

6.2. igraph_incidence — 从二分邻接矩阵创建一个二分图（已弃用的别名）。

警告

6.3. igraph_get_incidence — 将二分图转换为二分邻接矩阵（已弃用的别名）。

警告

第 30 章二分图，即二模图

2.1. `igraph_create_bipartite` — 创建一个二分图。

2.2. `igraph_full_bipartite` — 创建一个完整的二分图。

2.3. `igraph_bipartite_game_gnm` — 生成具有固定数量边的随机二分图。

2.4. `igraph_bipartite_game_gnp` — 生成具有固定连接概率的随机二分图。

3.1. `igraph_biadjacency` — 从二分邻接矩阵创建一个二分图。

3.2. `igraph_get_biadjacency` — 将二分图转换为二分邻接矩阵。

4.1. `igraph_bipartite_projection_size` — 计算二分投影中顶点和边的数量。

4.2. `igraph_bipartite_projection` — 创建二分（二模）网络的一个或两个投影。

5.1. `igraph_is_bipartite` — 检查图是否为二分图。

6.1. `igraph_bipartite_game` — 生成一个二分随机图（类似于 Erdős-Rényi）。

6.2. `igraph_incidence` — 从二分邻接矩阵创建一个二分图（已弃用的别名）。

6.3. `igraph_get_incidence` — 将二分图转换为二分邻接矩阵（已弃用的别名）。