A distributed algorithm with consistency for PageRank-like linear algebraic systems*. Issue 1 (July 2017)

• Record Type: Journal Article
• Authors: Lagoa, Constantino M.; Zaccarian, Luca; Dabbene, Fabrizio
• Is Part Of: IFAC-PapersOnLine. Volume 50:Issue 1(2017)
• Page Start: 5172
• Page End: 5177
• Publication Date: 2017-07
• Subjects: Distributed linear equations -- PageRank; Automatic control -- Periodicals; 629.805
• DOI: 10.1016/j.ifacol.2017.08.441
• Languages: English
• ISSNs: 2405-8963

Abstract

Abstract: We present a novel solution algorithm for a specific set of linear equations arising in large scale sparse interconnections, such as the PageRank problem. The algorithm is distributed, exploiting the underlying graph structure, and completely asynchronous. The main feature of the proposed algorithm is that it ensures that the consistency constraint (the sum of the solution components summing to one) is satisfied at every step, and not only when convergence is reached, as in the case of the different algorithms available in the literature. This represents an important feature, since in practice this kind of algorithms are stopped after a fixed number of steps. The algorithm is based on two projection steps, and represents a variation of the classical Kaczmarz method. In this paper, we present a completely deterministic version, and prove its convergence under mild assumptions on the node selection rule. Numerical examples testify for the goodness of the proposed methodology.