使用igraph/R查找所有最短路径 [英] Find All Shortest Paths using igraph/R

问题描述

首先，我对R不太熟练，但是我有一个要分析的100个节点的网络.我正在寻找网络中每对节点之间的所有最短路径(100次计算)，诀窍是将它们返回为整数，如果可以的话，返回路径长度.

First off I am not very proficient with R, but I have a network of 100 nodes I'm doing analysis on. I'm looking to find all the shortest paths between every single pair of nodes in the network (100 calculations), and the trick is to return them as integers, path lengths if you will.

#construct a small sample of the graph
g = graph.formula('insert graph') 

#use the function to retrieve shortest paths from a single vertex
get.all.shortest.paths(g, 1, to = V(g))

#output
$res
$res[[1]]
[1] 1

$res[[2]]
[1] 1 2

$res[[3]]
[1] 1 2 3

$res[[4]]
[1] 1 2 3 4

$res[[5]]
[1] 1 2 3 4 5

$res[[6]]
[1]  1 10  9  8  7  6

$res[[7]]
[1] 1 2 3 4 5 6

$res[[8]]
[1]  1 10  9  8  7

$res[[9]]
[1]  1 10  9  8

$res[[10]]
[1]  1 10  9

$res[[11]]
[1]  1 10


$nrgeo
 [1] 1 1 1 1 1 2 1 1 1 1

虽然这很好，但是对所有100个节点进行手动迭代并不现实.有没有一种自动化的方法?我的问题的第二个组成部分是，我希望将每个路径输出为数字，例如路径长度，而不是给出实际路径.我想做的另一件事是计算模式路径长度(或在网络中更常见的路径长度).查看100个数字是不可行的，因此它必须是自动化的.

While this is good it is not practical to manually iterate for all 100 nodes. Is there a way of automating this? A second component to my question is that I wish to output each path as a number, like a path length, instead of being given the actual path. Another thing I want is to calculate the mode path length (or the path length that is more frequently found in the network). Looking at 100 numbers is not feasible so it must be automated.

任何帮助将被彻底感谢，这似乎是一个新手问题，我有点像新手用户.

Any help would be thoroughly appreciated, this might seem like a novice question, I am somewhat of a novice user.

推荐答案

您可以使用shortest.paths返回每个节点之间的距离矩阵:

You could use shortest.paths that returns the matrix of the distances between each node:

distMatrix <- shortest.paths(g, v=V(g), to=V(g))

结果:

      cdc42 ste20 mkk2 bul1 mth1 vma6 vma2  ... 
cdc42     0     1  Inf  Inf    4    3    2  
ste20     1     0  Inf  Inf    3    2    1  
mkk2    Inf   Inf    0    1  Inf  Inf  Inf  
bul1    Inf   Inf    1    0  Inf  Inf  Inf  
mth1      4     3  Inf  Inf    0    1    2  
vma6      3     2  Inf  Inf    1    0    1
vma2      2     1  Inf  Inf    2    1    0  
...      

访问它非常容易:

# e.g. shortest path length between the second node and the fifth
distMatrix[2,5]
>
[1] 3

# or using node names:
distMatrix["ste20", "mth1"]
>
[1] 3

这篇关于使用igraph/R查找所有最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！