获取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)) 

期望的输出

所需的输出将是以下绿色子图（或者关闭，我正在观察上面的图形并在视觉上挑选出子图的内容）忽略/移除其他节点和边缘。

Answer 1

您找不到n个节点之间的最短路径。由于最短路径仅在两个节点之间定义。

我想你想要从1节点到你可以使用的其他n-1节点的最短路径 来自get_all_shortest_paths(v, to=None, mode=ALL)图书馆的igraph。

• v - 计算路径的来源
• to - 一个顶点选择器，用于描述计算路径的目标。这可以是单个顶点ID，顶点ID列表，单个顶点名称，顶点名称列表。无意味着所有顶点。
• mode - 路径的方向性。 IN表示计算输入路径，OUT表示计算输出路径，ALL表示计算两个输出路径。

返回：从给定节点到列表中图中每个其他可到达节点的所有最短路径。 get_all_shortest_paths

所以，现在你必须从最短路径列表中创建一个图形。

1. 初始化一个空图，然后从路径列表中添加所有路径 adding path in graph 要么
2. 为找到的每条最短路径制作一个图形并使图形联合。 union igraph

Answer 2

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

让关键顶点成为您所需的子图形出现的顶点。你说你有三个这样的关键顶点。

考虑到它们之间的任何i和j之间的最短路径是unlist(shortest_paths(g, i, j, mode="all", weights=NULL)$vpath)。您需要列出键 - 顶点的所有i-j组合（在您的情况下为1-2,1-3,2-3），然后列出它们之间的路径上显示的所有顶点。有时，肯定地，相同的顶点出现在多个ij对的最短路径上（参见betweenness centrality）。您想要的子图应该只包含这些顶点，您可以将它们提供给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