Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question
    
NeighborhoodGraph? –  kguler 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 :) –  kguler 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
add comment

1 Answer

up vote 4 down vote accepted

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?

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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