属性节点聚类¶

概述¶

class cdlib.AttrNodeClustering(communities: list, graph: object, method_name: str = '', coms_labels: dict | None = None, method_parameters: dict | None = None, overlap: bool = False)¶

属性节点社区表示。

Parameters:

communities – 社区列表
graph – 一个 networkx/igraph 对象
method_name – 社区发现算法名称
coms_labels – 字典，指定每个社区属性值的频率
method_parameters – 用于社区发现算法的配置
overlap – 布尔值，表示分区是否重叠

adjusted_mutual_information(clustering: Clustering) → MatchingResult¶

两个聚类之间的调整互信息。

调整互信息（AMI）是对互信息（MI）分数进行调整以考虑偶然性。它解释了这样一个事实，即对于具有更多簇的两个聚类，MI通常更高，无论是否实际上共享了更多信息。对于两个聚类 $U$ 和 $V$，AMI 给出如下：

AMI(U, V) = [MI(U, V) - E(MI(U, V))] / [max(H(U), H(V)) - E(MI(U, V))]

该指标与标签的绝对值无关：类别或聚类标签值的排列不会以任何方式改变得分值。

此外，该指标是对称的：交换label_true与label_pred将返回相同的分数值。这在真实的基础事实未知时，用于衡量同一数据集上两种独立标签分配策略的一致性非常有用。

请注意，此函数比其他指标（如调整兰德指数）慢一个数量级。

Parameters:: 聚类 – NodeClustering 对象
Returns:: AMI 分数
Example:

>>> from cdlib import algorithms
>>> g = nx.karate_club_graph()
>>> communities = algorithms.louvain(g)
>>> leiden_communities = algorithms.leiden(g)
>>> mod = communities.adjusted_mutual_information(leiden_communities)

Reference:

Vinh, N. X., Epps, J., & Bailey, J. (2010). 聚类比较的信息理论度量：变体、属性、归一化和机会校正。 机器学习研究杂志, 11(10月), 2837-2854.

adjusted_rand_index(clustering: Clustering) → MatchingResult¶

调整后的兰德指数以考虑机会因素。

兰德指数通过考虑所有样本对并计算在预测和真实聚类中被分配到相同或不同簇的样本对，来计算两个聚类之间的相似性度量。

原始RI分数随后通过以下方案“调整机会”转换为ARI分数：

ARI = (RI - Expected_RI) / (max(RI) - Expected_RI)

调整后的兰德指数因此确保在随机标记时具有接近0.0的值，无论聚类和样本的数量如何，当聚类完全相同时（除了排列），其值正好为1.0。

ARI 是一个对称的度量：

adjusted_rand_index(a, b) == adjusted_rand_index(b, a)

Parameters:: clustering – NodeClustering 对象
Returns:: ARI 分数
Example:

>>> from cdlib import algorithms
>>> g = nx.karate_club_graph()
>>> communities = algorithms.louvain(g)
>>> leiden_communities = algorithms.leiden(g)
>>> mod = communities.adjusted_rand_index(leiden_communities)

Reference:

Hubert, L., & Arabie, P. (1985). 比较分区. 分类学杂志, 2(1), 193-218.

average_internal_degree(**kwargs: dict) → FitnessResult¶

算法集的平均内部度数。

\[f(S) = \frac{2m_S}{n_S}\]

其中 $m_S$ 是算法内部边的数量，$n_S$ 是算法节点的数量。

Parameters:: summary – (可选，默认为 True) 如果为 True，则返回分区的总体摘要（最小值、最大值、平均值、标准差）；如果为 False，则返回社区得分的列表
Returns:: 一个 FitnessResult 对象/社区得分的列表
Example:

>>> from cdlib.algorithms import louvain
>>> g = nx.karate_club_graph()
>>> communities = louvain(g)
>>> mod = communities.average_internal_degree()

avg_distance(**kwargs: dict) → FitnessResult¶

平均距离。

社区的平均距离定义为组成它的所有可能节点对之间的平均路径长度。

Parameters:: summary – 布尔值。如果为True，则返回分区的聚合分数，否则返回单个社区的分数。默认值为True。
Returns:: 如果 summary==True 则返回一个 FitnessResult 对象，否则返回一个浮点数列表。

示例：

>>> from cdlib.algorithms import louvain
>>> from cdlib import evaluation
>>> g = nx.karate_club_graph()
>>> communities = louvain(g)
>>> scd = communities.avg_distance()

avg_embeddedness(**kwargs: dict) → FitnessResult¶

社区内节点的平均嵌入度。

节点n相对于社区C的嵌入度是其在社区内的度数与其总度数的比率。

\[emb(n,C) = \frac{k_n^C}{k_n}\]

社区C的平均嵌入度是：

\[avg_embd(c) = \frac{1}{|C|} \sum_{i \in C} \frac{k_n^C}{k_n}\]

Parameters:: summary – 布尔值。如果为True，则返回分区的聚合分数，否则返回单个社区的分数。默认值为True。
Returns:: 如果 summary==True 则返回一个 FitnessResult 对象，否则返回一个浮点数列表。

示例：

>>> from cdlib.algorithms import louvain
>>> from cdlib import evaluation
>>> g = nx.karate_club_graph()
>>> communities = louvain(g)
>>> ave = communities.avg_embeddedness()

avg_odf(**kwargs: dict) → FitnessResult¶

算法节点指向算法外部的边的平均比例。

