跳到内容

图的社区结构的模块化

来源: R/community.R
modularity.igraph.Rd

此函数计算将图划分为子图的模块化程度。

用法

# S3 method for class 'igraph'
modularity(x, membership, weights = NULL, resolution = 1, directed = TRUE, ...)

modularity_matrix(
  graph,
  membership = lifecycle::deprecated(),
  weights = NULL,
  resolution = 1,
  directed = TRUE
)

参数

x, graph

输入图。

membership

数值向量，每个顶点一个值，社区结构的成员向量。

weights

如果不是NULL，则为数值向量，给出边的权重。

resolution

分辨率参数。必须大于或等于 0。将其设置为 1 以使用模块度的经典定义。

directed

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

...

附加参数，目前没有。

值

对于modularity()，为数值标量，表示给定配置的模块度得分。

对于modularity_matrix()，为数值方阵，其阶数是图中的顶点数。

详细信息

modularity()计算图相对于给定membership向量的模块度。

图相对于某些划分（或顶点类型）的模块度衡量了划分的好坏，或者不同顶点类型之间的分离程度。它定义为 $$Q=\frac{1}{2m} \sum_{i,j} (A_{ij}-\gamma\frac{k_i k_j}{2m})\delta(c_i,c_j),$$ 其中 \(m\) 是边的数量，\(A_{ij}\) 是 \(A\) 邻接矩阵中第 \(i\) 行和第 \(j\) 列的元素，\(k_i\) 是 \(i\) 的度，\(k_j\) 是 \(j\) 的度，\(c_i\) 是 \(i\) 的类型（或组件），\(c_j\) 是 \(j\) 的类型（或组件），总和遍历所有 \(i\) 和 \(j\) 顶点对，\(\delta(x,y)\) 如果 \(x=y\) 则为 1，否则为 0。对于有向图，它定义为 $$Q = \frac{1}{m} \sum_{i,j} (A_{ij}-\gamma \frac{k_i^{out} k_j^{in}}{m})\delta(c_i,c_j).$$

分辨率参数 \(\gamma\) 允许加权随机空模型，这在找到具有高模块度的分区时可能很有用。当找到具有高模块度的分区时，使用更高的分辨率参数最大化模块度通常会导致更多、更小的集群。较低的值通常会导致更少、更大的集群。当将 \(\gamma\) 设置为 1 时，将检索模块度的原始定义。

如果给出了边权重，则这些权重被视为 \(A\) 邻接矩阵的元素，并且 \(k_i\) 是顶点 \(i\) 的相邻边的权重之和。

modularity_matrix()计算模块度矩阵。这是一个密集矩阵，它定义为邻接矩阵和配置模型空模型矩阵之差。换句话说，元素 \(M_{ij}\) 被给出为 \(A_{ij}-d_i d_j/(2m)\)，其中 \(A_{ij}\) 是（可能是加权的）邻接矩阵，\(d_i\) 是顶点 \(i\) 的度，\(m\) 是边的数量（或者如果是加权图，则为总权重）。

参考文献

Clauset, A.; Newman, M. E. J. & Moore, C. Finding community structure in very large networks, Physical Review E 2004, 70, 066111

参见

cluster_walktrap(), cluster_edge_betweenness(), cluster_fast_greedy(), cluster_spinglass(), cluster_louvain() 和 cluster_leiden() 用于各种社区检测方法。

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

作者

Gabor Csardi csardi.gabor@gmail.com

示例


g <- make_full_graph(5) %du% make_full_graph(5) %du% make_full_graph(5)
g <- add_edges(g, c(1, 6, 1, 11, 6, 11))
wtc <- cluster_walktrap(g)
modularity(wtc)
#> [1] 0.5757576
modularity(g, membership(wtc))
#> [1] 0.5757576