igraph 参考手册

用于使用 igraph C 库

第 19 章. 图基序、二元组普查和三元组普查

1. igraph_dyad_census — 二元组普查，由 Holland 和 Leinhardt 定义。
2. igraph_triad_census — 三元组普查，由 Davis 和 Leinhardt 定义。
3. 查找三角形
4. 图基序
5. 已弃用的函数

本节介绍在图中查找小型诱导子图的函数。这些函数最初由 Holland 和 Leinhardt 定义，用于两个和三个顶点的子图，并命名为二元组普查和三元组普查。

1. `igraph_dyad_census` — 二元组普查，由 Holland 和 Leinhardt 定义。

igraph_error_t igraph_dyad_census(const igraph_t *graph, igraph_real_t *mut,
                       igraph_real_t *asym, igraph_real_t *null);

二元组普查意味着将有向图的每对顶点分为三类：互惠（至少存在一条从 a 到 b 以及从 b 到 a 的边）；非对称（至少存在一条从 a 到 b 或从 b 到 a 的边，但不是反向）和空（a 和 b 之间在任何方向上都没有边）。

Holland, P.W. 和 Leinhardt, S. (1970). A Method for Detecting Structure in Sociometric Data. American Journal of Sociology, 70, 492-513.

参数：

`图`:	输入图。对于无向图，不存在非对称连接。
`mut`:	指向实数的指针，互惠二元组的数量存储在此处。
`asym`:	指向实数的指针，非对称二元组的数量存储在此处。
`null`:	指向实数的指针，空二元组的数量存储在此处。

返回值：

错误代码。

另请参阅：

igraph_reciprocity(), igraph_triad_census().

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

2. `igraph_triad_census` — 三元组普查，由 Davis 和 Leinhardt 定义。

igraph_error_t igraph_triad_census(const igraph_t *graph, igraph_vector_t *res);

计算三元组普查意味着根据它包含的成对连接的类型（即互惠、非对称或无连接）对有向图中的每三个顶点进行分类。一个三元组可以处于 16 种状态之一，通常使用 Davis 和 Leinhardt 的“MAN 标签”来描述。 res 向量将包含这些计数，顺序如下

`0: 003`	A、B、C，空图。
`1: 012`	A->B, C，具有单条有向边的图。
`2: 102`	A<->B, C，两个顶点之间具有互惠连接的图。
`3: 021D`	A<-B->C，二叉出树。
`4: 021U`	A->B<-C，二叉入树。
`5: 021C`	A->B->C，有向线。
`6: 111D`	A<->B<-C.
`7: 111U`	A<->B->C.
`8: 030T`	A->B<-C, A->C.
`9: 030C`	A<-B<-C, A->C.
`10: 201`	A<->B<->C.
`11: 120D`	A<-B->C, A<->C.
`12: 120U`	A->B<-C, A<->C.
`13: 120C`	A->B->C, A<->C.
`14: 210`	A->B<->C, A<->C.
`15: 300`	A<->B<->C, A<->C，完全图。

此函数用于有向图。如果输入是无向图，则会显示警告，并且无向边将被解释为互惠。

此函数调用 igraph_motifs_randesu()，它是 FANMOD 基序查找器工具的实现，有关详细信息，请参见 igraph_motifs_randesu()。请注意，igraph_triad_census() 和 igraph_motifs_randesu() 的三元组顺序不同。

参考

Davis, J.A. 和 Leinhardt, S. (1972). The Structure of Positive Interpersonal Relations in Small Groups. In J. Berger (Ed.), Sociological Theories in Progress, Volume 2, 218-251. Boston: Houghton Mifflin.

参数：

`图`:	输入图。
`res`:	指向已初始化向量的指针，结果按照上面列表给出的相同顺序存储在此处。请注意，此顺序与 `igraph_motifs_randesu()` 使用的顺序不同。

返回值：

错误代码。

另请参阅：

igraph_motifs_randesu(), igraph_dyad_census().

时间复杂度：待定。

3. 查找三角形

3.1. igraph_count_adjacent_triangles — 计算顶点所属的三角形的数量。
3.2. igraph_count_triangles — 计算图中的三角形。
3.3. igraph_list_triangles — 查找图中的所有三角形。

3.1. `igraph_count_adjacent_triangles` — 计算顶点所属的三角形的数量。

igraph_error_t igraph_count_adjacent_triangles(const igraph_t *graph,
                              igraph_vector_t *res,
                              const igraph_vs_t vids);

参数：

