igraph 参考手册

用于使用 igraph C 库

搜索手册
上一个 首页 下一个

第 24 章。检测社区结构

1. 与社区结构相关的常用函数
2. 基于统计力学的社区结构
3. 基于矩阵特征向量的社区结构
4. Walktrap：基于随机游走的社区结构
5. 基于边介数的社区检测
6. 基于模块化优化的社区结构
7. 流体社区
8. 标签传播
9. InfoMAP 算法
10. Voronoi 社区

社区检测关注将网络的顶点聚类成紧密连接的子图，称为“社区”。以下参考文献提供了社区检测主题的一个很好的介绍

S. Fortunato: "Graphs 中社区检测"。物理报告 486, no. 3–5 (2010): 75–174. https://doi.org/10.1016/j.physrep.2009.11.002。

S. Fortunato 和 D. Hric: "Networks 中的社区检测：用户指南"。物理报告 659 (2016): 1–44. https://doi.org/10.1016/j.physrep.2016.09.002。

1. 与社区结构相关的常用函数

1.1. igraph_modularity — 计算图相对于某些聚类或顶点类型的模块化。
1.2. igraph_modularity_matrix — 计算模块化矩阵。
1.3. igraph_community_optimal_modularity — 计算具有最高模块化值的社区结构。
1.4. igraph_community_to_membership — 从社区结构树状图创建一个成员向量。
1.5. igraph_reindex_membership — 使成员向量中的 ID 连续。
1.6. igraph_compare_communities — 使用各种指标比较社区结构。
1.7. igraph_split_join_distance — 计算两个社区结构的拆分-连接距离。

1.1. igraph_modularity — 计算图相对于某些聚类或顶点类型的模块化。

igraph_error_t igraph_modularity(const igraph_t *graph,
                      const igraph_vector_int_t *membership,
                      const igraph_vector_t *weights,
                      const igraph_real_t resolution,
                      const igraph_bool_t directed,
                      igraph_real_t *modularity);

图相对于顶点的某些聚类（或顶点类型的分配）的模块化衡量了与随机零模型相比，不同聚类彼此分离的程度。它被定义为

Q = 1/(2m) sum_ij (A_ij - γ k_i k_j / (2m)) δ(c_i,c_j),

其中 m 是边的数量，A_ij 是邻接矩阵，k_i 是顶点 i 的度，c_i 是顶点 i 所属的聚类（或其顶点类型），如果 i=j 则 δ(i,j)=1，否则为 0，并且总和遍历所有 i、j 顶点对。请注意，在此公式中，邻接矩阵的对角线包含自环数量的两倍。

分辨率参数 γ 允许对随机零模型进行加权，这可能在找到具有高模块化的分区时很有用。在寻找具有高模块化的分区时，使用较高的分辨率参数最大化模块化通常会导致更多、更小的聚类。较低的值通常会导致更少、更大的聚类。当设置 γ = 1 时，将检索模块化的原始定义。

也可以在有向图上计算模块化。这只需要相对适度的改变，

Q = 1/m sum_ij (A_ij - γ k^out_i k^in_j / m) δ(c_i,c_j),

其中 k^out_i 是节点 i 的出度，k^in_j 是节点 j 的入度。

加权图上的模块化也很有意义。当考虑边权重时，A_ij 等于相应边的权重（如果不存在边则为 0），k_i 是顶点 i 的强度（即加权度），对于有向图，有类似的对应项，m 是所有边的总权重。

请注意，模块化对于没有边的图没有明确定义。 igraph 为没有边的图返回 NaN；有关详细讨论，请参见 https://github.com/igraph/igraph/issues/1539。

有关模块化的原始定义，请参见 Newman, M. E. J., 和 Girvan, M. (2004)。在网络中寻找和评估社区结构。物理评论 E 69, 026113. https://doi.org/10.1103/PhysRevE.69.026113

有关模块化的有向定义，请参见 Leicht, E. A., 和 Newman, M. E. J. (2008)。有向网络中的社区结构。物理评论快报 100, 118703. https://doi.org/10.1103/PhysRevLett.100.118703

有关分辨率参数 γ 的介绍，请参见 Reichardt, J., 和 Bornholdt, S. (2006)。社区检测的统计力学。物理评论 E 74, 016110. https://doi.org/10.1103/PhysRevE.74.016110

参数： 

图:

输入图。

membership:

整数值的数字向量，给出每个顶点的类型，即它所属的聚类。它不必是连续的，即允许空社区。

weights:

权重向量或 NULL（如果未指定权重）。

resolution:

分辨率参数 γ。不得为负数。将其设置为 1 以使用模块化的经典定义。

有向:

是否使用模块化的有向或无向版本。对于无向图，将被忽略。

modularity:

指向实数的指针，结果将存储在此处。

返回值： 

错误代码。

另请参阅： 

igraph_modularity_matrix()

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

1.2. igraph_modularity_matrix — 计算模块化矩阵。

igraph_error_t igraph_modularity_matrix(const igraph_t *graph,
                             const igraph_vector_t *weights,
                             const igraph_real_t resolution,
                             igraph_matrix_t *modmat,
                             igraph_bool_t directed);

此函数返回模块化矩阵，该矩阵定义为

B_ij = A_ij - γ k_i k_j / (2m)

对于无向图，其中 A_ij 是邻接矩阵，γ 是分辨率参数，k_i 是顶点 i 的度，m 是图中的边数。当没有边，或者权重加起来为零时，结果是未定义的。

对于有向图，模块化矩阵更改为

B_ij = A_ij - γ k^out_i k^in_j / m

其中 k^out_i 是节点 i 的出度，k^in_j 是节点 j 的入度。

请注意，在此实现中，无向图中的自环乘以 2。如果指定了权重，则使用邻接矩阵和度的加权对应物。

参数： 

图:

输入图。

weights:

边权重，指向向量的指针。如果这是一个空指针，则假定每条边的权重为 1。

resolution:

分辨率参数 γ。不得为负数。默认值为 1。较低的值有利于更少、更大的社区；较高的值有利于更多、更小的社区。

modmat:

指向已初始化矩阵的指针，模块化矩阵存储在该矩阵中。

有向:

对于有向图：是否应将边视为无向边。对于无向图，此参数将被忽略。

另请参阅： 

igraph_modularity()

1.3. igraph_community_optimal_modularity — 计算具有最高模块化值的社区结构。

igraph_error_t igraph_community_optimal_modularity(const igraph_t *graph,
                                        igraph_real_t *modularity,
                                        igraph_vector_int_t *membership,
                                        const igraph_vector_t *weights);

此函数计算图的最佳社区结构，以最大模块化分数表示。

通过将模块化最大化转换为整数规划问题，然后调用 GLPK 库来解决该问题来完成计算。请参见 Ulrik Brandes 等人：关于模块化聚类，IEEE Transactions on Knowledge and Data Engineering 20(2):172-188, 2008 https://doi.org/10.1109/TKDE.2007.190689。

请注意，精确的模块化优化是一个 NP 完全问题，并且所有已知的算法都具有指数时间复杂度。这意味着您可能不想在较大的图上运行此函数。具有最多 50 个顶点的图应该没问题，具有几百个顶点的图可能是可以的。

参数： 

图:

输入图。它可以是无向的或有向的。

modularity:

指向实数的指针，或空指针。如果它不是空指针，则最佳模块化值将在此处返回。

membership:

指向向量的指针，或空指针。如果不是空指针，则最佳社区结构的成员向量将存储在此处。

weights:

给出边权重的向量。如果它是 NULL，则假定每条边都具有相同的权重。

返回值： 

错误代码。当 GLPK 不可用时，返回 IGRAPH_UNIMPLEMENTED。

另请参阅： 

igraph_modularity()、igraph_community_fastgreedy() 用于以贪婪方式寻找局部最优解的算法。

时间复杂度：顶点数量的指数。

示例 24.1.  文件 examples/simple/igraph_community_optimal_modularity.c

#include <igraph.h>

void prepare_weights_vector(igraph_vector_t* weights, const igraph_t* graph) {
    igraph_integer_t i, n = igraph_ecount(graph);
    igraph_vector_resize(weights, n);
    for (i = 0; i < n; i++) {
        VECTOR(*weights)[i] = i % 5;
    }
}

