[igraph] Average Path Length / Diameter

[Thomas F. Brantle]

Gabor and Others:

 

I know that those computations involving “shortest path” analyses will be fairly “costly and time consuming” from a computational point of view (i.e., m*n).  Please let me give you a general idea of my network data and other potential computer resource constraints.

 

The primary network data that I want to analyze includes a few datasets of approximately 2 – 3 million nodes and 10 – 30 million links, each. For these shortest path (e.g., average shortest path length) computations I assume that my network is “undirected” and I also expect the largest or giant component to include 90-99% of the nodes.

 

For these analyses I’m using an 8GB/2800MHz Linux (Ubuntu) server. Given these computing constraints, I would greatly appreciate your suggestions on a computing (and computational) strategy for my network dataset analyses. I’ve estimated that the computation could take a month or more.

 

Given this issue, is there a convergence strategy, computational sampling, numerical approximation or other alternative that may be incorporated? I’ve searched the literature and haven’t seen this issue directly addressed, unless I just missed it.

 

If you have any ideas or a suggested computational strategy I’d greatly appreciate it.

 

Thanks,

--Tom