Well, to start with, the issue here isn't that Ruby doesn't efficiently support the "modify-in-the-middle" access pattern. It's just that Ruby does this with the Array class. Similarly, even if you intend to insert into the middle, you still probably still want to use NSMutableArray in Objective C.
Even on fairly large graphs --- say, graphs at the scale of basic blocks in a program, but (obviously) not on the scale of "recommendation graph at Amazon" --- you shouldn't be burning huge numbers of cycles seeking through reference links. In naive reference-link implementations, Ruby sorely increases the constant factors for graph analysis, but computing a minimum cost spanning tree isn't going to kill you (especially because the intermediate data structures you'd use to do it would be native-code Arrays and Hashes). On the other hand, linked lists more or less pessimize Ruby, forcing it to do nothing but expensive interpreter looping, pointer chasing, and object management.
Having said all that, for serious work, I'd keep my data structures outboard, probably in Redis.
Other people would probably answer "just write a graph library in C; for instance, you could write a C wrapper around void-star-specialized boost::graph", then bridge it to Ruby with FFI.
Ruby is as good at C for I/O bound problem subsets. This is a lot of problems, and so having a language as pleasant to write in as Ruby is a win (you could say the same for Node.js and maybe even Python). It is obviously not the only language you'll ever need, though.
