igraph-help
[Top][All Lists]

## 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")
}

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
>
> 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:
>
> 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

```