The standard, transactional setting of pattern mining assumes that data is subdivided in transactions; the aim is to find patterns that can be mapped onto at least a minimum number of transactions. However, this setting can be hard to apply when the aim is to find graph patterns in databases consisting of large graphs. For instance, the web, or any social network, is a single large graph that one may not wish to split into small parts. The focus in network analysis is on finding structural regularities or anomalies in one network, rather than finding structural regularities common to a set of them. This requires us to revise the definition of key concepts in pattern mining, such as support, in the single-graph setting. Our contribution is a support measure that we prove to be computationally less expensive and often closer to intuition than other measures proposed. Further we prove several properties between these measures and experimentally validate the efficiency of our measure.