We're working on a paper that presents some algorithms for finding triangles and network motifs (constant size subgraphs, also known as graphlets) in a distributed setting. We characterize the tradeoff between the number of triangles in the graph and the communication load necessary. I am looking for references to work done on this question in the centralized model.
The problem is that nearly everything I found on this topic that had a theoretical flavor to it was within the framework of property testing. To illustrate the difference - consider the case of a graph with $n$ vertices, that is comprised of $n-2$ triangles all sharing the edge $\left(1,2\right)$. From the point of view of property testing, this graph is very close to be triangle-free (removing that critical edge does the job), whereas it has a linear number of triangles, which is a lot by our standards.
Any references at all will be appreciated.
Edit: I'm mainly interested in algorithms that can determine whether the graph contains triangles quickly. For triangle (or other subgraph) listing algorithms, the running time is naturally bounded from below by the number of triangles in the graph, as the algorithm needs to list them all, making such instances harder in a sense. From the point of view of a decision problem ("triangle-free or not"), having many triangles actually makes the problem easier, since you can easily find one.