R igraph 手册页

cluster_optimal {igraph}

R 文档

最佳社群结构

描述

此函数计算图的最佳社群结构，通过最大化所有可能划分上的模块度指标。

用法

cluster_optimal(graph, weights = NULL)

参数

图	输入图。 对于有向图，边缘方向将被忽略。
weights	边的权重。 必须是正数值向量、NULL 或 NA。 如果是 NULL 并且输入图具有 ‘weight’ 边属性，则将使用该属性。 如果是 NULL 且不存在此类属性，则边的权重将相等。 如果该图曾是 ‘weight’ 边属性，但您不想将其用于社群检测，请将其设置为 NA。 较大的边权重意味着此函数的连接更强。

详细信息

此函数计算图的最佳社群结构，以最大模块度得分衡量。

计算是通过将模块度最大化转换为整数规划问题，然后调用 GLPK 库来解决该问题来完成的。 详情请参阅下面的参考资料。

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

值

cluster_optimal 返回一个 communities 对象，请参阅 communities 手册页面以获取详细信息。

示例

## Zachary's karate club
g <- make_graph("Zachary")

## We put everything into a big 'try' block, in case
## igraph was compiled without GLPK support

## The calculation only takes a couple of seconds
oc <- cluster_optimal(g)

## Double check the result
print(modularity(oc))
print(modularity(g, membership(oc)))

## Compare to the greedy optimizer
fc <- cluster_fast_greedy(g)
print(modularity(fc))

作者

Gabor Csardi csardi.gabor@gmail.com

参考

Ulrik Brandes, Daniel Delling, Marco Gaertler, Robert Gorke, Martin Hoefer, Zoran Nikoloski, Dorothea Wagner: On Modularity Clustering, IEEE Transactions on Knowledge and Data Engineering 20(2):172-188, 2008.

参见

communities 用于结果的文档，modularity。 另请参阅 cluster_fast_greedy 以获取快速贪婪优化器。

---