igraph.community

模块文档
（源代码）

未文档化

函数 _community_edge_betweenness 基于网络中边的介数（betweenness）的社区结构。
函数 _community_fastgreedy 基于模块度贪婪优化的社区结构。
函数 _community_infomap 根据 Martin Rosvall 和 Carl T. Bergstrom 的 Infomap 方法，查找网络的社区结构。
函数 _community_label_propagation 根据 Raghavan 等人的标签传播方法，查找图的社区结构。
函数 _community_leading_eigenvector Newman 发现社区结构的主导特征向量方法。
函数 _community_leiden 使用 Traag, van Eck & Waltman 的 Leiden 算法查找图的社区结构。
函数 _community_multilevel 基于 Blondel 等人多级算法的社区结构。
函数 _community_optimal_modularity 计算图的最佳模块化分数和相应的社区结构。
函数 _community_spinglass 根据 Reichardt & Bornholdt 的自旋玻璃社区检测方法查找图的社区结构。
函数 _community_walktrap Latapy & Pons 提出的基于随机游走的社区检测算法。
函数 _k_core 返回图的某些 k-核。
函数 _modularity 计算图对于给定聚类的模块度分数。
函数 _optimal_cluster_count_from_merges_and_modularity 辅助函数，用于根据合并矩阵和每次合并后的模块度值列表，为图的层次聚类找到最优聚类计数。
def _community_edge_betweenness(graph, clusters=None, directed=True, weights=None): (source)

基于网络中边的介数（betweenness）的社区结构。

其思想是，连接两个社区的边的介数通常很高，因为许多不同社区节点间的最短路径都经过这些边。因此，我们逐渐移除介数最高的边，并在每次移除后重新计算介数。这样，网络迟早会分裂成独立的组件。聚类结果将以树状图表示。

参数
图（graph）未文档化
聚类数（clusters）我们希望看到的聚类数量。这实际上定义了我们“切分”树状图以获取顶点成员向量的“级别”。如果为无（None），则当图未加权时，树状图会在最大化模块度的级别处被切分；否则，树状图会在单个聚类处被切分（因为如果所有权重不相等，基于模块度的聚类计数选择对该方法没有意义）。
有向（directed）是否考虑边的方向性。
权重（weights）边属性的名称或包含边权重的列表。
返回
一个 VertexDendrogram 对象，最初在最大模块度或期望的聚类数处被切分。
def _community_fastgreedy(graph, weights=None): (source)

基于模块度贪婪优化的社区结构。

该算法以贪婪地最大化图的模块度分数的方式，将单个节点合并成社区。可以证明，如果没有任何合并能够增加当前的模块度分数，算法就可以停止，因为无法再进一步增加。

据称该算法在稀疏图上运行时间接近线性。

参考文献: A Clauset, MEJ Newman and C Moore: Finding community structure in very large networks. Phys Rev E 70, 066111 (2004)。

参数
图（graph）未文档化
权重（weights）边属性名称或包含边权重的列表
返回
一个合适的 VertexDendrogram 对象。
def _community_infomap(graph, edge_weights=None, vertex_weights=None, trials=10): (source)

根据 Martin Rosvall 和 Carl T. Bergstrom 的 Infomap 方法，查找网络的社区结构。

参考文献

参数
图（graph）未文档化
边权重（edge_weights）边属性的名称或包含边权重的列表。
顶点权重（vertex_weights）顶点属性的名称或包含顶点权重的列表。
尝试次数（trials）划分网络的尝试次数。
返回
一个合适的 VertexClustering 对象，带有一个额外的属性，名为编码长度（codelength），用于存储算法确定的编码长度。
def _community_label_propagation(graph, weights=None, initial=None, fixed=None): (source)

根据 Raghavan 等人的标签传播方法，查找图的社区结构。

最初，每个顶点被分配一个不同的标签。之后，在每次迭代中，每个顶点选择其邻域中的主导标签。冲突随机解决，并且在每次迭代之前，顶点的更新顺序会被随机化。当顶点达成一致时，算法结束。

请注意，由于冲突是随机解决的，因此无法保证算法在每次运行后返回相同的社区结构。事实上，它们经常不同。请参阅 Raghavan 等人的论文，了解如何生成聚合的社区结构。

另请注意，社区_标签_（数字）没有语义含义，igraph 可以自由地重新编号社区。如果您使用固定标签，igraph 仍然可以重新编号社区，但会尊重共同社区成员关系约束：如果您有两个固定标签的顶点属于同一社区，它们在结束时仍将属于同一社区。同样，如果您有两个固定标签的顶点属于不同社区，它们在结束时仍将属于不同社区。

参考文献: 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://arxiv.org/abs/0709.2938。

