Single-Graph Support Measures
Toon Calders, Jan Ramon, Dries Van Dyck · Lirias · 2014
In this chapter we will discuss measures for the frequency of graph patterns in a single large graph. Defining such a graph measure is a non-trivial task since many natural definitions in the graph transaction setting are non-monotonic in the single-graph setting. Many pattern mining algorithms, however, rely critically on the monotonicity of the support measure for efficient exploration of the search space. Besides imposing a computational burden, a non-monotonic measure also leads to nonintuitive situations where a sub-pattern seemingly occurs less frequently than a larger super-pattern. In our overview, we divide the support measures into two classes: those based on the overlap-graph of the pattern, and the others.