cdlib与igraph的Variation of Information计算结果差异问题咨询

我们有如下两个社区划分：

社区划分1 #

Community0= [8, 16, 17, 19, 20, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33]
Community1= [1, 2, 3, 7, 11, 12, 13, 15, 18]
Community2= [0, 4, 5, 6, 9, 10, 14, 22]

对应的节点社区标签列表：

[2, 1, 1, 1, 2, 2, 2, 1, 0, 2, 2, 1, 1, 1, 2, 1, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

社区划分2 #

Community0= [32, 33, 8, 16, 17, 19, 20, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31]
Community1= [0, 3, 4, 5, 6, 9, 10, 11, 22]
Community2= [1, 2, 7, 12, 13, 14, 15, 18]

对应的节点社区标签列表：

[1, 2, 2, 1, 1, 1, 1, 2, 0, 1, 1, 1, 2, 2, 2, 2, 0, 0, 2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

使用cdlib的evaluation.variation_of_information方法和Python版igraph的compare_communities(method='vi')方法计算Variation of Information（信息变差），得到的结果分别为0.66和0.46，二者存在差异，请问该如何正确计算？

两个工具结果差异的核心原因是对Variation of Information（VI）的标准化方式不同：

1. 结果差异的本质 #

• igraph的实现：返回的是未标准化的原始VI值。VI的原始计算公式为：
  $$VI(X,Y) = H(X) + H(Y) - 2I(X,Y)$$
  其中$H$代表熵，$I$代表互信息。针对你的数据，手动计算的原始VI值约为0.46，和igraph的结果完全一致。
• cdlib的实现：返回的是标准化后的VI值（默认将原始VI归一化到[0,1]区间，或基于节点总数的对数进行缩放）。你的节点总数为34，原始VI值0.46经过对应标准化处理后，得到约0.66的结果。

2. 正确计算的方式 #

VI的计算本身没有对错，关键看你需要的是原始值还是标准化值：

• 若需原始VI值：以igraph的结果为准，或严格按照原始公式手动计算：
  1. 分别计算两个社区划分的熵$H(X)$和$H(Y)$；
  2. 计算两个划分之间的互信息$I(X,Y)$；
  3. 代入公式$VI(X,Y)=H(X)+H(Y)-2I(X,Y)$得到结果。
• 若需标准化VI值：可以直接使用cdlib的结果，或者将原始VI值除以$\log(n)$（$n$为节点总数），将结果映射到[0,1]区间（当两个划分完全无关时，VI趋近于$\log(n)$，因此缩放后结果接近1）。

3. 额外注意事项 #

确保两个工具的输入格式一致：

• igraph的compare_communities接受VertexClustering对象或节点到社区的标签列表（VI计算与社区标签无关，只关注节点集合的划分）；
• cdlib的variation_of_information接受NodeClustering对象，需保证输入的社区划分是正确的集合形式。

手动验证你的数据可知：两个划分的大部分节点集合重合，仅少数节点跨社区，因此原始VI值较低（约0.46），符合预期。

内容的提问来源于stack exchange，提问作者tknsci