3-cycle enumeration on random dot product graph

Question

The graph is generated with $p=n^{-0.5}$,which $p$ means the probability the two random vector dot product is large enough to add an edge. Brute force algorithm run in expect time $O(n^2)$.I think the expect number of 3-cycles are O(n).Is there an algorithm run in expect time in $O(m)$ or at least better than brute force?

Answer 1

Finally , i get an negative result. This paper 1 shows that need at least $O(m^{4/3})$ time for a exact algorithm under ASPS hypothesis which is as bad as brute force.

Monochromatic Triangles, Triangle Listing and APSP