python - Python 中的 iGraph : Relation between a VertexDendrogram object and VertexClustering object

Question

在Python中使用iGraph的社区检测函数community_fastgreedy()，我得到了一个VertexDendrogram对象，我们称之为V。然后使用V.as_clustering()我从 TreeMap 中得到了一个VertexClustering对象。我知道社区是集群化的，因此模块化最大化，但我认为树形图对象一直在合并，因此很难在树形图上看到社区。

我的问题是:V.as_clustering() 的输出如何对应于树状图中社区之间的距离？

换句话来说，每个社区都有一个代表编号(例如社区[0]、社区[2])，那么该数字如何对应树状图上的位置呢？当树状图合并到最大化模块性的级别时，社区 0 和社区 1 是否彼此相邻，社区 12 是否比社区 3 距离社区 0 更远？

如果不是，那么 as_clustering 函数如何决定输出的顺序(每个社区的数字)？

提前致谢。

Answer 1

当 igraph 中的算法生成 VertexDendrogram 时，它也可以选择生成一个“提示”，告诉​​我们在哪里切割树状图(即在多少次合并之后)以获得 VertexClustering 在某种意义上是最优的。例如，由 community_fastgreedy() 生成的 VertexDendrogram 建议应在模块化最大化的点处切割树状图。在 VertexDendrogram 上运行 as_clustering() 只是使用聚类算法生成的提示将树形图展平为聚类，但您可以通过指定所需的聚类数量来覆盖它作为 as_clustering() 的参数。

至于两个社区之间的“距离”:这是一件复杂的事情，因为大多数社区检测方法不会为您提供该信息。它们只是生成一系列从单个顶点到封装每个人的大型社区的合并序列，并且树状图中没有编码“距离”信息；换句话说，树状图的分​​支没有“长度”。您能做的最好的可能就是返回图表并检查社区之间的边缘密度；这可能是亲密关系的良好指示。例如:

cl = g.community_fastgreedy().as_clustering()
comm1 = cl[0]
comm2 = cl[1]
edges_between = g.es.select(_between=(comm1, comm2))
print 2.0 * len(edges_between) / len(comm1) * len(comm2)

如果您的图表是有向图，请在最后一行使用乘数 1.0 而不是 2.0。