Big Data Graphs: Loopy Lattices

the content of this article was originally co-authored by marko rodriguez and bobby norton over at the aurelius blog .

a lattice is a graph that has a particular, well-defined structure. an nxn lattice is a 2-dimensional grid where there are n edges along its x-axis and n edges along its y-axis. an example 20x20 lattice is provided in the two images above. note that both images are the “same” 20x20 lattice. irrespective of the lattice being “folded,” both graphs are isomorphic to one another (i.e. the elements are in one-to-one correspondence with each other). as such, what is important about a lattice is not how it is represented on a 2d plane , but what its connectivity pattern is. using the r statistics language , some basic descriptive statistics are computed for the 20x20 lattice named g.

~$ r

r version 2.13.1 (2011-07-08)
copyright (c) 2011 the r foundation for statistical computing
...
> length(v(g))
[1] 441
> length(e(g))
[1] 840
> hist(degree(g), breaks=c(0,2,3,4), freq=true, xlab='vertex degree', ylab='frequency', cex.lab=1.25, main='', col=c('gray10','gray40','gray70'), labels=true, axes=false, cex=2)

the degree statistics of the 20x20 lattice can be analytically determined. there must exist 4 corner vertices each having a degree of 2. there must be 19 vertices along every side that each have a degree of 3. given that there are 4 sides, there are 76 vertices with degree 3 (19 x 4 = 76). finally, their exists 19 rows of 19 vertices in the inner-square of the lattice that each have a degree of 4 and therefore, there are 361 degree 4 vertices (19 x 19 = 361). the code snippet above plots the 20x20 lattice’s degree distribution –confirming the aforementioned derivation. the 20x20 lattice has 441 vertices and 840 edges. in general, the number of vertices in an nxn lattice will be (n+1)(n+1) and the number of edges will be 2((nn) + n).

traversals through a directed lattice

suppose a directed lattice where all edges either point to the vertex right of or below the tail vertex. in such a structure, the top-left corner vertex has only outgoing edges. similarly, the bottom-right corner vertex has only incoming edges. an interesting question that can be asked of a lattice of this form is:

“how many unique paths exist that start from the top-left vertex and end at the bottom-right vertex?”

for a 1x1 lattice, there are two unique paths.

0 -> 1 -> 3
0 -> 2 -> 3

as diagrammed above, these paths can be manually enumerated by simply drawing the paths from top-left to bottom-right without drawing the same path twice. when the lattice becomes too large to effectively diagram and manually draw on, then a computational numerical technique can be used to determine the number of paths. it is possible to construct a lattice using blueprints ‘ tinkergraph and traverse it using gremlin . in order to do this for a lattice of any size (any n), a function is defined named generatelattice(int n).

def generatelattice(n) {
  g = new tinkergraph()
  
  // total number of vertices
  max = math.pow((n+1),2)
  
  // generate the vertices
  (1..max).each { g.addvertex() }
    
  // generate the edges
  g.v.each {
    id = integer.parseint(it.id)

    right = id + 1
    if (((right % (n + 1)) > 0) && (right <= max)) {
      g.addedge(it, g.v(right), '')
    }

    down = id + n + 1
    if (down < max) {
      g.addedge(it, g.v(down), '')
    }
  }
  return g
}

an interesting property of the “top-to-bottom” paths is that they are always the same length. for the 1x1 lattice previously diagrammed, this length is 2. therefore, the bottom right vertex can be reached after two steps. in general, the number of steps required for an nxn lattice is 2n.

gremlin> g = generatelattice(1) 
==>tinkergraph[vertices:4 edges:4]
gremlin> g.v(0).out.out.path    
==>[v[0], v[2], v[3]]
==>[v[0], v[1], v[3]]
gremlin> g.v(0).out.loop(1){it.loops <= 2}.path
==>[v[0], v[2], v[3]]
==>[v[0], v[1], v[3]]

a 2x2 lattice is small enough where its paths can also be enumerated. this enumeration is diagrammed above. there are 6 unique paths. this can be validated in gremlin.

gremlin> g = generatelattice(2)               
==>tinkergraph[vertices:9 edges:12]
gremlin> g.v(0).out.loop(1){it.loops <= 4}.count()
==>6
gremlin> g.v(0).out.loop(1){it.loops <= 4}.path
==>[v[0], v[3], v[6], v[7], v[8]]
==>[v[0], v[3], v[4], v[7], v[8]]
==>[v[0], v[3], v[4], v[5], v[8]]
==>[v[0], v[1], v[4], v[7], v[8]]
==>[v[0], v[1], v[4], v[5], v[8]]
==>[v[0], v[1], v[2], v[5], v[8]]

