6
$\begingroup$

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.

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

1 Answer 1

6
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.