参数
图（graph）未文档化
权重（weights）边属性的名称或包含边权重的列表
初始值（initial）顶点属性的名称或包含初始顶点标签的列表。标签由从零到 n − 1 的整数标识，其中 n 是顶点数量。此向量中也可能存在负数，它们表示未标记的顶点。
固定（fixed）每个顶点的布尔值列表。真（True）对应于算法执行期间其标签不应更改的顶点。它仅在也给定初始标签时才有意义。未标记的顶点不能被固定。它也可以是顶点属性的名称；每个属性值将被解释为布尔值。
返回
一个合适的 VertexClustering 对象。
def _community_leading_eigenvector(graph, clusters=None, weights=None, arpack_options=None): (source)

Newman 发现社区结构的主导特征向量方法。

这是递归分裂算法的正确实现：每次分裂都是通过最大化相对于原始网络的模块度来完成的。

参考文献: MEJ Newman: Finding community structure in networks using the eigenvectors of matrices, arXiv:physics/0605087

参数
图（graph）未文档化
聚类数（clusters）期望的社区数量。如果为无（None），算法会尝试进行尽可能多的分裂。请注意，如果主导特征向量的所有符号都相同，算法将不会进一步分裂社区，因此实际发现的社区数量可能少于期望的数量。
权重（weights）边属性的名称或包含边权重的列表。
arpack_options用于微调 ARPACK 特征向量计算的 ARPACKOptions 对象。如果省略，则使用模块级变量arpack_选项（arpack_options）指定的默认调色板。
返回
一个合适的 VertexClustering 对象。
def _community_leiden(graph, objective_function='CPM', weights=None, resolution=1.0, beta=0.01, initial_membership=None, n_iterations=2, node_weights=None, **kwds): (source)

使用 Traag, van Eck & Waltman 的 Leiden 算法查找图的社区结构。

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

参数
图（graph）未文档化
目标函数（objective_function）是使用恒定波茨模型（CPM）还是模块度。必须是"CPM"或"modularity".
权重（weights）要使用的边权重。可以是序列、可迭代对象，甚至是边属性名称。
分辨率（resolution）要使用的分辨率参数。更高的分辨率会导致更多更小的社区，而更低的分辨率会导致更少更大的社区。
贝塔（beta）影响 Leiden 算法随机性的参数。这仅影响算法的细化步骤。
初始成员（initial_membership）如果提供，Leiden 算法将尝试改进此提供的成员关系。如果未提供参数，算法将简单地从单例分区开始。
迭代次数（n_iterations）Leiden 算法的迭代次数。每次迭代都可能进一步改善分区。使用负数迭代次数将运行直到遇到稳定迭代（即该迭代期间质量没有增加）。
节点权重（node_weights）Leiden 算法中使用的节点权重。如果未提供，将根据您是使用 CPM 还是模块度自动确定。如果您提供了此参数，请确保您了解正在进行的操作。
**kwds未文档化
返回
一个合适的 VertexClustering 对象，带有一个额外的属性，名为质量（quality）存储算法优化的内部质量函数的值。
def _community_multilevel(graph, weights=None, return_levels=False, resolution=1): (source)

基于 Blondel 等人多级算法的社区结构。

这是一种自下而上的算法：最初每个顶点都属于一个独立的社区，然后顶点在社区之间迭代移动，以最大化顶点对整体模块度分数的局部贡献。当达成共识（即没有任何单个移动会增加模块度分数）时，原始图中的每个社区都会收缩成一个单一顶点（同时保留入射边的总权重），并且该过程在下一级继续。当社区收缩成顶点后无法再增加模块度时，算法停止。

据称该算法在稀疏图上运行时间接近线性。

参考文献: VD Blondel, J-L Guillaume, R Lambiotte and E Lefebvre: Fast unfolding of community hierarchies in large networks, J Stat Mech P10008 (2008). https://arxiv.org/abs/0803.0476

参数
图（graph）未文档化
权重（weights）边属性名称或包含边权重的列表
返回级别（return_levels）如果真（True），每个级别的社区都以列表形式返回。如果为假（False），则只返回具有最佳模块度的社区结构。
分辨率（resolution）模块度度量中使用的分辨率参数。较小的值会产生数量较少但规模较大的聚类，而较大的值会产生数量较多但规模较小的聚类。经典的模块度度量假定分辨率参数为 1。
返回
一个 VertexClustering 对象列表，每个级别对应一个（如果return_levels为真（True）），或一个对应于最佳模块度的 VertexClustering。
def _community_optimal_modularity(graph, *args, **kwds): (source)

计算图的最佳模块化分数和相应的社区结构。

此函数使用 GNU 线性规划工具包来解决一个大型整数优化问题，以找到最优的模块度分数和相应的社区结构，因此它不太可能适用于顶点数量较多（少于一百个）的图。如果您有如此大的图，请考虑使用启发式方法。