\[\frac{1}{n_S} \sum_{u \in S} \frac{|\{(u,v)\in E: v \not\in S\}|}{d(u)}\]

其中 $E$ 是图的边集，$v$ 是 $S$ 中的一个节点，$d(u)$ 是 $u$ 的度数，$n_S$ 是算法节点的集合。

Parameters:: summary – (可选，默认为 True) 如果为 True，则返回分区的总体摘要（最小值、最大值、平均值、标准差）；如果为 False，则返回社区得分的列表
Returns:: 一个 FitnessResult 对象/社区得分的列表
Example:

>>> from cdlib.algorithms import louvain
>>> g = nx.karate_club_graph()
>>> communities = louvain(g)
>>> mod = communities.avg_odf()

avg_transitivity(**kwargs: dict) → FitnessResult¶

平均传递性。

社区的平均传递性被定义为其节点在社区内部连接的平均聚类系数。

Parameters:: summary – 布尔值。如果为True，则返回分区的聚合分数，否则返回单个社区的分数。默认值为True。
Returns:: 如果 summary==True 则返回一个 FitnessResult 对象，否则返回一个浮点数列表。

示例：

>>> from cdlib.algorithms import louvain
>>> from cdlib import evaluation
>>> g = nx.karate_club_graph()
>>> communities = louvain(g)
>>> scd = communities.avg_transitivity()

classification_error(clustering: object) → MatchingResult¶

此函数计算两个聚类之间的Jaccard指数。

\[CE = 1 - PI\]

Parameters:: 聚类 – NodeClustering 对象
Returns:: 匹配结果对象
Example:

>>> from cdlib import algorithms
>>> import networkx as nx
>>> g = nx.karate_club_graph()
>>> louvain_communities = algorithms.louvain(g)
>>> leiden_communities = algorithms.leiden(g)
>>> louvain_communities.classification_error(leiden_communities)

注意

该函数需要安装clusim库。您可以通过pip安装：pip install clusim

conductance(**kwargs: dict) → FitnessResult¶

指向算法外部的总边缘体积的比例。

\[f(S) = \frac{c_S}{2 m_S+c_S}\]

其中 $c_S$ 是算法节点的数量，$m_S$ 是算法边的数量

Parameters:: summary – (可选，默认为 True) 如果为 True，则返回分区的总体摘要（最小值、最大值、平均值、标准差）；如果为 False，则返回社区得分的列表
Returns:: 一个 FitnessResult 对象/社区得分的列表
Example:

>>> from cdlib.algorithms import louvain
>>> g = nx.karate_club_graph()
>>> communities = louvain(g)
>>> mod = communities.conductance()

cut_ratio(**kwargs: dict) → FitnessResult¶

现有边的比例（占所有可能边的比例）离开算法。

..math:: f(S) = frac{c_S}{n_S (n − n_S)}

其中 $c_S$ 是算法节点的数量，$n_S$ 是算法边界上的边的数量

Parameters:: summary – (可选，默认为 True) 如果为 True，则返回分区的总体摘要（最小值、最大值、平均值、标准差）；如果为 False，则返回社区得分的列表
Returns:: 一个 FitnessResult 对象/社区得分的列表
Example:

>>> from cdlib.algorithms import louvain
>>> g = nx.karate_club_graph()
>>> communities = louvain(g)
>>> mod = communities.cut_ratio()

czekanowski_index(clustering: object) → MatchingResult¶

此函数计算两个聚类之间的Czekanowski。

也被称为： Dice对称指数 Sorensen指数

\[F = \frac{2*N11}{(2*N11 + N10 + N01)}\]

Parameters:: 聚类 – NodeClustering 对象
Returns:: 匹配结果对象
Example:

>>> from cdlib import algorithms
>>> import networkx as nx
>>> g = nx.karate_club_graph()
>>> louvain_communities = algorithms.louvain(g)
>>> leiden_communities = algorithms.leiden(g)
>>> louvain_communities.czekanowski_index(leiden_communities)

注意

该函数需要安装clusim库。您可以通过pip安装：pip install clusim

dice_index(clustering: object) → MatchingResult¶

此函数计算两个聚类之间的Czekanowski。

也被称为： Czekanowski指数 Sorensen指数

\[F = \frac{2*N11}{(2*N11 + N10 + N01)}\]

Parameters:: 聚类 – NodeClustering 对象
Returns:: 匹配结果对象
Example:

>>> from cdlib import algorithms
>>> import networkx as nx
>>> g = nx.karate_club_graph()
>>> louvain_communities = algorithms.louvain(g)
>>> leiden_communities = algorithms.leiden(g)
>>> louvain_communities.dice_index(leiden_communities)

注意

该函数需要安装clusim库。您可以通过pip安装：pip install clusim

ecs(clustering: object, alpha: float = 0.9, r: float = 1.0, r2: float | None = None, rescale_path_type: str = 'max', ppr_implementation: str = 'prpack') → MatchingResult¶

以元素为中心的聚类相似性。

Parameters:

聚类 – NodeClustering 对象
alpha – 个性化页面排名返回概率，作为[0,1]范围内的浮点数。浮点数，默认值为0.9
r – 用于聚类1的层次缩放参数。浮点数，默认值为1.0
r2 – 用于clustering2的分层缩放参数。float，默认为None
rescale_path_type – 通过以下方式重新调整层次高度：'max' 从根节点到叶节点的最大路径；'min' 从根节点到叶节点的最小路径；'linkage' 使用聚类中的链接距离。
ppr_implementation – 选择用于个性化页面排名计算的实现方式：'prpack' 使用 igraph 中的 PPR 算法；'power_iteration'：使用 power_iteration 方法。

