[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 <=