Re: [igraph] shortest path between all nodes on a weighted network

[Gabor Csardi]

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