[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## 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*
>* 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

[Prev in Thread] |
**Current Thread** |
[Next in Thread] |

**Re: [igraph] igraph-help Digest, Vol 72, Issue 10**,
*Massimo Franceschet* **<=**