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

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.

• – kglr
Feb 7, 2013 at 4:58
• @kguler But what data structure does Mathematica use when you specify a graph, and is it efficient for very large graph structures? Feb 7, 2013 at 5:05
• very good question. Looking forward to an answer from someone who would know :)
– kglr
Feb 7, 2013 at 5:47
• Did you try AdjacencyList[g, v, k] ? Feb 7, 2013 at 14:04
• You might consider using a 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). Feb 7, 2013 at 14:49

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