`图`:	输入图。边方向和多重性将被忽略。
`res`:	已初始化向量，结果存储在此处。
`vids`:	要执行计算的顶点。

返回值：

错误模式。

另请参阅：

igraph_list_triangles() 用于列出三角形，igraph_count_triangles() 用于一次性计算所有三角形。

时间复杂度：O(d^2 n)，d 是查询顶点的平均顶点度，n 是它们的数量。

3.2. `igraph_count_triangles` — 计算图中的三角形。

igraph_error_t igraph_count_triangles(const igraph_t *graph, igraph_real_t *res);

此函数计算图中的三角形总数，即完全连接的顶点三元组。边方向、边多重性和自环将被忽略。

参数：

`图`:	图对象。边方向和多重性将被忽略。
`res`:	指向实变量的指针，结果将存储在此处。

返回值：

错误代码：IGRAPH_ENOMEM：临时数据内存不足。

另请参阅：

igraph_list_triangles(), igraph_count_adjacent_triangles(), igraph_transitivity_undirected().

时间复杂度：O(|V|*d^2)，|V| 是图中顶点的数量，d 是平均节点度。

3.3. `igraph_list_triangles` — 查找图中的所有三角形。

igraph_error_t igraph_list_triangles(const igraph_t *graph,
                          igraph_vector_int_t *res);

三角形报告为顶点 ID 三元组的长列表。使用 igraph_matrix_view_from_vector() 的 int 变体创建一个矩阵视图到向量中，其中每个三角形都存储在矩阵的一列中（请参见示例）。

参数：

`图`:	输入图，边方向将被忽略。多条边将被忽略。
`res`:	指向已初始化整数向量的指针，结果存储在此处，以顶点 ID 三元组的长列表形式存储。每个三元组都是图中的一个三角形。每个三角形只列出一次。

返回值：

错误代码。

另请参阅：

igraph_count_triangles() 用于计算三角形，igraph_adjacent_triangles() 用于计算顶点参与的三角形，igraph_transitivity_undirected() 用于计算全局聚类系数。

时间复杂度：O(d^2 n)，d 是平均度，n 是顶点的数量。

示例 19.1. 文件 examples/simple/igraph_list_triangles.c

#include <igraph.h>

int main(void) {
    igraph_t g;
    igraph_vector_int_t v;
    igraph_matrix_int_t result;

    igraph_full(&g, 5, 0, IGRAPH_NO_LOOPS);

    printf("Triangles in a full graph of 5 vertices:\n");
    igraph_vector_int_init(&v, 0);
    igraph_list_triangles(&g, &v);
    igraph_matrix_int_view_from_vector(&result, &v, /* nrow = */ 3);
    igraph_matrix_int_print(&result);
    igraph_vector_int_destroy(&v);
    igraph_destroy(&g);

    return 0;
}

4. 图基序

4.1. igraph_motifs_randesu — 计算图中基序的数量。
4.2. igraph_motifs_randesu_no — 计算图中基序的总数。
4.3. igraph_motifs_randesu_estimate — 估计图中基序的总数。
4.4. igraph_motifs_randesu_callback — 查找图中的基序并为每个基序调用一个函数。
4.5. igraph_motifs_handler_t — igraph_motifs_randesu_callback 的回调类型。

4.1. `igraph_motifs_randesu` — 计算图中基序的数量。

igraph_error_t igraph_motifs_randesu(const igraph_t *graph, igraph_vector_t *hist,
                          igraph_integer_t size, const igraph_vector_t *cut_prob);

基序是图中给定结构的小型弱连接诱导子图。有人认为，基序配置文件（即图中不同基序的数量）是不同类型的网络的特征，并且网络功能与图中的基序相关。

此函数能够查找大小为三和四的有向基序以及大小为三到六的无向基序（即网络中具有三到六个顶点的不同子图的数量）。

在大型网络中，基序的总数可能非常大，因此找到所有基序需要花费大量时间。在这种情况下，可以使用抽样方法。此函数能够通过 cut_prob 参数进行抽样。此参数给出了不探索基序搜索树的一个分支的概率。有关详细信息，请参见 S. Wernicke 和 F. Rasche：FANMOD：一种用于快速网络基序检测的工具，Bioinformatics 22(9), 1152--1153, 2006。 https://doi.org/10.1093/bioinformatics/btl038

将 cut_prob 参数设置为零向量以查找所有基序。

有向基序将在有向图中计数，无向基序将在无向图中计数。

参数：

