Does anybody know how to efficiently (non-exponentially) walk a web
graph to detect cycles. This would be very useful in identifying spammy
webpage and tight knit communities.

I have a program that I will be releasing soon that does the detection
through converting a webgraph into a tree and walking the tree nodes,
but it is exponential in terms of intermediate map reduce output and
computation.

Dennis