int main(void) {
    igraph_t graph;

    igraph_vector_int_t v;
    igraph_integer_t edges[] = { 0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, 0, 8,
                              0, 10, 0, 11, 0, 12, 0, 13, 0, 17, 0, 19, 0, 21, 0, 31,
                              1, 2, 1, 3, 1, 7, 1, 13, 1, 17, 1, 19, 1, 21, 1, 30,
                              2, 3, 2, 7, 2, 27, 2, 28, 2, 32, 2, 9, 2, 8, 2, 13,
                              3, 7, 3, 12, 3, 13, 4, 6, 4, 10, 5, 6, 5, 10, 5, 16,
                              6, 16, 8, 30, 8, 32, 8, 33, 9, 33, 13, 33, 14, 32, 14, 33,
                              15, 32, 15, 33, 18, 32, 18, 33, 19, 33, 20, 32, 20, 33,
                              22, 32, 22, 33, 23, 25, 23, 27, 23, 32, 23, 33, 23, 29,
                              24, 25, 24, 27, 24, 31, 25, 31, 26, 29, 26, 33, 27, 33,
                              28, 31, 28, 33, 29, 32, 29, 33, 30, 32, 30, 33, 31, 32, 31, 33,
                              32, 33
                            };

    igraph_vector_int_t membership;
    igraph_vector_t weights;
    igraph_real_t modularity;
    igraph_bool_t simple;
    igraph_error_t retval;

    igraph_vector_int_view(&v, edges, sizeof(edges) / sizeof(edges[0]));
    igraph_create(&graph, &v, 0, IGRAPH_UNDIRECTED);

    igraph_vector_init(&weights, 0);

    igraph_is_simple(&graph, &simple);
    if (!simple) {
        return 1;
    }

    igraph_vector_int_init(&membership, 0);

    igraph_set_error_handler(&igraph_error_handler_printignore);

    /* Zachary karate club, unweighted */
    retval = igraph_community_optimal_modularity(&graph, &modularity,
             &membership, 0);
    if (retval == IGRAPH_UNIMPLEMENTED) {
        return 77;
    }
    if (fabs(modularity - 0.4197896) > 0.0000001) {
        return 2;
    }
    /* Zachary karate club, weighted */
    prepare_weights_vector(&weights, &graph);
    igraph_community_optimal_modularity(&graph, &modularity,
                                        &membership, &weights);
    if (fabs(modularity - 0.5115767) > 0.0000001) {
        return 4;
    }
    igraph_destroy(&graph);

    /* simple graph with loop edges, unweighted */
    igraph_small(&graph, 6, IGRAPH_UNDIRECTED,
                 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 0, 0, 0, 2, 2, -1);
    igraph_community_optimal_modularity(&graph, &modularity,
                                        &membership, 0);
    if (fabs(modularity - 0.28125) > 0.00001) {
        return 3;
    }
    /* simple graph with loop edges, weighted */
    prepare_weights_vector(&weights, &graph);
    igraph_community_optimal_modularity(&graph, &modularity,
                                        &membership, &weights);
    if (fabs(modularity - 0.36686) > 0.00001) {
        return 5;
    }
    igraph_destroy(&graph);

    igraph_vector_int_destroy(&membership);
    igraph_vector_destroy(&weights);

    return 0;
}


1.4. igraph_community_to_membership — 从社区结构树状图创建一个成员向量。

igraph_error_t igraph_community_to_membership(const igraph_matrix_int_t *merges,
                                   igraph_integer_t nodes,
                                   igraph_integer_t steps,
                                   igraph_vector_int_t *membership,
                                   igraph_vector_int_t *csize);

此函数从社区结构树状图创建一个成员向量。成员向量包含每个顶点的图组件的 ID，图组件从零开始编号，有关成员向量的示例，请参见 igraph_connected_components() 的相同参数。

许多社区检测算法返回一个 merges 矩阵，igraph_community_walktrap() 和 igraph_community_edge_betweenness() 是两个示例。该矩阵包含在映射网络的层次结构时执行的合并操作。如果矩阵有 n-1 行，其中 n 是图中的顶点数，则它包含整个网络的层次结构，并且称为树状图。

此函数执行 steps 合并操作，如 merges 矩阵所规定，并返回网络的当前状态。

如果 merges 不是完整的树状图，则如果 steps 不大于 merges 中的行数，则可以执行 steps 步。

参数： 

merges:

包含合并操作的两列矩阵。有关详细语法，请参见 igraph_community_walktrap()。

nodes:

树状图中的叶节点数。

steps:

整数常量，要执行的步数。

membership:

指向已初始化向量的指针，如果不是 NULL，则成员结果将存储在此处。向量将根据需要调整大小。

csize:

指向已初始化向量的指针，或 NULL。如果不是 NULL，则组件的大小将存储在此处，向量将根据需要调整大小。

另请参阅： 

igraph_community_walktrap()、igraph_community_edge_betweenness()、igraph_community_fastgreedy() 用于社区结构检测算法。

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

1.5. igraph_reindex_membership — 使成员向量中的 ID 连续。

igraph_error_t igraph_reindex_membership(igraph_vector_int_t *membership,
                              igraph_vector_int_t *new_to_old,
                              igraph_integer_t *nb_clusters);

此函数以一种方式重新索引成员向量中的组件 ID，即新 ID 从零开始，一直到 C-1，其中 C 是原始向量中唯一组件 ID 的数量。提供的成员资格预计在 0, ..., n - 1 范围内。

参数： 

membership:

数字向量，给出每个顶点的类型，即它所属的组件。向量将就地更改。

new_to_old:

指向一个向量的指针，该向量将包含每个新组件的旧组件 ID，或者 NULL，在这种情况下，它不会返回。向量将根据需要调整大小。

nb_clusters:

指向不同聚类数量的整数的指针。如果不是 NULL，则此值将被更新以反映在成员资格中找到的不同聚类的数量。

时间复杂度：对于 n 个元素，应该是 O(n)。

1.6. igraph_compare_communities — 使用各种指标比较社区结构。

igraph_error_t igraph_compare_communities(const igraph_vector_int_t *comm1,
                               const igraph_vector_int_t *comm2, igraph_real_t* result,
                               igraph_community_comparison_t method);

此函数使用 Meila (2003) 的信息变异 (VI) 指标、Danon 等人 (2005) 的归一化互信息 (NMI)、van Dongen (2000) 的拆分-连接距离、Rand (1971) 的 Rand 索引或 Hubert 和 Arabie (1985) 的调整 Rand 索引来评估两个社区结构之间的距离。

这些度量中的一些是基于与给定顶点聚类 C 相关的离散随机变量的熵定义的。令 p_i 为随机选择的顶点属于聚类 i 的概率。那么聚类的熵为

H(C) = - sum_i p_i log p_i

类似地，我们可以根据随机顶点属于第一个聚类中的聚类 i 和第二个聚类中的聚类 j 的概率 p_ij 来定义两个聚类 C_1 和 C_2 的联合熵

H(C_1, C_2) = - sum_ii p_ij log p_ij

那么 C_1 和 C_2 的互信息为 MI(C_1, C_2) = H(C_1) + H(C_2) - H(C_1, C_2) >= 0 。较大的互信息表示两个聚类之间的高度重叠。归一化互信息，如 igraph 计算的那样，是

NMI(C_1, C_2) = 2 MI(C_1, C_2) / (H(C_1) + H(C_2)).

它从区间 (0, 1] 取值，当两个聚类重合时，达到 1。

信息变异定义为 VI(C_1, C_2) = [H(C_1) - MI(C_1, C_2)] + [H(C_2) - MI(C_1, C_2)]。信息变异的较低值表示两个聚类之间的差异较小，当它们重合时，VI = 0。igraph 使用自然单位进行信息变异，即在计算熵时使用自然对数。

Rand 索引定义为两个聚类对随机选择的顶点对的聚类成员资格达成一致的概率。考虑所有顶点对，如果两个顶点在两个聚类中都位于同一聚类中，或者在两个聚类中都位于不同的聚类中，则认为两个聚类对顶点对的成员资格达成一致。然后，Rand 索引是达成一致的顶点对的数量，除以顶点对的总数。Rand 索引为零表示两个聚类对所有顶点对的成员资格都不同意，而 1 表示两个聚类是相同的。

调整后的 Rand 索引类似于 Rand 索引，但它考虑了即使两个聚类完全随机选择，两个聚类之间的一致也可能偶然发生。因此，调整后的 Rand 索引从 Rand 索引的值中减去预期的一致分数，并将结果除以 1 减去预期的一致分数。调整后的 Rand 索引的最大值仍然是 1（类似于 Rand 索引），表示最大一致性，但如果两个聚类之间的一致性小于偶然预期的一致性，则该值可能小于零。

有关拆分-连接距离的说明，请参见 igraph_split_join_distance()。

参考

Meilă M: 通过信息变异比较聚类。In: Schölkopf B, Warmuth MK (eds.). 学习理论和核机器：第 16 届计算学习理论年会和第 7 届核研讨会，COLT/Kernel 2003，华盛顿特区，美国。计算机科学讲义，卷。2777，施普林格，2003 年。ISBN：978-3-540-40720-1. https://doi.org/10.1007/978-3-540-45167-9_14

Danon L, Diaz-Guilera A, Duch J, Arenas A: 比较社区结构识别。J Stat Mech P09008, 2005. https://doi.org/10.1088/1742-5468/2005/09/P09008

van Dongen S: 图聚类和马尔可夫聚类实验的性能标准。技术报告 INS-R0012，荷兰国家数学和计算机科学研究所，阿姆斯特丹，2000 年 5 月。 https://ir.cwi.nl/pub/4461

Rand WM: 评估聚类方法的客观标准。J Am Stat Assoc 66(336):846-850, 1971. https://doi.org/10.2307/2284239

Hubert L 和 Arabie P: 比较分区。Journal of Classification 2:193-218, 1985. https://doi.org/10.1007/BF01908075

参数： 

comm1:

第一个社区结构的成员向量

comm2:

第二个社区结构的成员向量

result:

结果存储在此处。

method:

要使用的比较方法。IGRAPH_COMMCMP_VI 选择 Meila (2003) 的信息变异 (VI) 指标，IGRAPH_COMMCMP_NMI 选择 Danon 等人 (2005) 提出的归一化互信息度量，IGRAPH_COMMCMP_SPLIT_JOIN 选择 van Dongen (2000) 的拆分-连接距离，IGRAPH_COMMCMP_RAND 选择未调整的 Rand 索引 (1971)，IGRAPH_COMMCMP_ADJUSTED_RAND 选择调整后的 Rand 索引。

返回值： 

错误代码。

另请参阅： 

igraph_split_join_distance().

时间复杂度：O(n log(n))。

1.7. igraph_split_join_distance — 计算两个社区结构的拆分-连接距离。

igraph_error_t igraph_split_join_distance(const igraph_vector_int_t *comm1,
                               const igraph_vector_int_t *comm2, igraph_integer_t *distance12,
                               igraph_integer_t *distance21);

分区 A 和 B 之间的拆分-连接距离是 A 从 B 的投影距离和 B 从 A 的投影距离之和。投影距离是不对称的度量，定义如下

首先，根据分区 B 中的所有集合评估分区 A 中的每个集合。对于分区 A 中的每个集合，找到分区 B 中最佳匹配的集合，并计算重叠大小。（匹配通过两个集合之间的重叠大小来量化）。然后，将 A 中每个集合的最大重叠大小加在一起，并从 A 中的元素数量中减去。