Returns:

匹配结果对象

Example:

>>> from cdlib import algorithms
>>> import networkx as nx
>>> g = nx.karate_club_graph()
>>> louvain_communities = algorithms.louvain(g)
>>> leiden_communities = algorithms.leiden(g)
>>> louvain_communities.ecs(leiden_communities)

Reference:

A.J. Gates, I.B. Wood, W.P. Hetrick, 和 YY Ahn [2019]. “以元素为中心的聚类比较统一了重叠和层次结构”. 科学报告 9, 8574

注意

该函数需要安装clusim库。您可以通过pip安装：pip install clusim

edges_inside(**kwargs: dict) → FitnessResult¶

算法内部的边数。

Parameters:: summary – (可选，默认为 True) 如果为 True，则返回分区的总体摘要（最小值、最大值、平均值、标准差）；如果为 False，则返回社区得分的列表
Returns:: 一个 FitnessResult 对象/社区得分的列表
Example:

>>> from cdlib.algorithms import louvain
>>> g = nx.karate_club_graph()
>>> communities = louvain(g)
>>> mod = communities.edges_inside()

erdos_renyi_modularity() → FitnessResult¶

Erdos-Renyi 模块度是 Newman-Girvan 模块度的一种变体。它假设网络中的顶点以恒定概率 $p$ 随机连接。

\[Q(S) = \frac{1}{m}\sum_{c \in S} (m_S − \frac{mn_S(n_S −1)}{n(n−1)})\]

其中 $m$ 是图的边数，$m_S$ 是算法边的数量，$l_S$ 是从 S 中的节点到 S 外节点的边的数量。

Returns:: Erdos-Renyi模块化得分
Example:

>>> from cdlib.algorithms import louvain
>>> g = nx.karate_club_graph()
>>> communities = louvain(g)
>>> mod = communities.erdos_renyi_modularity()

References:

Erdos, P., & Renyi, A. (1959). 关于随机图 I. Publ. Math. Debrecen, 6, 290-297.

expansion(**kwargs: dict) → FitnessResult¶

每个算法节点指向集群外部的边的数量。

\[f(S) = \frac{c_S}{n_S}\]

其中 $n_S$ 是算法边界上的边数，$c_S$ 是算法节点的数量。

Parameters:: summary – (可选，默认为 True) 如果为 True，则返回分区的总体摘要（最小值、最大值、平均值、标准差）；如果为 False，则返回社区得分的列表
Returns:: 一个 FitnessResult 对象/社区得分的列表
Example:

>>> from cdlib.algorithms import louvain
>>> g = nx.karate_club_graph()
>>> communities = louvain(g)
>>> mod = communities.expansion()

f1(clustering: Clustering) → MatchingResult¶

计算输入分区中最佳算法匹配的平均F1分数。适用于重叠/非重叠完整/部分覆盖分区。

Parameters:: 聚类 – NodeClustering 对象
Returns:: F1分数（精确率和召回率的调和平均数）
Example:

>>> from cdlib import algorithms
>>> g = nx.karate_club_graph()
>>> communities = algorithms.louvain(g)
>>> leiden_communities = algorithms.leiden(g)
>>> mod = communities.f1(leiden_communities)

Reference:

Rossetti, G., Pappalardo, L., & Rinzivillo, S. (2016). 一种新颖的方法来评估基于真实数据的算法检测内部。 在《复杂网络VII》（第133-144页）中。Springer, Cham.

flake_odf(**kwargs: dict) → FitnessResult¶

在S中，节点内部指向的边数少于指向算法外部的边数的比例。

\[f(S) = \frac{| \{ u:u \in S,| \{(u,v) \in E: v \in S \}| < d(u)/2 \}|}{n_S}\]

其中 $E$ 是图的边集，$v$ 是 $S$ 中的一个节点，$d(u)$ 是 $u$ 的度数，$n_S$ 是算法节点的集合。

Parameters:: summary – (可选，默认为 True) 如果为 True，则返回分区的总体摘要（最小值、最大值、平均值、标准差）；如果为 False，则返回社区得分的列表
Returns:: 一个 FitnessResult 对象/社区得分的列表
Example:

>>> from cdlib.algorithms import louvain
>>> g = nx.karate_club_graph()
>>> communities = louvain(g)
>>> mod = communities.flake_odf()

fowlkes_mallows_index(clustering: object) → MatchingResult¶

此函数计算两个聚类之间的Fowlkes和Mallows指数

\[FM = \frac{N11}{ \sqrt{ (N11 + N10) * (N11 + N01) }}\]

Parameters:: 聚类 – NodeClustering 对象
Returns:: 匹配结果对象
Example:

>>> from cdlib import algorithms
>>> import networkx as nx
>>> g = nx.karate_club_graph()
>>> louvain_communities = algorithms.louvain(g)
>>> leiden_communities = algorithms.leiden(g)
>>> louvain_communities.fowlkes_mallows_index(leiden_communities)

Reference:

爱德华·B·福克斯和科林·L·马洛斯。一种比较两种层次聚类的方法。美国统计协会杂志，78(383):553–569, 1983。

注意

该函数需要安装clusim库。您可以通过pip安装：pip install clusim

