Granularity of co-evolution patterns in dynamic attributed graphs

Many applications see huge demands for discovering relevant patterns in dynamic attributed graphs, for instance in the context of social interaction analysis. It is often possible to associate a hierarchy on the attributes related to graph vertices to explicit prior knowledge. For example, considering the study of scientific collaboration networks, conference venues and journals can be grouped with respect to types or topics. We propose to extend a recent constraint-based mining method by exploiting such hierarchies on attributes. We define an algorithm that enumerates all multi-level co-evolution sub-graphs, i.e., induced sub-graphs that satisfy a topologic constraint and whose vertices follow the same evolution on a set of attributes during some timestamps. Experiments show that hierarchies make it possible to return more concise collections of patterns without information loss in a feasible time. © 2014 Springer International Publishing Switzerland.