`图`:	要在其中查找基序的图。
`hist`:	计算结果，它给出了为每个同构类找到的基序数量。有关同构类的帮助，请参见 `igraph_isoclass()`。请注意，此函数不计算未连接的同构类，并将为它们报告 NaN（更准确地说是 `IGRAPH_NAN`）。
`size`:	要搜索的基序大小。对于有向图，仅实现了 3 和 4，对于无向图，实现了 3 到 6。限制不在于基序查找代码，而在于图同构代码。
`cut_prob`:	在给定级别切割搜索树的概率向量。第一个元素是第一个级别，依此类推。要执行完整搜索并找到所有基序，请提供长度为 `size` 的全零向量，或者（自 igraph 0.10.14 起）`NULL` 指针。

返回值：

错误代码。

另请参阅：

igraph_motifs_randesu_estimate() 用于估计图中基序的数量，这有助于设置 cut_prob 参数；igraph_motifs_randesu_no() 用于计算图中给定大小的基序总数；igraph_motifs_randesu_callback() 用于为找到的每个基序调用一个回调函数；igraph_subisomorphic_lad() 用于在多于 4 个（有向）或 6 个（无向）顶点的图中查找子图；igraph_graph_count() 用于查找给定顶点数量的图的数量，即 hist 向量的长度。

时间复杂度：待定。

示例 19.2. 文件 examples/simple/igraph_motifs_randesu.c

#include <igraph.h>

/* This is a callback function suitable for use with igraph_motifs_randesu_callback().
 * It prints each motif it is calld with. */
igraph_error_t print_motif(const igraph_t *graph, igraph_vector_int_t *vids,
                          igraph_integer_t isoclass, void* extra) {
    printf("Found isoclass %2" IGRAPH_PRId ":  ", isoclass);
    igraph_vector_int_print(vids);
    return IGRAPH_SUCCESS; /* Return 'IGRAPH_SUCCESS': do not interrupt the search. */
}

int main(void) {

    igraph_t graph;
    igraph_vector_t hist;

    /* Compute the 4-motif distritbuion in Zachary's karate club network. */

    igraph_famous(&graph, "Zachary");
    igraph_vector_init(&hist, 0);

    igraph_motifs_randesu(&graph, &hist, 4, NULL);

    /* Compute the total number of motifs (connected 4-vertex subgraphs)
     * so that we can print the normalized distribution. */
    igraph_real_t sum = 0.0;
    igraph_integer_t n = igraph_vector_size(&hist);
    for (igraph_integer_t i=0; i < n; i++) {
        if (!isnan(VECTOR(hist)[i])) {
            sum += VECTOR(hist)[i];
        }
    }
    printf("4-motif distribution:\n");
    for (igraph_integer_t i=0; i < n; i++) {
        /* Print NaN values in a platform-independent manner: */
        igraph_real_printf(VECTOR(hist)[i] / sum);
        printf(" ");
    }
    printf("\n\n");

    igraph_vector_destroy(&hist);
    igraph_destroy(&graph);

    /* Identify the vertices of each three-motif in a small Kautz graph. */

    igraph_kautz(&graph, 2, 1);
    igraph_motifs_randesu_callback(&graph, 3, NULL, &print_motif, NULL);
    igraph_destroy(&graph);

    return 0;
}

4.2. `igraph_motifs_randesu_no` — 计算图中基序的总数。

igraph_error_t igraph_motifs_randesu_no(const igraph_t *graph, igraph_integer_t *no,
                             igraph_integer_t size, const igraph_vector_t *cut_prob);

此函数计算 size 个顶点上的（弱）连接诱导子图的总数，而无需将同构类分配给它们。支持任意大的基序大小。

参数：

`图`:	要研究的图对象。
`no`:	指向整数类型的指针，结果将存储在此处。
`size`:	要计数的基序的大小。
`cut_prob`:	在给定级别切割搜索树的概率向量。第一个元素是第一个级别，依此类推。要执行完整搜索并找到所有连接的子图，请提供长度为 `size` 的全零向量，或者（自 igraph 0.10.14 起）`NULL` 指针。

返回值：

错误代码。

另请参阅：

igraph_motifs_randesu(), igraph_motifs_randesu_estimate().

时间复杂度：待定。

4.3. `igraph_motifs_randesu_estimate` — 估计图中基序的总数。

igraph_error_t igraph_motifs_randesu_estimate(const igraph_t *graph, igraph_integer_t *est,
                                   igraph_integer_t size, const igraph_vector_t *cut_prob,
                                   igraph_integer_t sample_size,
                                   const igraph_vector_int_t *parsample);

