Stability and similarity of link analysis ranking algorithms. (English) Zbl 1147.68882

Donato, Debora; Leonardi, Stefano; Tsaparas, Panayiotis

Internet Math. 3, No. 4, 479-507 (2006).

Summary: Recently, there has been a surge of research activity in the area of Link Analysis Ranking, where hyperlink structures are used to determine the relative authority of Web pages. One of the seminal works in this area is that of J. Kleinberg [J. ACM 46, No. 5, 604–632 (1999; Zbl 1065.68660)], who proposed the HITS algorithm. We undertake a theoretical analysis of the properties of the HITS algorithm on a broad class of random graphs. Working within the framework of A. Borodin, G. O. Roberts, J. S. Rosenthal, and P. Tsaparas [“Link analysis ranking: algorithms, experiments and theory’,’ ACM Trans. Internet Technol. 5, 231–297 (2005)], we prove that on this class (a) the HITS algorithm is stable with high probability, and (b) the HITS algorithm is similar to the InDegree heuristic that assigns to each node weight proportional to the number of incoming links.
We demonstrate that our results go through for the case that the expected in-degrees of the graph follow a power-law distribution. We also study experimentally the similarity between HITS and InDegree, and we investigate the general conditions under which the two algorithms are similar.

MSC:

68W40	Analysis of algorithms
68M10	Network design and communication in computer systems

Citations:

Zbl 1065.68660