Mining Contrasting Quasi-Clique Patterns
  Mining dense quasi-cliques is a well-known clustering task with applications
ranging from social networks over collaboration graphs to document analysis.
Recent work has extended this task to multiple graphs; i.e. the goal is to find
groups of vertices highly dense among multiple graphs. In this paper, we argue
that in a multi-graph scenario the sparsity is valuable for knowledge
extraction as well. We introduce the concept of contrasting quasi-clique
patterns: a collection of vertices highly dense in one graph but highly sparse
(i.e. less connected) in a second graph. Thus, these patterns specifically
highlight the difference/contrast between the considered graphs. Based on our
novel model, we propose an algorithm that enables fast computation of
contrasting patterns by exploiting intelligent traversal and pruning
techniques. We showcase the potential of contrasting patterns on a variety of
synthetic and real-world datasets.