此函数估计 size 个顶点上的（弱）连接诱导子图的总数。例如，n 个顶点上的无向完全图将具有一个大小为 n 的基序，以及 n 个大小为 size n - 1 的基序。作为另一个示例，一个三角形和一个单独的顶点将具有零个大小为四的基序。

此函数对于无法计算所有连接子图的大型图非常有用，因为它们太多了。

通过获取顶点样本并计算包含这些顶点的所有连接子图来进行估计。还有一个 cut_prob 参数，它给出了切割搜索树分支的概率。

参数：

`图`:	要研究的图对象。
`est`:	指向整数的指针，结果将存储在此处。
`size`:	要查找的子图的大小。
`cut_prob`:	在给定级别切割搜索树的概率向量。第一个元素是第一个级别，依此类推。要执行完整搜索并找到所有基序，请提供长度为 `size` 的全零向量，或者（自 igraph 0.10.14 起）`NULL` 指针。
`sample_size`:	用作样本的顶点数。仅当 `parsample` 参数为空指针时才使用此参数。
`parsample`:	指向已初始化向量的指针或空指针。如果是一个向量，则向量中的顶点 ID 将用作样本。如果是一个空指针，则 `sample_size` 参数将用于创建一个以均匀概率绘制的顶点样本。

返回值：

错误代码。

另请参阅：

igraph_motifs_randesu(), igraph_motifs_randesu_no().

时间复杂度：待定。

4.4. `igraph_motifs_randesu_callback` — 查找图中的基序并为每个基序调用一个函数。

igraph_error_t igraph_motifs_randesu_callback(const igraph_t *graph, igraph_integer_t size,
                                   const igraph_vector_t *cut_prob, igraph_motifs_handler_t *callback,
                                   void* extra);

与 igraph_motifs_randesu() 类似，此函数能够查找大小为三和四的有向基序以及大小为三到六的无向基序（即网络中具有三到六个顶点的不同子图的数量）。但是，该函数不是计数它们，而是会为找到的每个基序调用一个回调函数，以允许进一步测试或后处理。

与 igraph_motifs_randesu() 一样，cut_prob 参数也允许对基序进行抽样。将 cut_prob 参数设置为零向量以查找所有基序。

参数：

`图`:	要在其中查找基序的图。
`size`:	要搜索的基序的大小。目前仅实现了三和四。限制不在于基序查找代码，而在于图同构代码。
`cut_prob`:	在给定级别切割搜索树的概率向量。第一个元素是第一个级别，依此类推。要执行完整搜索并找到所有基序，请提供长度为 `size` 的全零向量，或者（自 igraph 0.10.14 起）`NULL` 指针。
`callback`:	指向 `igraph_motifs_handler_t` 类型函数的指针。每当找到新基序时，都会调用此函数。
`extra`:	要传递给回调函数的额外参数。

返回值：

错误代码。

时间复杂度：待定。

示例 19.3. 文件 examples/simple/igraph_motifs_randesu.c

#include <igraph.h>

/* This is a callback function suitable for use with igraph_motifs_randesu_callback().
 * It prints each motif it is calld with. */
igraph_error_t print_motif(const igraph_t *graph, igraph_vector_int_t *vids,
                          igraph_integer_t isoclass, void* extra) {
    printf("Found isoclass %2" IGRAPH_PRId ":  ", isoclass);
    igraph_vector_int_print(vids);
    return IGRAPH_SUCCESS; /* Return 'IGRAPH_SUCCESS': do not interrupt the search. */
}

int main(void) {

    igraph_t graph;
    igraph_vector_t hist;

    /* Compute the 4-motif distritbuion in Zachary's karate club network. */

    igraph_famous(&graph, "Zachary");
    igraph_vector_init(&hist, 0);

    igraph_motifs_randesu(&graph, &hist, 4, NULL);

    /* Compute the total number of motifs (connected 4-vertex subgraphs)
     * so that we can print the normalized distribution. */
    igraph_real_t sum = 0.0;
    igraph_integer_t n = igraph_vector_size(&hist);
    for (igraph_integer_t i=0; i < n; i++) {
        if (!isnan(VECTOR(hist)[i])) {
            sum += VECTOR(hist)[i];
        }
    }
    printf("4-motif distribution:\n");
    for (igraph_integer_t i=0; i < n; i++) {
        /* Print NaN values in a platform-independent manner: */
        igraph_real_printf(VECTOR(hist)[i] / sum);
        printf(" ");
    }
    printf("\n\n");

    igraph_vector_destroy(&hist);
    igraph_destroy(&graph);

    /* Identify the vertices of each three-motif in a small Kautz graph. */

    igraph_kautz(&graph, 2, 1);
    igraph_motifs_randesu_callback(&graph, 3, NULL, &print_motif, NULL);
    igraph_destroy(&graph);

    return 0;
}

