9

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

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.

Improve this question

2 Answers 2

Reset to default
17

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

Result:

      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  
...

And it's very easy to access it:

# 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
Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

Is there a way to automate this for every single node?
This function produces a matrix with ALL the distances between ALL nodes... not just from=1 to all vertices...
Thank you very much, this actually did exactly what is needed. I used this to plot a histogram and it gave me the mode too!
@codeBarer: you should use get.shortest.paths function instead of shortest.paths since the latter gives the paths and not just the distances (LINK to the function documentation)
@digEmAll Thanks, I used get.shortest.paths and it returned the id/indexes of all the vertex encountered on the path. This helped a lot! :)
|
3

If you only want the length, you should use path.length.hist. And to get the mode, just use 

which.max(path.length.hist(g)$res)
Improve this answer

1 Comment

Terrific! This gives me the mode, but I'll be using the raw data for additional analysis. Definitely help though, thank you.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.