Some thoughts on matrix-less graphs.

I’ve been lately thinking about graphs that have no matrix. An example of a matrix graph is the traditional planar coordinate plane you’re probably familiar with: the x,y graph where each element (vertex, in graph terminology) has an identity of two real numbers identifying its coordinate. Subsequently, to make this a graph, we draw lines (edges) in between points (vertices).

Usually, when graph theorists talk about graphs, there’s some explicit or implicit (e.g. they draw a picture of the graph on a piece of paper) coordinate plane. Having started to read through James Tauber’s excellent Poincaré Project I’ve got a clear idea of what a coordinate system (aka Metric Space is, now; it’s a set where every element of the set has a distance function that gives us a postive numerical value for any two elements of the set)
Without a matrix or coordinate system, there is no set of real numbers providing identity to a vertex.

Therefore, the only meaningful identity of a vertex in a matrix-free graph is its relationships.

We can consider a vertex to be a set of edges to other vertices; however, this suggests that every vertex would have to contain every other edge, becaue the set {vertex, vertex} that represents one edge would expand until it contained all the edges in the graph.

So it would be very helpful if each vertex had some identity, even if the identity isn’t something that can be mapped onto a matrix.

We’ll imagine that every vertex has an identity that can be represented as a binary sequence of arbitrary length.

Now we can store the {vertex,vertex} structure much more compactly; a given edge can be considered to be the symmetric difference (the XOR value) of the sequences.

If all of the vertex identities are unique, this suffices to uniquely represent a given state of connectivity.

However, the XOR value can be arbitrarily large, and so it would be better to find some guaranteed small value that still avoids collisions.

Furthermore, it leaves ‘edginess’ implicit; for the most part, edges between vertices have some meaning, whether it be ‘vertex is connected to vertex’ or ‘vertex occured before vertex’ or ‘vertex sucker punchced vertex at a kegger once’ so let’s further say that every edge also has an identity that can be represented as a binary sequence of arbitrary length.

Now we’re looking for compact representations of {vertex,edge,vertex} triplets. We can represent any triplet as a vector, and happily all the cool kids are into vector calculations these days.

Using a bloomier filter instead of a simple XOR should get rid of the arbitrary size problem of vector representation. I think I understand the general idea of bloomier filters, but Chazelle et al. use a lot of notation I find opaque at the moment.

An interesting question to me at the moment is the matter of distance functions. It’s one thing when we’re talking about simple spatial mapping, but I’m mostly curious about how to do spatial representations of nodes that are associated through qualitative or semi-quantitative relationships. A fairly straightforward example of this is the representation of a family tree; while there are ‘quantitative’ relationships (bob and jill begat jane, etc) there are also qualitative relationships (jill divorced bob) that need to be represented. There are other, more complicated qualitative relationships I’d like to graph, and in a perfect world I’d figure out some set of operations that could allow me to convert arbitrary qualitative relationships into some form of vaguely meaningful spatial relationships.

All of this is getting me exited about (one day) developing for the PS3; having all those vector processing units available would let me do some really expensive calculations – particularly ones where I need to consider the relative positions of a substantial portion of a set in order to represent them in an ordinal space (e.g. 3d) – and still give near real-time feedback to the user.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s