Создание графа смежности треугольника вершины узла в Python/R

Question

Как я могу написать R/Python программа, которая создает node-edge adjacency matrix в котором строки обозначают узлы, а столбцы обозначают ребра, а запись в этой матрице смежности - единица, если ребро является частью треугольника, а узел является частью того же треугольника. Я на самом деле более заинтересован, чтобы использовать 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 это не матрица. Любая идея о том, что я должен сделать, чтобы использовать m разреженной матрицы в cocluster функционировать?

>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