拆分-连接距离将在两个参数中返回，distance12 将包含第一个分区从第二个分区的投影距离，而 distance21 将是第二个分区从第一个分区的投影距离。这使得更容易检测分区是否是另一个分区的子分区，因为在这种情况下，相应的距离将为零。

参考

van Dongen S: 图聚类和马尔可夫聚类实验的性能标准。技术报告 INS-R0012，荷兰国家数学和计算机科学研究所，阿姆斯特丹，2000 年 5 月。

参数： 

comm1:

第一个社区结构的成员向量

comm2:

第二个社区结构的成员向量

distance12:

指向一个 igraph_integer_t 的指针，第一个社区结构从第二个社区结构的投影距离将在此处返回。

distance21:

指向一个 igraph_integer_t 的指针，第二个社区结构从第一个社区结构的投影距离将在此处返回。

返回值： 

错误代码。

另请参阅： 

如果您不关心单独的距离而只关心它们的总和，请使用 igraph_compare_communities() 和 IGRAPH_COMMCMP_SPLIT_JOIN 方法。

时间复杂度：O(n log(n))。

2. 基于统计力学的社区结构

2.1. igraph_community_spinglass — 基于统计力学的社区检测。
2.2. igraph_community_spinglass_single — 基于统计力学的单个节点的社区。

2.1. igraph_community_spinglass — 基于统计力学的社区检测。

igraph_error_t igraph_community_spinglass(const igraph_t *graph,
                               const igraph_vector_t *weights,
                               igraph_real_t *modularity,
                               igraph_real_t *temperature,
                               igraph_vector_int_t *membership,
                               igraph_vector_int_t *csize,
                               igraph_integer_t spins,
                               igraph_bool_t parupdate,
                               igraph_real_t starttemp,
                               igraph_real_t stoptemp,
                               igraph_real_t coolfact,
                               igraph_spincomm_update_t update_rule,
                               igraph_real_t gamma,
                               igraph_spinglass_implementation_t implementation,
                               igraph_real_t gamma_minus);

此函数实现了 Joerg Reichardt 和 Stefan Bornholdt 提出的社区结构检测算法。该算法在他们的论文中描述：社区检测的统计力学，http://arxiv.org/abs/cond-mat/0603718 。

从 0.6 版本开始，igraph 还支持该算法的扩展，该算法允许负边权重。这在 V. A. Traag 和 Jeroen Bruggeman 中描述：具有正负链接的网络中的社区检测，http://arxiv.org/abs/0811.2329 。

参数： 

图:

输入图，它可以是有向图，但算法忽略了边的方向。

weights:

给出边权重的向量，它可以是 NULL，在这种情况下，所有边的权重都相同。除非使用 IGRAPH_SPINCOMM_IMP_NEG 实现，否则边权重必须为正。

modularity:

指向实数的指针，如果不是 NULL，则解决方案的模块化分数将存储在此处。这是广义模块化，考虑了分辨率参数 gamma。有关详细信息，请参见 igraph_modularity()。

temperature:

指向实数的指针，如果不是 NULL，则算法结束时的温度将存储在此处。

membership:

指向已初始化向量或 NULL 的指针。如果不是 NULL，则聚类的结果将存储在此处。对于每个顶点，给出其聚类的数量，第一个聚类编号为零。向量将根据需要调整大小。

csize:

指向已初始化向量或 NULL 的指针。如果不是 NULL，则聚类的大小将按聚类编号顺序存储在此处。向量将根据需要调整大小。

spins:

整数给出自旋的数量，即最大聚类数。即使自旋数很高，结果中的聚类数也可能很小。

parupdate:

一个布尔常量，指示是否并行更新所有自旋。它未在 IGRAPH_SPINCOMM_INP_NEG 实现中实现。

starttemp:

实数，开始时的温度。一个合理的默认值为 1.0。

stoptemp:

实数，算法在此温度下停止。一个合理的默认值为 0.01。

coolfact:

实数，模拟退火的冷却因子。一个合理的默认值为 0.99。

update_rule:

更新规则的类型。可能的值：IGRAPH_SPINCOMM_UPDATE_SIMPLE 和 IGRAPH_SPINCOMM_UPDATE_CONFIG。基本上，此参数定义了实际聚类所基于的零模型。如果它是 IGRAPH_SPINCOMM_UPDATE_SIMPLE，则为随机图（即 G(n,p)），如果它是 IGRAPH_SPINCOMM_UPDATE，则使用配置模型。配置意味着聚类的基线是具有与输入图相同度分布的随机图。

gamma:

实数。算法的 gamma 参数，充当分辨率参数。较小的值通常会导致较大的聚类，较大的值通常会导致较小的聚类。

implementation:

常量，在 igraph 中包含的 spin-glass 算法的两个实现之间进行选择。IGRAPH_SPINCOMM_IMP_ORIG 选择原始实现，它更快，IGRAPH_SPINCOMM_INP_NEG 选择允许负边权重的实现。

gamma_minus:

实数。IGRAPH_SPINCOMM_IMP_NEG 实现的参数。这充当网络的负部分的分辨率参数。较小的 gamma_minus 值会导致聚类内的负边更少。如果将此参数设置为零，则当所有边都具有负权重时，该算法将简化为图形着色算法，使用自旋数作为颜色数。

返回值： 

错误代码。

另请参阅： 

有关计算单个顶点的社区的信息，请参见 igraph_community_spinglass_single()。

时间复杂度：待定。

2.2. igraph_community_spinglass_single — 基于统计力学的单个节点的社区。

igraph_error_t igraph_community_spinglass_single(const igraph_t *graph,
                                      const igraph_vector_t *weights,
                                      igraph_integer_t vertex,
                                      igraph_vector_int_t *community,
                                      igraph_real_t *cohesion,
                                      igraph_real_t *adhesion,
                                      igraph_integer_t *inner_links,
                                      igraph_integer_t *outer_links,
                                      igraph_integer_t spins,
                                      igraph_spincomm_update_t update_rule,
                                      igraph_real_t gamma);

此函数实现了 Joerg Reichardt 和 Stefan Bornholdt 提出的社区结构检测算法。它在他们的论文中描述：社区检测的统计力学，http://arxiv.org/abs/cond-mat/0603718 。

此函数计算单个顶点的社区，而无需计算图中的所有社区。

参数： 

图:

输入图，它可以是有向图，但该算法中未使用边的方向。

weights:

指向带有边权重的向量的指针。或者，可以提供 NULL 以使每条边具有相同的权重。

vertex:

为其计算社区的顶点的顶点 ID。

community:

指向已初始化向量的指针，结果（输入顶点的社区中顶点的 ID）将存储在此处。向量将根据需要调整大小。

cohesion:

指向实数变量的指针，如果不是 NULL，则社区的内聚指数将存储在此处。

adhesion:

指向实数变量的指针，如果不是 NULL，则社区的粘附指数将存储在此处。

inner_links:

指向整数的指针，如果不是 NULL，则社区内的边数将存储在此处。

outer_links:

指向整数的指针，如果不是 NULL，则社区和图中其余部分之间的边数将存储在此处。

spins:

要使用的自旋数，这可以高于网络中实际的聚类数，在这种情况下，某些聚类将包含零个顶点。

update_rule:

更新规则的类型。可能的值：IGRAPH_SPINCOMM_UPDATE_SIMPLE 和 IGRAPH_SPINCOMM_UPDATE_CONFIG。基本上，此参数定义了实际聚类所基于的零模型。如果它是 IGRAPH_SPINCOMM_UPDATE_SIMPLE，则为随机图（即 G(n,p)），如果它是 IGRAPH_SPINCOMM_UPDATE，则使用配置模型。配置意味着聚类的基线是具有与输入图相同度分布的随机图。

gamma:

实数。算法的 gamma 参数。这定义了聚类质量函数中缺失链接和现有链接的权重。原始代码中的默认值为 1.0，这等于缺失边和现有边的权重。较小的值使现有链接对能量函数的贡献更大，该能量函数在该算法中最小化。较大的值使缺失的链接更重要。（如果我的理解是正确的。）

返回值： 

错误代码。

另请参阅： 

对于算法的传统版本，请参见 igraph_community_spinglass()。

时间复杂度：待定。

3. 基于矩阵特征向量的社区结构

3.1. igraph_community_leading_eigenvector — 主导特征向量社区查找（正确版本）。
3.2. igraph_community_leading_eigenvector_callback_t — 主导特征向量社区查找方法的回调。
3.3. igraph_le_community_to_membership — 来自主导特征向量社区结构的顶点成员资格。

在这些部分中记录的函数实现了由 Mark Newman 开发并在 MEJ Newman 中发布的“主导特征向量”方法：使用矩阵特征向量查找社区结构，Phys Rev E 74:036104 (2006)。

该方法的核心是模块化矩阵 B = A - P 的定义，其中 A 是（无向）网络的邻接矩阵，P 包含根据“配置模型”存在的某些边的概率。换句话说，P_ij 的元素 P 是在随机网络中顶点 i 和 j 之间存在边的概率，在该随机网络中，所有顶点的度与输入图中的度相同。有关更多详细信息，请参见 igraph_modularity_matrix()。

主导特征向量方法的工作原理是计算最大正特征值模块化矩阵的特征向量，然后基于特征向量中相应元素的符号将顶点分为两个社区。如果特征向量中的所有元素都具有相同的符号，则表示网络没有潜在的社区结构。请检查 Newman 的论文，以了解为什么这是一种检测社区结构的好方法。

领先特征向量社群结构检测方法通过 igraph_community_leading_eigenvector() 实现。在初始分割之后，后续的分割将以优化相对于原始网络的模块度的方式进行。请注意，此处未实现任何进一步的优化，例如使用 Newman (2006) 第 V.A 节中提出的 Kernighan-Lin 方法。

