RWR: Random walk with Restart on a graph

In RANKS: Ranking of Nodes with Kernelized Score Functions

Random walk with Restart on a graph

Description

Function that performs a random Walk with restart (RWR) on a given graph

Usage

RWR(W, ind.positives, gamma = 0.6, tmax = 1000, eps = 1e-10, norm = TRUE)

Arguments

W	a numeric matrix representing the adjacency matrix of the graph
ind.positives	indices of the "core" positive examples of the graph. They represent the indices of W corresponding to the positive examples
gamma	restart parameter (def: 0.6)
tmax	maximum number of iterations (steps) (def: 1000)
eps	maximum allowed difference between the computed probabilities at the steady state (def. 1e-10)
norm	if TRUE (def) the adjacency matrix W of the graph is normalized to M = D^{-1} * W, otherwise it is assumed that the matrix W is just normalized

Details

RWR performs a random Walk with restart on a given graph by performing 1 or more steps on the graph, depending on the value of the tmax parameter. The restart parameter expresses the probability of "restarting" from a "core" node at each step of the random walk algorithm. It stops also if the difference of the norm of the probabilities between two consecutive steps is less than eps.

Value

A list with three elements:

p	numeric vector. Probability of each node at the steady state or after tmax iterations
ind.positives	indices of the "core" positive examples of the graph (it is equal to the same input parameter)
n.iter	number of performed steps/iterations

References

L. Lovasz, Random Walks on Graphs: a Survey, Combinatorics, Paul Erdos is Eighty, vol. 2, pp. 146, 1993.

See Also

RW

Examples

# Application of the random walk with restart to the prediction of the 
# DrugBank category Penicillins
# using the Tanimoto chemical structure similarity network 
# between 1253 DrugBank drugs
library(bionetdata);
data(DD.chem.data);
data(DrugBank.Cat);
labels <- DrugBank.Cat[,"Penicillins"];
ind.pos <- which(labels==1);
# 2-step RWR
res <- RWR(DD.chem.data, ind.pos, tmax = 2);

# till to convergence
res <- RWR(DD.chem.data, ind.pos, tmax = 5000, eps=1e-6);
# 5 steps and higher gamma
res <- RWR(DD.chem.data, ind.pos, tmax = 5, gamma=0.8);

RANKS documentation built on Sept. 21, 2022, 9:06 a.m.