Andrzej Bialecki
Mon, 14 Jul 2008 11:49:37 -0700
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