if a 1x1 lattice has 2 paths, a 2x2 6 paths, how many paths does a 3x3 lattice have? in general, how many paths does an nxn lattice have? computationally, with gremlin, these paths can be traversed and counted. however, there are limits to this method. for instance, try using gremlin’s traversal style to determine all the unique paths in a 1000x1000 lattice. as it will soon become apparent, it would take the age of the universe for gremlin to realize the solution. the code below demonstrates gremlin’s calculation of path counts up to lattices of size 10x10.

gremlin> (1..10).collect{ n ->
gremlin>   g = generatelattice(n)
gremlin>   g.v(0).out.loop(1){it.loops <= (2*n)}.count()
gremlin> }
==>2
==>6
==>20
==>70
==>252
==>924
==>3432
==>12870
==>48620
==>184756

a closed form solution and the power of analytical techniques

in order to know the number of paths through any arbitrary nxn lattice, a closed form equation must be derived. one way to determine the closed form equation is to simply search for the sequence on google . the first site returned is the online encyclopedia of integer sequences . the sequence discovered by gremlin is called a000984 and there exists the following note on the page:

“the number of lattice paths from (0,0) to (n,n) using steps (1,0) and (0,1). [joerg arndt, jul 01 2011]“

the same page states that the general form is “2n choose n.” this can be expanded out to its factorial representation (e.g. 5! = 5 * 4 * 3 * 2 * 1) as diagrammed below.

given this closed form solution, an explicit graph structure does not need to be traversed. instead, a combinatoric equation can be evaluated for any n. a directed 20x20 lattice has over 137 billion unique paths ! this number of paths is simply too many for gremlin to enumerate in a reasonable amount of time.

> n = 20
> factorial(2 * n) / factorial(n)^2
[1] 137846528820

a question that can be asked is: “how does 2n choose 2 explain the number of paths through an nxn lattice?” when counting the number of paths from vertex (0,0) to (n,n), where only down and right moves are allowed, there have to be n moves down and n moves right. this means there are 2n total moves, and as such, there are n choices (as the other n “choices” are forced by the previous n choices). thus, the total number of moves is “2n choose n.” this same integer sequence is also found in another seemingly unrelated problem (provided by the same web page).

“number of possible values of a 2*n bit binary number for which half the bits are on and half are off. – gavin scott, aug 09 2003″

each move is a sequence of letters that contains n ds and n rs, where down twice then right twice would be ddrr. this maps the “lattice problem” onto the “binary string of length 2n problem.” both problems are essentially realizing the same behavior via two different representations.

plotting the growth of a function

it is possible to plot the combinatorial function over the sequence 1 to 20 (left plot below). what is interesting to note is that when the y-axis of the plot is set to a log-scale , the plot is a straight line (right plot below). this means that the number of paths in a directed lattice grows exponentially as the size of the lattice grows linear.

> factorial(2 * seq(1,n)) / factorial(seq(1,n))^2
 [1]            2            6           20           70          252          924
 [7]         3432        12870        48620       184756       705432      2704156
[13]     10400600     40116600    155117520    601080390   2333606220   9075135300
[19]  35345263800 137846528820

> x <- factorial(2 * seq(1,n)) / factorial(seq(1,n))^2
> plot(x, xlab='lattice size (n x n)', ylab='total number of paths', cex.lab=1.4, cex.axis=1.6, lwd=1.5, cex=1.5, type='b')
> plot(x, xlab='lattice size (n x n)', ylab="total number of paths", cex.lab=1.4, cex.axis=1.6, lwd=1.5, cex=1.5, type='b' log='y')

conclusion

it is wild to think that a 20x20 lattice, with only 441 vertices and 840 edges, has over 137 billion unique directed paths from top-left to bottom-right. it’s this statistic that makes it such a loopy lattice ! anyone using graphs should take heed. the graph data structure is not like its simpler counterparts (e.g. the list , map , and tree ). the connectivity patterns of a graph can yield combinatorial explosions . when working with graphs, it’s important to understand this behavior. it’s very easy to run into situations, where if all the time in the universe doesn’t exist, then neither does a solution.

acknowledgments

this exploration was embarked on with dr. vadas gintautas . vadas has published high-impact journal articles on a variety of problems involving biological networks, information theory, computer vision, and nonlinear dynamics. he holds a ph.d. in physics from the university of illinois at urbana champaign.

finally, this post was inspired by project euler . project euler is a collection of math and programming challenges. problem 15 asks, “how many routes are there through a 20x20 grid?”