[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] shortest path between all nodes on a weighted network
From: |
Gabor Csardi |
Subject: |
Re: [igraph] shortest path between all nodes on a weighted network |
Date: |
Mon, 16 Apr 2007 11:59:21 +0200 |
User-agent: |
Mutt/1.5.12-2006-07-14 |
Ok, i think i got it, the diagonal of the 1 and Wmax matrices in the formula
should be zero. So for an igraph graph the weighted transitivity is
something like this:
wtrans <- function(g) {
if (!is.igraph(g)) {
stop("Not a graph!")
}
if (is.directed(g)) {
stop("Directed graph")
}
if (!"weight" %in% list.edge.attributes(g)) {
stop("Graph is not weighted")
}
W <- get.adjacency(g, attr="weight")
WM <- matrix(max(W), nrow(W), ncol(W))
diag(WM) <- 0
diag( W %*% W %*% W ) / diag( W %*% WM %*% W)
}
It seems to work:
> g <- erdos.renyi.game(10, 4/10)
> E(g)$weight <- 1
> wtrans(g)
[1] 0.3000000 0.6666667 0.5714286 0.8000000 0.8333333 0.5357143 NaN
[8] 0.6000000 1.0000000 0.6000000
> transitivity(g, "local")
[1] 0.3000000 0.6666667 0.5714286 0.8000000 0.8333333 0.5357143 NaN
[8] 0.6000000 1.0000000 0.6000000
> E(g)$weight <- runif(ecount(g))
> wtrans(g)
[1] 0.2428481 0.2490994 0.1984833 0.2744277 0.3708430 0.1877194 NaN
[8] 0.3688126 0.3357178 0.4359122
>
I like this definition after all. :)
Gabor
On Sat, Apr 14, 2007 at 06:05:12PM +0200, Gabor Csardi wrote:
> On Wed, Apr 11, 2007 at 04:25:44PM -0400, Colin Garroway wrote:
> > Gabor,
> >
> > Thanks for the quick response. I'll keep working at it.
> >
> > Again I'm new to networks but Holme et al. 2007 Physica A 373 (2007),
> > 821-830 ([1]http://arxiv.org/abs/cond-mat/0411634 ) seem to have come up
> > with a clustering coefficient for weighted networks that has all the
> > typical desired porperties.
>
> Colin, i've checked this definition, and IMHO there is a problem with it.
> It doesn't even work for unweighted graphs, see for example the
> small graph in Fig. 5 from
> http://www-personal.umich.edu/~mejn/courses/2004/cscs535/review.pdf
>
> g <- graph ( c(0,1, 0,2, 1,2, 2,3, 2,4), directed=FALSE)
> transitivity(g, "local")
>
> [1] 1.0000000 1.0000000 0.1666667 NaN NaN
>
> Which is correct according to my calculation and the paper (apart from
> the NaNs). The method in the Holme paper however gives
>
> A <- get.adjacency(g)
> diag ( A %*% A %*% A ) / diag (A %*% matrix(1, nr=nrow(A), nc=ncol(A)) %*% A)
>
> [1] 0.500 0.500 0.125 0.000 0.000
>
> It is clear that diag( A %*% A %*% A ) gives twice the number triangles
> a vertex is connected to. It is not clear for me what
> diag (A %*% matrix(1, nr=nrow(A), nc=ncol(A)) %*% A) gives,
> but it should give twice the number of triples centered on the vertex
> to get the correct transitivity. But it doesn't. Or do i make a
> mistake somewhere?
>
> So, to sum it up. If you like this definition of transitivity then
> you easily calculate the weighted transitivity of g as:
>
> W <- get.adjacency(g, attr="weight")
> diag(W %*% W %*% W) / diag(W %*% matrix(max(W),nr=nrow(W),nc=ncol(W)) %*% W)
>
> G.
>
> > Colin
> >
>
> --
> Csardi Gabor <address@hidden> MTA RMKI, ELTE TTK
--
Csardi Gabor <address@hidden> MTA RMKI, ELTE TTK