Mining Persistent and Discriminative Communities in Graph Ensembles

Detecting all communities in a single graph is a prevalent task in graph data analytics. However, many scientific applications naturally create data as an ensemble of graphs. For example, graph ensembles can be created from multiple: social networks at distinct points in time, biological networks created from independent experiments, and global climate networks created from unique climate models. In this work, we present a method for enumerating community subsets across an ensemble of graphs, with the ability to detect both persistent and discriminative subcommunities. Moreover, we support queries, consisting of user-specified vertices of interest and arbitrary ensemble slices, to produce output that is more relevant to the user while reducing output size and computation time. While related methods are designed around a single community definition, our method is designed around the idea that choosing an appropriate community definition often depends on the application at hand. Therefore, our goal is to provide a framework that can leverage the abundance of community detection methods available when discovering persistent and discriminative substructures.