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.
SparseArray
for the adjacency matrix, and matrix multiplication (or matrix-vector) for the k-hop computations. But even with that structure I don't think you can get to the size range of interest (or at best you might hit the lower end of it). $\endgroup$