检测 Networks/communities 并分配 ID

Question

我有一个 table，它显示了具有 ID 的两列。下面的 table 表示第 1 列中的 ID 与第 2 列中的 ID 相关。 table 的模式是我们同时拥有两者（假设 ID 是 A 和 B ，两者都是相关的。然后条目将出现两次，一次是 A 到 B 和 B 到 A)，示例 table 下面：

ID.1    ID.2
 A       B 
 A       C
 B       C
 C       B
 C       A
 B       A
 D       E
 E       F
 F       E
 D       F
 E       D
 F       D

（例如，对于 A、B、C，我们看到 A 和 B 是相关的，A 和 C 是相关的，B 和 C 是相关的 - 我将所有这些都标记在一个房子里并给出一个唯一的 ID）

输出

  ID.1    ID.2      HouseID
     A       B       X1
     A       C       X1
     B       C       X1
     C       B       X1
     C       A       X1
     B       A       X1
     D       E       X2
     E       F       X2
     F       E       X2
     D       F       X2 
     D       F       X2
     E       D       X2
     F       D       X2

我如何在 R 中获得上述内容？如果我添加一个传递逻辑，例如 A 与 B 相关，A 与 C 相关，那么 B 也必须知道 C 怎么办？

Answer 1

据我了解这个问题，@Scarabee 是对的。答案取决于 maximal cliques，但赏金显示 OP 认为这不是一个完整的答案。这个答案推动了分配 HouseID.

library(igraph)

## Your sample data
Edges1 = read.table(text="ID.1    ID.2
 A       B 
 A       C
 B       C
 C       B
 C       A
 B       A
 D       E
 E       F
 F       E
 D       F
 E       D
 F       D", 
header=TRUE, stringsAsFactors=FALSE)

g1 = graph_from_edgelist(as.matrix(Edges1), directed=FALSE)
plot(g1)
MC1 = max_cliques(g1)
MC1
[[1]]
+ 3/6 vertices, named, from 8123133:
[1] A B C

[[2]]
+ 3/6 vertices, named, from 8123133:
[1] D E F

这给出了最大的派系（房屋），但我们需要构建 HouseID 变量。

Edges1$HouseID = apply(Edges1, 1, 
    function(e) 
        which(sapply(MC1, function(mc) all(e %in% names(unclass(mc))))))
Edges1
   ID.1 ID.2 HouseID
1     A    B       1
2     A    C       1
3     B    C       1
4     C    B       1
5     C    A       1
6     B    A       1
7     D    E       2
8     E    F       2
9     F    E       2
10    D    F       2
11    E    D       2
12    F    D       2

外层 apply 循环通过边缘。内部 sapply 检查哪个 clique（房子）包含来自边缘的 both 个节点。

这提供了问题所要求的结构。但正如@Scarabee 指出的那样，一个节点可能属于多个最大集团（房子）。这不完全是个问题，因为请求的结构将 HouseID 分配给 edges。这是一个节点属于两个房屋的示例。

Edges3 = read.table(text="ID.1    ID.2
 A       B 
 A       C
 B       C
 D       E
 D       A
 E       A", 
header=TRUE, stringsAsFactors=FALSE)

g3 = graph_from_edgelist(as.matrix(Edges3), directed=FALSE)
plot(g3)
MC3 = max_cliques(g3)

Edges3$HouseID = apply(Edges3, 1, 
    function(e) 
        which(sapply(MC3, function(mc) all(e %in% names(unclass(mc))))))
Edges3
  ID.1 ID.2 HouseID
1    A    B       2
2    A    C       2
3    B    C       2
4    D    E       1
5    D    A       1
6    E    A       1

在这种情况下，我们仍然可以为每个edge分配一个HouseID，即使节点A在两个不同的Houses中。请注意边 A-B 有 HouseID = 2，但边 D-A 有 HouseD = 1。 HouseID 是 edge 的属性，而不是 node。

但是，还是有问题。边的两端可能属于两个房子，不能将一个房子分配给边。

Edges4 = read.table(text="ID.1    ID.2
 A       B 
 A       C
 B       C
 D       A
 D       B", 
header=TRUE, stringsAsFactors=FALSE)

g4 = graph_from_edgelist(as.matrix(Edges4), directed=FALSE)
plot(g4)
MC4 = max_cliques(g4)
MC4
[[1]]
+ 3/4 vertices, named, from fbd5929:
[1] A B C

[[2]]
+ 3/4 vertices, named, from fbd5929:
[1] A B D

边 A-B 属于两个最大团。正如@Scarabee 所说，问题实际上并不是所有图表的 well-defined 。

检测 Networks/communities 并分配 ID

Detect Networks/communities and assign IDs

r

graph

igraph

plyr