示例 24.2.  文件 examples/simple/igraph_community_leading_eigenvector.c

#include <igraph.h>

int main(void) {

    igraph_t g;
    igraph_matrix_int_t merges;
    igraph_vector_int_t membership;
    igraph_vector_t x;
    igraph_arpack_options_t options;

    /* Zachary Karate club */
    igraph_small(&g, 0, IGRAPH_UNDIRECTED,
                 0,  1,  0,  2,  0,  3,  0,  4,  0,  5,
                 0,  6,  0,  7,  0,  8,  0, 10,  0, 11,
                 0, 12,  0, 13,  0, 17,  0, 19,  0, 21,
                 0, 31,  1,  2,  1,  3,  1,  7,  1, 13,
                 1, 17,  1, 19,  1, 21,  1, 30,  2,  3,
                 2,  7,  2,  8,  2,  9,  2, 13,  2, 27,
                 2, 28,  2, 32,  3,  7,  3, 12,  3, 13,
                 4,  6,  4, 10,  5,  6,  5, 10,  5, 16,
                 6, 16,  8, 30,  8, 32,  8, 33,  9, 33,
                 13, 33, 14, 32, 14, 33, 15, 32, 15, 33,
                 18, 32, 18, 33, 19, 33, 20, 32, 20, 33,
                 22, 32, 22, 33, 23, 25, 23, 27, 23, 29,
                 23, 32, 23, 33, 24, 25, 24, 27, 24, 31,
                 25, 31, 26, 29, 26, 33, 27, 33, 28, 31,
                 28, 33, 29, 32, 29, 33, 30, 32, 30, 33,
                 31, 32, 31, 33, 32, 33,
                 -1);

    igraph_matrix_int_init(&merges, 0, 0);
    igraph_vector_int_init(&membership, 0);
    igraph_vector_init(&x, 0);
    igraph_arpack_options_init(&options);

    igraph_community_leading_eigenvector(&g, /*weights=*/ 0, &merges,
                                         &membership, 1,
                                         &options, /*modularity=*/ 0,
                                         /*start=*/ 0, /*eigenvalues=*/ 0,
                                         /*eigenvectors=*/ 0, /*history=*/ 0,
                                         /*callback=*/ 0,
                                         /*callback_extra=*/ 0);

    igraph_matrix_int_print(&merges);
    igraph_vector_int_print(&membership);

    printf("\n");

    /* Make all the steps */
    igraph_community_leading_eigenvector(&g, /*weights=*/ 0, &merges,
                                         &membership, igraph_vcount(&g),
                                         &options, /*modularity=*/ 0,
                                         /*start=*/ 0, /*eigenvalues=*/ 0,
                                         /*eigenvectors=*/ 0, /*history=*/ 0,
                                         /*callback=*/ 0,
                                         /*callback_extra=*/ 0);

    igraph_matrix_int_print(&merges);
    igraph_vector_int_print(&membership);

    igraph_vector_destroy(&x);
    igraph_vector_int_destroy(&membership);
    igraph_matrix_int_destroy(&merges);
    igraph_destroy(&g);

    return 0;
}


3.1. igraph_community_leading_eigenvector — 领先特征向量社群发现（正确版本）。

igraph_error_t igraph_community_leading_eigenvector(
        const igraph_t *graph,
        const igraph_vector_t *weights,
        igraph_matrix_int_t *merges,
        igraph_vector_int_t *membership,
        igraph_integer_t steps,
        igraph_arpack_options_t *options,
        igraph_real_t *modularity,
        igraph_bool_t start,
        igraph_vector_t *eigenvalues,
        igraph_vector_list_t *eigenvectors,
        igraph_vector_t *history,
        igraph_community_leading_eigenvector_callback_t *callback,
        void *callback_extra);

Newman 的领先特征向量方法用于检测社群结构。这是递归、分裂算法的正确实现：每次分割都通过最大化相对于原始网络的模块度来完成，参见 MEJ Newman: Finding community structure in networks using the eigenvectors of matrices, Phys Rev E 74:036104 (2006)。https://doi.org/10.1103/PhysRevE.74.036104

参数： 

图:

输入图。边的方向将被忽略。

weights:

边的权重，对于未加权图，则为 null 指针。

merges:

算法的结果，是一个包含已执行分割信息的矩阵。但是，该矩阵是以相反的方式构建的，类似于凝聚算法的结果。与 igraph 中大多数其他分层社群检测函数不同，此矩阵中的整数表示社群索引，而不是顶点索引。如果在算法结束时（执行 steps 步之后）有 “p” 个社群，则这些社群从零编号到 p-1。矩阵的第一行包含将两个社群合并到社群 p 的第一个 “merge”（实际上是最后一次分割），第二行中的合并形成社群 p+1，依此类推。该矩阵应在调用之前初始化，并会根据需要调整大小。如果此参数为 NULL，则将被忽略。

membership:

所有分割执行完毕后，顶点成员资格将存储在此处。该向量必须在调用之前初始化，并会根据需要调整大小。如果此参数为 NULL，则将被忽略。此参数也可以用于以成员资格向量的形式提供社群发现的起始配置。在这种情况下，start 参数必须设置为 1。

steps:

要执行的最大步数。可能发生某些组件（或整个网络）没有底层社群结构，并且无法执行进一步的步骤。如果您想要尽可能多的步骤，请在此处提供网络中的顶点数。

选项:

ARPACK 的选项。在此处提供 NULL 以使用默认值。n 始终会被覆盖。ncv 设置为至少 4。

modularity:

如果不是 null 指针，则它必须是指向实数的指针，并且最终分割的模块度分数将存储在此处。

开始:

布尔值，是否使用 membership 参数中给出的社群结构作为起点。

特征值:

指向已初始化向量的指针或 null 指针。如果不是 null 指针，则沿社群结构检测计算的特征值将存储在此处。不导致分割的非正特征值也会被存储。

特征向量:

如果不是 null 指针，则在算法的每个步骤中计算的特征向量将存储在此处，以向量列表的形式存储。每个特征向量都存储在 igraph_vector_t 对象中。

历史:

指向已初始化向量的指针或 null 指针。如果不是 null 指针，则算法的轨迹将以数字方式编码存储在此处。各种操作

IGRAPH_LEVC_HIST_START_FULL

从初始状态开始算法，其中每个连通组件都是一个单独的社群。

IGRAPH_LEVC_HIST_START_GIVEN

从给定的社群结构开始算法。向量中的下一个值包含社群的初始数量。

IGRAPH_LEVC_HIST_SPLIT

将社群分割成两个社群。已分割社群的 id 在历史向量的下一个元素中给出。第一个新社群的 id 与已分割社群的 id 相同。第二个社群的 id 等于分割之前的社群数量。

IGRAPH_LEVC_HIST_FAILED

尝试分割社群，但这不值得，因为它不会导致更大的模块度值。社群的 id 在向量的下一个元素中给出。

回调:

一个 null 指针或 igraph_community_leading_eigenvector_callback_t 类型的函数。如果给定，则在每次特征向量/特征值计算后都会调用此回调函数。如果回调返回 IGRAPH_STOP，则社群发现算法停止。如果它返回 IGRAPH_SUCCESS，则算法正常继续。任何其他返回值都被视为 igraph 错误代码，并将以相同的错误代码终止算法。请参阅传递给 igraph_community_leading_eigenvector_callback_t 文档的回调的参数。

callback_extra:

要传递给回调函数的额外参数。

返回值： 

错误代码。

另请参阅： 

igraph_community_walktrap() 和 igraph_community_spinglass() 用于其他社群结构检测方法。

时间复杂度：O(|E|+|V|^2*steps)，|V| 是顶点数，|E| 是边数，“steps” 是执行的分割数。

3.2. igraph_community_leading_eigenvector_callback_t — 领先特征向量社群发现方法的回调。

typedef igraph_error_t igraph_community_leading_eigenvector_callback_t(
    const igraph_vector_int_t *membership,
    igraph_integer_t comm,
    igraph_real_t eigenvalue,
    const igraph_vector_t *eigenvector,
    igraph_arpack_function_t *arpack_multiplier,
    void *arpack_extra,
    void *extra);

igraph 中的领先特征向量社群发现实现能够在每次特征值计算后调用回调函数。此回调函数必须是 igraph_community_leading_eigenvector_callback_t 类型。以下参数将传递给回调

参数： 

membership:

实际成员资格向量，在记录新发现的特征值所暗示的潜在变化之前。

comm:

算法尝试在上次迭代中分割的社群的 id。社群 ID 从零开始索引！

特征值:

算法刚刚找到的特征值。

特征向量:

与算法刚刚找到的特征值相对应的特征向量。

arpack_multiplier:

传递给 igraph_arpack_rssolve() 以求解最后一个特征值问题的函数。

arpack_extra:

传递给 ARPACK 求解器的额外参数。

extra:

传递给 igraph_community_leading_eigenvector() 的额外参数。

另请参阅： 

igraph_community_leading_eigenvector(), igraph_arpack_function_t, igraph_arpack_rssolve().

3.3. igraph_le_community_to_membership — 来自领先特征向量社群结构的顶点成员资格。

igraph_error_t igraph_le_community_to_membership(const igraph_matrix_int_t *merges,
                                                 igraph_integer_t steps,
                                                 igraph_vector_int_t *membership,
                                                 igraph_vector_int_t *csize);

此函数从 igraph_community_leading_eigenvector() 的结果创建成员资格向量。它接受 membership 并根据提供的 merges 矩阵执行 steps 合并。

参数： 

merges:

包含合并操作的两列矩阵。有关详细语法，请参阅 igraph_community_leading_eigenvector()。这通常来自领先特征向量社群结构检测例程的输出。

steps:

根据 merges 进行的步骤数。

