[R-sig-Geo] grabriel graphs weighted by alternative distance measure

Roger Bivand Roger.Bivand at nhh.no
Tue Apr 6 12:09:41 CEST 2010


On Mon, 5 Apr 2010, Ilona Naujokaitis-Lewis wrote:

> Hello everyone,
>
> I am working on the problem of creating alternative types of graphs (i.e.
> networks) based on alternative distance measures and then comparing
> topological differences between them.  Specifically I am constructing graphs
> created using euclidean distances versus genetic distances. These different
> distance measures are used to create alternative graphs as they represent
> the links (or edges) between the nodes (vertices).
> I would like to compare 3 types of graphs:
> 1. Complete (saturated graphs where all nodes are connected to one another)
> 2. Gabriel graphs,
> 3. minimum spanning trees
>
> I can build complete and minimum spanning trees using both distance types as
> weights for the links. For the minimum spanning tree situation, this creates
> 2 very different looking graphs. I am currently not able to create Gabriel
> graphs using an alternative to Euclidean distance as links between nodes.
> Although, gabriel graphs are a type of planar graph, it is my understanding
> that one should be able to construct Gabriel graphs based on alternative
> distance measures. In the population genetics software it is possible to do
> this. The result is generally 2 Gabriel graphs where the links between nodes
> are in different locations (i.e. the graphs should not look identical). I
> would like to do this in R but am running into trouble as the Garbriel
> functions seem to only use coordinates as inputs. I have looked into the
> following packages: spdep (spatial neighbour applications), igraph,
> spatgraphs, ade4.
>
> The data I have are:
> 1. coordinates of nodes (vertices)
> 2. pairwise distance matrix of genetic and euclidean distance between nodes
>
> Here is a small bit of code using some simulated data.
>
> # Create coordinate data
> x <- round(runif(20,1,10),1)
> y <- round(runif(20,5,10),1)
> xy <- cbind(x,y)
> # Create gabriel graph based on Euclidean distance
> col.gab <- graph2nb(gabrielneigh(xy))
> plot(col.gab,xy)
>
>
> # create a matrix of weights: in my case this represents measures of genetic
> distance between each pair of nodes
> # diagonal = 0
> # lower and upper matrix parts have identical values
> genetic <- matrix(0,nrow=20,ncol=20)
> genetic <- matrix(rnorm(500, 0.5, 0.25),nrow=20,ncol=20)
> genetic[lower.tri(genetic)] <- genetic[upper.tri(genetic)]
> diag(genetic)<-c(rep(0,length(genetic[1,])))
>
>
> Weighting the links after the Gabriel graph is created based on Euclidean
> distance does not make sense for me.
> If anyone has an idea of how I might try and create Gabriel graphs based on
> a distance measure that is not Euclidean, I would love to hear it.
>
> Thanks in advance for everyone's help.

In an earlier thread relevant to this topic, it was suggested that 
syntheic coordinates could be extracted from multidimensional scaling of 
the non-Euclidean distance matrix. You could try this, and judge how far 
from what you need you land by doing complete and MST on the synthetic 
coordinates for comparison. If this shows that the synthetic coordinates 
are no use, you'll be obliged to program your own Gabriel function for 
user-supplied distances. If you'd like to contribute such a function back, 
I think others would be grateful.

Hope this helps,

Roger

>
> I am currently using R (v.2.10.1) on Windows XP.
>
> Ilona Naujokaitis-Lewis, PhD student
>
>

-- 
Roger Bivand
Economic Geography Section, Department of Economics, Norwegian School of
Economics and Business Administration, Helleveien 30, N-5045 Bergen,
Norway. voice: +47 55 95 93 55; fax +47 55 95 95 43
e-mail: Roger.Bivand at nhh.no



More information about the R-sig-Geo mailing list