fraction_over_median_degree(**kwargs: dict) → FitnessResult¶

算法节点中内部度高于中位度值的比例。

\[f(S) = \frac{|\{u: u \in S,| \{(u,v): v \in S\}| > d_m\}| }{n_S}\]

其中 $d_m$ 是内部度中值

Parameters:: summary – (可选，默认为 True) 如果为 True，则返回分区的总体摘要（最小值、最大值、平均值、标准差）；如果为 False，则返回社区得分的列表
Returns:: 一个 FitnessResult 对象/社区得分的列表
Example:

>>> from cdlib.algorithms import louvain
>>> g = nx.karate_club_graph()
>>> communities = louvain(g)
>>> mod = communities.fraction_over_median_degree()

geometric_accuracy(clustering: object) → MatchingResult¶

此函数计算两个（重叠）聚类之间的几何精度。

Parameters:: 聚类 – NodeClustering 对象
Returns:: 匹配结果对象
Example:

>>> from cdlib import algorithms
>>> import networkx as nx
>>> g = nx.karate_club_graph()
>>> louvain_communities = algorithms.louvain(g)
>>> leiden_communities = algorithms.leiden(g)
>>> louvain_communities.geometric_accuracy(leiden_communities)

Reference:

Tamás Nepusz、Haiyuan Yu 和 Alberto Paccanaro。检测蛋白质-蛋白质相互作用网络中的重叠蛋白质复合物。《自然方法》，9(5):471–472，2012年。

注意

该函数需要安装clusim库。您可以通过pip安装：pip install clusim

get_description(parameters_to_display: list | None = None, precision: int = 3) → str¶

返回聚类的描述，包括方法的名称及其数值参数。

Parameters:

parameters_to_display – 要显示的参数。默认情况下，显示所有浮点参数。
precision – 用于绘制参数的精度。默认值：3

Returns:

方法的字符串描述。

hub_dominance(**kwargs: dict) → FitnessResult¶

中心主导地位。

社区的中心支配性被定义为其连接最紧密节点的度与社区内理论上最大度的比率。

Parameters:: summary – 布尔值。如果为True，则返回分区的聚合分数，否则返回单个社区的分数。默认值为True。
Returns:: 如果 summary==True 则返回一个 FitnessResult 对象，否则返回一个浮点数列表。

示例：

>>> from cdlib.algorithms import louvain
>>> from cdlib import evaluation
>>> g = nx.karate_club_graph()
>>> communities = louvain(g)
>>> scd = communities.hub_dominance()

internal_edge_density(**kwargs: dict) → FitnessResult¶

算法集的内部密度。

\[f(S) = \frac{m_S}{n_S(n_S−1)/2}\]

其中 $m_S$ 是算法内部边的数量，$n_S$ 是算法节点的数量。

Parameters:: summary – (可选，默认为 True) 如果为 True，则返回分区的总体摘要（最小值、最大值、平均值、标准差）；如果为 False，则返回社区得分的列表
Returns:: 一个 FitnessResult 对象/社区得分的列表
Example:

>>> from cdlib.algorithms import louvain
>>> g = nx.karate_club_graph()
>>> communities = louvain(g)
>>> mod = communities.internal_edge_density()

jaccard_index(clustering: object) → MatchingResult¶

此函数计算两个聚类之间的Jaccard指数。

\[J = \frac{N11}{(N11+N10+N01)}\]

Parameters:: 聚类 – NodeClustering 对象
Returns:: 匹配结果对象
Example:

>>> from cdlib import algorithms
>>> import networkx as nx
>>> g = nx.karate_club_graph()
>>> louvain_communities = algorithms.louvain(g)
>>> leiden_communities = algorithms.leiden(g)
>>> louvain_communities.jaccard_index(leiden_communities)

Reference:

保罗·雅卡尔。高山地区植物区系的分布。新植物学家，11(2):37–50，1912年。

注意

该函数需要安装clusim库。您可以通过pip安装：pip install clusim

link_modularity() → FitnessResult¶

为具有重叠社区的有向图设计的质量函数。

Returns:: 链接模块化分数
Example:

>>> from cdlib import evaluation
>>> from cdlib.algorithms import louvain
>>> g = nx.karate_club_graph()
>>> communities = louvain(g)
>>> mod = communities.link_modularity()

max_odf(**kwargs: dict) → FitnessResult¶

算法节点指向算法外部的边的最大比例。

\[max_{u \in S} \frac{|\{(u,v)\in E: v \not\in S\}|}{d(u)}\]

其中 $E$ 是图的边集，$v$ 是 $S$ 中的一个节点，$d(u)$ 是 $u$ 的度数

Parameters:: summary – (可选，默认为 True) 如果为 True，则返回分区的总体摘要（最小值、最大值、平均值、标准差）；如果为 False，则返回社区得分的列表
Returns:: 一个 FitnessResult 对象/社区得分的列表
Example:

>>> from cdlib.algorithms import louvain
>>> g = nx.karate_club_graph()
>>> communities = louvain(g)
>>> mod = communities.max_odf()

mi(clustering: object) → MatchingResult¶

此函数计算两个聚类之间的互信息（MI）。

\[MI = (S(c1) + S(c2) - S(c1, c2))\]

其中 S(c1) 是聚类大小分布的香农熵，S(c1, c2) 是联合聚类大小分布的香农熵，

