从起始节点创建随机子图

Question

我在 R 中有这个网络图：

set.seed(123)
library(igraph)

# Define a vector of names
names <- c("John", "Alex", "Jason", "Matt", "Tim", "Luke", "Shawn", "Henry", "Steven", "Scott", "Adam", "Jeff", "Connor", "Peter", "Andrew", "Dave", "Daniel", "Benjamin", "Joseph", "Martin")

# Create an empty graph with 20 nodes
g <- make_empty_graph(20)

# Add random edges between nodes to represent friendships
set.seed(123)  # for reproducibility
num_edges <- 40
edge_list <- sample(names, size = num_edges * 2, replace = TRUE)
edge_list <- matrix(edge_list, ncol = 2, byrow = TRUE)
g <- graph_from_edgelist(edge_list, directed = FALSE)

# Set the node names to be the names vector
V(g)$name <- names

# Plot the graph
plot(g, vertex.label.cex = 0.7, vertex.label.color = "black", vertex.label.dist = 2)

我的问题： 假设我从约翰开始 - 我想制作一个随机子图：

• “最大程度”是= n
• 子图中的“节点数”为= m
• 子图中的所有节点都可以追溯到John

使用之前的问题R: All Nodes of Degree "N" that can be reached from Some Node，我试图解决这个问题：

all_distances = as.numeric(max(distances(g, "John")))
max_degree =  as.numeric(sample(0:all_distances, 1))
frame_with_max_degree = data.frame(unlist(ego(g, max_degree, "John")))
number_of_nodes = as.numeric(sample(0:nrow(frame_with_max_degree), 1))

我的问题：但是从这里开始，我不确定如何随机选择单个节点

number_of_nodes

使得所有这些节点都必须连接到“约翰”。

例如——假设 n = 3 和 m = 2：我不想用“John”、“Jason”和“Steven”创建子图——因为即使“Jason and Steven”可能在随机生成的半径内， “杰森和史蒂文”仍然没有直接连接到“约翰”。

有人可以告诉我怎么做吗？

谢谢！

Answer 1

如果我正确理解您的目的，您希望在子图中保留从给定顶点（例如“John”）出发的路径。我想除了我的方法应该还有其他一些方法（我认为我的解决方案不够有效）

v <- s <- "John"
M <- m - 1
done <- FALSE
repeat {
  for (k in 1:n) {
    nbs <- unlist(ego(g, 1, s, "out", 1))
    s <- setdiff(names(sample(nbs, sample.int(min(length(nbs), M), 1))), v)
    v <- c(v, s)
    M <- M - length(s)
    if (M == 0) {
      done <- TRUE
      break
    }
  }
  if (done) break
}
gs <- subgraph(g, v)

例如，用

n <- 3

和

m <- 7

，我们可以得到一个子图像

Answer 2

我认为我们可以尝试另一种方法：从

make_ego_graph

开始，我们可以通过删除顶点

迭代

（但需要一直检查顶点连通性）来将ego网络的大小减小到所需的大小。

例如

n <- 3
m <- 7
src <- "John" # assume starting from "John"
gs <- make_ego_graph(g, order = n - 1, nodes = src)[[1]]
repeat{
  if (vcount(gs) == m) break # terminate the loop if we reached the desired size
  v_del <- sample(V(gs)[names(V(gs)) != src], 1) # random vertex to delete
  if (cohesion(gs - v_del)) { #check the connectivity
    gs <- gs - v_del
  }
}

然后我们有

> gs
IGRAPH fdc5e70 UN-- 7 9 -- 
+ attr: name (v/c)
+ edges from fdc5e70 (vertex names):
[1] John --Alex     Jason--Matt     Alex --Henry    Henry--Benjamin
[5] Alex --Henry    Matt --Adam     Jason--Matt     John --Matt
[9] Henry--Adam

Answer 3

基本方法是执行 dfs() 搜索并计算到根的最小距离。 然后按照距根的距离的顺序删除顶点。

惰性方法，从图 g 中的单个顶点输入。

n <- 3                               # number of hubs allowed.
m <- 7                               # number of vertices to maintain in result graph.
d1 <- distances(g, "John")[1,]       # distances from chosen vertex, e.g. "John" (as vector).
d2 <- sort(d1)                       # in ascending order.
l1           <- length(which(d2 <= n )) 
d3           <- head(d2,  l1)        # keep vertices within family.
                                     
d4           <- head(d3,  m)         # keep m vertices.
g2 <- induced_subgraph(g, names(d4)) 
plot(g2)
g2

给予：

IGRAPH 225afed UN-- 7 9 -- 
+ attr: name (v/c)
+ edges from 225afed (vertex names):
[1] John  --Alex   John  --Matt   Jason --Matt   Jason --Matt   John  --Scott 
[6] Matt  --Scott  John  --Andrew John  --Martin Andrew--Martin