membership:

最初是起始成员资格向量，在输出时是执行 steps 合并后的结果成员资格向量。

csize:

可选地，社群的大小存储在此处，如果这不是 null 指针，而是已初始化的向量。

返回值： 

错误代码。

时间复杂度：O(|V|)，顶点数。

4. Walktrap：基于随机游走的社群结构

4.1. igraph_community_walktrap — 使用基于随机游走的相似性度量的社群发现。

4.1. igraph_community_walktrap — 使用基于随机游走的相似性度量的社群发现。

igraph_error_t igraph_community_walktrap(const igraph_t *graph,
                              const igraph_vector_t *weights,
                              igraph_integer_t steps,
                              igraph_matrix_int_t *merges,
                              igraph_vector_t *modularity,
                              igraph_vector_int_t *membership);

此函数是 Walktrap 社群发现算法的实现，参见 Pascal Pons, Matthieu Latapy: Computing communities in large networks using random walks, https://arxiv.org/abs/physics/0512106

目前，igraph 中使用了原始 C++ 实现，参见 https://www-complexnetworks.lip6.fr/~latapy/PP/walktrap.html 我们感谢 Matthieu Latapy 和 Pascal Pons 提供了此源代码。

与原始实现相比，图中允许存在孤立的顶点，并且假定它们具有权重为 1 的单个入射环边。

参数： 

图:

输入图，边的方向将被忽略。

weights:

给出边的权重的数字向量。如果它是 NULL 指针，则所有边将具有相等的权重。权重预计为正。

steps:

整数常数，随机游走的长度。通常，使用 3-8 之间的值可以获得良好的结果，其中 4-5 是合理的默认值。

merges:

指向矩阵的指针，算法执行的合并将存储在此处（如果不是 NULL）。每次合并都是一个两列矩阵中的一行，并且包含合并的集群的 ID。集群从零开始编号，并且集群编号小于网络中节点数的集群属于单个顶点作为单例集群。在每个步骤中，都会从两个其他集群创建一个新集群，并且其 id 将比到目前为止最大的集群 id 大 1。这意味着在第一次合并之前，我们有 n 个集群（图中顶点的数量），编号从零到 n - 1。第一次合并创建集群 n，第二次合并创建集群 n + 1，依此类推。

modularity:

指向向量的指针。如果不是 NULL，则每次合并操作后，当前聚类的模块度分数将存储在此处。

membership:

指向向量的指针。如果不是 NULL 指针，则与最大模块度分数相对应的成员资格向量将存储在此处。

返回值： 

错误代码。

另请参阅： 

igraph_community_spinglass(), igraph_community_edge_betweenness().

时间复杂度：最坏情况下为 O(|E||V|^2)，通常为 O(|V|^2 log|V|)，|V| 是顶点数，|E| 是边数。

示例 24.3.  文件 examples/simple/walktrap.c

#include <igraph.h>

int main(void) {
    igraph_t g;
    igraph_matrix_int_t merges;
    igraph_vector_t modularity;
    igraph_integer_t no_of_nodes;
    igraph_integer_t i;

    igraph_small(&g, 5, IGRAPH_UNDIRECTED,
                 0, 1, 0, 2, 0, 3, 0, 4, 1, 2, 1, 3, 1, 4, 2, 3, 2, 4, 3, 4,
                 5, 6, 5, 7, 5, 8, 5, 9, 6, 7, 6, 8, 6, 9, 7, 8, 7, 9, 8, 9, 0, 5, 4, 9, -1);
    igraph_vector_init(&modularity, 0);
    igraph_matrix_int_init(&merges, 0, 0);

    igraph_community_walktrap(&g,
                              NULL /* no weights */,
                              4 /* steps */,
                              &merges, &modularity,
                              /* membership=*/ NULL);

    no_of_nodes = igraph_vcount(&g);
    printf("Merges:\n");
    for (i = 0; i < igraph_matrix_int_nrow(&merges); i++) {
        printf("%2.1" IGRAPH_PRId " + %2." IGRAPH_PRId " -> %2." IGRAPH_PRId " (modularity %4.2f)\n",
               MATRIX(merges, i, 0), MATRIX(merges, i, 1),
               no_of_nodes + i, VECTOR(modularity)[i]);
    }

    igraph_destroy(&g);

    igraph_matrix_int_destroy(&merges);
    igraph_vector_destroy(&modularity);

    return 0;
}


5. 基于边介数的社群检测

5.1. igraph_community_edge_betweenness — 基于边介数的社群发现。
5.2. igraph_community_eb_get_merges — 计算合并，即边介数社群结构的树状图。

5.1. igraph_community_edge_betweenness — 基于边介数的社群发现。

igraph_error_t igraph_community_edge_betweenness(const igraph_t *graph,
                                      igraph_vector_int_t *removed_edges,
                                      igraph_vector_t *edge_betweenness,
                                      igraph_matrix_int_t *merges,
                                      igraph_vector_int_t *bridges,
                                      igraph_vector_t *modularity,
                                      igraph_vector_int_t *membership,
                                      igraph_bool_t directed,
                                      const igraph_vector_t *weights);

基于网络中边的介数的社群结构检测，称为 Grivan-Newman 算法。

其思想是，连接两个社群的边的介数通常很高，因为单独社群中节点之间的许多最短路径都通过它们。因此，我们逐渐从网络中删除具有最高介数的边，并在每次删除后重新计算边介数。这样，网络迟早会分成两个组件，然后在一段时间后，其中一个组件再次分成两个较小的组件，依此类推，直到所有边都被删除。这是一种分裂式分层方法，其结果是树状图。

在有向图中，当 directed 设置为 true 时，将使用有向版本的介数和模块度，但是，仅检测到分割成弱连通组件的情况。

参考

M. Girvan 和 M. E. J. Newman：社交和生物网络中的社群结构。Proc. Nat. Acad. Sci. USA 99, 7821-7826 (2002)。https://doi.org/10.1073/pnas.122653799

参数： 

图:

输入图。

removed_edges:

指向已初始化向量的指针，结果将存储在此处，已删除边的 ID 按删除顺序排列。它会根据需要调整大小。如果调用方不需要边 ID，则可以为 NULL。

edge_betweenness:

指向已初始化向量或 NULL 的指针。在前一种情况下，已删除边的边介数将存储在此处。向量会根据需要调整大小。

merges:

指向已初始化矩阵或 NULL 的指针。如果不是 NULL，则算法执行的合并将存储在此处。即使这是一个分裂算法，我们也可以向后重放它，并记录哪些两个集群被合并。集群从零开始编号，有关详细信息，请参阅 igraph_community_walktrap() 的 merges 参数。矩阵会根据需要调整大小。

bridges:

指向 NULL 的已初始化向量的指针。如果不是 NULL，则导致其中一个 merges 的所有边的 result 中的索引将放在此处。这等效于以相反的顺序将网络分成更多组件的所有边删除。

modularity:

如果不是 null 指针，则不同分割的模块度值将存储在此处，其顺序与合并矩阵相对应。如果 weights 不为 null，则模块度值将考虑权重。

membership:

如果不是 null 指针，则与最高模块度值相对应的成员资格向量将存储在此处。

有向:

布尔常量。控制是否为有向图计算有向介数（即有向路径），以及是否使用有向版本的模块度。它对于无向图将被忽略。

weights:

包含边权重的可选向量。如果为 null，将计算并使用未加权的边介数分数。如果不为 null，将计算并使用加权的边介数分数。

返回值： 

错误代码。

另请参阅： 

igraph_community_eb_get_merges(), igraph_community_spinglass(), igraph_community_walktrap().

时间复杂度：O(|V||E|^2)，因为介数计算需要 O(|V||E|)，并且我们执行 |E|-1 次。

示例 24.4.  文件 examples/simple/igraph_community_edge_betweenness.c

#include <igraph.h>

int main(void) {
    igraph_t graph;
    igraph_vector_int_t edges;
    igraph_vector_t eb, weights;
    igraph_matrix_int_t merges;
    igraph_vector_int_t bridges;

    igraph_small(&graph, 0, IGRAPH_UNDIRECTED,
                 0,1, 0,1, 0,1, -1);
    igraph_vector_init_int(&weights, 3, 1, 2, 3);
    igraph_vector_init(&eb, 0);
    igraph_vector_int_init(&edges, 0);
    igraph_matrix_int_init(&merges, 0, 0);
    igraph_vector_int_init(&bridges, 0);
    igraph_community_edge_betweenness(&graph, &edges, &eb, &merges,
                                      &bridges, /*modularity*/ NULL,
                                      /*membership*/ NULL,
                                      IGRAPH_UNDIRECTED,
                                      &weights);
    printf("edges:\n");
    igraph_vector_int_print(&edges);
    printf("edge betweenness:\n");
    igraph_vector_print(&eb);
    printf("merges:\n");
    igraph_matrix_int_print(&merges);
    printf("bridges:\n");
    igraph_vector_int_print(&bridges);

    igraph_destroy(&graph);
    igraph_vector_int_destroy(&edges);
    igraph_vector_destroy(&eb);
    igraph_vector_destroy(&weights);
    igraph_matrix_int_destroy(&merges);
    igraph_vector_int_destroy(&bridges);

    return 0;
}


5.2. igraph_community_eb_get_merges — 计算合并，即边介数社群结构的树状图。

igraph_error_t igraph_community_eb_get_merges(const igraph_t *graph,
                                   const igraph_bool_t directed,
                                   const igraph_vector_int_t *edges,
                                   const igraph_vector_t *weights,
                                   igraph_matrix_int_t *res,
                                   igraph_vector_int_t *bridges,
                                   igraph_vector_t *modularity,
                                   igraph_vector_int_t *membership);

