[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[igraph] igraph issue with massive matrices

From: address@hidden
Subject: [igraph] igraph issue with massive matrices
Date: Fri, 29 Nov 2019 08:42:39 +0000

Dear all,


I have a question about using igraph on huge transition matrices because I have encountered some strange effects in the analysis I am doing, and I think the source of these could be in the igraph package.


Some background

I have been working with Jacob van Etten (gdistance package owner) and Dan Weiss (U Oxford) to generate global scale models of travel time across raster surfaces using the gdistance package, which depends on igraph.  You can see some of the outputs here and here.


To make these travel time surfaces, I have been generating 1km spatial resolution maps where each 1km pixel has a resistance value representing the travel time required to cross that pixel.  This represents a cost surface which  then use to estimate the ground or water-based travel time from any location on the earth to the nearest city.


In gdistance I generate a symmetric distance or transition matrix from this cost surface. I have been doing this for areas up to 40 x 40 degrees in size, which is 4440 x 4440 pixels, and I then save it as a file for future processing since it takes many hours to generate these.  Luckily I have access to a  server with 512GB RAM for this.  I need these huge tiles because the distance between a location and a nearest large city can be many thousands of kms. 


This transition matrix is then used in to derive the travel time maps you see in the links above based an accumulated cost (accost) function.


The problem

I am using tiles up to 40 x 40 degrees because anything larger results in the transition matrix calculation bailing out with an error (memory limit perhaps?).   I thought this was the only issue and thought I had solved it by limiting my analysis to this size of tile.  However, I have discovered another issue where the transition matrix calculation completes “successfully” on these large graphs, but the results still contain or produce flaws in the accCost results despite appearing to have run correctly. 


Sometimes they are obvious, (e.g., 1/3 of the tile would be a solid block of zeros).  On other occasions, this issue manifests itself in a much more insidious way (i.e., results that appear OK, but may not be, with example of obtaining travel times of zero in the top left corner of the tiles). 


I am not sure why this happens.  On one hand, I may be running into a memory limit in R, but the other behaviours may be related to limits within igraph.


Would you have some insight or advice on this issue? 


In an ideal situation I would like to run these models globally without resorting to overlapping smaller tiles, which is what I have done in GIS packages in the past, but none of these GIS packages deal correctly with great circle distances between locations, so R using gdistance and igraph provides the most realistic output.


Has anyone run into the problem before and has any advice on how to solve it?







Andy Nelson Professor, Spatial Agriculture and Food Security & Head of Department

Department of Natural Resources (Room 4-144)

ITC - Faculty of Geo-Information Science and Earth Observation of the University of Twente

PO Box 217, 7500 AE Enschede, the Netherlands.

Tel: +31 (0) 53 489 3072

Natural Resources Management Research and MSc programmes at ITC



reply via email to

[Prev in Thread] Current Thread [Next in Thread]