Subgraph Enumeration in Dynamic Graphs

A fundamental problem in many applications involving social and biological networks is to identify and count the number of embeddings of a given small sub graph in a large graph. Often, they involve dynamic graphs, in which the graph changes incrementally (e.g., by edge addition/deletion). We study the Dynamic Sub graph Enumeration (DSE) Problem, where the goal is to maintain a dynamic data structure to solve the sub graph enumeration problem efficiently when the graph changes incrementally. We develop a new data structure that combines two techniques: (i) the color-coding technique of Alon et al., 2008, for enumerating trees, and (ii) a dynamic data structure for maintaining the h-index of the graph (developed by Eppstein and Spiro, 2009). We derive worst case bounds for the update time in terms of the h-index of the graph and the maximum degree. We also study the empirical performance of our algorithm in a large set of real networks, and find significant improvement over the static methods.