获取所有观察组合的集合之间的交集
Get intersections between sets of all combinations of observations
我有一个看起来像这样的数据集
target.id source.id connected
1 1 0
2 1 0
3 1 0
4 1 0
5 1 0
6 1 0
1 2 1
2 2 0
3 2 1
基本上我有源位置、目标位置以及它们是否连接。这里的连接是定向的,例如,位置 1 可以连接到位置 8,而位置 8 不连接到位置 1(想想航空公司的航班,亚特兰蒂斯可以向火星发送航班,而火星可能不会向亚特兰蒂斯发送航班,这意味着亚特兰蒂斯连接到火星,火星不连接到亚特兰蒂斯)。
我需要确定一组 'fully' 个相连的位置,其中所有观察结果都是彼此的来源和目标。考虑到我有 75 个位置,我需要成对地进行,3 乘 3,直到可行为止。示例输出是,对于 3 x 3,位置 3、5 和 8 是彼此的源和目标。
我试图解决这个问题的方法是获取 1:length(unique(target.id))
2 乘 2、3 乘 3,直到 8 乘 8 的所有排列(8 乘 8 将是我要查看的最大集合)和然后intersect
全部。
但是,显然,这太慢了。有更好的方法吗?
听起来你想要一个有向图中所有大小为 2 到 8 的派系,其中节点是你的 ID,当源 -> 目的地在你的数据集中被标记为连接时存在边。第一步是只过滤连接的边缘,产生类似于以下示例数据的内容:
(filtered <- data.frame(source.id = c(1, 1, 2, 2, 3, 3, 3, 4, 4), target.id = c(2, 3, 1, 3, 1, 2, 4, 3, 5), connected = 1))
# source.id target.id connected
# 1 1 2 1
# 2 1 3 1
# 3 2 1 1
# 4 2 3 1
# 5 3 1 1
# 6 3 2 1
# 7 3 4 1
# 8 4 3 1
# 9 4 5 1
接下来,您可以将数据限制为双向连接的 ID 对:
(bidir <- filtered[duplicated(paste(pmin(filtered$source.id, filtered$target.id),
pmax(filtered$source.id, filtered$target.id))),])
# source.id target.id connected
# 3 2 1 1
# 5 3 1 1
# 6 3 2 1
# 8 4 3 1
在此示例数据中,大小为 2 的团为 (1, 2)、(1, 3)、(2, 3) 和 (3, 4),大小为 3 的团为 (1 , 2, 3). igraph 包在 "near-optimal time":
中计算这些
library(igraph)
g <- graph.data.frame(bidir, directed=FALSE)
cliques(g, min=2, max=8)
# [[1]]
# + 2/4 vertices, named:
# [1] 2 3
#
# [[2]]
# + 2/4 vertices, named:
# [1] 2 1
#
# [[3]]
# + 2/4 vertices, named:
# [1] 3 4
#
# [[4]]
# + 2/4 vertices, named:
# [1] 3 1
#
# [[5]]
# + 3/4 vertices, named:
# [1] 2 3 1
我有一个看起来像这样的数据集
target.id source.id connected
1 1 0
2 1 0
3 1 0
4 1 0
5 1 0
6 1 0
1 2 1
2 2 0
3 2 1
基本上我有源位置、目标位置以及它们是否连接。这里的连接是定向的,例如,位置 1 可以连接到位置 8,而位置 8 不连接到位置 1(想想航空公司的航班,亚特兰蒂斯可以向火星发送航班,而火星可能不会向亚特兰蒂斯发送航班,这意味着亚特兰蒂斯连接到火星,火星不连接到亚特兰蒂斯)。
我需要确定一组 'fully' 个相连的位置,其中所有观察结果都是彼此的来源和目标。考虑到我有 75 个位置,我需要成对地进行,3 乘 3,直到可行为止。示例输出是,对于 3 x 3,位置 3、5 和 8 是彼此的源和目标。
我试图解决这个问题的方法是获取 1:length(unique(target.id))
2 乘 2、3 乘 3,直到 8 乘 8 的所有排列(8 乘 8 将是我要查看的最大集合)和然后intersect
全部。
但是,显然,这太慢了。有更好的方法吗?
听起来你想要一个有向图中所有大小为 2 到 8 的派系,其中节点是你的 ID,当源 -> 目的地在你的数据集中被标记为连接时存在边。第一步是只过滤连接的边缘,产生类似于以下示例数据的内容:
(filtered <- data.frame(source.id = c(1, 1, 2, 2, 3, 3, 3, 4, 4), target.id = c(2, 3, 1, 3, 1, 2, 4, 3, 5), connected = 1))
# source.id target.id connected
# 1 1 2 1
# 2 1 3 1
# 3 2 1 1
# 4 2 3 1
# 5 3 1 1
# 6 3 2 1
# 7 3 4 1
# 8 4 3 1
# 9 4 5 1
接下来,您可以将数据限制为双向连接的 ID 对:
(bidir <- filtered[duplicated(paste(pmin(filtered$source.id, filtered$target.id),
pmax(filtered$source.id, filtered$target.id))),])
# source.id target.id connected
# 3 2 1 1
# 5 3 1 1
# 6 3 2 1
# 8 4 3 1
在此示例数据中,大小为 2 的团为 (1, 2)、(1, 3)、(2, 3) 和 (3, 4),大小为 3 的团为 (1 , 2, 3). igraph 包在 "near-optimal time":
中计算这些library(igraph)
g <- graph.data.frame(bidir, directed=FALSE)
cliques(g, min=2, max=8)
# [[1]]
# + 2/4 vertices, named:
# [1] 2 3
#
# [[2]]
# + 2/4 vertices, named:
# [1] 2 1
#
# [[3]]
# + 2/4 vertices, named:
# [1] 3 4
#
# [[4]]
# + 2/4 vertices, named:
# [1] 3 1
#
# [[5]]
# + 3/4 vertices, named:
# [1] 2 3 1