Distances and paths

library(igraph)
source("currentflow.R")

Shortest paths

# Preferential attachment graph
g = sample_pa(100, m=2, directed=FALSE)
coords = layout_with_fr(g)
plot(g, layout=coords, vertex.size = 3, vertex.label=NA)

# average distance (degree of separation)
mean_distance(g)

## [1] 3.019394

# maximum distance (diameter)
diameter(g)

## [1] 5

# highlight the diameter
d = get_diameter(g)
V(g)$color  = "white"
E(g)$color = "grey"
E(g)$width = 1
E(g, path=d)$color = "red"
E(g, path=d)$width = 2
V(g)[d]$color = "red"
plot(g, layout=coords, vertex.label = NA, vertex.size=5)

# single-pair distances and paths
s = d[1]
t = d[length(d)]
distances(g, v=s, to=t)

##      [,1]
## [1,]    5

shortest_paths(g, from=s, to=t)$vpath

## [[1]]
## + 6/100 vertices:
## [1] 18  2  1 13 26 61

all_shortest_paths(g, from=s, to=t)$res

## [[1]]
## + 6/100 vertices:
## [1] 18 10  6 21 55 61
## 
## [[2]]
## + 6/100 vertices:
## [1] 18  2  1 21 55 61
## 
## [[3]]
## + 6/100 vertices:
## [1] 18 10  1 21 55 61
## 
## [[4]]
## + 6/100 vertices:
## [1] 18  2  1 31 55 61
## 
## [[5]]
## + 6/100 vertices:
## [1] 18 10  1 31 55 61
## 
## [[6]]
## + 6/100 vertices:
## [1] 18  2 59 13 26 61
## 
## [[7]]
## + 6/100 vertices:
## [1] 18  2 35 13 26 61
## 
## [[8]]
## + 6/100 vertices:
## [1] 18  2  1 13 26 61
## 
## [[9]]
## + 6/100 vertices:
## [1] 18 10  1 13 26 61
## 
## [[10]]
## + 6/100 vertices:
## [1] 18  2  4 23 26 61
## 
## [[11]]
## + 6/100 vertices:
## [1] 18  2  1 23 26 61
## 
## [[12]]
## + 6/100 vertices:
## [1] 18 10  1 23 26 61

# histogram of distances
paths = distance_table(g)$res
names(paths) = 1:length(paths)
barplot(paths / sum(paths), xlab="Distance", ylab="Frequency")

Resistance distances

A = as_adjacency_matrix(g, sparse=FALSE)
R = resistance(A)

# the closest
min = min(R[R>0])
closest = which(R == min, arr.ind=TRUE)

# the farest
max = max(R)
farest = which(R == max, arr.ind=TRUE)

s = farest[1,1]
t = farest[1,2]
distances(g, v=s, to=t)

##      [,1]
## [1,]    5

d = shortest_paths(g, from=s, to=t)$vpath[[1]]
E(g, path=d)$color = "green"
E(g, path=d)$width = 2
V(g)[d]$color = "green"

s = closest[1,1]
t = closest[1,2]
distances(g, v=s, to=t)

##      [,1]
## [1,]    1

d = shortest_paths(g, from=s, to=t)$vpath[[1]]
E(g, path=d)$color = "blue"
E(g, path=d)$width = 2
V(g)[d]$color = "blue"
plot(g, layout=coords, vertex.label = NA, vertex.size=5)

summary(as.vector(R))

##    Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
##  0.0000  0.7659  0.9678  0.9473  1.1520  1.6390

hist(as.vector(R), xlab="Resistance distance", main="")