Home | Search | Help  
Home Page Università di Genova

Technical Report Details


Date 3-4-2006
Number DISI-TR-06-05
Title Effects of the decay factor in the BFS Algorithm
Authors Alessandro Di Marco
Bibtex Entry @techreport {bfsdrain06, author = {Alessandro Di Marco}, title = {Effects of the decay factor in
E-mail dmr@disi.unige.it
Link ftp://ftp.disi.unige.it/person/DimarcoA/bfsdrain.pdf
Abstract The BFS algorithm is a generalization of the InDegree algorithm inspired by the Hits algorithm. The BFS algorithm extends the idea of popularity that appears in the InDegree algorithm from a one-link neighborhood to an n-link neighborhood, and the construction of this latter is inspired by the Hits algorithm. The BFS algorithm starts from a node and visits its neighbors in BFS order, alternating between backward and forward steps. Every time we move one link further from the starting node, we update the weight factors according to an exponentially decreasing weighting scheme. In this paper we analyze the BFS behavior for different weighting schemes. In particular, we will show how different schemes, each characterized by a particular decay factor, affect the authorithy weights of pages in several synthetic hyperlink graphs. Furthermore, we will introduce a clever technique, named "weight draining", that can actually increase the weigth of a target node through few hyperlink injections.
Back to Technical Reports