Friday, October 24, 2008

Pattern Recognition in Graphs

Recognition of a pattern in a graph is a curious thing. On the one hand, if patterns can be seen among relationships of nodes by their edges, then relationships exist whether or not they can be seen with the eye. In other words, the relationship is inherently mathematical and can be conclusively tested. On the other hand, decision making is not strictly binary, i.e., does the relationship exist? yes/no. Even when decision making is highly quantitative it is most often multi-dimensional. This is where graph visualization comes in. There is significant utility in having the capability to see multiple data dimensions simultaneously by affecting the many attributes of graphical objects. When people are considering multi-dimensional problem spaces then they are engaged in a level of thinking that is poorly supported by low-level primitives (ex., tables of numbers).  Decision-making based on tables of tuples is no way to go.  Pattern recognition is mind numbing.  The best we can do is perform operations on rows and columns; counting, sorting, grouping, filtering.  While these are immensly useful and powerful, they overlook the possibility that patterns exist among the atomic, non-aggregate entities themselves.  Furthermore, we don't know what they are until we see them and therefore cannot apply operations a priori.  On the other hand, given layered, multi-dimensional graphics we can map these many atomic attributes of abstract data to the attributes of graphical objects.  Then we can use operations for manipulating graphical attributes to reveal patterns.  This is particularly useful in graph visualization, i.e., of networks:



Revealing two distinct communities of interest