在 R Igraph 中提取开放三角形（网络分析）

Question

我有一个边缘列表，我想在其中提取 open 三角形，这意味着如果：A 知道 B 并且 B 知道 C，但是 C 与 A 的关系没有被捕获图。

有没有办法在 R 中提取它？我知道你可以用普通三角形来做，但我想知道你是否可以提取空心三角形。

我在 R 中创建了一个网络图，其中的边列表如下所示：

structure(list(ego = c(323L, 174L, 174L, 174L, 174L, 174L, 174L, 
174L, 174L, 174L, 428L, 428L, 428L, 428L, 428L, 428L, 428L, 428L, 
364L, 364L, 364L, 364L, 364L, 364L, 364L, 364L, 422L, 422L, 422L, 
422L, 422L, 422L, 422L, 422L, 329L, 329L, 329L, 329L, 329L, 329L, 
329L, 329L, 31L, 31L, 31L, 31L, 31L, 31L, 31L, 31L, 330L, 330L, 
330L, 330L, 330L, 330L, 330L, 330L, 415L, 428L), alter = c(174L, 
323L, 428L, 364L, 422L, 329L, 31L, 330L, 415L, 392L, 174L, 364L, 
422L, 329L, 31L, 330L, 415L, 392L, 174L, 428L, 422L, 329L, 31L, 
330L, 415L, 392L, 174L, 428L, 364L, 329L, 31L, 330L, 415L, 392L, 
174L, 428L, 364L, 422L, 31L, 330L, 415L, 392L, 174L, 428L, 364L, 
422L, 329L, 330L, 415L, 392L, 174L, 428L, 364L, 422L, 329L, 31L, 
415L, 392L, 174L, 323L), advice_tie = c(1L, 1L, 1L, 1L, 1L, 1L, 
1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 
1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 
1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 
1L, 1L, 1L, 1L, 1L, 1L)), .Names = c("ego", "alter", "advice_tie"
), class = "data.frame", row.names = c(NA, -60L))

我在 R 中创建了如下网络图：

edges2 <- graph.data.frame(edges)

edges3 <- as.undirected(edges2, mode='collapse')
summary(edges3)

plot(edges3)
edges

这是 edges3 变成无向后的样子：

IGRAPH UN-- 10 37 -- 
+ attr: name (v/c)
+ edges (vertex names):
 [1] 323--174 323--428 174--428 174--364 428--364
 [6] 174--422 428--422 364--422 174--329 428--329
 [11] 364--329 422--329 174--31  428--31  364--31 
 [16] 422--31  329--31  174--330 428--330 364--330
 [21] 422--330 329--330 31 --330 174--415 428--415
 [26] 364--415 422--415 329--415 31 --415 330--415
 [31] 174--392 428--392 364--392 422--392 329--392
 [36] 31 --392 330--392

所需的输出（因为在这种情况下 323 和 392 是唯一不连接到除 428 之外的其他任何东西的输出）：

415  174 323
31   174 323
422  174 323
329  174 323
364  174 323
392  174 323
330  174 323
31   415 392
422  415 392
329  415 392
364  415 392
392  415 392
330  415 392
428  415 392
174  415 392

我希望这是有道理的！谢谢

Answer 1

如果我们从给定的边开始，首先我们构造一个 igraph 对象，在这里我们将其称为 G 而不是 edges3 因为它是一个图不是边 .

library(igraph)
g <- graph.data.frame(edges)
G <- as.undirected(g, mode='collapse')

为了找到所有的空心三角形，我们遍历图的所有顶点，这就是第一行中 lapply(as_ids(V(G)), .. 所做的, 并找出所有的邻居并再次循环它们，即 lapply(as_ids(neighbors(G, v)), ..。

我们在第四行进行条件检查，确保原点v和邻居的邻居之间的距离为2，从而保证三角形是开放的（不连接，也不v本身）。

结果将被 return 编辑为有序向量，这有助于我们稍后删除重复的空心三角形，这是由第一行开头的 unique 函数完成的。

openTriList <- unique(do.call(c, lapply(as_ids(V(G)), function(v) {
    do.call(c, lapply(as_ids(neighbors(G, v)), function(v1) {
        v2 <- as_ids(neighbors(G, v1))
        v2 <- v2[shortest.paths(G, v, v2) == 2]

        if(length(v2) != 0) {
            lapply(v2, function(vv2) { c(v, v1, vv2)[order(c(v, v1, vv2))] })
        } else { list() }
    }))
})))

这段代码会return一个空心三角形的列表，你可以通过do.call(rbind, openTriList)将它转换成一个矩阵，其中每一行代表一个唯一的空心三角形：

> do.call(rbind, openTriList)
      [,1]  [,2]  [,3] 
 [1,] "174" "323" "364"
 [2,] "174" "323" "422"
 [3,] "174" "323" "329"
 [4,] "174" "31"  "323"
 [5,] "174" "323" "330"
 [6,] "174" "323" "415"
 [7,] "174" "323" "392"
 [8,] "323" "364" "428"
 [9,] "323" "422" "428"
[10,] "323" "329" "428"
[11,] "31"  "323" "428"
[12,] "323" "330" "428"
[13,] "323" "415" "428"
[14,] "323" "392" "428"
[15,] "174" "392" "415"
[16,] "392" "415" "428"
[17,] "364" "392" "415"
[18,] "392" "415" "422"
[19,] "329" "392" "415"
[20,] "31"  "392" "415"
[21,] "330" "392" "415"

在 R Igraph 中提取开放三角形（网络分析）

Extracting Open Triangles in R Igraph (Network Analysis)

r

igraph