# 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 '13 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? – Roger Harris Feb 7 '13 at 5:05
very good question. Looking forward to an answer from someone who would know :) – kglr Feb 7 '13 at 5:47
Did you try AdjacencyList[g, v, k] ? – halmir Feb 7 '13 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). – Daniel Lichtblau Feb 7 '13 at 14:49

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?

-