Parameters:: 聚类 – NodeClustering 对象
Returns:: 匹配结果对象
Example:

>>> from cdlib import algorithms
>>> import networkx as nx
>>> g = nx.karate_club_graph()
>>> louvain_communities = algorithms.louvain(g)
>>> leiden_communities = algorithms.leiden(g)
>>> louvain_communities.mi(leiden_communities)

Reference:

Leon Danon, Albert D ıaz-Guilera, Jordi Duch, 和 Alex Arenas. 比较社区结构识别. 统计力学杂志: 理论与实验, 2005(09):P09008–P09008, 2005年9月.

注意

该函数需要安装clusim库。您可以通过pip安装：pip install clusim

modularity_density() → FitnessResult¶

模块化密度是几种旨在缓解基于模块化度量的分辨率限制问题的提议之一。该指标的想法是将算法大小的信息纳入算法的预期密度中，以避免忽视小而密集的社区。对于分区$S$中的每个算法$C$，它使用由$d(C) = d^{int(C)} − d^{ext(C)}$计算的平均模块化度，其中$d^{int(C)}$和$d^{ext(C)}$分别是$C$的平均内部和外部度，以评估$C$在其网络中的适应性。最后，模块化密度可以如下计算：

\[Q(S) = \sum_{C \in S} \frac{1}{n_C} ( \sum_{i \in C} k^{int}_{iC} - \sum_{i \in C} k^{out}_{iC})\]

其中 $n_C$ 是 C 中的节点数，$k^{int}_{iC}$ 是节点 i 在 $C$ 内的度数，$k^{out}_{iC}$ 是节点 i 在 $C$ 外的度数。

Returns:: 模块化密度分数
Example:

>>> from cdlib.algorithms import louvain
>>> g = nx.karate_club_graph()
>>> communities = louvain(g)
>>> mod = communities.modularity_density()

References:

Li, Z., Zhang, S., Wang, R. S., Zhang, X. S., & Chen, L. (2008). 算法检测的定量函数。 物理评论 E, 77(3), 036109.

modularity_overlap(weight: str | None = None) → FitnessResult¶

确定图G上分区C的重叠模块性。

重叠模块性定义为

\[M_{c_{r}}^{ov} = \sum_{i \in c_{r}} \frac{\sum_{j \in c_{r}, i \neq j}a_{ij} - \sum_{j \not \in c_{r}}a_{ij}}{d_{i} \cdot s_{i}} \cdot \frac{n_{c_{r}}^{e}}{n_{c_{r}} \cdot \binom{n_{c_{r}}}{2}}\]

Parameters:: weight – 标识边权重参数名称的标签（如果存在），默认为 None
Returns:: FitnessResult 对象

示例：

>>> from cdlib.algorithms import louvain
>>> from cdlib import evaluation
>>> g = nx.karate_club_graph()
>>> communities = louvain(g)
>>> mod = communities.modularity_overlap()

References:

1. Lazar, D. Abel 和 T. Vicsek, “具有重叠社区网络的模块化度量” EPL, 90 (2010) 18001 doi: 10.1209/0295-5075/90/18001

newman_girvan_modularity() → FitnessResult¶

将分区内算法边的分数与根据零模型分布的此类边的预期数量进行差异比较。

在模块化的标准版本中，零模型保留了所考虑图的预期度序列。换句话说，模块化将真实的网络结构与一个对应的网络结构进行比较，其中节点在没有任何邻居偏好的情况下连接。

\[Q(S) = \frac{1}{m}\sum_{c \in S}(m_S - \frac{(2 m_S + l_S)^2}{4m})\]

其中 $m$ 是图的边数，$m_S$ 是算法边的数量，$l_S$ 是从 S 中的节点到 S 外部节点的边的数量。

Returns:: 纽曼-吉文模块度分数
Example:

>>> from cdlib.algorithms import louvain
>>> g = nx.karate_club_graph()
>>> communities = louvain(g)
>>> mod = communities.newman_girvan_modularity()

References:

Newman, M.E.J. 和 Girvan, M. 在网络中寻找和评估算法结构。 物理评论 E 69, 26113(2004).

nf1(clustering: Clustering) → MatchingResult¶

计算输入分区中最佳算法匹配的归一化F1分数。适用于重叠/非重叠的完全/部分覆盖分区。

Parameters:: 聚类 – NodeClustering 对象
Returns:: 匹配结果实例
Example:

>>> from cdlib import algorithms
>>> g = nx.karate_club_graph()
>>> communities = algorithms.louvain(g)
>>> leiden_communities = algorithms.leiden(g)
>>> mod = communities.nf1(leiden_communities)

Reference:

Rossetti, G., Pappalardo, L., & Rinzivillo, S. (2016). 一种新颖的方法来评估算法在地面实况上的内部检测。
Rossetti, G. (2017). : RDyn: 处理算法动态的图基准。复杂网络期刊。 5(6), 893-912.

normalized_cut(**kwargs: dict) → FitnessResult¶

Cut-Ratio的归一化变体

\[: f(S) = \frac{c_S}{2m_S+c_S} + \frac{c_S}{2(m−m_S )+c_S}\]

其中 $m$ 是图的边数，$m_S$ 是算法内部边数，$c_S$ 是算法节点数。

Parameters:: summary – (可选，默认为 True) 如果为 True，则返回分区的总体摘要（最小值、最大值、平均值、标准差）；如果为 False，则返回社区得分的列表
Returns:: 一个 FitnessResult 对象/社区得分的列表
Example:

