提取R Igraph中的开放三角形(网络分析) [英] Extracting Open Triangles in R Igraph (Network Analysis)

问题描述

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

I have an edge list where I want to extract the open triangles meaning that if: A knows B and B knows C, but C's relationship with A isn't captured in the graph.

有没有一种方法可以在R中提取它?我知道您可以使用普通三角形来做到这一点，但我想知道是否可以提取开放三角形.

Is there a way to extract this is in R? I know you can do it with plain triangles but I wanted to know if you can extract open triangles.

我已经在R中创建了一个网络图，其边缘列表如下所示:

I have created a network graph in R with an edge list that looks as follows:

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中创建了网络图，如下所示:

I created the network graph as follows in R:

edges2 <- graph.data.frame(edges)

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

plot(edges3)
edges

这是Edge3变得无方向后的样子:

This is what edges3 looks like after going becoming undirected:

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以外的所有其他端口):

Desired Output (because 323 and 392 are the only ones in this case that do not connect to everything else besides to 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 

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

I hope this makes sense! Thanks

推荐答案

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

If we start from the edges given, firstly we construct an igraph object which we will call it G instead of edges3 here because it is a graph not edges.

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

为了找到所有的开放三角形，我们遍历了图的所有顶点，这就是 lapply(as_ids(V(G))，.. 在第一行中正在执行此操作，并找出所有邻居并再次遍历它们，即 lapply(as_ids(neighbors(G，v))，.. .

In order to find all the open triangles, we loop through all the vertices of the graph, which is what the lapply(as_ids(V(G)), .. is doing here in the first line, and find out all the neighbors and loop through them again, i.e. lapply(as_ids(neighbors(G, v)), ...

我们在第四行进行条件检查，以确保原点 v 与邻居的邻居之间的距离为2，从而确保三角形是开放的(未连接且也不是v 本身.

We make a condition check on the fourth line to make sure the distance between the origin v and neighbor's neighbor is 2, thus guaranteeing that the triangle is open (not connected and also not v itself).

结果将作为有序向量返回，这有助于我们稍后删除重复的开放三角形，这由第一行开头的 unique 函数完成.

The result is going to be returned as an ordered vector, which helps us to remove duplicated open triangles later which is done by the unique function at the beginning of the first line.

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() }
    }))
})))

这段代码将返回一个空心三角形列表，您可以通过 do.call(rbind，openTriList)将其转换为矩阵，其中每一行代表一个唯一的空心三角形:

This piece of code will return a list of open triangles, and you can convert it to a matrix by do.call(rbind, openTriList), where each row represent a unique open triangle:

> 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中的开放三角形(网络分析)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！