在Python/R中创建节点边缘三角形邻接图

Question

如何编写一个R/Python程序，该程序创建一个node-edge adjacency matrix，其中行表示节点和列表示边缘，如果边缘是零件，则该邻接矩阵中的条目为1一个三角形的节点是同一个三角形的一部分。我其实更感兴趣的是为此目的使用igraph或linkcomm，但不介意为此目的看到不同的程序包/程序。

我知道我可以使用maximal.clique（g）来定位三角形，但我不确定如何利用这些数据来创建节点边缘三角形邻接矩阵。

> g <- erdos.renyi.game(15, 45, type="gnm", dir=TRUE) 
> triad.census(g) 
[1] 113 168 38 16 13 49 23 17 7 2 
[11] 2 1 2 2 2 0 
> str(g) 
IGRAPH D--- 15 45 -- Erdos renyi (gnm) graph 
+ attr: name (g/c), type (g/c), loops 
(g/x), m (g/n) 
+ edges: 
1 -> 3 4 6 12 13 2 -> 1 3 7 
3 -> 2 5 10 15 4 -> 5 12 14 
5 -> 6 7 9 6 -> 4 8 12 
7 -> 5 9 12 8 -> 2 7 15 
9 -> 1 4 11 13 10 -> 4 5 8 
11 -> 1 2 9 12 -> 1 4 14 15 
13 -> 15 14 -> 11 12 
15 -> 3 
> maximal.cliques(g) 
[[1]] 
[1] 13 15 


[[2]] 
[1] 13 1 9 


[[3]] 
[1] 2 8 7 


[[4]] 
[1] 2 1 3 


[[5]] 
[1] 2 1 11 


[[6]] 
[1] 3 5 10 


[[7]] 
[1] 3 15 


[[8]] 
[1] 4 14 12 


[[9]] 
[1] 4 10 5 


[[10]] 
[1] 4 5 6 


[[11]] 
[1] 4 5 9 


[[12]] 
[1] 4 1 9 


[[13]] 
[1] 4 1 12 6 


[[14]] 
[1] 5 7 9 


[[15]] 
[1] 6 8 


[[16]] 
[1] 7 12 


[[17]] 
[1] 8 15 


[[18]] 
[1] 8 10 


[[19]] 
[1] 9 1 11 


[[20]] 
[1] 11 14 


[[21]] 
[1] 12 15 


Warning message: 
In maximal.cliques(g) : 
At maximal_cliques_template.h:203 :Edge directions are ignored for maximal clique calculation 

按照文森特的答案时，我用下面我怀疑它是否找到了完全符合尺寸3的集团或找到大小3和更大的派系？ （我只需要三角形）。一个问题是这个代码超慢。任何想法如何加快这一点？

library(igraph) 
set.seed(1) 
g <- erdos.renyi.game(100, .6) 
#print(g) 
plot(g) 
ij <- get.edgelist(g) 
print(ij) 
library(Matrix) 
m <- sparseMatrix(
    i = rep(seq(nrow(ij)), each=2), 
    j = as.vector(t(ij)), 
    x = 1 
) 
print(m) 
# Maximal cliques of size at least 3 
cl <- maximal.cliques(g) 
print(cl) 
cl <- cl[ sapply(cl, length) > 2 ] 
print(cl) 
# Function to test if an edge is part of a triangle 
triangle <- function(e) { 
    any(sapply(cl, function(u) all(e %in% u))) 
} 
print(triangle) 
# Only keep those edges 
kl <- ij[ apply(ij, 1, triangle), ] 
print(kl) 
# Same code as before 
m <- sparseMatrix(
    i = rep(seq(nrow(kl)), each=2), 
    j = as.vector(t(kl)), 
    x = 1 
) 
print(m) 

而且因为某些原因功能cocluster告诉我，输出m不是一个矩阵。有什么想法，我应该怎么做才能在cocluster函数中使用m稀疏矩阵？

>library("blockcluster") 
> out<-cocluster(m,datatype="binary",nbcocluster=c(2,3)) 
Error in cocluster(m, datatype = "binary", nbcocluster = c(2, 3)) : 
    Data should be matrix. 

Answer 1

下面给你一个边缘/顶点邻接矩阵， 但对于所有的边，而不仅仅是那些包含在三角形。

library(igraph) 
set.seed(1) 
g <- erdos.renyi.game(6, .6) 
plot(g) 

ij <- get.edgelist(g) 
library(Matrix) 
m <- sparseMatrix(
    i = rep(seq(nrow(ij)), each=2), 
    j = as.vector(t(ij)), 
    x = 1 
) 

如你建议，可以使用maximal.cliques ，以确定是三角形 的一部分的边缘（等效地，是最大 团大小至少3的一部分）。

# Maximal cliques of size at least 3 
cl <- maximal.cliques(g) 
cl <- cl[ sapply(cl, length) > 2 ] 

# Function to test if an edge is part of a triangle 
triangle <- function(e) { 
    any(sapply(cl, function(u) all(e %in% u))) 
} 

# Only keep those edges 
kl <- ij[ apply(ij, 1, triangle), ] 

# Same code as before 
m <- sparseMatrix(
    i = rep(seq(nrow(kl)), each=2), 
    j = as.vector(t(kl)), 
    x = 1 
) 
m 
# 5 x 5 sparse Matrix of class "dgCMatrix" 
# [1,] 1 1 . . . 
# [2,] . 1 1 . . 
# [3,] 1 . . . 1 
# [4,] . 1 . . 1 
# [5,] . . 1 . 1