>>> from cdlib.algorithms import louvain
>>> g = nx.karate_club_graph()
>>> communities = louvain(g)
>>> mod = communities.normalized_cut()

normalized_mutual_information(clustering: Clustering) → MatchingResult¶

两个聚类之间的归一化互信息。

归一化互信息（NMI）是互信息（MI）得分的归一化，用于将结果缩放到0（无互信息）和1（完全相关）之间。在此函数中，互信息通过sqrt(H(labels_true) * H(labels_pred))进行归一化。

Parameters:: 聚类 – NodeClustering 对象
Returns:: 归一化互信息分数
Example:

>>> from cdlib import algorithms
>>> g = nx.karate_club_graph()
>>> communities = algorithms.louvain(g)
>>> leiden_communities = algorithms.leiden(g)
>>> mod = communities.normalized_mutual_information(leiden_communities)

omega(clustering: Clustering) → MatchingResult¶

重叠、完全覆盖、网络聚类的相似性指数。

Parameters:: 聚类 – NodeClustering 对象
Returns:: 欧米茄指数
Example:

>>> from cdlib import algorithms
>>> g = nx.karate_club_graph()
>>> communities = algorithms.louvain(g)
>>> leiden_communities = algorithms.leiden(g)
>>> mod = communities.omega(leiden_communities)

Reference:

Gabriel Murray, Giuseppe Carenini, 和 Raymond Ng. 2012. 使用omega指数评估抽象算法检测。 在自动摘要评估指标和系统比较研讨会论文集。计算语言学协会，美国宾夕法尼亚州斯特劳兹堡，10-18。

overlap_quality(clustering: object) → MatchingResult¶

此函数计算两个（重叠）聚类之间的重叠质量。

Parameters:: 聚类 – NodeClustering 对象
Returns:: 匹配结果对象
Example:

>>> from cdlib import algorithms
>>> import networkx as nx
>>> g = nx.karate_club_graph()
>>> louvain_communities = algorithms.louvain(g)
>>> leiden_communities = algorithms.leiden(g)
>>> louvain_communities.overlap_quality(leiden_communities)

Reference:

Yong-Yeol Ahn, James P Bagrow, 和 Sune Lehmann. 链接社区揭示了网络中的多尺度复杂性. 自然, 466(7307):761–764, 2010年6月.

注意

该函数需要安装clusim库。您可以通过pip安装：pip install clusim

overlapping_normalized_mutual_information_LFK(clustering: Clustering) → MatchingResult¶

两个聚类之间的重叠归一化互信息。

扩展归一化互信息（NMI）分数以处理重叠分区。这是Lancichinetti等人提出的版本。

Parameters:: 聚类 – NodeClustering 对象
Returns:: onmi 分数
Example:

>>> from cdlib import algorithms
>>> g = nx.karate_club_graph()
>>> communities = algorithms.louvain(g)
>>> leiden_communities = algorithms.leiden(g)
>>> mod = communities.overlapping_normalized_mutual_information_LFK(leiden_communities)

Reference:

Lancichinetti, A., Fortunato, S., & Kertesz, J. (2009). 检测复杂网络中的重叠和层次社区结构。新物理学杂志, 11(3), 033015.

overlapping_normalized_mutual_information_MGH(clustering: Clustering, normalization: str = 'max') → MatchingResult¶

两个聚类之间的重叠归一化互信息。

扩展归一化互信息（NMI）分数以处理重叠分区。这是McDaid等人提出的版本，使用了与原始LFR不同的归一化方法。更多详情请参见参考文献。

Parameters:

聚类 – NodeClustering 对象
normalization – 其中之一为“max”或“LFK”。默认为“max”（对应于文章中描述的主要方法）

Returns:

onmi 分数

Example:

>>> from cdlib import evaluation, algorithms
>>> g = nx.karate_club_graph()
>>> louvain_communities = algorithms.louvain(g)
>>> leiden_communities = algorithms.leiden(g)
>>> evaluation.overlapping_normalized_mutual_information_MGH(louvain_communities,leiden_communities)
:Reference:

McDaid, A. F., Greene, D., & Hurley, N. (2011). 使用归一化互信息评估重叠社区发现算法。arXiv预印本 arXiv:1110.2515. 芝加哥

partition_closeness_simple(clustering: Clustering) → MatchingResult¶

社区规模密度接近度。简单的实现，不利用核密度估计器。

$$ S_G(A,B) = frac{1}{2} Sum_{i=1}^{r}Sum_{j=1}^{s} min(frac{n^a(x^a_i)}{N^a}, frac{n^b_j(x^b_j)}{N^b}) delta(x_i^a,x_j^b) $$

其中：

$$ N^a $$ A中任何大小的社区总数； $$ x^a $$ A的社区大小有序列表； $$ n^a $$ A的社区大小的多重性。

（对于B对称）

Parameters:: 聚类 – NodeClustering 对象
Returns:: 匹配结果对象
Example:

>>> from cdlib import algorithms
>>> import networkx as nx
>>> g = nx.karate_club_graph()
>>> louvain_communities = algorithms.louvain(g)
>>> leiden_communities = algorithms.leiden(g)
>>> louvain_communities.partition_closeness_simple(leiden_communities)

Reference:

Dao, Vinh-Loc, Cécile Bothorel, 和 Philippe Lenca. “基于集群大小分布的社区检测方法相似性估计。” 国际复杂网络及其应用会议。Springer, Cham, 2018.

