  Counting the number of triangles in a graph has many important applications
in network analysis. Several frequently computed metrics like the clustering
coefficient and the transitivity ratio need to count the number of triangles in
the network. Furthermore, triangles are one of the most important graph classes
considered in network mining. In this paper, we present a new randomized
algorithm for approximate triangle counting. The algorithm can be adopted with
different sampling methods and give effective triangle counting methods. In
particular, we present two sampling methods, called the \textit{$q$-optimal
sampling} and the \textit{edge sampling}, which respectively give $O(sm)$ and
$O(sn)$ time algorithms with nice error bounds ($m$ and $n$ are respectively
the number of edges and vertices in the graph and $s$ is the number of
samples). Among others, we show, for example, that if an upper bound
$\widetilde{\Delta^e}$ is known for the number of triangles incident to every
edge, the proposed method provides an $1\pm \epsilon$ approximation which runs
in $O( \frac{\widetilde{\Delta^e} n \log n}{\widehat{\Delta^e} \epsilon^2} )$
time, where $\widehat{\Delta^e}$ is the average number of triangles incident to
an edge. Finally we show that the algorithm can be adopted with streams. Then
it, for example, will perform 2 passes over the data (if the size of the graph
is known, otherwise it needs 3 passes) and will use $O(sn)$ space.
