Processing and storing a graph with a large number of vertices s.t. k-hop neighborhoods are efficiently retrievable

Question

I have an unweighted, undirected graph $G$ with $(v_1, ..., v_N) \in V$ vertices, where each vertex in the lattice represents a string of some length ($\leq 200$ characters), and I need to construct $G$ from an unordered list of edges between vertices (i.e. a list saying that vertex $v_i$ is connected to vertex $v_j$ for some $i \neq j$). Here, $||V||$ is very large, on order $10^{9}$ to $10^{12}$ or so, but the degree of each vertex $v_i$ is bounded by some small integer value s.t. the maximum vertex degree is $\Delta G\approx 16$.

What is a good way to store or process $G$ in Mathematica (some sort of suffix tree or hash table?) s.t. I can efficiently retrieve a list of vertices in the $k$-hop neighborhood of some vertex $v_i$? By $k$-hop neighborhood, I mean the set of vertices that can be reached from $v_i$ by traveling along at most $k$ edges.

---

To provide an example, I might start with a list of vertices corresponding to unique binary strings:

$v_1 = 10101011110...$

$v_2 = 01110100101...$

...

$v_N = 00000011110...$

And an unordered list of (undirected) edges between vertices:

$v_{36544} \to v_{3}$

$v_{740943} \to v_{92034}$

$v_{36544} \to v_{674}$

...

Is there a nice / efficient way to process the about lists in Mathematica s.t. I can retrieve the set of nearest-neighbors for, say, $v_{36544}$, which includes $(v_{3}, v_{674}, ...)$?

The naive way to proceed is to simply specify a graph structure as: Graph[{...}], but is this efficient for very large instances of $G$?

---

Update - OK, some data.

Intel Xeon CPU (X5690) 3.47 GHz 64 bit system

(No attempt at parallelization)

Lookup time for the $k=1$ hop neighborhood of an arbitrary vertex (using NeighborhoodGraph[G]):

G = 10 x 10 integer lattice: 27.4 milliseconds

G = 50 x 50 integer lattice: 0.765 seconds

G = 100 x 100 integer lattice: 3.08 seconds

The scaling appears exactly linear with graph size: http://www.wolframalpha.com/input/?i=%7B0.0274%2C+10%5E2%7D%2C%7B0.765%2C2500%7D%2C%7B3.08%2C100%5E2%7D

This is awful, especially considering that Mathematica can draw a spring minimized graph in relatively short order for the 100 x 100 integer lattice.

Answer 1

Mathematica uses an adjacency list representation or an adjacency matrix representation depending on the input graph.

On a 64 bit machine, a graph (or sparse adjacency matrix) with n vertices of degree less than d requires at least 64*n + 2*64*m bits with 64*n bits to store vertices and 2*64*m bits to store connectivity informations for approximately m = n*d/2 edges. For n = 10^9 and d = 16, at least 136 GB are needed to represent the graph and probably twice this amount for processing.

AdjacencyList[g, v, k] will efficiently retrieve the set of nearest neighbors, roughly constant time.

In[1]:= First[AbsoluteTiming[AdjacencyList[#, 1, 4]]] & /@ Table[ GridGraph[{n, n}], {n, 4, 10}]

Out[1]= {0.000184, 0.000180, 0.000103, 0.000102, 0.000102, 0.000198, 0.000201}

NeighborhoodGraph builds a graph as well as the subsequent embedding, hence the linear complexity for integer lattices. See Why is NeighborhoodGraph so slow?