如果您有一系列逐渐从网络中删除的边，并且您想知道网络如何分解为单独的组件，则此函数很方便。边序列可能来自 igraph_community_edge_betweenness() 函数，但这并不是必需的。请注意，igraph_community_edge_betweenness() 也可以通过其 merges 参数来计算树状图。当反向运行边删除过程并且两个组件连接在一起时，会发生合并。

参数： 

图:

输入图。

边:

包含要从网络中删除的边的向量，所有边预计在向量中恰好出现一次。

有向:

是否使用有向或无向版本的模块度。对于无向图将被忽略。

weights:

包含边权重的可选向量。如果为 null，将计算未加权的模块度分数。如果不为 null，将计算加权的模块度分数。如果 modularity 和 membership 都是 NULL 指针，则将被忽略。

res:

指向已初始化矩阵的指针，如果不是 NULL，则树状图将存储在此处，其形式与 igraph_community_walktrap() 函数相同：该矩阵有两列，每行都是由合并组件的 ID 给出的合并。组件 ID 从零开始编号，小于图中顶点数量的组件 ID 属于单个顶点。包含至少两个顶点的非平凡组件从 n 开始编号，其中 n 是图中顶点的数量。因此，如果第一行包含 a 和 b，则表示组件 a 和 b 合并到组件 n，第二行创建组件 n + 1，依此类推。矩阵会根据需要调整大小。

bridges:

指向 NULL 的已初始化向量的指针。如果不是 NULL，则导致其中一个合并的所有边的 edges 中的索引将放在此处。这等效于以相反的顺序将网络分成更多组件的所有边删除。

modularity:

如果不是 null 指针，则与合并矩阵相对应的不同分割的模块度值将存储在此处。

membership:

如果不是 null 指针，则最佳分割（就模块度而言）的成员资格向量将存储在此处。

返回值： 

错误代码。

另请参阅： 

igraph_community_edge_betweenness().

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

6. 基于模块度优化的社群结构

6.1. igraph_community_fastgreedy — 通过模块度的贪婪优化来查找社群结构。
6.2. igraph_community_multilevel — 通过模块度的多层优化（Louvain）来查找社群结构。
6.3. igraph_community_leiden — 使用 Leiden 算法查找社群结构。

6.1. igraph_community_fastgreedy — 通过模块度的贪婪优化来查找社群结构。

igraph_error_t igraph_community_fastgreedy(const igraph_t *graph,
                                const igraph_vector_t *weights,
                                igraph_matrix_int_t *merges,
                                igraph_vector_t *modularity,
                                igraph_vector_int_t *membership);

此函数实现快速贪婪模块度优化算法来查找社群结构，有关详细信息，请参阅 A Clauset, MEJ Newman, C Moore: Finding community structure in very large networks, http://www.arxiv.org/abs/cond-mat/0408187。

还实现了一些 K Wakita, T Tsurumi: Finding community structure in mega-scale social networks, http://www.arxiv.org/abs/cs.CY/0702048v1 中提出的改进。

参数： 

图:

输入图。它必须是没有多重边的图。这将进行检查，并且对于具有多重边的图，将给出错误消息。

weights:

可能是包含边权重的数字向量。对于未加权图，请在此处提供 null 指针。权重预计为非负数。

merges:

指向已初始化矩阵或 NULL 的指针，计算结果将存储在此处。该矩阵有两列，每个合并对应于一个合并，存储了两个合并组件的 ID。组件 ID 从零开始编号，并且第一个 n 个组件是单个顶点，n 是图中顶点的数量。组件 n 在第一次合并中创建，组件 n+1 在第二次合并中创建，依此类推。矩阵会根据需要调整大小。如果此参数为 NULL，则将完全忽略它。

modularity:

指向已初始化向量或 NULL 指针的指针，在前一种情况下，计算阶段的模块度分数将记录在此处。向量会根据需要调整大小。

membership:

指向向量的指针。如果不是 null 指针，则与最佳分割（就模块度而言）相对应的成员资格向量将存储在此处。

返回值： 

错误代码。

另请参阅： 

对于其他社群检测算法，请参阅 igraph_community_walktrap(), igraph_community_edge_betweenness()，要将树状图转换为成员资格向量，请使用 igraph_community_to_membership()。

时间复杂度：最坏情况下为 O(|E||V|log|V|)，通常为 O(|E|+|V|log^2|V|)，|V| 是顶点数，|E| 是边数。

示例 24.5.  文件 examples/simple/igraph_community_fastgreedy.c

#include <igraph.h>

int main(void) {
    igraph_t g;
    igraph_vector_t weights;
    igraph_matrix_int_t merges;

    igraph_matrix_int_init(&merges, 0, 0);
    igraph_vector_init_int(&weights, 8, 10, 10, 1, 1, 1, 1, 1, 1);

    igraph_small(&g, 6, IGRAPH_UNDIRECTED,
                 0,1, 1,2, 2,3, 2,4, 2,5, 3,4, 3,5, 4,5, -1);
    igraph_community_fastgreedy(&g, &weights, &merges,
                                /*modularity*/ NULL,
                                /*membership=*/ NULL);
    igraph_matrix_int_print(&merges);
    igraph_destroy(&g);
    igraph_vector_destroy(&weights);
    igraph_matrix_int_destroy(&merges);
    return 0;
}


6.2. igraph_community_multilevel — 通过模块度的多层优化（Louvain）来查找社群结构。

igraph_error_t igraph_community_multilevel(const igraph_t *graph,
                                           const igraph_vector_t *weights,
                                           const igraph_real_t resolution,
                                           igraph_vector_int_t *membership,
                                           igraph_matrix_int_t *memberships,
                                           igraph_vector_t *modularity);

此函数实现一种多层模块度优化算法来查找社群结构，有时称为 Louvain 算法。

该算法基于模块度度量和分层方法。最初，每个顶点都分配给自己的社群。在每个步骤中，顶点都以局部贪婪的方式重新分配给社群：以随机顺序，每个顶点都会移动到对其模块度贡献最高的社群。当没有顶点可以重新分配时，每个社群都被视为自己的顶点，并且该过程会重新开始，合并后的社群。当只剩下一个顶点或模块度在一个步骤中不能再增加时，该过程停止。

分辨率参数 γ 允许在不同的分辨率下查找社群。分辨率参数的较高值通常会导致更多、更小的社群。较低的值通常会导致更少、更大的社群。当设置 γ=1 时，将检索模块度的原始定义。请注意，返回的模块度值是使用指示的分辨率参数计算的。有关更多详细信息，请参阅 igraph_modularity()。

此函数的原始版本由 Tom Gregorovic 贡献。

参考

Blondel, V. D., Guillaume, J.-L., Lambiotte, R., & Lefebvre, E.: 大型网络中社群的快速展开。Journal of Statistical Mechanics: Theory and Experiment, 10008(10), 6 (2008)。https://doi.org/10.1088/1742-5468/2008/10/P10008

参数： 

图:

输入图。它必须是无向图。

weights:

包含边权重的数字向量。如果 NULL，则每条边的权重相等。权重预计为非负数。

resolution:

分辨率参数。必须大于或等于 0。较低的值有利于更少、更大的社群；较高的值有利于更多、更小的社群。将其设置为 1 以使用模块度的经典定义。

membership:

成员资格向量，结果将在此处返回。对于每个顶点，它都给出其社群的 ID。该向量必须初始化，并且会相应地调整大小。

成员资格:

数字矩阵，如果不是 NULL，则将包含每个级别之后的成员资格向量。它必须初始化，并且会相应地调整大小。

modularity:

数字向量，如果不是 NULL，则将包含每个级别之后的模块度分数。它必须初始化，并且会相应地调整大小。

返回值： 

错误代码。

时间复杂度：在稀疏图上平均接近线性。

示例 24.6.  文件 examples/simple/igraph_community_multilevel.c

#include <igraph.h>

void show_results(igraph_t *g, igraph_vector_int_t *membership, igraph_matrix_int_t *memberships, igraph_vector_t *modularity, FILE* f) {
    igraph_integer_t i, j, no_of_nodes = igraph_vcount(g);

    j = igraph_vector_which_max(modularity);
    for (i = 0; i < igraph_vector_int_size(membership); i++) {
        if (VECTOR(*membership)[i] != MATRIX(*memberships, j, i)) {
            fprintf(f, "WARNING: best membership vector element %" IGRAPH_PRId " does not match the best one in the membership matrix\n", i);
        }
    }

    fprintf(f, "Modularities:\n");
    igraph_vector_print(modularity);

    for (i = 0; i < igraph_matrix_int_nrow(memberships); i++) {
        for (j = 0; j < no_of_nodes; j++) {
            fprintf(f, "%" IGRAPH_PRId " ", MATRIX(*memberships, i, j));
        }
        fprintf(f, "\n");
    }

    fprintf(f, "\n");
}

