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

[Gabor Csardi]

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