purity() → FitnessResult¶: 纯度是社区内节点携带的最频繁标签的频率的乘积 :return: FitnessResult 对象

rand_index(clustering: object) → MatchingResult¶

此函数计算两个聚类之间的兰德指数。

\[RI = \frac{(N11 + N00)}{(N11 + N10 + N01 + N00)}\]

Parameters:: 聚类 – NodeClustering 对象
Returns:: 匹配结果对象
Example:

>>> from cdlib import algorithms
>>> import networkx as nx
>>> g = nx.karate_club_graph()
>>> louvain_communities = algorithms.louvain(g)
>>> leiden_communities = algorithms.leiden(g)
>>> louvain_communities.rand_index(leiden_communities)

Reference:

威廉·M·兰德。聚类方法评估的客观标准。美国统计协会杂志，66(336):846, 1971。

注意

该函数需要安装clusim库。您可以通过pip安装：pip install clusim

rmi(clustering: object, norm_type: str = 'none', logbase: int = 2) → MatchingResult¶

此函数计算两个聚类之间的简化互信息（RMI）。

\[RMI = MI(c1, c2) - \log \frac{Omega(a, b)}{n}\]

其中 MI(c1, c2) 是聚类 c1 和 c2 的互信息，而 Omega(a, b) 是行和列总和等于 a 和 b 的列联表的数量。

Parameters:

聚类 – NodeClustering 对象
norm_type – 归一化类型有：'none' 返回未归一化的RMI；'normalized' 返回上界等于1的RMI。
logbase – int, 默认值 2

Returns:

匹配结果对象

Example:

>>> from cdlib import algorithms
>>> import networkx as nx
>>> g = nx.karate_club_graph()
>>> louvain_communities = algorithms.louvain(g)
>>> leiden_communities = algorithms.leiden(g)
>>> louvain_communities.rmi(leiden_communities)

Reference:

1. 1. Newman, George T. Cantwell, 和 Jean-Gabriel Young. 改进的互信息度量用于分类和社区检测. arXiv:1907.12581, 2019.

注意

该函数需要安装clusim库。您可以通过pip安装：pip install clusim

rogers_tanimoto_index(clustering: object) → MatchingResult¶

此函数计算两个聚类之间的Rogers和Tanimoto指数。

\[RT = \frac{(N11 + N00)}{(N11 + 2*(N10+N01) + N00)}\]

Parameters:: 聚类 – NodeClustering 对象
Returns:: 匹配结果对象
Example:

>>> from cdlib import algorithms
>>> import networkx as nx
>>> g = nx.karate_club_graph()
>>> louvain_communities = algorithms.louvain(g)
>>> leiden_communities = algorithms.leiden(g)
>>> louvain_communities.rogers_tanimoto_index(leiden_communities)

注意

该函数需要安装clusim库。您可以通过pip安装：pip install clusim

sample_expected_sim(clustering: object, measure: str = 'jaccard_index', random_model: str = 'perm', n_samples: int = 1, keep_samples: bool = False) → MatchingResult¶

此函数计算从六种随机模型之一绘制的聚类之间所有成对比较的预期相似度。

注意

聚类2被认为是单边期望的黄金标准聚类

Parameters:

聚类 – NodeClustering 对象
measure – 要评估的相似性度量。必须是 [ecs, jaccard_index, rand_index, fowlkes_mallows_index, classification_error, czekanowski_index, dice_index, sorensen_index, rogers_tanimoto_index, southwood_index, mi, rmi, vi, geometric_accuracy, overlap_quality, sample_expected_sim] 之一
random_model –
使用的随机模型：

’all’在所有聚类集合上的均匀分布
n_elements

’all1’从所有聚类集合上的均匀分布中进行单边选择
n_elements

’num’在n_clusters中的所有聚类集合上的均匀分布
n_elements

’num1’从n_clusters中的所有聚类集合上的均匀分布中进行单边选择
n_elements

’perm’ : 固定聚类大小序列的排列模型

’perm1’从固定聚类大小序列的排列模型中进行单边选择
与’perm’相同
n_samples – 用于确定预期相似性的随机聚类样本数量。
keep_samples – 如果为True，返回相似性样本本身，否则返回它们的平均值。

Returns:

匹配结果对象

Example:

>>> from cdlib import algorithms
>>> import networkx as nx
>>> g = nx.karate_club_graph()
>>> louvain_communities = algorithms.louvain(g)
>>> leiden_communities = algorithms.leiden(g)
>>> louvain_communities.sample_expected_sim(leiden_communities)

注意

该函数需要安装clusim库。您可以通过pip安装：pip install clusim

scaled_density(**kwargs: dict) → FitnessResult¶

缩放密度。

社区的缩放密度定义为社区密度与完全图密度的比率。

Parameters:: summary – 布尔值。如果为True，则返回分区的聚合分数，否则返回单个社区的分数。默认值为True。
Returns:: 如果 summary==True 则返回一个 FitnessResult 对象，否则返回一个浮点数列表。

示例：

>>> from cdlib.algorithms import louvain
>>> from cdlib import evaluation
>>> g = nx.karate_club_graph()
>>> communities = louvain(g)
>>> scd = communities.scaled_density()

significance() → FitnessResult¶

显著性估计了在随机图中出现密集社区分区的可能性。

Returns:: 显著性分数
Example:

