get_greedy_routing_paths: Obtain the greedy paths of a greedy routing process

In galanisl/NetHypGeom: Hyperbolic geometry of complex networks

Description

Given a network and source and destination nodes, greedy route packets in hyperbolic space and record the path followed until the target is reached. If the packet visits any of the nodes in the vector faulty, the second closest neighbour to the target is used instead, unless the faulty node is a target or the source itself. If the packet cannot reach its destination, a -1 is added to the path.

Usage

get_greedy_routing_paths(net, polar, source, target, faulty = c())

Arguments

net	igraph; A complex network with N nodes.
polar	data frame; Polar coordinates (r, theta) of all nodes in the network.
source	vector; A vector with one or more node indices representing sources.
target	vector; A vector, the same size as source, with one or more node indices representing targets.
faulty	vector; A vector with one or more node indices representing faulty system components (default = c()).

Value

A list, the same size of source or target, with the paths followed to deliver the packet from each source to each target.

Author(s)

Gregorio Alanis-Lobato [e-mail]

References

Boguna, M. and Krioukov, D. (2009) Navigating Ultrasmall Worlds in Ultrashort Time. Physical Review Letters 102(5).

Krioukov, D. et al. (2010) Hyperbolic geometry of complex networks. Physical Review E 82(3).

Examples

# Generate an artificial network with the PS model
N <- 500
net <- ps_model(N, 6, 2.5, 0)

# Form vectors of random non-redundant source-target pairs
st <- 1000
# We subtract 1, because the formulae to go from linear upper 
# diagonal indexing to (i,j) are zero-based
k <- sample(N*(N-1)/2, st) - 1
sources <- (N - 2 - floor(sqrt(-8*k + 4*N*(N-1)-7)/2.0 - 0.5))
targets <- (k + sources + 1 - N*(N-1)/2 + (N-sources)*((N-sources)-1)/2)

# Back to 1-based indexing
sources <- sources + 1
targets <- targets + 1

# Analyse the network's navigability
paths <- get_greedy_routing_paths(net$network, net$polar, sources, targets)

galanisl/NetHypGeom documentation built on May 16, 2019, 5:36 p.m.