Abstract
The frequency of small patterns, such 3 or 4-cliques or rectangles can reveal a lot of information about a graph. In social sciences, they are referred to as structural signatures, and in biology they are called graphlets. Subsequently, many algorithms have been proposed to efficiently count these patterns. We are developing sampling based approaches to count frequent patterns in graphs. Our methods come with provable error/confidence bounds. This talk will summarize the wedge sampling method for computing triadic measures, its generalization as a streaming algorithm, and our recent results on higher order structures.