>>> from cdlib.algorithms import louvain
>>> g = nx.karate_club_graph()
>>> communities = louvain(g)
>>> mod = communities.significance()

References:

Traag, V. A., Aldecoa, R., & Delvenne, J. C. (2015). 使用渐近惊喜检测社区。 物理评论 E, 92(2), 022816.

size(**kwargs: dict) → FitnessResult¶

大小是社区中节点的数量

Parameters:: summary – (可选，默认为 True) 如果为 True，则返回分区的总体摘要（最小值、最大值、平均值、标准差）；如果为 False，则返回社区得分的列表
Returns:: 一个 FitnessResult 对象/社区得分的列表

示例：

>>> from cdlib.algorithms import louvain
>>> g = nx.karate_club_graph()
>>> communities = louvain(g)
>>> mod = communities.size()

sorensen_index(clustering: object) → MatchingResult¶

此函数计算两个聚类之间的Sorensen。

也被称为： Czekanowski指数 Dice指数

\[F = \frac{2*N11}{(2*N11 + N10 + N01)}\]

Parameters:: 聚类 – NodeClustering 对象
Returns:: 匹配结果对象
Example:

>>> from cdlib import algorithms
>>> import networkx as nx
>>> g = nx.karate_club_graph()
>>> louvain_communities = algorithms.louvain(g)
>>> leiden_communities = algorithms.leiden(g)
>>> louvain_communities.sorensen_index(leiden_communities)

注意

该函数需要安装clusim库。您可以通过pip安装：pip install clusim

southwood_index(clustering: object) → MatchingResult¶

此函数计算两个聚类之间的Southwood指数。

\[\frac{N11}{(N10 + N01)}\]

Parameters:: 聚类 – NodeClustering 对象
Returns:: 匹配结果对象
Example:

>>> from cdlib import algorithms
>>> import networkx as nx
>>> g = nx.karate_club_graph()
>>> louvain_communities = algorithms.louvain(g)
>>> leiden_communities = algorithms.leiden(g)
>>> louvain_communities.southwood_index(leiden_communities)

注意

该函数需要安装clusim库。您可以通过pip安装：pip install clusim

surprise() → FitnessResult¶

Surprise 是一种统计方法，提出了一种质量度量，假设顶点之间的边根据超几何分布随机出现。

根据Surprise指标，分区的得分越高，它由随机实现产生的可能性就越小，算法结构的质量就越好。

Returns:: 惊喜分数
Example:

>>> from cdlib.algorithms import louvain
>>> g = nx.karate_club_graph()
>>> communities = louvain(g)
>>> mod = communities.surprise()

References:

Traag, V. A., Aldecoa, R., & Delvenne, J. C. (2015). 使用渐近惊喜检测社区。 物理评论 E, 92(2), 022816.

to_json() → str¶

生成算法对象的JSON表示

Returns:: 表示对象的JSON格式字符串

to_node_community_map() → dict¶

生成当前聚类的<节点, 列表(社区)>表示

Returns:: 形式为 <节点, 列表(社区)> 的字典

triangle_participation_ratio(**kwargs: dict) → FitnessResult¶

属于三元组的算法节点的比例。

\[f(S) = \frac{ | \{ u: u \in S,\{(v,w):v, w \in S,(u,v) \in E,(u,w) \in E,(v,w) \in E \} \not = \emptyset \} |}{n_S}\]

其中 $n_S$ 是算法节点的集合。

Parameters:: summary – (可选，默认为 True) 如果为 True，则返回分区的总体摘要（最小值、最大值、平均值、标准差）；如果为 False，则返回社区得分的列表
Returns:: 一个 FitnessResult 对象/社区得分的列表
Example:

>>> from cdlib.algorithms import louvain
>>> g = nx.karate_club_graph()
>>> communities = louvain(g)
>>> mod = communities.triangle_participation_ratio()

variation_of_information(clustering: Clustering) → MatchingResult¶

两个节点分区之间的信息变化。

$$ H(p)+H(q)-2MI(p, q) $$

其中MI是互信息，H是分区熵，p和q是算法集

Parameters:: 聚类 – NodeClustering 对象
Returns:: VI 分数
Example:

>>> from cdlib import algorithms
>>> g = nx.karate_club_graph()
>>> communities = algorithms.louvain(g)
>>> leiden_communities = algorithms.leiden(g)
>>> mod = communities.variation_of_information(leiden_communities)

Reference:

Meila, M. (2007). 比较聚类 - 基于信息的距离。 多元分析杂志, 98, 873-895. doi:10.1016/j.jmva.2006.11.013

z_modularity() → FitnessResult¶

Z-modularity 是标准模块化的另一种变体，旨在避免分辨率限制。这个版本的概念基于一个观察，即社区内部边的比例与零模型中此类边的预期数量之间的差异不应被视为算法结构最终质量的唯一贡献。

Returns:: z模块化得分
Example:

>>> from cdlib.algorithms import louvain
>>> g = nx.karate_club_graph()
>>> communities = louvain(g)
>>> mod = communities.z_modularity()

References:

Miyauchi, Atsushi, 和 Yasushi Kawase. 基于Z分数的模块化算法检测网络中的算法。 PloS one 11.1 (2016): e0147805.

方法¶

评估节点聚类¶

AttrNodeClustering.purity()

纯度是社区内节点携带的最频繁标签的频率的乘积 :return: FitnessResult 对象