Totally asynchronous distributed estimation of eigenvector centrality in digraphs with application to the PageRank problem
Authors:
- Themistoklis CharalambousTCThemistoklis Charalambous
- Christoforos N. HadjicostisCHChristoforos N. Hadjicostis
- Michael G. RabbatMRMichael G. Rabbat
- Mikael JohanssonMJMikael Johansson
- 1 December 2016
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 25-30
Abstract
We propose a distributed coordination mechanism which enables nodes in a directed graph to accurately estimate their eigenvector centrality (eigencentrality) even if they update their values at times determined by their own clocks. The clocks need neither be synchronized nor have the same speed. The main idea is to let nodes adjust the weights on outgoing links to compensate for their update speed: the higher the update frequency, the smaller the link weights. Our mechanism is used to develop a distributed algorithm for computing the PageRank vector, commonly used to assign importance to web pages and rank search results. Although several distributed approaches in the literature can deal with asynchronism, they cannot handle the different update speeds that occur when servers have heterogeneous computational capabilities. When existing algorithms are executed using heterogeneous update speeds, they compute incorrect PageRank values. The advantages of our algorithm over existing approaches are verified through illustrative examples.Keywords
This publication has 19 references indexed in Scilit:
- Parameter Estimation in a Stochastic System Model for PageRank2015
- Asynchronous decentralized optimization in heterogeneous systems2014
- Ergodic Randomized Algorithms and Dynamics Over NetworksIEEE Transactions on Control of Network Systems, 2014
- The PageRank Problem, Multiagent Consensus, and Web Aggregation: A Systems and Control ViewpointIEEE Control Systems, 2014
- PageRank optimization by edge selectionDiscrete Applied Mathematics, 2014
- A distributed algorithm for average consensus on strongly connected weighted digraphsAutomatica, 2014
- On the complexity of the Monte Carlo method for incremental PageRankInformation Processing Letters, 2014
- Cooperative control with distributed gain adaptation and connectivity estimation for directed networksInternational Journal of Robust and Nonlinear Control, 2012
- Distributed pagerank for P2P systems2004
- Power and Centrality: A Family of MeasuresAmerican Journal of Sociology, 1987