最佳社区结构

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

用法

cluster_optimal(graph, weights = NULL)

参数

graph

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

weights

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

值

cluster_optimal() 返回一个 communities() 对象，有关详细信息，请参见 communities() 手册页面。

详细信息

此函数计算图的最优社群结构，以最大模块度分数为衡量标准。

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

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

示例

## 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))

参考文献

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() 以获得快速贪婪优化器。

社群检测 as_membership(), cluster_edge_betweenness(), cluster_fast_greedy(), cluster_fluid_communities(), cluster_infomap(), cluster_label_prop(), cluster_leading_eigen(), cluster_leiden(), cluster_louvain(), cluster_spinglass(), cluster_walktrap(), compare(), groups(), make_clusters(), membership(), modularity.igraph(), plot_dendrogram(), split_join_distance(), voronoi_cells()

作者

Gabor Csardi csardi.gabor@gmail.com