int main(void) {
    igraph_t g;
    igraph_vector_t modularity;
    igraph_vector_int_t edges;
    igraph_vector_int_t membership;
    igraph_matrix_int_t memberships;
    igraph_integer_t i, j, k;

    igraph_vector_init(&modularity, 0);
    igraph_vector_int_init(&membership, 0);
    igraph_matrix_int_init(&memberships, 0, 0);

    igraph_rng_seed(igraph_rng_default(), 42);

    /* Unweighted test graph from the paper of Blondel et al */
    igraph_small(&g, 16, IGRAPH_UNDIRECTED,
                 0, 2, 0, 3, 0, 4, 0, 5,
                 1, 2, 1, 4, 1, 7,
                 2, 4, 2, 5, 2, 6,
                 3, 7,
                 4, 10,
                 5, 7, 5, 11,
                 6, 7, 6, 11,
                 8, 9, 8, 10, 8, 11, 8, 14, 8, 15,
                 9, 12, 9, 14,
                 10, 11, 10, 12, 10, 13, 10, 14,
                 11, 13,
                 -1);
    igraph_community_multilevel(&g, 0, 1, &membership, &memberships, &modularity);
    show_results(&g, &membership, &memberships, &modularity, stdout);

    /* Higher resolution */
    igraph_community_multilevel(&g, 0, 1.5, &membership, &memberships, &modularity);
    show_results(&g, &membership, &memberships, &modularity, stdout);

    igraph_destroy(&g);

    /* Ring of 30 cliques */
    igraph_vector_int_init(&edges, 0);
    for (i = 0; i < 30; i++) {
        for (j = 0; j < 5; j++) {
            for (k = j + 1; k < 5; k++) {
                igraph_vector_int_push_back(&edges, i * 5 + j);
                igraph_vector_int_push_back(&edges, i * 5 + k);
            }
        }
    }
    for (i = 0; i < 30; i++) {
        igraph_vector_int_push_back(&edges, i * 5 % 150);
        igraph_vector_int_push_back(&edges, (i * 5 + 6) % 150);
    }
    igraph_create(&g, &edges, 150, 0);
    igraph_community_multilevel(&g, 0, 1, &membership, &memberships, &modularity);
    show_results(&g, &membership, &memberships, &modularity, stdout);
    igraph_destroy(&g);

    igraph_vector_destroy(&modularity);
    igraph_vector_int_destroy(&membership);
    igraph_vector_int_destroy(&edges);
    igraph_matrix_int_destroy(&memberships);

    return 0;
}


6.3. igraph_community_leiden — 使用 Leiden 算法查找社群结构。

igraph_error_t igraph_community_leiden(const igraph_t *graph,
                            const igraph_vector_t *edge_weights, const igraph_vector_t *node_weights,
                            const igraph_real_t resolution_parameter, const igraph_real_t beta, const igraph_bool_t start,
                            const igraph_integer_t n_iterations,
                            igraph_vector_int_t *membership, igraph_integer_t *nb_clusters, igraph_real_t *quality);

此函数实现 Leiden 算法来查找社群结构。

它类似于多层算法，通常称为 Louvain 算法，但它更快，并产生更高质量的解决方案。它可以优化模块度和常数 Potts 模型，该模型不受分辨率限制的影响（参见 Tragg、Van Dooren 和 Nesterov）。

Leiden算法包含三个阶段：（1）节点的局部移动，（2）划分的细化，以及（3）基于细化划分的网络聚合，使用非细化划分来为聚合网络创建初始划分。在Leiden算法的局部移动过程中，仅访问邻域已更改的节点。仅进行严格改善质量函数的移动。细化是通过从每个集群内的单例划分重新开始，并逐步合并子集群来完成的。聚合时，单个集群可以由多个节点表示（这些节点是在细化中识别出的子集群）。

Leiden算法提供多个保证。Leiden算法通常是迭代的：一个迭代的输出用作下一个迭代的输入。在每次迭代中，保证所有集群都是连接良好且分隔良好的。在没有任何变化的迭代之后，保证所有节点和某些部分都已局部优化分配。请注意，即使单个迭代没有导致任何更改，后续迭代仍有可能发现一些改进。每次迭代都会探索不同的节点子集，以考虑从一个集群移动到另一个集群。最后，渐近地，保证所有集群的所有子集都已局部优化分配。更多详细信息，请参阅Traag, Waltman & van Eck (2019)。

正在优化的目标函数是

1 / 2m sum_ij (A_ij - γ n_i n_j) δ(s_i, s_j)

其中m是总边权重，A_ij是边（i，j）的权重，γ是所谓的解析度参数，n_i是节点i的节点权重，s_i是节点i的集群，如果且仅当x = y时δ(x, y) = 1，否则为0。通过设置n_i = k_i（节点i的度数）并将γ除以2m，我们可以有效地获得模块化的表达式。因此，当您将度数作为node_weights提供，并通过提供解析度参数1/(2m)（其中m是边的数量）时，将优化标准模块化。

参考

V. A. Traag, L. Waltman, N. J. van Eck: From Louvain to Leiden: guaranteeing well-connected communities. Scientific Reports, 9(1), 5233 (2019). http://dx.doi.org/10.1038/s41598-019-41695-z

V. A. Traag, P. Van Dooren, and Y. Nesterov: Narrow scope for resolution-limit-free community detection. Phys. Rev. E 84, 016114 (2011). https://doi.org/10.1103/PhysRevE.84.016114

参数： 

图:

输入图。它必须是无向图。

edge_weights:

包含边权重的数字向量。如果NULL，则每条边的权重均为1。权重不必为非负数。

node_weights:

包含节点权重的数字向量。如果NULL，则每个节点的权重均为1。

resolution_parameter:

使用的解析度参数，在文档中提到的目标函数中用gamma表示。

beta:

合并时细化步骤中使用的随机性。少量随机性（beta = 0.01）通常效果很好。

开始:

Start from membership vector.

n_iterations:

将核心Leiden算法迭代指示的次数。如果这是一个负数，它将继续迭代直到迭代没有改变聚类。

membership:

成员向量。这既用作优化的初始成员，也在适当的位置进行更新。因此，必须正确初始化。从头开始查找集群时，通常使用单例聚类开始。这可以使用igraph_vector_int_init_range()来实现。

nb_clusters:

membership中包含的集群数。如果NULL，则不会返回集群数。

quality:

划分的质量，根据文档中包含的目标函数。如果NULL，则不会计算质量。

返回值： 

错误代码。

时间复杂度：在稀疏图上接近线性。

示例 24.7.  文件 examples/simple/igraph_community_leiden.c

#include <igraph.h>

int main(void) {
    igraph_t graph;
    igraph_vector_int_t membership;
    igraph_vector_int_t degree;
    igraph_vector_t weights;
    igraph_integer_t nb_clusters, i;
    igraph_real_t quality;

    /* Set default seed to get reproducible results */
    igraph_rng_seed(igraph_rng_default(), 0);

    /* Simple unweighted graph */
    igraph_small(&graph, 10, IGRAPH_UNDIRECTED,
                 0, 1, 0, 2, 0, 3, 0, 4, 1, 2, 1, 3, 1, 4, 2, 3, 2, 4, 3, 4,
                 5, 6, 5, 7, 5, 8, 5, 9, 6, 7, 6, 8, 6, 9, 7, 8, 7, 9, 8, 9,
                 0, 5, -1);

    /* Perform Leiden algorithm using CPM for 1 iteration */
    igraph_vector_int_init(&membership, igraph_vcount(&graph));
    igraph_community_leiden(&graph, NULL, NULL, 0.05, 0.01, 0, 1, &membership, &nb_clusters, &quality);

    printf("Leiden found %" IGRAPH_PRId " clusters using CPM (resolution parameter 0.05), quality is %.4f.\n", nb_clusters, quality);
    printf("Membership: ");
    igraph_vector_int_print(&membership);
    printf("\n");

    /* Start from existing membership for 10 iterations to improve it further */
    igraph_community_leiden(&graph, NULL, NULL, 0.05, 0.01, 1, 10, &membership, &nb_clusters, &quality);

    printf("Iterated Leiden, using CPM (resolution parameter 0.05), quality is %.4f.\n", quality);
    printf("Membership: ");
    igraph_vector_int_print(&membership);
    printf("\n");

    /* Initialize degree vector to use for optimizing modularity */
    igraph_vector_int_init(&degree, igraph_vcount(&graph));
    igraph_degree(&graph, &degree, igraph_vss_all(), IGRAPH_ALL, 1);
    igraph_vector_init(&weights, igraph_vector_int_size(&degree));
    for (i = 0; i < igraph_vector_int_size(&degree); i++) {
        VECTOR(weights)[i] = VECTOR(degree)[i];
    }

    /* Perform Leiden algorithm using modularity until stable iteration */
    igraph_community_leiden(&graph, NULL, &weights, 1.0 / (2 * igraph_ecount(&graph)), 0.01, 0, -1, &membership, &nb_clusters, &quality);

    printf("Leiden found %" IGRAPH_PRId " clusters using modularity, quality is %.4f.\n", nb_clusters, quality);
    printf("Membership: ");
    igraph_vector_int_print(&membership);
    printf("\n");

    igraph_vector_destroy(&weights);
    igraph_vector_int_destroy(&degree);
    igraph_vector_int_destroy(&membership);
    igraph_destroy(&graph);

    return 0;
}


7. 流体社区

7.1. igraph_community_fluid_communities — 基于在图上相互作用的流体的社区检测。

7.1. igraph_community_fluid_communities — 基于在图上相互作用的流体的社区检测。

igraph_error_t igraph_community_fluid_communities(const igraph_t *graph,
                                       igraph_integer_t no_of_communities,
                                       igraph_vector_int_t *membership);

该算法基于这样一种简单的想法，即几种流体在非均匀环境（图拓扑）中相互作用，并根据它们的相互作用和密度进行扩展和收缩。不支持加权图。

此函数实现了以下社区检测方法：Parés F, Gasulla DG, et. al. (2018) Fluid Communities: A Competitive, Scalable and Diverse Community Detection Algorithm. In: Complex Networks & Their Applications VI: Proceedings of Complex Networks 2017 (The Sixth International Conference on Complex Networks and Their Applications), Springer, vol 689, p 229. https://doi.org/10.1007/978-3-319-72150-7_19

参数： 

图:

输入图。该图必须是简单且连通的。将忽略边方向。

no_of_communities:

要找到的社区的数量。必须大于0且少于图中顶点的数量。

membership:

结果向量，将顶点映射到它们被分配到的社区。

modularity:

如果不是空指针，则它必须是指向实数的指针。检测到的社区结构的模块化分数存储在此处。

返回值： 

错误代码。

时间复杂度：O(|E|)

8. 标签传播

8.1. igraph_community_label_propagation — 基于标签传播的社区检测。

8.1. igraph_community_label_propagation — 基于标签传播的社区检测。

