r - 如何比较两个连续图中的社区

Question

我有在两个不同时间表示的相同图表:g.t0 和 g.t1。 g.t1 与 g.t0 的不同之处在于，它多了一条边​​，但保留了相同的顶点。

我想比较g.t0和g.t1中的社区，即测试顶点是否从t0到t1移动到了不同的社区。我尝试了以下方法

library(igraph)

m <- matrix(c(0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0),nrow=4,ncol=4)

g.t0 <- graph.adjacency(m)
memb.t0 <- membership(edge.betweenness.community(g.t0))
V(g.t0)
# Vertex sequence:
#   [1] 1 2 3 4
memb.t0
# [1] 1 2 2 3

g.t1 <- add.edges(g.t0,c(1,2))
memb.t1 <- membership(edge.betweenness.community(g.t1))
V(g.t1)
# Vertex sequence:
#   [1] 1 2 3 4
memb.t1
# [1] 1 1 1 2

但是问题当然是社区的索引总是从1开始。那么在例子中看起来所有的顶点都移动到了不同的社区，但是最直观的阅读是实际上只有顶点1发生了变化社区，与 2 和 3 一起移动。

如何解决计算社区从 t0 变为 t1 的顶点数量的问题？

Answer 1

其实这不是一个简单的问题。一般来说，您需要使用匹配优化的某些规则或标准来匹配两个图中的社区。由于您可以拥有不同数量的社区，因此匹配不一定是双射的。

针对这个问题提出了几种方法和数量，其中一堆是在 igraph 中实现的，请参阅 http://igraph.org/r/doc/compare.html

compare.communities(memb.t1, memb.t0, method="vi")
# [1] 0.4773856
compare.communities(memb.t1, memb.t0, method="nmi")
# [1] 0.7020169
compare.communities(memb.t1, memb.t0, method="rand")
# [1] 0.6666667

有关方法的详细信息，请参阅 igraph 手册中的引用资料。