igraph.community

module documentation

未记录

函数	`_community_edge_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的spinglass社区检测方法找到图的社区结构。
函数	`_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) ¶

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

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

参数
graph	未记录
clusters	我们想要看到的聚类数量。这实际上定义了我们在“切割”树状图以获取顶点成员向量时的“级别”。如果`None`，则在图未加权时，树状图在最大化模块性的级别处被切割；否则，树状图在单个聚类处被切割（因为如果并非所有权重都相等，基于模块性的聚类数量选择对于此方法没有意义）。
directed	是否应考虑边的方向性。
weights	边的属性名称或包含边权重的列表。
返回
一个 `VertexDendrogram` 对象，最初在最大模块度或所需聚类数处切割。

def _community_fastgreedy(graph, weights=None): (source) ¶

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

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

该算法据说在稀疏图上几乎以线性时间运行。

参考文献: A Clauset, MEJ Newman 和 C Moore: 在非常大的网络中寻找社区结构。 物理评论 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方法找到网络的社区结构。

参考文献

M. Rosvall and C. T. Bergstrom: Maps of information flow reveal community structure in complex networks, PNAS 105, 1118 (2008). http://dx.doi.org/10.1073/pnas.0706851105, http://arxiv.org/abs/0707.0609.
M. Rosvall, D. Axelsson, and C. T. Bergstrom: The map equation, Eur Phys. J Special Topics 178, 13 (2009). http://dx.doi.org/10.1140/epjst/e2010-01179-1, http://arxiv.org/abs/0906.1405.

参数
graph	未记录
edge_weights	边属性的名称或包含边权重的列表。
vertex_weights	顶点属性的名称或包含顶点权重的列表。
trials	尝试划分网络的次数。
返回
一个适当的 `VertexClustering` 对象，带有一个额外的属性 `codelength`，该属性存储由算法确定的代码长度。

def _community_label_propagation(graph, weights=None, initial=None, fixed=None): (source) ¶

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

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

请注意，由于平局是随机打破的，不能保证算法在每次运行后返回相同的社区结构。事实上，它们经常不同。请参阅Raghavan等人的论文，了解如何得出一个聚合的社区结构。

还要注意，社区的_labels_（数字）没有语义意义，igraph可以自由地重新编号社区。如果您使用固定标签，igraph可能仍然会重新编号社区，但会尊重共同社区成员资格约束：如果您有两个具有固定标签的顶点属于同一个社区，它们最终仍将在同一个社区中。同样，如果您有两个具有固定标签的顶点属于不同的社区，它们最终仍将在不同的社区中。

参考文献: Raghavan, U.N. 和 Albert, R. 以及 Kumara, S. 近线性时间算法检测大规模网络中的社区结构。 物理评论 E 76:036106, 2007. http://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: 使用矩阵的特征向量在网络中寻找社区结构, arXiv:physics/0605087

参数
graph	未记录
clusters	期望的社区数量。如果为`None`，算法会尽可能多地进行分割。请注意，如果前导特征向量的符号都相同，算法将不会进一步分割社区，因此实际发现的社区数量可能少于期望的数量。
weights	边的属性名称或包含边权重的列表。
arpack_options	一个用于微调ARPACK特征向量计算的`ARPACKOptions`对象。如果省略，则使用名为`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). 从Louvain到Leiden：保证良好连接的社区。 科学报告, 9(1), 5233. doi: 10.1038/s41598-019-41695-z

参数
graph	未记录
objective_function	是否使用常数Potts模型（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 和 E Lefebvre: 大型网络中社区层次的快速展开, J Stat Mech P10008 (2008). http://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的spinglass社区检测方法，找到图的社区结构。

参考文献

Reichardt J and Bornholdt S: Statistical mechanics of community detection. Phys Rev E 74:016110 (2006). http://arxiv.org/abs/cond-mat/0603718.
Traag VA and Bruggeman J: Community detection in networks with positive and negative links. Phys Rev E 80:036115 (2009). http://arxiv.org/abs/0811.2329.

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

def _community_walktrap(graph, weights=None, steps=4): (source) ¶

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

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

参考: Pascal Pons, Matthieu Latapy: 使用随机游走计算大型网络中的社区, http://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 和 M Girvan: 在网络中寻找和评估社区结构。 物理评论 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) ¶

辅助函数，用于在给定合并矩阵和每次合并后的模块度值列表的情况下，找到图层次聚类的最佳聚类数量。

作为副作用反转模块化向量。