Подмножество направленного графа

Работаю с направленной сетью в igraph. Вот код для создания такой сети:

# example graph
# install.packages(c("igraph"), dependencies = TRUE)
library(igraph)
set.seed(1)
g <- erdos.renyi.game(20, 1/20,directed=TRUE,loops=FALSE)
V(g)$name <- letters[1:20]
par(mar=rep(0,4))
plot(g)

Я хотел бы выделить подмножества этой сети, которые включают произвольную вершину и все ребра и вершины, которые направляются к этой вершине, независимо от степени или расстояния этого соединения.

Вот фотошоп-пример того, что я хотел бы извлечь, используя в данном случае вершину "E". Я хотел бы извлечь сеть, которая включает в себя все вершины, отмеченные синим, и соединенные ребра. Подмножество сетевого графика


r igraph network-analysis
person Electioneer    schedule 18.01.2018    source источник

Ответы (4)


arrow_upward
4
arrow_downward

Я думаю, что помимо того, что @ 42-, можно также использовать distance.

> d = distances(g, to='e', mode='out')
> V(g)[which(!is.infinite(d) & d >0)]
+ 4/20 vertices, named:
[1] a n r t

Вкратце, код в скобках возвращает индексы вершин, которые имеют ненулевые и конечные расстояния от e до других.

person Zhiya    schedule 18.01.2018

arrow_upward
3
arrow_downward

Кажется, что функция edge_connectivity - хороший кандидат для этой задачи. У него есть параметры source и target, которые учитывают направленность ребер:

 sapply(V(g) , function(v) if( v != 5){edge_connectivity(g, source=v, target=5)} else NA )
 a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t 
 1  0  0  0 NA  0  0  0  0  0  0  0  0  1  0  0  0  1  0  1 
 # set the retruned vector to the value named `e_con`

 #then select the vertices
 V(g)[ which(e_con >0)]
+ 4/20 vertices, named, from ba45ff0:
[1] a n r t

С помощью этого списка можно восстановить объект графика:

small_g <- delete_vertices( g, !V(g) %in% c(5, V(g)[ which(econ >0)] ))

plot( small_g)

введите описание изображения здесь

И вы просили список ребер:

edges(small_g)
[[1]]
IGRAPH 11d63f6 DN-- 5 4 -- Erdos renyi (gnp) graph
+ attr: name (g/c), type (g/c), loops (g/l), p (g/n), name (v/c)
+ edges from 11d63f6 (vertex names):
[1] n->a t->a a->e r->e
person IRTFM    schedule 18.01.2018

arrow_upward
2
arrow_downward

Вы можете получить граф окрестностей определенного узла (ов), используя make_ego_graph. Установите порядок числа вершин (или n-1), чтобы можно было пройти по всему графу.

make_ego_graph(g, order=length(V(g)), nodes="e", mode="in")

введите описание изображения здесь

person user20650    schedule 18.01.2018

arrow_upward
0
arrow_downward

Я думал, что все три приведенных здесь ответа были полезны, но решение от @Zhiya - это то, что я в конечном итоге использовал (кажется, это самый быстрый в вычислительном отношении метод).

Тем не менее, я в конечном итоге использовал элементы из @ 42-, потому что моим желаемым выходом была сеть с подмножеством. Вот изменения для решения этой проблемы:

d = distances(g, to='e', mode='out')
vertices.to.delete <- row.names(d)[which(is.infinite(d))]
g1 <- igraph::delete.vertices(g, vertices.to.delete)
person Electioneer    schedule 19.01.2018