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

[Massimo Franceschet]

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

> Message: 1
> Date: Thu, 12 Jul 2012 19:02:32 +0200
> From: Umberto77 <address@hidden>
> To: address@hidden
> Subject: [igraph] random walk betweenness
> Message-ID: <address@hidden>
> 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