R：编写基于图形的函数

Question

我有一组朋友的图形网络，如下所示：

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)

这些朋友中的每一个都有一定数量的饼干：

cookies = data.frame(names = names, cookies = as.integer(rnorm(length(names), 20,10)))

我正在尝试通过以下步骤编写一个函数：

• 第一步：随机选择一个（原始）节点
• 第二步：随机选择一个“半径”（度）
• 第三步：在原节点半径范围内随机选择若干节点进行搜索（但原节点必须与这些节点相连）
• Step 4: 添加原始节点的cookie数和步骤3中选择的节点的所有cookie
• 第 5 步：如果第 4 步中的总数大于 50 或小于 100：结束。 ELSE 从第 1 步重新开始
• 第六步：从原始图中减去所有选择的名字

举个例子：

• 假设我选择斯科特
• 半径 = 3
• 节点数 = 4（Matt、Jason、John、Adam）——注意所有这些名字都可以追溯到 Scott
• 为 Scott、Matt、Jason、John 和 Adam 添加饼干数量（25 + 16 + 16 + 14 + 16 = 87）
• 因为 87 大于 50 小于 100 - finish
• 从图中删除“Scott、Matt、Jason、John、Adam”

我试着写了R代码如下：

#STEP 1
original_node =  sample(V(g), 1)$name

#STEP 2: Find the degree of the farthest node from the original node to be the max "ceiling" 

# Calculate the distance from original_node to all other nodes
distances <- distances(g, original_node)

# Find the node furthest away from original node
max_distance <- max(distances)
furthest_node <- which(distances == max_distance)

# Find the degree of the furthest node
furthest_degree <- max(as.numeric(degree(g, furthest_node)))
radius <- sample(0:furthest_degree, 1)

# STEP 3 : 

# Find the neighbors of original node with degrees ranging from 1 to max
neighbors_degree_1_to_max <- induced.subgraph(g, unlist(ego(g, order=2, nodes=original_node)))

# Find the number of neighbors with degrees ranging from 1 to max
num_neighbors_degree_1_to_max <- length( neighbors_degree_1_to_max)

# randomly select number of nodes to search
nodes_to_search <- sample(0:num_neighbors_degree_1_to_max, 1)

# randomly select individual nodes within nodes_to_search
# stuck from here

但我不确定如何从这里开始，有人可以告诉我该怎么做吗？

谢谢！

参考资料：

• R：从图中减去子图

Answer 1

你可以这样做

# add attribute `cookie` to vertices
V(g)$cookie <- cookies$cookies

# loop till you find the desired clique
repeat {
  rand_neighbours <- ego(g, order = 2, nodes = original_node) %>%
    unlist() %>%
    sample(sample.int(length(.) + 1, 1) - 1)

  clique_cookie_sum <- sum(V(g)$cookie[rand_neighbours])

  if (clique_cookie_sum > 50 & clique_cookie_sum < 100) {
    grp <- subgraph(g, rand_neighbours)
    g <- subgraph(g, !V(g) %in% rand_neighbours) # update `g` by subtracting `grp` 
    break
  }
}

你会看到

> V(grp)
+ 4/4 vertices, named, from 52d6fc7:
[1] Steven Adam   Andrew Martin
> V(grp)$cookie
[1] 13 12 20 23
> sum(V(grp)$cookie)
[1] 68