Dennis Kubes wrote:
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.
Perhaps this could be helpful:
* http://www.cs.berkeley.edu/~kamil/teaching/sp03/041403.pdf see the
last section.
* http://citeseer.ist.psu.edu/395003.html
* http://en.wikipedia.org/wiki/Cycle_detection
--
Best regards,
Andrzej Bialecki <><
___. ___ ___ ___ _ _ __________________________________
[__ || __|__/|__||\/| Information Retrieval, Semantic Web
___|||__|| \| || | Embedded Unix, System Integration
http://www.sigram.com Contact: info at sigram dot com