4.5. `igraph_motifs_handler_t` — `igraph_motifs_randesu_callback` 的回调类型。

typedef igraph_error_t igraph_motifs_handler_t(const igraph_t *graph,
        igraph_vector_int_t *vids,
        igraph_integer_t isoclass,
        void* extra);

igraph_motifs_randesu_callback() 在基序搜索期间找到新基序时调用指定的回调函数。此回调函数必须是 igraph_motifs_handler_t 类型。它具有以下参数

参数：

`图`:	算法正在处理的图。当然，这不能修改。
`vids`:	刚刚找到的基序中顶点的 ID。此向量归基序搜索算法所有，因此请勿修改或销毁它；如果以后需要它，请复制它。
`isoclass`:	刚刚找到的基序的同构类。使用 `igraph_graph_count()` 查找给定大小的图的最大可能同构类。有关更多信息，请参见 `igraph_isoclass` 和 `igraph_isoclass_subgraph`。
`extra`:	传递给 `igraph_motifs_randesu_callback()` 的额外参数。

返回值：

IGRAPH_SUCCESS 继续基序搜索，IGRAPH_STOP 停止基序搜索并正常返回给调用者。任何其他返回值都将被解释为 igraph 错误代码，这将终止搜索并将相同的错误代码返回给调用者。

另请参阅：

igraph_motifs_randesu_callback()

5. 已弃用的函数

5.1. igraph_adjacent_triangles — 计算顶点所属的三角形的数量（已弃用的别名）。

5.1. `igraph_adjacent_triangles` — 计算顶点所属的三角形的数量（已弃用的别名）。

igraph_error_t igraph_adjacent_triangles(const igraph_t *graph,
                                         igraph_vector_t *res,
                                         const igraph_vs_t vids);

警告

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

参数：

`图`:	输入图。边方向和多重性将被忽略。
`res`:	已初始化向量，结果存储在此处。
`vids`:	要执行计算的顶点。

返回值：

错误模式。

另请参阅：

igraph_list_triangles() 用于列出它们。

时间复杂度：O(d^2 n)，d 是查询顶点的平均顶点度，n 是它们的数量。

igraph 参考手册

第 19 章. 图基序、二元组普查和三元组普查

1. igraph_dyad_census — 二元组普查，由 Holland 和 Leinhardt 定义。

2. igraph_triad_census — 三元组普查，由 Davis 和 Leinhardt 定义。

3. 查找三角形

3.1. igraph_count_adjacent_triangles — 计算顶点所属的三角形的数量。

3.2. igraph_count_triangles — 计算图中的三角形。

3.3. igraph_list_triangles — 查找图中的所有三角形。

4. 图基序

4.1. igraph_motifs_randesu — 计算图中基序的数量。

4.2. igraph_motifs_randesu_no — 计算图中基序的总数。

4.3. igraph_motifs_randesu_estimate — 估计图中基序的总数。

4.4. igraph_motifs_randesu_callback — 查找图中的基序并为每个基序调用一个函数。

4.5. igraph_motifs_handler_t — igraph_motifs_randesu_callback 的回调类型。

5. 已弃用的函数

5.1. igraph_adjacent_triangles — 计算顶点所属的三角形的数量（已弃用的别名）。

警告

1. `igraph_dyad_census` — 二元组普查，由 Holland 和 Leinhardt 定义。

2. `igraph_triad_census` — 三元组普查，由 Davis 和 Leinhardt 定义。

3.1. `igraph_count_adjacent_triangles` — 计算顶点所属的三角形的数量。

3.2. `igraph_count_triangles` — 计算图中的三角形。

3.3. `igraph_list_triangles` — 查找图中的所有三角形。

4.1. `igraph_motifs_randesu` — 计算图中基序的数量。

4.2. `igraph_motifs_randesu_no` — 计算图中基序的总数。

4.3. `igraph_motifs_randesu_estimate` — 估计图中基序的总数。

4.4. `igraph_motifs_randesu_callback` — 查找图中的基序并为每个基序调用一个函数。

4.5. `igraph_motifs_handler_t` — `igraph_motifs_randesu_callback` 的回调类型。

5.1. `igraph_adjacent_triangles` — 计算顶点所属的三角形的数量（已弃用的别名）。