igraph-help
[Top][All Lists]

## Re: [igraph] igraph-help Digest, Vol 72, Issue 10

 From: Massimo Franceschet Subject: Re: [igraph] igraph-help Digest, Vol 72, Issue 10 Date: Fri, 13 Jul 2012 18:46:39 +0200

```Il giorno 13/lug/2012, alle ore 18:00, address@hidden ha scritto:

> Message: 1
> Date: Thu, 12 Jul 2012 19:02:32 +0200
> Subject: [igraph] random walk betweenness
> Content-Type: text/plain; charset="iso-8859-1"
>
> Hi list,
> any suggestion for calculating random walk betweenness centrality using
> igraph 0.6?

Ciao Umberto.

Here is a naive implementation of random-walk betweenness:

# Computes current-flow betweenness centrality
# Input: an adjacency matrix A of an undirected graph
# Output: a vector with the centrality score for each node
rwb = function(A) {

# get number of nodes
n = dim(A)[1]

# ignore self-edges
diag(A) = 0

# get Laplacian matrix
L = -A
diag(L) = A %*% rep(1,n)

# get reduced Laplacian matrix by removing first row and first column
L = L[-1,-1]

# invert reduced Laplacian matrix (first bottleneck!)
L = solve(L)

# add first row and first column of all 0s back
L = rbind(0,L)
L = cbind(0,L)

# compute centralities (second bottleneck!)
f = 0
b = rep(0,n)
for (i in 1:n) {
#compute neighborhood of i
nei = which(A[i,] != 0)
for (s in 1:(n-1)) {
for (t in (s+1):n) {
if ((s == i) | (t == i)) {
f = 1
}
else {
x = A[i,nei]
y = abs((L[s,i] - L[t,i]) - (L[s,nei] - L[t,nei]))
f = (x %*% y) / 2
}
b[i] = b[i] + f
}
}
b[i] = 2 * b[i] / (n * (n-1))
}

return(b)
}

As Tamás Nepusz said, it works for relatively small graphs, since it has a
couple of bottlenecks (inverting the Laplacian matrix and computing the
centralities). See http://arxiv.org/abs/1205.4894 for finding approximations of
the pseudo-inverse of Laplacian (first bottleneck) and randomly sample pairs of
nodes to get rid of the second bottleneck.

Enjoy.

Massimo Franceschet

```