返回
计算出的成员向量和相应的模块度，以元组形式返回。
def _community_spinglass(graph, *args, **kwds): (source)

根据 Reichardt & Bornholdt 的自旋玻璃社区检测方法查找图的社区结构。

参考文献

参数
图（graph）未文档化
*args未文档化
权重（weights）要使用的边权重。可以是序列、可迭代对象，甚至是边属性名称。
自旋数（spins）整数，要使用的自旋数。这是社区数量的上限。提供一个（合理地）大的数字在这里不是问题，这种情况下某些自旋状态将不会被填充。
并行更新（parupdate）是否并行（同步）更新顶点的自旋
起始温度（start_temp）起始温度
停止温度（stop_temp）停止温度
冷却因子（cool_fact）模拟退火的冷却因子
更新规则（update_rule）指定模拟的空模型。可能的值是"config"（与输入图具有相同顶点度数的随机图）或"simple"（具有相同边数的随机图）
伽马（gamma）算法的 gamma 参数，指定社区内存在边和缺失边之间的重要性平衡。默认值为 1.0，表示两者同等重要。
实现（implementation）当前 igraph 包含两种自旋玻璃社区检测算法的实现。更快的原始实现是默认的。另一种实现能够考虑负权重，可以通过设置为实现（implementation）设置为"neg"
lambda_算法的 lambda 参数，它指定了社区内存在负权重边和缺失负权重边之间的重要性平衡。较小的 lambda 值会导致社区内部连通性负值较少。如果参数为零，算法将简化为图着色算法，使用自旋数作为颜色。如果使用原始实现，则忽略此参数。请注意参数名称末尾的下划线；这是因为 lambda 是 Python 中的保留关键字。
返回
一个合适的 VertexClustering 对象。
def _community_walktrap(graph, weights=None, steps=4): (source)

Latapy & Pons 提出的基于随机游走的社区检测算法。

该算法的基本思想是短的随机游走倾向于停留在同一个社区中。聚类结果将以树状图表示。

参考文献: Pascal Pons, Matthieu Latapy: Computing communities in large networks using random walks, https://arxiv.org/abs/physics/0512106。

参数
图（graph）未文档化
权重（weights）边属性的名称或包含边权重的列表
步数（steps）执行随机游走的长度
返回
一个 VertexDendrogram 对象，最初在最大模块度处被切分。
def _k_core(graph, *args): (source)

返回图的某些 k-核。

该方法接受任意数量的参数，这些参数表示要返回的 k-核的期望索引。参数也可以是列表或元组。如果只给出了一个整数参数，结果将是一个 Graph 对象，否则结果将是一个 Graph 对象列表，按照参数指定的顺序表示所需的 k-核。如果没有给出参数，则返回所有 k-核，并按 k 递增的顺序排列。

def _modularity(self, membership, weights=None, resolution=1, directed=True): (source)

计算图对于给定聚类的模块度分数。

图对于某个划分的模块度衡量了划分的优劣，或者不同顶点类型之间的分离程度。它定义为 Q = 1 ⁄ (2m)*sum(Aij − gamma*ki*kj ⁄ (2m)delta(ci, cj), i, j)。m 是边数，Aij 是 A 邻接矩阵中第 i 行第 j 列的元素，ki 是节点 i 的度，kj 是节点 j 的度，Ci 和cj是两个顶点（i 和 j）的类型，gamma 是一个分辨率参数，对于模块度的经典定义，其默认值为 1。delta(x, y) 当且仅当 x = y 时为 1，否则为 0。

如果给出了边权重，模块度的定义修改如下：Aij 变为对应边的权重，ki 是与顶点 i 相邻的边总权重，kj 是与顶点 j 相邻的边总权重，m 是图中的总边权重。

参考文献: MEJ Newman and M Girvan: Finding and evaluating community structure in networks. Phys Rev E 69 026113, 2004。

参数
自身（self）未文档化
成员关系（membership）成员列表或一个 VertexClustering 对象
权重（weights）可选的边权重或无（None）如果所有边权重相等。也允许属性名称。
分辨率（resolution）上述公式中的分辨率参数 gamma。当分辨率参数设置为 1 时，即得到模块度的经典定义。
有向（directed）如果图是有向的，是否考虑边的方向。真（True）将使用模块度度量的有向变体，其中节点的入度和出度分别处理；假（False）将有向图视为无向图。
返回
模块度分数
def _optimal_cluster_count_from_merges_and_modularity(graph, merges: Sequence[tuple[int, int]], qs: list[float]) -> float: (source)

辅助函数，用于根据合并矩阵和每次合并后的模块度值列表，为图的层次聚类找到最优聚类计数。

作为副作用，反转模块度向量。