Chris Gatti

The Academic Acrobat

Graph Search

More and more phenomena and data can be modeled using graphs, with some of these graphs being extremely large. This work was aimed at developing and implementing a graph search method that could quickly search for a specific fragment (subgraph) within a very large graph. The methodology was based on developing a vector which containes the local neighborhood of graph nodes, and then comparing the fragment vectors to those of the large graph. This comparison can be done very quickly if the nodes are indexed appropriately. This work was able to find subgraphs of about 20 nodes in a database graph with over 1 million nodes and about 3 million edges in a few seconds (based on prototyped code, developed in R).