igraph_error_t igraph_community_label_propagation(const igraph_t *graph,
                                       igraph_vector_int_t *membership,
                                       igraph_neimode_t mode,
                                       const igraph_vector_t *weights,
                                       const igraph_vector_int_t *initial,
                                       const igraph_vector_bool_t *fixed);

此函数实现了Raghavan、Albert和Kumara描述的基于标签传播的社区检测算法。此版本通过考虑边权重以及允许固定某些标签来扩展了原始方法。

权重考虑如下：当确定节点i的新标签时，算法迭代节点i上的所有边，并计算通向标签为0、1、2、...、k - 1的其他节点的边的总权重（其中k是可能标签的数量）。然后，节点i的新标签将是其边（在节点i上的边中）具有最高总权重的标签。

对于有向图，重要的是要知道标签只能在图的强连通分量内自由循环，并且可能仅在一个方向（或根本不）在强连通分量之间传播。如果您了解后果，则应将有向边视为有向边。

参考

Raghavan, U.N. and Albert, R. and Kumara, S.: Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E 76, 036106 (2007). https://doi.org/10.1103/PhysRevE.76.036106

Šubelj, L.: Label propagation for clustering. Chapter in "Advances in Network Clustering and Blockmodeling" edited by P. Doreian, V. Batagelj & A. Ferligoj (Wiley, New York, 2018). https://doi.org/10.1002/9781119483298.ch5 https://arxiv.org/abs/1709.05634

参数： 

图:

输入图。请注意，该算法最初是为无向图定义的。如果在此处传递有向图以将其视为无向图，则建议将mode设置为IGRAPH_ALL。

membership:

成员向量，结果在此处返回。对于每个顶点，它给出其社区（标签）的ID。

模式:

是否考虑用于标签传播的边方向，如果是，则标签应沿哪个方向传播。无向图将被忽略。IGRAPH_ALL表示忽略边方向（即使在有向图中）。IGRAPH_OUT表示沿边的自然方向传播标签。IGRAPH_IN表示向后传播标签（即从头到尾）。建议将此设置为IGRAPH_ALL，除非您对边方向的影响特别感兴趣。

weights:

权重向量，它应包含所有边的正权重。

initial:

初始状态。如果NULL，则每个顶点在一开始将具有不同的标签。否则，它必须是每个顶点都有一个条目的向量。非负值表示不同的标签，负值表示没有标签的顶点。从任何标记顶点都无法访问的未标记顶点将在标签传播过程结束时保持未标记状态，并将被标记在一个附加步骤中以避免在membership中返回负值。在无向图中，当整个连通分量未标记时，会发生这种情况。然后，每个未标记的分量将收到其自己单独的标签。在有向图中，附加标记的结果应被视为未定义，并且将来可能会更改；请不要依赖它。

fixed:

指示哪些标签是固定的布尔向量。当然，只有在您提供初始状态时才有意义，否则将忽略此元素。请注意，没有标签的顶点无法固定。对于那些带有警告的顶点，将忽略固定状态。另请注意，标签编号本身没有任何意义，igraph可能会重新编号标签。但是，共成员约束将得到尊重：可以将两个顶点固定在同一社区中或不同的社区中。

modularity:

如果不是空指针，则它必须是指向实数的指针。检测到的社区结构的模块化分数存储在此处。请注意，如果输入图是有向的，即使您将mode设置为IGRAPH_ALL，igraph也将计算有向模块化。

返回值： 

错误代码。

时间复杂度：O(m+n)

示例 24.8.  文件 examples/simple/igraph_community_label_propagation.c

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

int main(void) {
    igraph_t graph;
    igraph_vector_int_t membership;
    igraph_real_t modularity;

    igraph_famous(&graph, "Zachary"); /* We use Zachary's karate club network. */

    /* Label propagation is a stochastic method; the result will depend on the random seed. */
    igraph_rng_seed(igraph_rng_default(), 123);

    /* All igraph functions that returns their result in an igraph_vector_t must be given
       an already initialized vector. */
    igraph_vector_int_init(&membership, 0);
    igraph_community_label_propagation(
        &graph, &membership, /* mode = */ IGRAPH_ALL,
        /* weights= */ NULL, /* initial= */ NULL, /* fixed= */ NULL
        );

    /* Also calculate the modularity of the partition */
    igraph_modularity(
        &graph, &membership, /* weights= */ NULL, /* resolution = */ 1,
        /* directed= */ 0, &modularity);

    printf("%" IGRAPH_PRId " communities found; modularity score is %g.\n",
           igraph_vector_int_max(&membership) + 1, modularity);

    printf("Communities membership: ");
    igraph_vector_int_print(&membership);

    /* Destroy data structures at the end. */
    igraph_vector_int_destroy(&membership);
    igraph_destroy(&graph);

    return 0;
}


9. InfoMAP算法

9.1. igraph_community_infomap — 查找最小化随机游走轨迹的预期描述长度的社区结构。

9.1. igraph_community_infomap — 查找最小化随机游走轨迹的预期描述长度的社区结构。

igraph_error_t igraph_community_infomap(const igraph_t * graph,
                             const igraph_vector_t *e_weights,
                             const igraph_vector_t *v_weights,
                             igraph_integer_t nb_trials,
                             igraph_vector_int_t *membership,
                             igraph_real_t *codelength);

Martin Rosvall和Carl T. Bergstrom的Infomap社区检测算法的实现。该算法考虑了边方向。

有关更多详细信息，请参见数学可视化和地图生成器，网址为https://www.mapequation.org 。描述该算法的原始论文是：M. Rosvall和C. T. Bergstrom, Maps of information flow reveal community structure in complex networks, PNAS 105, 1118 (2008) (https://dx.doi.org/10.1073/pnas.0706851105, https://arxiv.org/abs/0707.0609)。有关该算法的更详细的论文是：M. Rosvall, D. Axelsson, and C. T. Bergstrom, The map equation, Eur. Phys. J. Special Topics 178, 13 (2009). (https://dx.doi.org/10.1140/epjst/e2010-01179-1, https://arxiv.org/abs/0906.1405)

使用了Martin Rosvall的原始C++实现，请参见http://www.tp.umu.se/~rosvall/downloads/infomap_undir.tgz 。在igraph中的集成由Emmanuel Navarro完成（他感谢Martin Rosvall和Carl T. Bergstrom提供此源代码）。

请注意，该图不能包含孤立的顶点。

如果您想指定一个随机种子（如原始实现中一样），则可以使用igraph_rng_seed()。

参数： 

图:

输入图。考虑了边方向。

e_weights:

数字向量，给出边的权重。随机游走者将偏爱权重高的边而不是权重低的边；从节点选择特定出站边的概率与其权重成正比。如果它是NULL，则所有边的权重都相等。权重预计为非负数。

v_weights:

数字向量，给出顶点的权重。当随机游走者需要在陷入接收器节点（即没有出站边的节点）后“传送”到新节点时，具有较高权重的顶点会受到青睐。当随机游走者传送时，选择顶点的概率与顶点的权重成正比。如果此参数为NULL，则所有顶点的权重都相等。权重预计为正数。

nb_trials:

尝试划分网络的次数（可以是等于或大于1的任何整数值）。

membership:

指向向量的指针。成员向量存储在此处。

codelength:

指向实数的指针。如果不是NULL，则分区的代码长度存储在此处。

返回值： 

错误代码。

另请参阅： 

igraph_community_spinglass(), igraph_community_edge_betweenness(), igraph_community_walktrap().

时间复杂度：待定。

10. Voronoi社区

10.1. igraph_community_voronoi — 使用Voronoi分区查找社区。

10.1. igraph_community_voronoi — 使用Voronoi分区查找社区。

igraph_error_t igraph_community_voronoi(
        const igraph_t *graph,
        igraph_vector_int_t *membership, igraph_vector_int_t *generators,
        igraph_real_t *modularity,
        const igraph_vector_t *lengths, const igraph_vector_t *weights,
        igraph_neimode_t mode, igraph_real_t r);

警告

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

此函数使用基于给定边长度除以边聚类系数的顶点的Voronoi分区来查找社区（igraph_ecc()）。生成器顶点被选择为在半径r内具有最大局部相对密度的顶点，其中顶点的局部相对密度定义为s m / (m + k)，其中s是顶点的强度，m是顶点一阶邻域内的边数，而k是只有端点在此邻域内的边数。

参考

Deritei et al., Community detection by graph Voronoi diagrams, New Journal of Physics 16, 063007 (2014) https://doi.org/10.1088/1367-2630/16/6/063007

Molnár et al., Community Detection in Directed Weighted Networks using Voronoi Partitioning, Scientific Reports 14, 8124 (2024) https://doi.org/10.1038/s41598-024-58624-4

参数： 

图:

输入图。它必须是简单的。

membership:

如果不是NULL，则在此处返回每个顶点的成员资格。

generators:

如果不是NULL，则在此处返回用于Voronoi分区的生成器点。

modularity:

如果不是NULL，则在此处返回分区的模块化分数。

lengths:

边长度，或NULL以将所有边视为具有单位长度。Voronoi分区将使用等于长度/ ECC的边长度，其中ECC是边聚类系数。

weights:

边权重，或NULL以将所有边视为具有单位权重。权重用于选择生成器点，以及用于计算模块化。

模式:

如果IGRAPH_OUT，则考虑从生成器点到所有其他节点的距离。如果IGRAPH_IN，则使用反向距离。如果IGRAPH_ALL，则忽略边方向。对于无向图，将忽略此参数。

r:

选择生成器点时要使用的半径/分辨率。此值越大，分区越少。传入一个负值以自动选择使模块化最大化的半径。

返回值： 

错误代码。

另请参阅： 

igraph_voronoi(), igraph_ecc().

时间复杂度：待定。

← Chapter 23. Vertex separators Chapter 25. Graphlets →