获取n个节点之间最短路径的子图

Question

我有一个无权图，想要获取一个子图，其中只包含n个已知节点之间的最短路径所包含的节点和边。在这种情况下，有3个节点（名称为11、29和13）。

问题

如何在R中获取n个节点之间的最短路径的子图？

MWE

library(ggraph)
library(igraph)

hs <- highschool[highschool$year == '1958',]
set.seed(11)
graph <- graph_from_data_frame(hs[sample.int(nrow(hs), 60),])


# plot using ggraph
ggraph(graph, layout = 'kk') + 
    geom_edge_fan() + 
    geom_node_text(aes(label = name)) 

期望输出

期望的输出应该是以下绿色子图（或者接近，我正在观察上面的图形并直观地挑选出将成为子图的内容），忽略/删除其他节点和边缘。

- Tyler Rinker

---

@Frank，我编辑并添加了所需子图输出的可视化表示。 - Tyler Rinker

哦，好的。那看起来是一个有些复杂的问题，不仅仅是两两最短路径的并集。我猜答案会是：取诱导子图，然后以某种方式“修剪”。 - Frank

我原以为是一个简单的问题，但很可能比我想象的要困难得多：https://math.stackexchange.com/questions/773324/shortest-path-between-three-nodes-in-a-graph - Tyler Rinker

我也遇到了这个问题：https://dev59.com/pmsz5IYBdhLWcg3wwKmh/ - Frank

@maraca 没错。我已经声明“或者接近，我正在观察上面的图表并直观地挑选子图”，但你确实正确，41不是必需的。你的建议将是我要找的解决方案。 - Tyler Rinker

Answer 1

你无法找到n个节点之间的最短路径，因为最短路径只在两个节点之间定义。

我认为你想要从1节点到其他n-1个节点的最短路径，你可以使用igraph库中的get_all_shortest_paths(v, to=None, mode=ALL)方法。

v - 计算路径的源 to - 描述计算路径的目标的顶点选择器。这可以是单个顶点ID、顶点ID列表、单个顶点名称或顶点名称列表。None表示所有顶点。 mode - 路径的方向性。IN表示计算传入路径，OUT表示计算传出路径，ALL表示计算两者。

返回：给定节点到图中每个可达节点的所有最短路径列表。 get_all_shortest_paths 现在，你需要从最短路径列表创建一个图。

1. 初始化一个空图，然后将路径列表中的所有路径添加到其中
   在图中添加路径

   或者

2. 为每个找到的最短路径创建一个图，并取图的并集。
   合并图

- Vineet Jain

Answer 2

你需要一个最短路径的矩阵，然后使用这些路径上所有边的并集创建子图。

将关键顶点定义为所需子图出现的顶点。你说你有三个这样的关键顶点。

考虑到它们之间的任何i和j的最短路径是unlist(shortest_paths(g, i, j, mode="all", weights=NULL)$vpath)。你需要列出所有i-j组合(在你的情况下是1-2、1-3、2-3)，然后列出它们之间出现的所有顶点。有时候，同一个顶点会出现在多个ij对的最短路径上(参见介数中心性)。你所需的子图应仅包括这些顶点，你可以将它们提供给induced_subgraph()。

然后出现另一个有趣的问题。并非所有连接您选择的顶点的边都是最短路径的一部分。我不确定您在子图中需要什么，但我假设您只想要最短路径的顶点和边。 induced_subgraph() 的手册说明可以提供eids来过滤边缘子图，但我无法使其起作用。如果有人解决了这个问题，欢迎发表评论。为了创建仅包含最短路径上实际的边和顶点的子图，必须删除一些多余的边。

下面是一个示例，其中随机选择了一些关键顶点，可视化了子图的多余边问题，并生成了一个适当的仅限于更短路径的子图：

library(igraph)
N <- 40 # Number of vertices in a random network
E <- 70 # Number of edges in a random network
K <- 5  # Number of KEY vertices between which we are to calculate the
        # shortest paths and extract a sub-graph.

# Make a random network
g <- erdos.renyi.game(N, E, type="gnm", directed = FALSE, loops = FALSE)
V(g)$label <- NA
V(g)$color <- "white"
V(g)$size <- 8
E(g)$color <- "gray"

# Choose some random verteces and mark them as KEY vertices
key_vertices <- sample(1:N, 5)
g <- g %>% set_vertex_attr("color", index=key_vertices, value="red")
g <- g %>% set_vertex_attr("size", index=key_vertices, value=12)

# Find shortest paths between two vertices in vector x:
get_path <- function(x){
  # Get atomic vector of two key verteces and return their shortest path as vector.
  i <- x[1]; j <- x[2]
  # Check distance to see if any verticy is outside component. No possible
  # connection will return infinate distance:
  if(distances(g,i,j) == Inf){
    path <- c()
  } else {
    path <- unlist(shortest_paths(g, i, j, mode="all", weights=NULL)$vpath)
  }
}

# List pairs of key vertices between which we need the shortest path
key_el <- expand.grid(key_vertices, key_vertices)
key_el <- key_el[key_el$Var1 != key_el$Var2,]

# Get all shortest paths between each pair of key_vertices:
paths <- apply(key_el, 1, get_path)

# These are the vertices BETWEEN key vertices - ON the shortest paths between them:
path_vertices <- setdiff(unique(unlist(paths)), key_vertices)
g <- g %>% set_vertex_attr("color", index=path_vertices, value="gray")


# Mark all edges of a shortest path
mark_edges <- function(path, edges=c()){
  # Get a vector of id:s of connected vertices, find edge-id:s of all edges between them.
  for(n in 1:(length(path)-1)){
    i <- path[n]
    j <- path[1+n]
    edge <- get.edge.ids(g, c(i,j), directed = TRUE, error=FALSE, multi=FALSE)
    edges <- c(edges, edge)
  }
  # Return all edges in this path
  (edges)
}

# Find all edges that are part of the shortest paths between key vertices
key_edges <- lapply(paths, function(x) if(length(x) > 1){mark_edges(x)})
key_edges <- unique(unlist(key_edges))
g <- g %>% set_edge_attr("color", index=key_edges, value="green")

# This now shoes the full graph and the sub-graph which will be created
plot(g)

# Create sub-graph:
sg_vertices <- sort(union(key_vertices, path_vertices))
unclean_sg <- induced_subgraph(g, sg_vertices)
# Note that it is essential to provide both a verticy AND an edge-index for the
# subgraph since edges between included vertices do not have to be part of the
# calculated shortest path. I never used it before, but eids=key_edges given
# to induced_subgraph() should work (even though it didn't for me just now).

# See the problem here:
plot(unclean_sg)

# Kill edges of the sub-graph that were not part of shortest paths of the mother
# graph:
sg <- delete.edges(unclean_sg, which(E(unclean_sg)$color=="gray"))

# Plot a comparison:
l <-layout.auto(g)
layout(matrix(c(1,1,2,3), 2, 2, byrow = TRUE))
plot(g, layout=l)
plot(unclean_sg, layout=l[sg_vertices,])  # cut l to keep same layout in subgraph
plot(sg, layout=l[sg_vertices,])          # cut l to keep same layout in subgraph

- nJGL