比较具有不同顶点数的图中的社区

我正在根据通信数据图计算鲁汶社区，其中顶点代表大型项目的执行者。这些图表代表不同的通信方式（例如电子邮件、电话）。

我们想尝试从通信数据中识别表演者团队。由于表演者对不同的通信方法有不同的偏好，因此图的大小不同，并且可能有一些独特的顶点，而这些顶点可能不会同时出现。当我尝试比较各个图中的社区对象时，igraph::compare() 抛出异常。请参阅下面的玩具代表。

在构造图和社区对象以使它们具有相同大小之前，我考虑了顶点列表的 dplyr::full_join() 或 inner_join() ，但担心这样做会对生成的 cluster_louvain() 解决方案产生影响。

关于如何通过这些不同的通信方法将社区对象相互进行比较，有什么想法吗？提前致谢！

library(tidyverse, warn.conflicts = FALSE)
library(igraph, warn.conflicts = FALSE)

nodes <- as_tibble(list(id = c("sample1", "sample2", "sample3")))
edge <- as_tibble(list(from = "sample1",
                       to = "sample2"))
net <- graph_from_data_frame(d = edge, vertices = nodes, directed = FALSE)
com <- cluster_louvain(net)

nodes2 <- as_tibble(list(id = c("sample1","sample21", "sample22","sample23"
                                )))
edge2 <- as_tibble(list(from = c("sample1", "sample21"),
                       to = c("sample21", "sample22")))
net2 <- graph_from_data_frame(d = edge2, vertices = nodes2, directed = FALSE)
com2 <- cluster_louvain(net2)

# # uncomment to see graph plots
# plot.igraph(net, mark.groups = com)
# plot.igraph(net2, mark.groups = com2)

compare(com, com2)
#> Error in i_compare(comm1, comm2, method): At community.c:3106 : community membership vectors have different lengths, Invalid value

^{Created on 2019-02-22 by the reprex package https://reprex.tidyverse.org (v0.2.1)}

You will not (I don't believe) be able to compare clustering algorithms from two different graphs that contain two different sets of nodes. Practically you can't do it in igraph and conceptually its hard because the way clustering algorithms are compared is by considering all pairs of nodes in a graph and checking whether they are placed in the same cluster or a different cluster in each of the two clustering approaches. If both clustering approaches typically put the same nodes together and the same nodes apart then they are considered more similar.¹

我认为解决该问题的另一种有效方法是评估纯粹作为两个图的交集的节点集的聚类方案的相似程度。您必须决定什么对您的环境更有意义。我将展示如何使用节点的并集而不是交集来完成此操作。

因此，您需要两个图中的所有相同节点才能进行比较。事实上，我认为更简单的方法是将所有相同的节点放在一个图中并具有不同的边类型。然后，您可以分别计算每种边缘类型的聚类，然后进行比较。希望下面的表述是清楚的：

# repeat your set-up
library(tidyverse, warn.conflicts = FALSE)
library(igraph, warn.conflicts = FALSE)

nodes <- as_tibble(list(id = c("sample1", "sample2", "sample3")))
edge <- as_tibble(list(from = "sample1",
                       to = "sample2"))

nodes2 <- as_tibble(list(id = c("sample1","sample21", "sample22","sample23")))
edge2 <- as_tibble(list(from = c("sample1", "sample21"),
                        to = c("sample21", "sample22")))

# approach from a single graph
# concatenate edges
edges <- rbind(edge, edge2)
# create an edge attribute indicating network type
edges$type <- c("phone", "email", "email")
# the set of nodes (across both graphs)
nodes <- unique(rbind(nodes, nodes2))

g <- graph_from_data_frame(d = edges, vertices = nodes, directed = F)

# We cluster over the graph without the email edges
com_phone <- cluster_louvain(g %>% delete_edges(E(g)[E(g)$type=="email"]))
plot(g, mark.groups = com_phone)

# Now we can cluster over the graph without the phone edges
com_email <- cluster_louvain(g %>% delete_edges(E(g)[E(g)$type=="phone"]))
plot(g, mark.groups = com_email)

# Now we can compare
compare(com_phone, com_email)
#> [1] 0.7803552

正如您从图中看到的，我们挑选出与您在单独的图中找到的相同的初始聚类结构，并添加了额外的孤立节点。

1：显然这是一个相当模糊的解释。使用的默认算法compare来自这张纸 https://link.springer.com/chapter/10.1007/978-3-540-45167-9_14，这有一个很好的讨论。